summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorToby Vincent <tobyv13@gmail.com>2021-04-23 16:34:12 -0500
committerToby Vincent <tobyv13@gmail.com>2021-04-23 16:34:12 -0500
commit66ecdbf20f2a29af26e4bfefb255e7fbe1061eac (patch)
tree1279f40c1838d1202fccf527b22c51f1d6b05a9f
parent824469649aca839e9fa86c3f4dd00294d8eba8d3 (diff)
implimented MSTApproximate
-rw-r--r--graphs/graph3.csv13
-rw-r--r--graphs/graph7.csv13
-rw-r--r--graphs/graph8.txt13
-rw-r--r--src/CS340.Plotter/Plot.Designer.cs137
-rw-r--r--src/CS340.Plotter/Plot.cs6
-rw-r--r--src/CS340.Plotter/graphs/graph2.csv13
-rw-r--r--src/CS340.Plotter/graphs/graph2.txt6
-rw-r--r--src/CS340.TSP/TSPSolver.cs110
-rw-r--r--src/CS340.TSP/Tour.cs2
-rw-r--r--test_graphs/coordinates.csv (renamed from src/CS340.Plotter/graphs/coordinates.csv)0
-rw-r--r--test_graphs/graph1.csv13
-rw-r--r--test_graphs/graph1.txt6
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