From 2a5db460a9d9091238f64c48a640aac7cbe40678 Mon Sep 17 00:00:00 2001 From: Toby Vincent Date: Thu, 22 Apr 2021 20:43:24 -0500 Subject: implemented graph printing --- src/CS340.TSP/CS340.TSP.csproj | 6 ------ src/CS340.TSP/City.cs | 20 +++++++++++--------- src/CS340.TSP/Coordinates.cs | 33 +++++++++++++++++++++++++++------ src/CS340.TSP/Solve.cs | 17 +++++++++++------ src/CS340.TSP/Tour.cs | 11 ++++++++--- src/CS340.TSP/graphs/test.txt | 6 ------ 6 files changed, 57 insertions(+), 36 deletions(-) delete mode 100644 src/CS340.TSP/graphs/test.txt (limited to 'src/CS340.TSP') diff --git a/src/CS340.TSP/CS340.TSP.csproj b/src/CS340.TSP/CS340.TSP.csproj index 08af2ae..dae9f9e 100644 --- a/src/CS340.TSP/CS340.TSP.csproj +++ b/src/CS340.TSP/CS340.TSP.csproj @@ -4,12 +4,6 @@ net5.0 - - - Always - - - diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs index 962a864..a64439b 100644 --- a/src/CS340.TSP/City.cs +++ b/src/CS340.TSP/City.cs @@ -1,6 +1,5 @@ using System; using System.Collections.Generic; -using System.Linq; using Graph; using Interfaces; @@ -16,25 +15,28 @@ namespace TSP public new double Key { get => this[Parent].Weight; set => Key = value; } - public Coordinates Location { get; set; } + 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) + public City(int id, List edges) : this(id) { - Id = city.Id; - Parent = city.Parent; - foreach (Road edge in city.Edges) + foreach (Road edge in edges) { Road newEdge = new Road(edge.U, edge.V, edge.Weight); Edges.Add(newEdge); } } + + public City(IVertex city) : this(city.Id, city.Edges) => + Parent = city.Parent; + + public City(IVertex city, Coordinate location) : this(city) => + Location = new Coordinate(location.X, location.Y); + + 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 index f377c89..1e74021 100644 --- a/src/CS340.TSP/Coordinates.cs +++ b/src/CS340.TSP/Coordinates.cs @@ -1,17 +1,38 @@ -using Graph; -using Interfaces; +using System.Collections.Generic; +using System.IO; namespace TSP { - public struct Coordinates + public struct Coordinate { - public double X { get; set; } - public double Y { get; set; } + public int X { get; set; } + public int Y { get; set; } - public Coordinates(double x, double y) + 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/Solve.cs b/src/CS340.TSP/Solve.cs index dd3d306..8adcd50 100644 --- a/src/CS340.TSP/Solve.cs +++ b/src/CS340.TSP/Solve.cs @@ -1,6 +1,6 @@ using System.Diagnostics; using System.Linq; -using System.Text.RegularExpressions; +using Extensions; using Graph; using Graph.IO; @@ -14,11 +14,18 @@ namespace TSP static Map Map { get; set; } static Tour BestTour = null; - public static Tour BruteForce(string file, int init) + + 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); - GenerateTour(intialTour[init], new Tour(Map.Vertices), new Tour()); + Tour intialTour = new Tour(Map.Vertices, Coordinate.Parse(coords)); + GenerateTour(intialTour[init], intialTour, new Tour()); return BestTour; } @@ -39,9 +46,7 @@ namespace TSP // add current City to visited if (currVisited.Cities.Count > 0) - { currCity.Parent = currVisited.Cities.Last().Id; - } currVisited.Cities.Add(currCity); diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs index e6e5d40..d90ab7e 100644 --- a/src/CS340.TSP/Tour.cs +++ b/src/CS340.TSP/Tour.cs @@ -19,11 +19,16 @@ namespace TSP // indexer: get vertex where vertex.Id == index public City this[int index] { get => Cities.Find(vertex => vertex.Id == index); } - public Tour(List cities) => Cities.AddRange(cities.Select(city => new City(city))); - public Tour(List cities) => Cities.AddRange(cities.Select(city => new City(city))); - public Tour() => Cities = new List(); + 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.Zip(coordinates, (city, coord) => new City(city, coord))); public override string ToString() => $"tour: {String.Join(" -> ", Cities.Select(city => city.Id))}\n" + diff --git a/src/CS340.TSP/graphs/test.txt b/src/CS340.TSP/graphs/test.txt deleted file mode 100644 index 113fb4f..0000000 --- a/src/CS340.TSP/graphs/test.txt +++ /dev/null @@ -1,6 +0,0 @@ -0 1 78.85429601486528 2 64.62197768561404 3 59.135437767890075 4 71.84705978674423 5 54.08326913195984 -1 0 78.85429601486528 2 93.47726996441435 3 21.095023109728988 4 28.635642126552707 5 102.55242561733974 -2 0 64.62197768561404 1 93.47726996441435 3 85.23496934944014 4 67.89698078707183 5 21.840329667841555 -3 0 59.135437767890075 1 21.095023109728988 2 85.23496934944014 4 33.54101966249684 5 90.21086409075129 -4 0 71.84705978674423 1 28.635642126552707 2 67.89698078707183 3 33.54101966249684 5 80.45495634204272 -5 0 54.08326913195984 1 102.55242561733974 2 21.840329667841555 3 90.21086409075129 4 80.45495634204272 \ No newline at end of file -- cgit v1.2.3-70-g09d2