From b03ade8a3c2d94c1931d09f8d09b7865826a9743 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Sun, 2 May 2021 14:58:01 -0500 Subject: removed CS340 namespace Signed-off-by: Toby Vincent --- src/CS340.TSP/CS340.TSP.csproj | 13 ----- src/CS340.TSP/City.cs | 36 ------------ src/CS340.TSP/Coordinates.cs | 38 ------------ src/CS340.TSP/TSPSolver.cs | 127 ----------------------------------------- src/CS340.TSP/Tour.cs | 42 -------------- 5 files changed, 256 deletions(-) delete mode 100644 src/CS340.TSP/CS340.TSP.csproj delete mode 100644 src/CS340.TSP/City.cs delete mode 100644 src/CS340.TSP/Coordinates.cs delete mode 100644 src/CS340.TSP/TSPSolver.cs delete mode 100644 src/CS340.TSP/Tour.cs (limited to 'src/CS340.TSP') diff --git a/src/CS340.TSP/CS340.TSP.csproj b/src/CS340.TSP/CS340.TSP.csproj deleted file mode 100644 index dae9f9e..0000000 --- a/src/CS340.TSP/CS340.TSP.csproj +++ /dev/null @@ -1,13 +0,0 @@ - - - - net5.0 - - - - - - - - - diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs deleted file mode 100644 index 4889bdb..0000000 --- a/src/CS340.TSP/City.cs +++ /dev/null @@ -1,36 +0,0 @@ -using System; -using System.Collections.Generic; -using Graph; -using Interfaces; - -namespace TSP -{ - using INode = INode; - using IVertex = IVertex, double>; - using Road = Edge; - using Vertex = Vertex, double>; - - public partial class City : Vertex, IVertex, IComparable - { - - public new double Key { get => this[Parent].Weight; } - - public Coordinate Location { get; set; } - - public City() { } - - public City(int id) => - Id = id; - - public City(int id, List edges) : this(id) => - Edges = edges; - - public City(IVertex city) : this(city.Id, city.Edges) => - Parent = city.Parent; - - public City(IVertex city, Coordinate location) : this(city) => - Location = location; - - public City(City city) : this(city, city.Location) { } - } -} \ No newline at end of file diff --git a/src/CS340.TSP/Coordinates.cs b/src/CS340.TSP/Coordinates.cs deleted file mode 100644 index 1e74021..0000000 --- a/src/CS340.TSP/Coordinates.cs +++ /dev/null @@ -1,38 +0,0 @@ -using System.Collections.Generic; -using System.IO; - -namespace TSP -{ - public struct Coordinate - { - public int X { get; set; } - public int Y { get; set; } - - public Coordinate(int x, int y) - { - X = x; - Y = y; - } - - public Coordinate(string coords) - { - string[] items = coords.Split(','); - X = int.Parse(items[0]); - Y = int.Parse(items[1]); - } - - - - public static List Parse(string file) - { - List coordinates = new List(); - foreach (string coords in File.ReadAllLines(file)) - coordinates.Add(new Coordinate(coords)); - - return coordinates; - } - - - public override string ToString() => $"({X}, {Y})"; - } -} diff --git a/src/CS340.TSP/TSPSolver.cs b/src/CS340.TSP/TSPSolver.cs deleted file mode 100644 index 84d3945..0000000 --- a/src/CS340.TSP/TSPSolver.cs +++ /dev/null @@ -1,127 +0,0 @@ -using System; -using System.Collections.Generic; -using System.Diagnostics; -using System.Linq; -using Extensions; -using Graph; -using Graph.IO; - -namespace TSP -{ - - using Map = Graph, double>, Edge, double>; - using Road = Edge; - - 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 BestTour = new(); - - BruteForce(map, init, map.Vertices.Select(city => city.Id).ToList(), new List(), 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 unvisitedInput, List visitedInput, double weight) - { - // create local copy of Tour variables - List unvisited = new(unvisitedInput); - List 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}"); - } - } - } - } - } -} diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs deleted file mode 100644 index 5f530be..0000000 --- a/src/CS340.TSP/Tour.cs +++ /dev/null @@ -1,42 +0,0 @@ -using System; -using System.Collections.Generic; -using System.Linq; -using Graph; - -namespace TSP -{ - using Vertex = Vertex, double>; - public class Tour - { - public List Cities { get; set; } = new List(); - public double Weight - { - 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 - public City this[int index] { get => Cities.Find(city => city.Id == index); } - - public Tour() => - Cities = new List(); - - public Tour(Tour tour) : this(tour.Cities) { } - - public Tour(List cities) => - Cities.AddRange(cities.Select(city => new City(city))); - - public Tour(List cities, List coordinates) => - Cities.AddRange(cities.Select(city => new City(city, coordinates[city.Id]))); - - public override string ToString() => - $"{Weight},{String.Join(",", Cities.Select(city => city.Id))}"; - - } -} -- cgit v1.2.3-70-g09d2