renamed TSPSolver

1 files changed, 76 insertions, 0 deletions

diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs
new file mode 100644
index 0000000..e2ea98f
--- /dev/null
+++ b/src/CS340.TSP/TSPSolver.cs
@@ -0,0 +1,76 @@
+using System.Diagnostics;
+using System.Linq;
+using Extensions;
+using Graph;
+using Graph.IO;
+
+namespace TSP
+{
+
+    using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, 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));
+        }
+
+        public static Tour BruteForce(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());
+
+            return BestTour;
+        }
+
+        static void GenerateTour(City city, Tour tour, Tour visited)
+        {
+            // create local copy of Tour variables
+            Tour currTour = new Tour(tour.Cities);
+            Tour currVisited = new Tour(visited.Cities);
+            City currCity = new City(city);
+
+            // remove current City from tour
+            currTour.Cities.RemoveAt(currTour.Cities.FindIndex(city => city.Id == currCity.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;
+
+            currVisited.Cities.Add(currCity);
+
+            //? 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}");
+
+            // 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);
+
+
+            if (currTour.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}");
+            }
+
+
+            return;
+        }
+    }
+}