generic tsp

justcoding121 · justcoding121 · commit ecf71861bf97 · 2019-04-22T16:06:59.000-04:00
diff --git a/src/Advanced.Algorithms/Graph/ShortestPath/TravellingSalesman.cs b/src/Advanced.Algorithms/Graph/ShortestPath/TravellingSalesman.cs
@@ -1,5 +1,6 @@
 ﻿
 using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;
+using System;
 using System.Collections.Generic;
 using System.Linq;
 
@@ -9,21 +10,25 @@ namespace Advanced.Algorithms.Graph
     /// Uses dynamic programming for a
     /// psuedo-polynomial time runTime complexity for this NP hard problem.
     /// </summary>
-    public class TravellingSalesman
+    public class TravellingSalesman<T, W> where W : IComparable
     {
-        public static int FindMinWeight(WeightedDiGraph<int, int> graph)
+        IShortestPathOperators<W> @operator;
+
+        public W FindMinWeight(WeightedDiGraph<T, W> graph, IShortestPathOperators<W> @operator)
         {
+            this.@operator = @operator;
+
             return findMinWeight(graph.ReferenceVertex, graph.ReferenceVertex,
                                 graph.VerticesCount,
-                                new HashSet<WeightedDiGraphVertex<int, int>>(),
-                                new Dictionary<string, int>());
+                                new HashSet<WeightedDiGraphVertex<T, W>>(),
+                                new Dictionary<string, W>());
         }
 
-        private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,
-            WeightedDiGraphVertex<int, int> tgtVertex,
+        private W findMinWeight(WeightedDiGraphVertex<T, W> currentVertex,
+            WeightedDiGraphVertex<T, W> tgtVertex,
             int remainingVertexCount,
-            HashSet<WeightedDiGraphVertex<int, int>> visited,
-            Dictionary<string, int> cache)
+            HashSet<WeightedDiGraphVertex<T, W>> visited,
+            Dictionary<string, W> cache)
         {
             var cacheKey = $"{currentVertex.Value}-{remainingVertexCount}";
 
@@ -34,7 +39,7 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,
 
             visited.Add(currentVertex);
 
-            var results = new List<int>();
+            var results = new List<W>();
 
             foreach (var vertex in currentVertex.OutEdges)
             {
@@ -50,9 +55,9 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,
                 {
                     var result = findMinWeight(vertex.Key, tgtVertex, remainingVertexCount - 1, visited, cache);
 
-                    if (result != int.MaxValue)
+                    if (!result.Equals(@operator.MaxValue))
                     {
-                        results.Add(result + vertex.Value);
+                        results.Add(@operator.Sum(result, vertex.Value));
                     }
 
                 }
@@ -62,7 +67,7 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,
 
             if (results.Count == 0)
             {
-                return int.MaxValue;
+                return @operator.MaxValue;
             }
 
             var min = results.Min();
diff --git a/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/TravellingSalesman_Tests.cs b/tests/Advanced.Algorithms.Tests/Graph/ShortestPath/TravellingSalesman_Tests.cs
@@ -37,7 +37,39 @@ public void TravellingSalesman_Smoke_Test()
             graph.AddEdge(3, 1, 4);
             graph.AddEdge(3, 2, 8);
 
-            Assert.AreEqual(21, TravellingSalesman.FindMinWeight(graph));
+            var tsp = new TravellingSalesman<int, int>();
+            Assert.AreEqual(21, tsp.FindMinWeight(graph, new TSPShortestPathOperators()));
+        }
+    }
+
+    /// <summary>
+    /// generic operations for int type
+    /// </summary>
+    public class TSPShortestPathOperators : IShortestPathOperators<int>
+    {
+        public int DefaultValue
+        {
+            get
+            {
+                return 0;
+            }
+
+
+        }
+
+        public int MaxValue
+        {
+            get
+            {
+                return int.MaxValue;
+            }
+        }
+
+        public int Sum(int a, int b)
+        {
+            return checked(a + b);
         }
     }
 }
