diff options
| -rw-r--r-- | src/CS340.Plotter/Plot.cs | 12 | ||||
| -rw-r--r-- | src/CS340.Plotter/TourPlot.cs | 21 | ||||
| -rw-r--r-- | src/CS340.TSP/TSPSolver.cs | 12 | ||||
| -rw-r--r-- | src/CS340.TSP/Tour.cs | 11 |
4 files changed, 36 insertions, 20 deletions
diff --git a/src/CS340.Plotter/Plot.cs b/src/CS340.Plotter/Plot.cs index e07cdc0..cb46dd8 100644 --- a/src/CS340.Plotter/Plot.cs +++ b/src/CS340.Plotter/Plot.cs @@ -60,21 +60,21 @@ namespace Plotter stopWatch.Start(); bruteForce.Tour = TSPSolver.Solve(graphFile, coordsFile, 0); stopWatch.Stop(); - bruteForce.RunTime = stopWatch.Elapsed; + bruteForce.Runtime = stopWatch.Elapsed; stopWatch.Reset(); stopWatch.Start(); approximate.Tour = TSPSolver.Approximate(graphFile, coordsFile, 0); // TODO create estimation function stopWatch.Stop(); - approximate.RunTime = stopWatch.Elapsed; + approximate.Runtime = stopWatch.Elapsed; stopWatch.Reset(); stopWatch.Start(); mst.Tour = TSPSolver.MST(graphFile, coordsFile, 0); stopWatch.Stop(); - mst.RunTime = stopWatch.Elapsed; + mst.Runtime = stopWatch.Elapsed; return new[] { bruteForce, approximate, mst }; } @@ -84,9 +84,9 @@ namespace Plotter if (!System.IO.Directory.Exists(Path.Join(folderName, plots[0].GraphName))) System.IO.Directory.CreateDirectory(Path.Join(folderName, plots[0].GraphName)); - plots[0].Save(Path.Join(folderName, plots[0].GraphName, $"bruteforce.png")); - plots[1].Save(Path.Join(folderName, plots[0].GraphName, $"approximate.png")); - plots[2].Save(Path.Join(folderName, plots[0].GraphName, $"mst.png")); + plots[0].Save(Path.Join(folderName, plots[0].GraphName, $"bruteforce")); + plots[1].Save(Path.Join(folderName, plots[0].GraphName, $"approximate")); + plots[2].Save(Path.Join(folderName, plots[0].GraphName, $"mst")); } private void Canvas_SizeChanged(object sender, EventArgs e) diff --git a/src/CS340.Plotter/TourPlot.cs b/src/CS340.Plotter/TourPlot.cs index 09cd514..a5d9f30 100644 --- a/src/CS340.Plotter/TourPlot.cs +++ b/src/CS340.Plotter/TourPlot.cs @@ -1,5 +1,6 @@ using System; using System.Drawing; +using System.IO; using System.Linq; using System.Windows.Forms; using TSP; @@ -13,7 +14,7 @@ namespace Plotter public PictureBox Canvas { get; set; } public Label WeightLabel { get; set; } public Label RuntimeLabel { get; set; } - public TimeSpan RunTime { get; set; } + public TimeSpan Runtime { get; set; } public TourPlot(string graphName, PictureBox canvas, Label weightLabel, Label runtimeLabel) { @@ -26,8 +27,11 @@ namespace Plotter public void Save(string filename) => Save(filename, Canvas.Width, Canvas.Height); - public void Save(string filename, int width, int height) => - Draw(300, 300).Save(filename); + public void Save(string filename, int width, int height) + { + Draw(300, 300).Save($"{filename}.png"); + File.WriteAllText($"{filename}.txt", $"{this}"); + } public void Render() { @@ -39,14 +43,14 @@ namespace Plotter // set runtime and weight labels RuntimeLabel.Text = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", - RunTime.Hours, RunTime.Minutes, RunTime.Seconds, RunTime.Milliseconds / 10); + Runtime.Hours, Runtime.Minutes, Runtime.Seconds, Runtime.Milliseconds / 10); WeightLabel.Text = Tour.Weight.ToString("F3"); } public Bitmap Draw(int width, int height) { - const int Scaler = 25; + const int Offset = 25; const int PlotSize = 100; using Bitmap bmp = new(width, height); @@ -95,12 +99,15 @@ namespace Plotter // helper function to unify the scaling of images Point ScaleLocation(Coordinate coordinate) { - int x = width * (coordinate.X + Scaler / 2) / (Scaler + PlotSize); - int y = height * ((coordinate.Y - PlotSize) * -1 + Scaler / 2) / (Scaler + PlotSize); + int x = width * (coordinate.X + Offset / 2) / (Offset + PlotSize); + int y = height * ((coordinate.Y - PlotSize) * -1 + Offset / 2) / (Offset + PlotSize); return new Point(x, y); } + } + public override string ToString() => $"{Tour}\n" + + $"runtime: {Runtime}"; } } diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs index 159286a..2700bc2 100644 --- a/src/CS340.TSP/TSPSolver.cs +++ b/src/CS340.TSP/TSPSolver.cs @@ -12,7 +12,7 @@ namespace TSP public static class TSPSolver { - static Tour BestTour = null; + static Tour BestTour; public static Tour MST(string file, string coords, int init) @@ -39,7 +39,7 @@ namespace TSP Map map = GraphFile.Read(new FileReader(file)); Tour intialTour = new Tour(map.Vertices, Coordinate.Parse(coords)); - BestTour = null; + BestTour = new(); BruteForce(intialTour[init], intialTour, new Tour()); @@ -66,7 +66,7 @@ namespace TSP // 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; } @@ -91,6 +91,10 @@ namespace TSP // add current City to visited visited.Cities.Add(city); + + if (visited.Weight > BestTour.Weight) + return; + // loop through each city. Each level of recursion has a one less city in unvisited.Cities // so each loop is (n - 1)! down to n == 0 as the base case foreach (City neighbor in unvisited.Cities) @@ -103,7 +107,7 @@ namespace TSP visited.Cities.First().Parent = visited.Cities.Last().Id; // set as best if lower weight than previous best - if (BestTour == null || visited.Weight < BestTour.Weight) + if (visited.Weight < BestTour.Weight) { BestTour = new Tour(visited.Cities); Debug.WriteLine("*** Found new best tour ***"); diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index 27ab5a5..a4ef10f 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -11,9 +11,14 @@ namespace TSP public List<City> Cities { get; set; } = new List<City>(); public double Weight { - get => Cities - .Where(city => city.Parent != -1) - .Sum(city => city.Key); + get + { + if (Cities.Count == 0) + return double.MaxValue; + + return Cities.Where(city => city.Parent != -1) + .Sum(city => city.Key); + } } // indexer: get vertex where vertex.Id == index |