diff options
Diffstat (limited to 'src')
-rw-r--r-- | src/CS340.Plotter/Plot.Designer.cs | 137 | ||||
-rw-r--r-- | src/CS340.Plotter/Plot.cs | 6 | ||||
-rw-r--r-- | src/CS340.Plotter/graphs/coordinates.csv | 15 | ||||
-rw-r--r-- | src/CS340.Plotter/graphs/graph2.csv | 13 | ||||
-rw-r--r-- | src/CS340.Plotter/graphs/graph2.txt | 6 | ||||
-rw-r--r-- | src/CS340.TSP/TSPSolver.cs | 110 | ||||
-rw-r--r-- | src/CS340.TSP/Tour.cs | 2 |
7 files changed, 180 insertions, 109 deletions
diff --git a/src/CS340.Plotter/Plot.Designer.cs b/src/CS340.Plotter/Plot.Designer.cs index e509bdc..1fe8745 100644 --- a/src/CS340.Plotter/Plot.Designer.cs +++ b/src/CS340.Plotter/Plot.Designer.cs @@ -51,9 +51,10 @@ namespace Plotter this.BruteForceLabel = new System.Windows.Forms.Label(); this.EstimatedLabel = new System.Windows.Forms.Label(); this.MSTLabel = new System.Windows.Forms.Label(); + this.tableLayoutPanel7 = new System.Windows.Forms.TableLayoutPanel(); this.NextGraph = new System.Windows.Forms.Button(); - this.PrevGraph = new System.Windows.Forms.Button(); this.GraphLabel = new System.Windows.Forms.Label(); + this.PrevGraph = new System.Windows.Forms.Button(); this.tableLayoutPanel2 = new System.Windows.Forms.TableLayoutPanel(); this.label2 = new System.Windows.Forms.Label(); this.label3 = new System.Windows.Forms.Label(); @@ -70,6 +71,7 @@ namespace Plotter this.tableLayoutPanel1.SuspendLayout(); this.tableLayoutPanel5.SuspendLayout(); this.tableLayoutPanel6.SuspendLayout(); + this.tableLayoutPanel7.SuspendLayout(); this.tableLayoutPanel2.SuspendLayout(); this.tableLayoutPanel3.SuspendLayout(); this.tableLayoutPanel4.SuspendLayout(); @@ -80,25 +82,25 @@ namespace Plotter this.BruteForcePlot.Dock = System.Windows.Forms.DockStyle.Fill; this.BruteForcePlot.Location = new System.Drawing.Point(3, 3); this.BruteForcePlot.Name = "BruteForcePlot"; - this.BruteForcePlot.Size = new System.Drawing.Size(248, 213); + this.BruteForcePlot.Size = new System.Drawing.Size(254, 273); this.BruteForcePlot.TabIndex = 0; this.BruteForcePlot.TabStop = false; // // EstimationPlot // this.EstimationPlot.Dock = System.Windows.Forms.DockStyle.Fill; - this.EstimationPlot.Location = new System.Drawing.Point(257, 3); + this.EstimationPlot.Location = new System.Drawing.Point(263, 3); this.EstimationPlot.Name = "EstimationPlot"; - this.EstimationPlot.Size = new System.Drawing.Size(248, 213); + this.EstimationPlot.Size = new System.Drawing.Size(254, 273); this.EstimationPlot.TabIndex = 1; this.EstimationPlot.TabStop = false; // // MSTPlot // this.MSTPlot.Dock = System.Windows.Forms.DockStyle.Fill; - this.MSTPlot.Location = new System.Drawing.Point(511, 3); + this.MSTPlot.Location = new System.Drawing.Point(523, 3); this.MSTPlot.Name = "MSTPlot"; - this.MSTPlot.Size = new System.Drawing.Size(250, 213); + this.MSTPlot.Size = new System.Drawing.Size(255, 273); this.MSTPlot.TabIndex = 2; this.MSTPlot.TabStop = false; // @@ -118,19 +120,17 @@ namespace Plotter this.LayoutPanel.Controls.Add(this.EstimatedLabel, 1, 1); this.LayoutPanel.Controls.Add(this.MSTPlot, 2, 0); this.LayoutPanel.Controls.Add(this.MSTLabel, 2, 1); - this.LayoutPanel.Controls.Add(this.NextGraph, 2, 4); - this.LayoutPanel.Controls.Add(this.PrevGraph, 0, 4); - this.LayoutPanel.Controls.Add(this.GraphLabel, 1, 4); + this.LayoutPanel.Controls.Add(this.tableLayoutPanel7, 1, 4); this.LayoutPanel.Dock = System.Windows.Forms.DockStyle.Fill; this.LayoutPanel.Location = new System.Drawing.Point(0, 0); this.LayoutPanel.Name = "LayoutPanel"; - this.LayoutPanel.RowCount = 5; + this.LayoutPanel.RowCount = 4; this.LayoutPanel.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 100F)); this.LayoutPanel.RowStyles.Add(new System.Windows.Forms.RowStyle()); this.LayoutPanel.RowStyles.Add(new System.Windows.Forms.RowStyle()); this.LayoutPanel.RowStyles.Add(new System.Windows.Forms.RowStyle()); this.LayoutPanel.RowStyles.Add(new System.Windows.Forms.RowStyle()); - this.LayoutPanel.Size = new System.Drawing.Size(764, 312); + this.LayoutPanel.Size = new System.Drawing.Size(781, 381); this.LayoutPanel.TabIndex = 4; // // tableLayoutPanel1 @@ -144,12 +144,12 @@ namespace Plotter this.tableLayoutPanel1.Controls.Add(this.BruteForceWeightLabel, 0, 0); this.tableLayoutPanel1.Controls.Add(this.BruteForceTimeLabel, 0, 1); this.tableLayoutPanel1.Dock = System.Windows.Forms.DockStyle.Fill; - this.tableLayoutPanel1.Location = new System.Drawing.Point(3, 246); + this.tableLayoutPanel1.Location = new System.Drawing.Point(3, 306); this.tableLayoutPanel1.Name = "tableLayoutPanel1"; this.tableLayoutPanel1.RowCount = 2; this.tableLayoutPanel1.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); this.tableLayoutPanel1.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); - this.tableLayoutPanel1.Size = new System.Drawing.Size(248, 34); + this.tableLayoutPanel1.Size = new System.Drawing.Size(254, 34); this.tableLayoutPanel1.TabIndex = 12; // // BruteForceTime @@ -157,7 +157,7 @@ namespace Plotter this.BruteForceTime.AutoSize = true; this.BruteForceTime.Dock = System.Windows.Forms.DockStyle.Left; this.BruteForceTime.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.BruteForceTime.Location = new System.Drawing.Point(127, 17); + this.BruteForceTime.Location = new System.Drawing.Point(130, 17); this.BruteForceTime.Name = "BruteForceTime"; this.BruteForceTime.Size = new System.Drawing.Size(76, 17); this.BruteForceTime.TabIndex = 13; @@ -169,7 +169,7 @@ namespace Plotter this.BruteForceWeight.AutoSize = true; this.BruteForceWeight.Dock = System.Windows.Forms.DockStyle.Left; this.BruteForceWeight.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.BruteForceWeight.Location = new System.Drawing.Point(127, 0); + this.BruteForceWeight.Location = new System.Drawing.Point(130, 0); this.BruteForceWeight.Name = "BruteForceWeight"; this.BruteForceWeight.Size = new System.Drawing.Size(44, 17); this.BruteForceWeight.TabIndex = 12; @@ -182,7 +182,7 @@ namespace Plotter this.BruteForceWeightLabel.Dock = System.Windows.Forms.DockStyle.Right; this.BruteForceWeightLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); this.BruteForceWeightLabel.ImageAlign = System.Drawing.ContentAlignment.MiddleRight; - this.BruteForceWeightLabel.Location = new System.Drawing.Point(63, 0); + this.BruteForceWeightLabel.Location = new System.Drawing.Point(66, 0); this.BruteForceWeightLabel.Name = "BruteForceWeightLabel"; this.BruteForceWeightLabel.Size = new System.Drawing.Size(58, 17); this.BruteForceWeightLabel.TabIndex = 11; @@ -194,7 +194,7 @@ namespace Plotter this.BruteForceTimeLabel.AutoSize = true; this.BruteForceTimeLabel.Dock = System.Windows.Forms.DockStyle.Right; this.BruteForceTimeLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.BruteForceTimeLabel.Location = new System.Drawing.Point(54, 17); + this.BruteForceTimeLabel.Location = new System.Drawing.Point(57, 17); this.BruteForceTimeLabel.Name = "BruteForceTimeLabel"; this.BruteForceTimeLabel.Size = new System.Drawing.Size(67, 17); this.BruteForceTimeLabel.TabIndex = 9; @@ -212,12 +212,12 @@ namespace Plotter this.tableLayoutPanel5.Controls.Add(this.EstimatedWeightLabel, 0, 0); this.tableLayoutPanel5.Controls.Add(this.EstimatedTimeLabel, 0, 1); this.tableLayoutPanel5.Dock = System.Windows.Forms.DockStyle.Fill; - this.tableLayoutPanel5.Location = new System.Drawing.Point(257, 246); + this.tableLayoutPanel5.Location = new System.Drawing.Point(263, 306); this.tableLayoutPanel5.Name = "tableLayoutPanel5"; this.tableLayoutPanel5.RowCount = 2; this.tableLayoutPanel5.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); this.tableLayoutPanel5.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); - this.tableLayoutPanel5.Size = new System.Drawing.Size(248, 34); + this.tableLayoutPanel5.Size = new System.Drawing.Size(254, 34); this.tableLayoutPanel5.TabIndex = 13; // // EstimatedTime @@ -225,7 +225,7 @@ namespace Plotter this.EstimatedTime.AutoSize = true; this.EstimatedTime.Dock = System.Windows.Forms.DockStyle.Left; this.EstimatedTime.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.EstimatedTime.Location = new System.Drawing.Point(127, 17); + this.EstimatedTime.Location = new System.Drawing.Point(130, 17); this.EstimatedTime.Name = "EstimatedTime"; this.EstimatedTime.Size = new System.Drawing.Size(76, 17); this.EstimatedTime.TabIndex = 13; @@ -237,7 +237,7 @@ namespace Plotter this.EstimatedWeight.AutoSize = true; this.EstimatedWeight.Dock = System.Windows.Forms.DockStyle.Left; this.EstimatedWeight.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.EstimatedWeight.Location = new System.Drawing.Point(127, 0); + this.EstimatedWeight.Location = new System.Drawing.Point(130, 0); this.EstimatedWeight.Name = "EstimatedWeight"; this.EstimatedWeight.Size = new System.Drawing.Size(44, 17); this.EstimatedWeight.TabIndex = 12; @@ -249,7 +249,7 @@ namespace Plotter this.EstimatedWeightLabel.AutoSize = true; this.EstimatedWeightLabel.Dock = System.Windows.Forms.DockStyle.Right; this.EstimatedWeightLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.EstimatedWeightLabel.Location = new System.Drawing.Point(63, 0); + this.EstimatedWeightLabel.Location = new System.Drawing.Point(66, 0); this.EstimatedWeightLabel.Name = "EstimatedWeightLabel"; this.EstimatedWeightLabel.Size = new System.Drawing.Size(58, 17); this.EstimatedWeightLabel.TabIndex = 11; @@ -261,7 +261,7 @@ namespace Plotter this.EstimatedTimeLabel.AutoSize = true; this.EstimatedTimeLabel.Dock = System.Windows.Forms.DockStyle.Right; this.EstimatedTimeLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.EstimatedTimeLabel.Location = new System.Drawing.Point(54, 17); + this.EstimatedTimeLabel.Location = new System.Drawing.Point(57, 17); this.EstimatedTimeLabel.Name = "EstimatedTimeLabel"; this.EstimatedTimeLabel.Size = new System.Drawing.Size(67, 17); this.EstimatedTimeLabel.TabIndex = 9; @@ -279,12 +279,12 @@ namespace Plotter this.tableLayoutPanel6.Controls.Add(this.MSTWeightLabel, 0, 0); this.tableLayoutPanel6.Controls.Add(this.MSTTimeLabel, 0, 1); this.tableLayoutPanel6.Dock = System.Windows.Forms.DockStyle.Fill; - this.tableLayoutPanel6.Location = new System.Drawing.Point(511, 246); + this.tableLayoutPanel6.Location = new System.Drawing.Point(523, 306); this.tableLayoutPanel6.Name = "tableLayoutPanel6"; this.tableLayoutPanel6.RowCount = 2; this.tableLayoutPanel6.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); this.tableLayoutPanel6.RowStyles.Add(new System.Windows.Forms.RowStyle(System.Windows.Forms.SizeType.Percent, 50F)); - this.tableLayoutPanel6.Size = new System.Drawing.Size(250, 34); + this.tableLayoutPanel6.Size = new System.Drawing.Size(255, 34); this.tableLayoutPanel6.TabIndex = 14; // // MSTTime @@ -292,7 +292,7 @@ namespace Plotter this.MSTTime.AutoSize = true; this.MSTTime.Dock = System.Windows.Forms.DockStyle.Left; this.MSTTime.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.MSTTime.Location = new System.Drawing.Point(128, 17); + this.MSTTime.Location = new System.Drawing.Point(130, 17); this.MSTTime.Name = "MSTTime"; this.MSTTime.Size = new System.Drawing.Size(76, 17); this.MSTTime.TabIndex = 13; @@ -304,7 +304,7 @@ namespace Plotter this.MSTWeight.AutoSize = true; this.MSTWeight.Dock = System.Windows.Forms.DockStyle.Left; this.MSTWeight.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.MSTWeight.Location = new System.Drawing.Point(128, 0); + this.MSTWeight.Location = new System.Drawing.Point(130, 0); this.MSTWeight.Name = "MSTWeight"; this.MSTWeight.Size = new System.Drawing.Size(44, 17); this.MSTWeight.TabIndex = 12; @@ -316,7 +316,7 @@ namespace Plotter this.MSTWeightLabel.AutoSize = true; this.MSTWeightLabel.Dock = System.Windows.Forms.DockStyle.Right; this.MSTWeightLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.MSTWeightLabel.Location = new System.Drawing.Point(64, 0); + this.MSTWeightLabel.Location = new System.Drawing.Point(66, 0); this.MSTWeightLabel.Name = "MSTWeightLabel"; this.MSTWeightLabel.Size = new System.Drawing.Size(58, 17); this.MSTWeightLabel.TabIndex = 11; @@ -328,7 +328,7 @@ namespace Plotter this.MSTTimeLabel.AutoSize = true; this.MSTTimeLabel.Dock = System.Windows.Forms.DockStyle.Right; this.MSTTimeLabel.Font = new System.Drawing.Font("Arial", 11.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.MSTTimeLabel.Location = new System.Drawing.Point(55, 17); + this.MSTTimeLabel.Location = new System.Drawing.Point(57, 17); this.MSTTimeLabel.Name = "MSTTimeLabel"; this.MSTTimeLabel.Size = new System.Drawing.Size(67, 17); this.MSTTimeLabel.TabIndex = 9; @@ -340,9 +340,9 @@ namespace Plotter this.BruteForceLabel.AutoSize = true; this.BruteForceLabel.Dock = System.Windows.Forms.DockStyle.Top; this.BruteForceLabel.Font = new System.Drawing.Font("Arial", 15.75F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.BruteForceLabel.Location = new System.Drawing.Point(3, 219); + this.BruteForceLabel.Location = new System.Drawing.Point(3, 279); this.BruteForceLabel.Name = "BruteForceLabel"; - this.BruteForceLabel.Size = new System.Drawing.Size(248, 24); + this.BruteForceLabel.Size = new System.Drawing.Size(254, 24); this.BruteForceLabel.TabIndex = 3; this.BruteForceLabel.Text = "Brute Force"; this.BruteForceLabel.TextAlign = System.Drawing.ContentAlignment.MiddleCenter; @@ -352,9 +352,9 @@ namespace Plotter this.EstimatedLabel.AutoSize = true; this.EstimatedLabel.Dock = System.Windows.Forms.DockStyle.Top; this.EstimatedLabel.Font = new System.Drawing.Font("Arial", 15.75F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.EstimatedLabel.Location = new System.Drawing.Point(257, 219); + this.EstimatedLabel.Location = new System.Drawing.Point(263, 279); this.EstimatedLabel.Name = "EstimatedLabel"; - this.EstimatedLabel.Size = new System.Drawing.Size(248, 24); + this.EstimatedLabel.Size = new System.Drawing.Size(254, 24); this.EstimatedLabel.TabIndex = 4; this.EstimatedLabel.Text = "Estimated"; this.EstimatedLabel.TextAlign = System.Drawing.ContentAlignment.MiddleCenter; @@ -364,47 +364,71 @@ namespace Plotter this.MSTLabel.AutoSize = true; this.MSTLabel.Dock = System.Windows.Forms.DockStyle.Top; this.MSTLabel.Font = new System.Drawing.Font("Arial", 15.75F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.MSTLabel.Location = new System.Drawing.Point(511, 219); + this.MSTLabel.Location = new System.Drawing.Point(523, 279); this.MSTLabel.Name = "MSTLabel"; - this.MSTLabel.Size = new System.Drawing.Size(250, 24); + this.MSTLabel.Size = new System.Drawing.Size(255, 24); this.MSTLabel.TabIndex = 5; this.MSTLabel.Text = "MST"; this.MSTLabel.TextAlign = System.Drawing.ContentAlignment.MiddleCenter; // + // tableLayoutPanel7 + // + this.tableLayoutPanel7.AutoSize = true; + this.tableLayoutPanel7.ColumnCount = 3; + this.tableLayoutPanel7.ColumnStyles.Add(new System.Windows.Forms.ColumnStyle(System.Windows.Forms.SizeType.Percent, 50F)); + this.tableLayoutPanel7.ColumnStyles.Add(new System.Windows.Forms.ColumnStyle()); + this.tableLayoutPanel7.ColumnStyles.Add(new System.Windows.Forms.ColumnStyle(System.Windows.Forms.SizeType.Percent, 50F)); + this.tableLayoutPanel7.Controls.Add(this.NextGraph, 2, 0); + this.tableLayoutPanel7.Controls.Add(this.GraphLabel, 1, 0); + this.tableLayoutPanel7.Controls.Add(this.PrevGraph, 0, 0); + this.tableLayoutPanel7.Dock = System.Windows.Forms.DockStyle.Fill; + this.tableLayoutPanel7.Location = new System.Drawing.Point(263, 346); + this.tableLayoutPanel7.Name = "tableLayoutPanel7"; + this.tableLayoutPanel7.RowCount = 1; + this.tableLayoutPanel7.RowStyles.Add(new System.Windows.Forms.RowStyle()); + this.tableLayoutPanel7.Size = new System.Drawing.Size(254, 32); + this.tableLayoutPanel7.TabIndex = 18; + // // NextGraph // - this.NextGraph.Dock = System.Windows.Forms.DockStyle.Right; - this.NextGraph.Location = new System.Drawing.Point(686, 286); + this.NextGraph.Anchor = System.Windows.Forms.AnchorStyles.Left; + this.NextGraph.AutoSize = true; + this.NextGraph.AutoSizeMode = System.Windows.Forms.AutoSizeMode.GrowAndShrink; + this.NextGraph.Font = new System.Drawing.Font("Arial", 9.75F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); + this.NextGraph.Location = new System.Drawing.Point(165, 3); this.NextGraph.Name = "NextGraph"; - this.NextGraph.Size = new System.Drawing.Size(75, 23); + this.NextGraph.Size = new System.Drawing.Size(25, 26); this.NextGraph.TabIndex = 15; - this.NextGraph.Text = "Next Graph"; + this.NextGraph.Text = ">"; this.NextGraph.UseVisualStyleBackColor = true; this.NextGraph.Click += new System.EventHandler(this.NextGraph_Click); // - // PrevGraph - // - this.PrevGraph.Dock = System.Windows.Forms.DockStyle.Left; - this.PrevGraph.Location = new System.Drawing.Point(3, 286); - this.PrevGraph.Name = "PrevGraph"; - this.PrevGraph.Size = new System.Drawing.Size(75, 23); - this.PrevGraph.TabIndex = 16; - this.PrevGraph.Text = "Previous Graph"; - this.PrevGraph.UseVisualStyleBackColor = true; - this.PrevGraph.Click += new System.EventHandler(this.PrevGraph_Click); - // // GraphLabel // this.GraphLabel.AutoSize = true; this.GraphLabel.Dock = System.Windows.Forms.DockStyle.Fill; - this.GraphLabel.Font = new System.Drawing.Font("Arial", 14.25F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); - this.GraphLabel.Location = new System.Drawing.Point(257, 283); + this.GraphLabel.Font = new System.Drawing.Font("Arial", 12F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); + this.GraphLabel.Location = new System.Drawing.Point(95, 0); this.GraphLabel.Name = "GraphLabel"; - this.GraphLabel.Size = new System.Drawing.Size(248, 29); + this.GraphLabel.Size = new System.Drawing.Size(64, 32); this.GraphLabel.TabIndex = 17; this.GraphLabel.Text = "Graph 1"; this.GraphLabel.TextAlign = System.Drawing.ContentAlignment.MiddleCenter; // + // PrevGraph + // + this.PrevGraph.Anchor = System.Windows.Forms.AnchorStyles.Right; + this.PrevGraph.AutoSize = true; + this.PrevGraph.AutoSizeMode = System.Windows.Forms.AutoSizeMode.GrowAndShrink; + this.PrevGraph.Font = new System.Drawing.Font("Arial", 9.75F, System.Drawing.FontStyle.Regular, System.Drawing.GraphicsUnit.Point); + this.PrevGraph.Location = new System.Drawing.Point(64, 3); + this.PrevGraph.Name = "PrevGraph"; + this.PrevGraph.Size = new System.Drawing.Size(25, 26); + this.PrevGraph.TabIndex = 16; + this.PrevGraph.Text = "<"; + this.PrevGraph.UseVisualStyleBackColor = true; + this.PrevGraph.Click += new System.EventHandler(this.PrevGraph_Click); + // // tableLayoutPanel2 // this.tableLayoutPanel2.AutoSize = true; @@ -526,7 +550,7 @@ namespace Plotter // this.AutoScaleDimensions = new System.Drawing.SizeF(7F, 15F); this.AutoScaleMode = System.Windows.Forms.AutoScaleMode.Font; - this.ClientSize = new System.Drawing.Size(764, 312); + this.ClientSize = new System.Drawing.Size(781, 381); this.Controls.Add(this.LayoutPanel); this.MinimumSize = new System.Drawing.Size(780, 350); this.Name = "PlotWindow"; @@ -543,6 +567,8 @@ namespace Plotter this.tableLayoutPanel5.PerformLayout(); this.tableLayoutPanel6.ResumeLayout(false); this.tableLayoutPanel6.PerformLayout(); + this.tableLayoutPanel7.ResumeLayout(false); + this.tableLayoutPanel7.PerformLayout(); this.tableLayoutPanel2.ResumeLayout(false); this.tableLayoutPanel2.PerformLayout(); this.tableLayoutPanel3.ResumeLayout(false); @@ -587,9 +613,10 @@ namespace Plotter private System.Windows.Forms.TableLayoutPanel tableLayoutPanel4; private System.Windows.Forms.Label label8; private System.Windows.Forms.Label label9; + private System.Windows.Forms.TableLayoutPanel tableLayoutPanel7; + private System.Windows.Forms.Label GraphLabel; private System.Windows.Forms.Button NextGraph; private System.Windows.Forms.Button PrevGraph; - private System.Windows.Forms.Label GraphLabel; } } diff --git a/src/CS340.Plotter/Plot.cs b/src/CS340.Plotter/Plot.cs index 636d955..7028d29 100644 --- a/src/CS340.Plotter/Plot.cs +++ b/src/CS340.Plotter/Plot.cs @@ -45,21 +45,21 @@ namespace Plotter Stopwatch stopWatch = new Stopwatch(); stopWatch.Start(); - bruteForce.Tour = Solve.BruteForce(graphFile, coordsFile, 0); + bruteForce.Tour = TSPSolver.Solve(graphFile, coordsFile, 0); stopWatch.Stop(); bruteForce.RunTime = stopWatch.Elapsed; stopWatch.Reset(); stopWatch.Start(); - estimation.Tour = Solve.BruteForce(graphFile, coordsFile, 0); // TODO create estimation function + estimation.Tour = TSPSolver.Approximate(graphFile, coordsFile, 0); // TODO create estimation function stopWatch.Stop(); estimation.RunTime = stopWatch.Elapsed; stopWatch.Reset(); stopWatch.Start(); - mst.Tour = Solve.MST(graphFile, coordsFile, 0); + mst.Tour = TSPSolver.MST(graphFile, coordsFile, 0); stopWatch.Stop(); mst.RunTime = stopWatch.Elapsed; diff --git a/src/CS340.Plotter/graphs/coordinates.csv b/src/CS340.Plotter/graphs/coordinates.csv deleted file mode 100644 index f99e185..0000000 --- a/src/CS340.Plotter/graphs/coordinates.csv +++ /dev/null @@ -1,15 +0,0 @@ -Graph 1,,Graph 2,,Graph 3,,Graph 4,,Graph 5,,Graph 6,,Graph 7,,Graph 8,,Graph 9,,Graph 10, -x,y,x,y,x,y,x,y,x,y,x,y,x,y,x,y,x,y,x,y -20,72,92,35,45,38,68,35,34,23,52,24,80,19,86,87,42,18,76,4 -97,89,90,73,36,59,75,20,4,0,23,81,5,13,88,21,67,75,91,57 -44,12,1,42,68,7,23,3,2,20,54,64,69,0,97,72,66,14,95,93 -76,91,31,38,82,99,70,52,29,93,80,70,87,84,82,48,81,1,45,72 -91,61,80,66,20,89,37,72,5,13,69,58,28,37,69,13,21,94,33,14 -23,18,13,2,56,90,6,89,72,57,71,6,51,11,34,4,20,79,72,18 -25,79,82,80,46,65,19,65,42,12,63,15,49,6,54,52,6,20,80,42 -67,53,2,86,67,37,46,60,52,39,35,85,74,20,58,64,93,81,40,86 -72,17,48,25,4,28,48,83,92,43,36,87,68,59,96,51,83,1,20,2 -62,53,17,82,66,57,35,54,74,31,84,21,3,82,7,46,13,6,54,20 -95,98,91,20,93,80,96,53,3,82,70,8,92,14,64,56,21,15,51,97 -8,87,26,48,28,29,14,7,3,31,30,39,27,24,21,29,83,37,65,86 -94,34,87,48,72,60,13,64,98,58,49,98,81,8,21,56,34,79,90,19 diff --git a/src/CS340.Plotter/graphs/graph2.csv b/src/CS340.Plotter/graphs/graph2.csv new file mode 100644 index 0000000..2610f5c --- /dev/null +++ b/src/CS340.Plotter/graphs/graph2.csv @@ -0,0 +1,13 @@ +92,35 +90,73 +1,42 +31,38 +80,66 +13,2 +82,80 +2,86 +48,25 +17,82 +91,20 +26,48 +87,48 diff --git a/src/CS340.Plotter/graphs/graph2.txt b/src/CS340.Plotter/graphs/graph2.txt new file mode 100644 index 0000000..e8a9c25 --- /dev/null +++ b/src/CS340.Plotter/graphs/graph2.txt @@ -0,0 +1,6 @@ +0 1 38.05259518088089 2 91.26883367283708 3 61.07372593840988 4 33.24154027718932 5 85.61541917201598 +1 0 38.05259518088089 2 94.2443632266673 3 68.60029154456998 4 12.206555615733702 5 104.7377677822093 +2 0 91.26883367283708 1 94.2443632266673 3 30.265491900843113 4 82.56512580987206 5 41.7612260356422 +3 0 61.07372593840988 1 68.60029154456998 2 30.265491900843113 4 56.43580423808985 5 40.24922359499622 +4 0 33.24154027718932 1 12.206555615733702 2 82.56512580987206 3 56.43580423808985 5 92.65527507918802 +5 0 85.61541917201598 1 104.7377677822093 2 41.7612260356422 3 40.24922359499622 4 92.65527507918802
\ No newline at end of file diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs index e2ea98f..567c7de 100644 --- a/src/CS340.TSP/TSPSolver.cs +++ b/src/CS340.TSP/TSPSolver.cs @@ -1,3 +1,4 @@ +using System.Collections.Generic; using System.Diagnostics; using System.Linq; using Extensions; @@ -8,69 +9,108 @@ namespace TSP { using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; + using Road = Edge<double>; public static class TSPSolver { - static Map Map { get; set; } static Tour BestTour = null; public static Tour MST(string file, string coords, int init) { - Map mst = GraphFile.Read(new FileReader(file)).MST(0); - return new Tour(mst.Vertices.OrderBy(vertex => vertex.Id).ToList(), Coordinate.Parse(coords)); + Map map = GraphFile.Read(new FileReader(file)).MST(0); + return new Tour(map.Vertices, Coordinate.Parse(coords)); } - public static Tour BruteForce(string file, string coords, int init) + public static Tour Approximate(string file, string coords, int init) { - Map = GraphFile.Read(new FileReader(file)); - Tour intialTour = new Tour(Map.Vertices, Coordinate.Parse(coords)); - GenerateTour(intialTour[init], intialTour, new Tour()); + Map map = GraphFile.Read(new FileReader(file)).MST(0); + Tour mstTour = new Tour(map.Vertices, Coordinate.Parse(coords)); + + Tour approximateTour = PreOrder(mstTour[init], mstTour, new Tour()); + + Debug.WriteLine("\nApproximate Best Tour"); + Debug.WriteLine(BestTour); + + return approximateTour; + } + + public static Tour Solve(string file, string coords, int init) + { + Map map = GraphFile.Read(new FileReader(file)); + Tour intialTour = new Tour(map.Vertices, Coordinate.Parse(coords)); + + BestTour = null; + + BruteForce(intialTour[init], intialTour, new Tour()); + + Debug.WriteLine("\nTrue Best Tour"); + Debug.WriteLine(BestTour); return BestTour; } - static void GenerateTour(City city, Tour tour, Tour visited) + public static Tour PreOrder(City city, Tour mst, Tour visited) + { + // set parent of current city to previous city + if (visited.Cities.Count > 0) + city.Parent = visited.Cities.Last().Id; + + // add current City to visited + visited.Cities.Add(city); + + // loop through each child, and recursivly traverse + foreach (Road road in city.Edges) + if (mst[road.V].Parent == city.Id) + PreOrder(mst[road.V], mst, visited); + + // on the last node, set init node's parent to the last node + if (visited.Cities.Count == mst.Cities.Count) + visited.Cities.First().Parent = visited.Cities.Last().Id; + + return visited; + } + + static void BruteForce(City cityInput, Tour unvisitedInput, Tour visitedInput) { // create local copy of Tour variables - Tour currTour = new Tour(tour.Cities); - Tour currVisited = new Tour(visited.Cities); - City currCity = new City(city); + Tour unvisited = new Tour(unvisitedInput.Cities); + Tour visited = new Tour(visitedInput.Cities); + City city = new City(cityInput); // remove current City from tour - currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.Id)); + int removed = unvisited.Cities.RemoveAll(c => c.Id == city.Id); - //? verify that city was removed - Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) == null, - $"Failed to remove a city from the tour. \nTour: {tour}\nCity: {currCity.Id}"); - - // add current City to visited - if (currVisited.Cities.Count > 0) - currCity.Parent = currVisited.Cities.Last().Id; + //? verify that a single city was removed + Debug.Assert(removed == 1, + $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city.Id}"); - currVisited.Cities.Add(currCity); + // set parent of current city to previous city + if (visited.Cities.Count > 0) + city.Parent = visited.Cities.Last().Id; - //? verify that city was added - Debug.Assert(currVisited.Cities.Find(city => city.Id == currCity.Id) != null, - $"Failed to add a city to the tour. \nTour: {tour}\nCity: {currCity.Id}"); + // add current City to visited + visited.Cities.Add(city); // loop through each city. Each level of recursion has a one less city in currTour.Cities // leaving the base case - foreach (City neighbor in currTour.Cities) - GenerateTour(neighbor, currTour, currVisited); - + foreach (City neighbor in unvisited.Cities) + BruteForce(neighbor, unvisited, visited); - if (currTour.Cities.Count == 0) + // if we traversed all cities in the graph + if (unvisited.Cities.Count == 0) { - currVisited.Cities.First().Parent = currVisited.Cities.Last().Id; - - if (BestTour == null || currVisited.Weight < BestTour.Weight) - BestTour = new Tour(currVisited.Cities); - // Debug.Print($"{currTour}"); + // add the return home + visited.Cities.First().Parent = visited.Cities.Last().Id; + + // set as best if lower weight than previous best + if (BestTour == null || visited.Weight < BestTour.Weight) + { + BestTour = new Tour(visited.Cities); + Debug.WriteLine("*** Found new best tour ***"); + Debug.WriteLine(visited); + } } - - - return; } } } diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index 99c0f5d..27ab5a5 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -17,7 +17,7 @@ namespace TSP } // indexer: get vertex where vertex.Id == index - public City this[int index] { get => Cities.Find(vertex => vertex.Id == index); } + public City this[int index] { get => Cities.Find(city => city.Id == index); } public Tour() => Cities = new List<City>(); |