+
+

Original file line number	Diff line number	Diff line change
`@@ -1,5 +1,6 @@`
`1`	`1`
`2`	`2`	`using Advanced.Algorithms.DataStructures.Graph.AdjacencyList;`
	`3`	`+using System;`
`3`	`4`	`using System.Collections.Generic;`
`4`	`5`	`using System.Linq;`
`5`	`6`
`@@ -9,21 +10,25 @@ namespace Advanced.Algorithms.Graph`
`9`	`10`	`/// Uses dynamic programming for a`
`10`	`11`	`/// psuedo-polynomial time runTime complexity for this NP hard problem.`
`11`	`12`	`/// </summary>`
`12`		`- public class TravellingSalesman`
	`13`	`+ public class TravellingSalesman<T, W> where W : IComparable`
`13`	`14`	`{`
`14`		`- public static int FindMinWeight(WeightedDiGraph<int, int> graph)`
	`15`	`+ IShortestPathOperators<W> @operator;`
	`16`	`+`
	`17`	`+ public W FindMinWeight(WeightedDiGraph<T, W> graph, IShortestPathOperators<W> @operator)`
`15`	`18`	`{`
	`19`	`+ this.@operator = @operator;`
	`20`	`+`
`16`	`21`	`return findMinWeight(graph.ReferenceVertex, graph.ReferenceVertex,`
`17`	`22`	`graph.VerticesCount,`
`18`		`- new HashSet<WeightedDiGraphVertex<int, int>>(),`
`19`		`- new Dictionary<string, int>());`
	`23`	`+ new HashSet<WeightedDiGraphVertex<T, W>>(),`
	`24`	`+ new Dictionary<string, W>());`
`20`	`25`	`}`
`21`	`26`
`22`		`- private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,`
`23`		`- WeightedDiGraphVertex<int, int> tgtVertex,`
	`27`	`+ private W findMinWeight(WeightedDiGraphVertex<T, W> currentVertex,`
	`28`	`+ WeightedDiGraphVertex<T, W> tgtVertex,`
`24`	`29`	`int remainingVertexCount,`
`25`		`- HashSet<WeightedDiGraphVertex<int, int>> visited,`
`26`		`- Dictionary<string, int> cache)`
	`30`	`+ HashSet<WeightedDiGraphVertex<T, W>> visited,`
	`31`	`+ Dictionary<string, W> cache)`
`27`	`32`	`{`
`28`	`33`	`var cacheKey = $"{currentVertex.Value}-{remainingVertexCount}";`
`29`	`34`
`@@ -34,7 +39,7 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,`
`34`	`39`
`35`	`40`	`visited.Add(currentVertex);`
`36`	`41`
`37`		`- var results = new List<int>();`
	`42`	`+ var results = new List<W>();`
`38`	`43`
`39`	`44`	`foreach (var vertex in currentVertex.OutEdges)`
`40`	`45`	`{`
`@@ -50,9 +55,9 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,`
`50`	`55`	`{`
`51`	`56`	`var result = findMinWeight(vertex.Key, tgtVertex, remainingVertexCount - 1, visited, cache);`
`52`	`57`
`53`		`- if (result != int.MaxValue)`
	`58`	`+ if (!result.Equals(@operator.MaxValue))`
`54`	`59`	`{`
`55`		`- results.Add(result + vertex.Value);`
	`60`	`+ results.Add(@operator.Sum(result, vertex.Value));`
`56`	`61`	`}`
`57`	`62`
`58`	`63`	`}`
`@@ -62,7 +67,7 @@ private static int findMinWeight(WeightedDiGraphVertex<int, int> currentVertex,`
`62`	`67`
`63`	`68`	`if (results.Count == 0)`
`64`	`69`	`{`
`65`		`- return int.MaxValue;`
	`70`	`+ return @operator.MaxValue;`
`66`	`71`	`}`
`67`	`72`
`68`	`73`	`var min = results.Min();`