summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
m---------src/CS340.Extensions0
m---------src/CS340.Graph0
m---------src/CS340.Interfaces0
-rw-r--r--src/CS340.Plotter/CS340.Plotter.csproj11
-rw-r--r--src/CS340.Plotter/Plot.Designer.cs1
-rw-r--r--src/CS340.Plotter/Plot.cs7
-rw-r--r--src/CS340.Plotter/Program.cs32
-rw-r--r--src/CS340.Plotter/graphs/test.txt6
m---------src/CS340.PriorityQueue0
-rw-r--r--src/CS340.TSP/City.cs57
-rw-r--r--src/CS340.TSP/Program.cs6
-rw-r--r--src/CS340.TSP/Road.cs26
-rw-r--r--src/CS340.TSP/TSP.cs10
-rw-r--r--src/CS340.TSP/Tour.cs30
14 files changed, 161 insertions, 25 deletions
diff --git a/src/CS340.Extensions b/src/CS340.Extensions
-Subproject 7d01bcd7a01fa877496b7d541648415c2c1830b
+Subproject 9524e96711b9a01868717395f6a040373f5678f
diff --git a/src/CS340.Graph b/src/CS340.Graph
-Subproject 63c57d1a602694ea94b23abc7c59e2779767b6a
+Subproject e3c487f39f44cdecb514fd33e0f5d3f4465451b
diff --git a/src/CS340.Interfaces b/src/CS340.Interfaces
-Subproject 416cddd6ac05790d977414459ca0e91a04a53be
+Subproject 187e8aaf854e9262f1ff6c574a2c28fe662dbbf
diff --git a/src/CS340.Plotter/CS340.Plotter.csproj b/src/CS340.Plotter/CS340.Plotter.csproj
index 7a10161..1cbf369 100644
--- a/src/CS340.Plotter/CS340.Plotter.csproj
+++ b/src/CS340.Plotter/CS340.Plotter.csproj
@@ -1,5 +1,16 @@
<Project Sdk="Microsoft.NET.Sdk">
+ <ItemGroup>
+ <ProjectReference Include="..\CS340.Graph\CS340.Graph.csproj" />
+ <ProjectReference Include="..\CS340.TSP\CS340.TSP.csproj" />
+ <Content Include="graphs\*.*">
+ <CopyToOutputDirectory>Always</CopyToOutputDirectory>
+ </Content>
+ </ItemGroup>
+
+ <ItemGroup>
+ <None Remove="graphs\test.txt" />
+ </ItemGroup>
<PropertyGroup>
<OutputType>WinExe</OutputType>
<TargetFramework>net5.0-windows</TargetFramework>
diff --git a/src/CS340.Plotter/Plot.Designer.cs b/src/CS340.Plotter/Plot.Designer.cs
index 36d9a56..562d725 100644
--- a/src/CS340.Plotter/Plot.Designer.cs
+++ b/src/CS340.Plotter/Plot.Designer.cs
@@ -52,6 +52,7 @@ namespace Plotter
this.Controls.Add(this.Canvas);
this.Name = "Plot";
this.Text = "Plot";
+ this.Load += new System.EventHandler(this.Plot_Load);
((System.ComponentModel.ISupportInitialize)(this.Canvas)).EndInit();
this.ResumeLayout(false);
diff --git a/src/CS340.Plotter/Plot.cs b/src/CS340.Plotter/Plot.cs
index f26978f..0559ece 100644
--- a/src/CS340.Plotter/Plot.cs
+++ b/src/CS340.Plotter/Plot.cs
@@ -32,6 +32,8 @@ namespace Plotter
Canvas.Image = (Bitmap)bmp.Clone();
}
+
+
private void Canvas_SizeChanged(object sender, EventArgs e)
{
Render();
@@ -41,5 +43,10 @@ namespace Plotter
{
Render();
}
+
+ private void Plot_Load(object sender, EventArgs e)
+ {
+
+ }
}
}
diff --git a/src/CS340.Plotter/Program.cs b/src/CS340.Plotter/Program.cs
index 0205767..497ac32 100644
--- a/src/CS340.Plotter/Program.cs
+++ b/src/CS340.Plotter/Program.cs
@@ -1,11 +1,17 @@
+using Graph;
+using Graph.IO;
using System;
using System.Collections.Generic;
+using System.Diagnostics;
+using System.IO;
using System.Linq;
using System.Threading.Tasks;
using System.Windows.Forms;
+using TSP;
namespace Plotter
{
+ using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;
static class Program
{
/// <summary>
@@ -17,7 +23,33 @@ namespace Plotter
Application.SetHighDpiMode(HighDpiMode.SystemAware);
Application.EnableVisualStyles();
Application.SetCompatibleTextRenderingDefault(false);
+ Run();
Application.Run(new Plot());
}
+
+ static void Run()
+ {
+ 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.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));
+ }
+ }
}
}
diff --git a/src/CS340.Plotter/graphs/test.txt b/src/CS340.Plotter/graphs/test.txt
new file mode 100644
index 0000000..113fb4f
--- /dev/null
+++ b/src/CS340.Plotter/graphs/test.txt
@@ -0,0 +1,6 @@
+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
diff --git a/src/CS340.PriorityQueue b/src/CS340.PriorityQueue
-Subproject cbb581eefb3ac38f36810865c264d9b52fbd965
+Subproject 7b0641c6f967b6843ea93010d3eb338eaada014
diff --git a/src/CS340.TSP/City.cs b/src/CS340.TSP/City.cs
new file mode 100644
index 0000000..1990094
--- /dev/null
+++ b/src/CS340.TSP/City.cs
@@ -0,0 +1,57 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using Graph;
+using Interfaces;
+
+namespace TSP
+{
+
+ public class City : IVertex<Road, double>, IComparable<INode<double>>
+ {
+ public int Id { get; set; }
+ public double Key { get; set; }
+
+ public int Parent { get; set; } = -1;
+ public List<Road> Edges { get; set; } = new List<Road>();
+
+ // indexer for accessing edge with v of index
+ public Road this[int index] { get => Edges.Find(edge => edge.V == index); }
+
+ public City() { }
+
+ public City(int id) =>
+ Id = id;
+
+ public City(int id, List<Road> edges) : this(id) =>
+ Edges = edges;
+
+ public City(City vertex)
+ {
+ 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);
+ Edges.Add(newEdge);
+ }
+ }
+ public City(Vertex<Edge<double>, double> vertex)
+ {
+ 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);
+ Edges.Add(newEdge);
+ }
+ }
+
+ public int CompareTo(INode<double> node) =>
+ Key.CompareTo(node.Key);
+
+ public override string ToString() => $"{Id} {String.Join(" ", Edges.Select(e => (e.V, e.Weight)))}";
+ }
+} \ No newline at end of file
diff --git a/src/CS340.TSP/Program.cs b/src/CS340.TSP/Program.cs
index 16c041c..618c58a 100644
--- a/src/CS340.TSP/Program.cs
+++ b/src/CS340.TSP/Program.cs
@@ -7,8 +7,8 @@ using Interfaces;
namespace TSP
{
- using Graph = Graph<double>;
- using Tour = Tour<double>;
+
+ using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;
class Program
{
@@ -17,7 +17,7 @@ namespace TSP
{
foreach (string file in Directory.GetFiles("graphs/"))
{
- Graph graph = GraphFile.Read(new FileReader(file));
+ Map graph = GraphFile.Read(new FileReader(file));
// Graph mst = graph.MST(0);
// GraphFile.Print(mst, new ConsoleWriter());
// Console.WriteLine(
diff --git a/src/CS340.TSP/Road.cs b/src/CS340.TSP/Road.cs
new file mode 100644
index 0000000..9711c3c
--- /dev/null
+++ b/src/CS340.TSP/Road.cs
@@ -0,0 +1,26 @@
+using System;
+using Interfaces;
+
+namespace TSP
+{
+ public class Road : IEdge<double>
+ {
+ public int U { get; set; }
+ public int V { get; set; }
+ public double Weight { get; set; }
+
+ public Road() { }
+
+ public Road(int u, int v, double weight)
+ {
+ U = u;
+ V = v;
+ Weight = weight;
+ }
+
+ public int CompareTo(IEdge<double> edge) =>
+ Weight.CompareTo(edge.Weight);
+
+ public override string ToString() => $"{U} {V} {Weight}";
+ }
+}
diff --git a/src/CS340.TSP/TSP.cs b/src/CS340.TSP/TSP.cs
index de7eda8..a26fe6c 100644
--- a/src/CS340.TSP/TSP.cs
+++ b/src/CS340.TSP/TSP.cs
@@ -1,18 +1,20 @@
using System.Diagnostics;
using System.Linq;
+using System.Text.RegularExpressions;
using Graph;
+using Graph.IO;
namespace TSP
{
- using City = Vertex<double>;
- using Tour = Tour<double>;
+
+ using Map = Graph<Vertex<Edge<double>, double>, Edge<double>, double>;
public static class TSP
{
static Tour BestTour = null;
- static Graph<double> Map;
+ static Map Map;
- public static Tour BruteForce(Graph<double> map, int init)
+ public static Tour BruteForce(Map map, int init)
{
Map = map;
Tour intialTour = new Tour(map.Vertices);
diff --git a/src/CS340.TSP/Tour.cs b/src/CS340.TSP/Tour.cs
index 80db19d..e6e5d40 100644
--- a/src/CS340.TSP/Tour.cs
+++ b/src/CS340.TSP/Tour.cs
@@ -5,30 +5,24 @@ using Graph;
namespace TSP
{
-
- public class Tour<T> where T : IComparable<T>
+ using Vertex = Vertex<Edge<double>, double>;
+ public class Tour
{
- public List<Vertex<T>> Cities { get; set; } = new List<Vertex<T>>();
- public T Weight
+ public List<City> Cities { get; set; } = new List<City>();
+ public double Weight
{
- get
- {
- dynamic _weight = default(T);
- Cities.Where(city => city.Parent != -1).ToList()
- .ForEach(city =>
- _weight += city.Edges
- .Where(edge => edge.V == city.Parent)
- .First().Weight);
- return _weight;
- }
+ get => Cities
+ .Where(city => city.Parent != -1)
+ .Sum(city => city.Key);
}
// indexer: get vertex where vertex.Id == index
- public Vertex<T> this[int index] { get => Cities.Find(vertex => vertex.Id == index); }
+ public City this[int index] { get => Cities.Find(vertex => vertex.Id == index); }
- public Tour(List<Vertex<T>> cities) => Cities.AddRange(cities.Select(city => new Vertex<T>(city)));
- public Tour() => Cities = new List<Vertex<T>>();
- public Tour(Tour<T> tour) : this(tour.Cities) { }
+ public Tour(List<Vertex> cities) => Cities.AddRange(cities.Select(city => new City(city)));
+ public Tour(List<City> cities) => Cities.AddRange(cities.Select(city => new City(city)));
+ public Tour() => Cities = new List<City>();
+ public Tour(Tour tour) : this(tour.Cities) { }
public override string ToString() =>
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2024-09-20 13:33:14 +0000