implimented MSTApproximate

2 files changed, 76 insertions, 36 deletions

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>();