1 files changed, 127 insertions, 0 deletions
diff --git a/src/TSP/TSPSolver.cs b/src/TSP/TSPSolver.cs
new file mode 100644
index 0000000..84d3945
--- /dev/null
+++ b/src/TSP/TSPSolver.cs
@@ -0,0 +1,127 @@
+using System;
+using System.Collections.Generic;
+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>;
+    using Road = Edge<double>;
+
+    public static class TSPSolver
+    {
+        public static Tour MST(string file, string coords, int init)
+        {
+            Map map = GraphFile.Read(new FileReader(file)).MST(0);
+            return new Tour(map.Vertices, Coordinate.Parse(coords));
+        }
+
+        public static Tour Approximate(string file, string coords, int init)
+        {
+            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(approximateTour);
+
+            return approximateTour;
+
+            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;
+            }
+        }
+
+
+        public static Tour Solve(string file, string coords, int init)
+        {
+            Map map = GraphFile.Read(new FileReader(file));
+            Tour bestTour = new Tour(map.Vertices, Coordinate.Parse(coords));
+
+            double BestWeight = double.MaxValue;
+            List<int> BestTour = new();
+
+            BruteForce(map, init, map.Vertices.Select(city => city.Id).ToList(), new List<int>(), 0);
+
+
+            int parent = BestTour.Last();
+
+            foreach (int city in BestTour.Skip(1))
+            {
+                bestTour[city].Parent = parent;
+                parent = city;
+            }
+
+            Debug.WriteLine("\nTrue Best Tour");
+            Debug.WriteLine(bestTour);
+
+            return bestTour;
+
+            void BruteForce(Map map, int city, List<int> unvisitedInput, List<int> visitedInput, double weight)
+            {
+                // create local copy of Tour variables
+                List<int> unvisited = new(unvisitedInput);
+                List<int> visited = new(visitedInput);
+
+                // remove current City from tour
+                int removed = unvisited.RemoveAll(c => c == city);
+
+                //? verify that a single city was removed
+                Debug.Assert(removed == 1,
+                             $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city}");
+
+                // set parent of current city to previous city
+                if (visited.Count > 0)
+                    weight += map[city][visited.Last()].Weight;
+
+                // add current City to visited
+                visited.Add(city);
+
+                if (weight > BestWeight)
+                    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 (int neighbor in unvisited)
+                    BruteForce(map, neighbor, unvisited, visited, weight);
+
+                // if we traversed all cities in the graph
+                if (unvisited.Count == 0)
+                {
+                    // add the return home
+                    weight += map[visited.First()][visited.Last()].Weight;
+
+                    // set as best if lower weight than previous best 
+                    if (weight < BestWeight)
+                    {
+                        BestTour = visited;
+                        BestWeight = weight;
+                        Debug.WriteLine($"New best tour: {String.Join(" -> ", visited)} = {weight}");
+                    }
+                }
+            }
+        }
+    }
+}