changed from object based to array based access

3 files changed, 39 insertions, 26 deletions

diff --git a/src/CS340.Plotter/TourPlot.cs b/src/CS340.Plotter/TourPlot.cs
index a5d9f30..5b3aa37 100644
--- a/src/CS340.Plotter/TourPlot.cs
+++ b/src/CS340.Plotter/TourPlot.cs
@@ -57,7 +57,7 @@ namespace Plotter
             using Graphics gfx = Graphics.FromImage(bmp);
             using Pen pen = new(Color.Black);
             using Pen gridPen = new(Color.LightGray);
-            using Font font = new("Arial", 16);
+            using Font font = new("Arial", 12);
             using Font gridFont = new("Arial", 10);
             using SolidBrush brush = new(Color.Black);
             using StringFormat stringFormat = new StringFormat();
diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs
index 460b5cd..f60cc92 100644
--- a/src/CS340.TSP/City.cs
+++ b/src/CS340.TSP/City.cs
@@ -29,7 +29,7 @@ namespace TSP
             Parent = city.Parent;
 
         public City(IVertex city, Coordinate location) : this(city) =>
-            Location = new Coordinate(location.X, location.Y);
+            Location = location;
 
         public City(City city) : this(city, city.Location) { }
     }
diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs
index 2700bc2..e5fd45a 100644
--- a/src/CS340.TSP/TSPSolver.cs
+++ b/src/CS340.TSP/TSPSolver.cs
@@ -1,3 +1,5 @@
+using System;
+using System.Collections.Generic;
 using System.Diagnostics;
 using System.Linq;
 using Extensions;
@@ -12,7 +14,8 @@ namespace TSP
 
     public static class TSPSolver
     {
-        static Tour BestTour;
+        static List<int> BestTour;
+        static double BestWeight;
 
 
         public static Tour MST(string file, string coords, int init)
@@ -29,7 +32,7 @@ namespace TSP
             Tour approximateTour = PreOrder(mstTour[init], mstTour, new Tour());
 
             Debug.WriteLine("\nApproximate Best Tour");
-            Debug.WriteLine(BestTour);
+            Debug.WriteLine(approximateTour);
 
             return approximateTour;
         }
@@ -37,16 +40,26 @@ namespace TSP
         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));
+            Tour bestTour = new Tour(map.Vertices, Coordinate.Parse(coords));
 
+            BestWeight = double.MaxValue;
             BestTour = new();
 
-            BruteForce(intialTour[init], intialTour, new Tour());
+            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);
+            Debug.WriteLine(bestTour);
 
-            return BestTour;
+            return bestTour;
         }
 
         public static Tour PreOrder(City city, Tour mst, Tour visited)
@@ -70,48 +83,48 @@ namespace TSP
             return visited;
         }
 
-        static void BruteForce(City cityInput, Tour unvisitedInput, Tour visitedInput)
+        static void BruteForce(Map map, int city, List<int> unvisitedInput, List<int> visitedInput, double weight)
         {
             // create local copy of Tour variables
-            Tour unvisited = new(unvisitedInput.Cities);
-            Tour visited = new(visitedInput.Cities);
-            City city = new(cityInput);
+            List<int> unvisited = new(unvisitedInput);
+            List<int> visited = new(visitedInput);
 
             // remove current City from tour
-            int removed = unvisited.Cities.RemoveAll(c => c.Id == city.Id);
+            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.Id}");
+                         $"Failed to remove a city from the tour. \nTour: {unvisited}\nCity: {city}");
 
             // set parent of current city to previous city
-            if (visited.Cities.Count > 0)
-                city.Parent = visited.Cities.Last().Id;
+            if (visited.Count > 0)
+                weight += map[city][visited.Last()].Weight;
 
             // add current City to visited
-            visited.Cities.Add(city);
+            visited.Add(city);
 
-
-            if (visited.Weight > BestTour.Weight)
+            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 (City neighbor in unvisited.Cities)
-                BruteForce(neighbor, unvisited, visited);
+            foreach (int neighbor in unvisited)
+                BruteForce(map, neighbor, unvisited, visited, weight);
 
             // if we traversed all cities in the graph
-            if (unvisited.Cities.Count == 0)
+            if (unvisited.Count == 0)
             {
                 // add the return home
-                visited.Cities.First().Parent = visited.Cities.Last().Id;
+                weight += map[visited.First()][visited.Last()].Weight;
 
                 // set as best if lower weight than previous best 
-                if (visited.Weight < BestTour.Weight)
+                if (weight < BestWeight)
                 {
-                    BestTour = new Tour(visited.Cities);
+                    BestTour = visited;
+                    BestWeight = weight;
                     Debug.WriteLine("*** Found new best tour ***");
-                    Debug.WriteLine(visited);
+                    Debug.WriteLine(String.Join(" -> ", visited));
+                    Debug.WriteLine(weight);
                 }
             }
         }