diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/CS340.Plotter/Program.cs | 11 | ||||
| -rw-r--r-- | src/CS340.TSP/City.cs | 4 | ||||
| -rw-r--r-- | src/CS340.TSP/Program.cs | 47 | ||||
| -rw-r--r-- | src/CS340.TSP/Road.cs | 5 | ||||
| -rw-r--r-- | src/CS340.TSP/Solve.cs (renamed from src/CS340.TSP/TSP.cs) | 15 |
5 files changed, 15 insertions, 67 deletions
diff --git a/src/CS340.Plotter/Program.cs b/src/CS340.Plotter/Program.cs index 497ac32..9e9a52a 100644 --- a/src/CS340.Plotter/Program.cs +++ b/src/CS340.Plotter/Program.cs @@ -1,5 +1,3 @@ -using Graph; -using Graph.IO; using System; using System.Collections.Generic; using System.Diagnostics; @@ -7,11 +5,12 @@ using System.IO; using System.Linq; using System.Threading.Tasks; using System.Windows.Forms; +using Graph; +using Graph.IO; using TSP; namespace Plotter { - using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; static class Program { /// <summary> @@ -31,15 +30,15 @@ namespace Plotter { foreach (string file in Directory.GetFiles("graphs/")) { - Map graph = GraphFile.Read(new FileReader(file)); + Tour bruteForce = Solve.BruteForce(file, 0); + Debug.WriteLine(bruteForce); + // Graph mst = graph.MST(0); // GraphFile.Print(mst, new ConsoleWriter()); // Console.WriteLine( // graph.Vertices.Sum(vertex => // vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); - Tour bruteForce = TSP.TSP.BruteForce(graph, 0); - Debug.WriteLine(bruteForce); // mst.Vertices.ForEach(vertex => // { // Console.Write($"{vertex.Id}"); diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs index 1990094..1a38e2c 100644 --- a/src/CS340.TSP/City.cs +++ b/src/CS340.TSP/City.cs @@ -10,7 +10,7 @@ namespace TSP public class City : IVertex<Road, double>, IComparable<INode<double>> { public int Id { get; set; } - public double Key { get; set; } + public double Key { get => this[Parent].Weight; set => Key = value; } public int Parent { get; set; } = -1; public List<Road> Edges { get; set; } = new List<Road>(); @@ -30,7 +30,6 @@ namespace TSP { Id = vertex.Id; Parent = vertex.Parent; - Key = vertex.Key; foreach (Road edge in vertex.Edges) { Road newEdge = new Road(edge.U, edge.V, edge.Weight); @@ -41,7 +40,6 @@ namespace TSP { Id = vertex.Id; Parent = vertex.Parent; - Key = vertex.Key; foreach (Edge<double> edge in vertex.Edges) { Road newEdge = new Road(edge.U, edge.V, edge.Weight); diff --git a/src/CS340.TSP/Program.cs b/src/CS340.TSP/Program.cs deleted file mode 100644 index 618c58a..0000000 --- a/src/CS340.TSP/Program.cs +++ /dev/null @@ -1,47 +0,0 @@ -using System; -using System.Diagnostics; -using System.IO; -using Graph; -using Graph.IO; -using Interfaces; - -namespace TSP -{ - - using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; - class Program - { - - // https://swharden.com/CsharpDataVis/drawing/3-drawing-in-wpf.md.html - static void Main(string[] args) - { - foreach (string file in Directory.GetFiles("graphs/")) - { - Map graph = GraphFile.Read(new FileReader(file)); - // Graph mst = graph.MST(0); - // GraphFile.Print(mst, new ConsoleWriter()); - // Console.WriteLine( - // graph.Vertices.Sum(vertex => - // vertex.Edges.FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); - - Tour bruteForce = TSP.BruteForce(graph, 0); - Debug.WriteLine(bruteForce); - // mst.Vertices.ForEach(vertex => - // { - // Console.Write($"{vertex.Id}"); - // vertex.Edges.ForEach(edge => Console.Write($" {edge.V} {edge.Weight.ToString("F1")}")); - // Console.WriteLine(); - // }); - // Console.WriteLine(mst.Vertices - // .Sum(vertex => vertex.Edges - // .FirstOrDefault(edge => edge.V == vertex.Parent).Weight)); - } - } - } - - class ConsoleWriter : IFileWriter - { - public void WriteAllLines(string[] lines) => - Array.ForEach(lines, line => Debug.WriteLine(line)); - } -} diff --git a/src/CS340.TSP/Road.cs b/src/CS340.TSP/Road.cs index 9711c3c..cc939e9 100644 --- a/src/CS340.TSP/Road.cs +++ b/src/CS340.TSP/Road.cs @@ -3,7 +3,8 @@ using Interfaces; namespace TSP { - public class Road : IEdge<double> + using IEdge = IEdge<double>; + public class Road : IEdge, IComparable<IEdge> { public int U { get; set; } public int V { get; set; } @@ -18,7 +19,7 @@ namespace TSP Weight = weight; } - public int CompareTo(IEdge<double> edge) => + public int CompareTo(IEdge edge) => Weight.CompareTo(edge.Weight); public override string ToString() => $"{U} {V} {Weight}"; diff --git a/src/CS340.TSP/TSP.cs b/src/CS340.TSP/Solve.cs index a26fe6c..dd3d306 100644 --- a/src/CS340.TSP/TSP.cs +++ b/src/CS340.TSP/Solve.cs @@ -9,16 +9,16 @@ namespace TSP using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>; - public static class TSP + public static class Solve { + static Map Map { get; set; } static Tour BestTour = null; - static Map Map; - public static Tour BruteForce(Map map, int init) + public static Tour BruteForce(string file, int init) { - Map = map; - Tour intialTour = new Tour(map.Vertices); - GenerateTour(intialTour[init], new Tour(map.Vertices), new Tour()); + Map = GraphFile.Read(new FileReader(file)); + Tour intialTour = new Tour(Map.Vertices); + GenerateTour(intialTour[init], new Tour(Map.Vertices), new Tour()); return BestTour; } @@ -41,9 +41,6 @@ namespace TSP if (currVisited.Cities.Count > 0) { currCity.Parent = currVisited.Cities.Last().Id; - currCity.Key = Map.Vertices[currCity.Id].Edges - .Where(edge => edge.V == currCity.Parent) - .Last().Weight; } currVisited.Cities.Add(currCity); |