diff options
author | Toby Vincent <tobyv13@gmail.com> | 2021-04-23 16:34:12 -0500 |
---|---|---|
committer | Toby Vincent <tobyv13@gmail.com> | 2021-04-23 16:34:12 -0500 |
commit | 66ecdbf20f2a29af26e4bfefb255e7fbe1061eac (patch) | |
tree | 1279f40c1838d1202fccf527b22c51f1d6b05a9f | |
parent | 824469649aca839e9fa86c3f4dd00294d8eba8d3 (diff) |
implimented MSTApproximate
-rw-r--r-- | graphs/graph3.csv | 13 | ||||
-rw-r--r-- | graphs/graph7.csv | 13 | ||||
-rw-r--r-- | graphs/graph8.txt | 13 | ||||
-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/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 | ||||
-rw-r--r-- | test_graphs/coordinates.csv (renamed from src/CS340.Plotter/graphs/coordinates.csv) | 0 | ||||
-rw-r--r-- | test_graphs/graph1.csv | 13 | ||||
-rw-r--r-- | test_graphs/graph1.txt | 6 |
12 files changed, 199 insertions, 133 deletions
diff --git a/graphs/graph3.csv b/graphs/graph3.csv deleted file mode 100644 index 863fc99..0000000 --- a/graphs/graph3.csv +++ /dev/null @@ -1,13 +0,0 @@ -45,38 -36,59 -68,7 -82,99 -20,89 -56,90 -46,65 -67,37 -4,28 -66,57 -93,80 -28,29 -72,60 diff --git a/graphs/graph7.csv b/graphs/graph7.csv deleted file mode 100644 index 2d6f16e..0000000 --- a/graphs/graph7.csv +++ /dev/null @@ -1,13 +0,0 @@ -80,19 -5,13 -69,0 -87,84 -28,37 -51,11 -49,6 -74,20 -68,59 -3,82 -92,14 -27,24 -81,8 diff --git a/graphs/graph8.txt b/graphs/graph8.txt deleted file mode 100644 index bb0eb23..0000000 --- a/graphs/graph8.txt +++ /dev/null @@ -1,13 +0,0 @@ -0 1 66.03029607687671 2 18.601075237738275 3 39.20459156782532 4 75.92759709091287 5 97.94386147176351 6 47.4236228055175 7 36.235341863986875 8 37.36308338453881 9 89.00561780022652 10 38.01315561749642 11 87.11486669908874 12 72.01388754955533 -1 0 66.03029607687671 2 51.78802950489621 3 27.65863337187866 4 20.615528128088304 5 56.61271941887264 6 46.010868281309364 7 52.43090691567332 8 31.04834939252005 9 84.77027781009096 10 42.43819034784589 11 67.47592163134935 12 75.59100475585703 -2 0 18.601075237738275 1 51.78802950489621 3 28.30194339616981 4 65.30696746902278 5 92.69843580125827 6 47.4236228055175 7 39.81205847478876 8 21.02379604162864 9 93.68030742904295 10 36.6742416417845 11 87.32124598286491 12 77.6659513557904 -3 0 39.20459156782532 1 27.65863337187866 2 28.30194339616981 4 37.33630940518894 5 65.11528238439882 6 28.284271247461902 7 28.844410203711913 8 14.317821063276353 9 75.02666192761077 10 19.697715603592208 11 63.89053137985315 12 61.5223536610881 -4 0 75.92759709091287 1 20.615528128088304 2 65.30696746902278 3 37.33630940518894 5 36.138621999185304 6 41.78516483155236 7 52.172789842982326 8 46.61544808322666 9 70.2353187506115 10 43.289721643826724 11 50.59644256269407 12 64.4437739428721 -5 0 97.94386147176351 1 56.61271941887264 2 92.69843580125827 3 65.11528238439882 4 36.138621999185304 6 52.0 7 64.62197768561404 8 77.80102827083971 9 49.92995093127971 10 60.03332407921454 11 28.178005607210743 12 53.600373133029585 -6 0 47.4236228055175 1 46.010868281309364 2 47.4236228055175 3 28.284271247461902 4 41.78516483155236 5 52.0 7 12.649110640673518 8 42.01190307520001 9 47.38143096192854 10 10.770329614269007 11 40.22437072223753 12 33.24154027718932 -7 0 36.235341863986875 1 52.43090691567332 2 39.81205847478876 3 28.844410203711913 4 52.172789842982326 5 64.62197768561404 6 12.649110640673518 8 40.162171256046406 9 54.08326913195984 10 10.0 11 50.93132631298737 12 37.8549864614954 -8 0 37.36308338453881 1 31.04834939252005 2 21.02379604162864 3 14.317821063276353 4 46.61544808322666 5 77.80102827083971 6 42.01190307520001 7 40.162171256046406 9 89.1403387922662 10 32.38826948140329 11 78.16009211867653 12 75.16648189186454 -9 0 89.00561780022652 1 84.77027781009096 2 93.68030742904295 3 75.02666192761077 4 70.2353187506115 5 49.92995093127971 6 47.38143096192854 7 54.08326913195984 8 89.1403387922662 10 57.87054518492115 11 22.02271554554524 12 17.204650534085253 -10 0 38.01315561749642 1 42.43819034784589 2 36.6742416417845 3 19.697715603592208 4 43.289721643826724 5 60.03332407921454 6 10.770329614269007 7 10.0 8 32.38826948140329 9 57.87054518492115 11 50.774009099144415 12 43.0 -11 0 87.11486669908874 1 67.47592163134935 2 87.32124598286491 3 63.89053137985315 4 50.59644256269407 5 28.178005607210743 6 40.22437072223753 7 50.93132631298737 8 78.16009211867653 9 22.02271554554524 10 50.774009099144415 12 27.0 -12 0 72.01388754955533 1 75.59100475585703 2 77.6659513557904 3 61.5223536610881 4 64.4437739428721 5 53.600373133029585 6 33.24154027718932 7 37.8549864614954 8 75.16648189186454 9 17.204650534085253 10 43.0 11 27.0 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/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>(); diff --git a/src/CS340.Plotter/graphs/coordinates.csv b/test_graphs/coordinates.csv index f99e185..f99e185 100644 --- a/src/CS340.Plotter/graphs/coordinates.csv +++ b/test_graphs/coordinates.csv diff --git a/test_graphs/graph1.csv b/test_graphs/graph1.csv new file mode 100644 index 0000000..17891b7 --- /dev/null +++ b/test_graphs/graph1.csv @@ -0,0 +1,13 @@ +20,72 +97,89 +44,12 +76,91 +91,61 +23,18 +25,79 +67,53 +72,17 +62,53 +95,98 +8,87 +94,34 diff --git a/test_graphs/graph1.txt b/test_graphs/graph1.txt new file mode 100644 index 0000000..113fb4f --- /dev/null +++ b/test_graphs/graph1.txt @@ -0,0 +1,6 @@ +0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984 +1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974 +2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555 +3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129 +4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272 +5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272
\ No newline at end of file |