Commits

Shu Zong Chen committed 4e84146

Fixed topological sort edge case, added some more unittests

Comments (0)

Files changed (1)

dependency_graph.py

 		#graph = self.clone() # and doesn't require a copy
 		L = [] # Empty list that will contain the sorted nodes
 		S = self.ends # Set of all nodes with no incoming edges
+		if len(S) == 0 and len(self.vectors):
+			raise dependency_graph.CYCLIC_GRAPH("Cycle discovered during topological sort")
 		V = set() # Set of nodes that have been visited
 		def visit(n):
 			if n not in V: # if n has not been visited yet then
 if __name__ == "__main__":
 	import unittest
 	class BasicTest(unittest.TestCase):
-		def setUp(self):
-			self.simple_graph = [(1, 2), (2, 3)]
-			self.ends_graph = [(1, 2), (3, 4), (4, 5), (5, 6), (7, 8)]
-			self.double_ends = [(1, 2), (1, 3), (2, 3)]
-			pass
+		simple_graph = [(1, 2), (2, 3)]
+		ends_graph = [(1, 2), (3, 4), (4, 5), (5, 6), (7, 8)]
+		double_ends = [(1, 2), (1, 3), (2, 3)]
+		straight_graph = [(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
+		cyclic_graph = [(1, 2), (2, 3), (3, 4), (4, 2)]
+		cyclic_graphb = [(1, 2), (1, 3), (2, 3), (3, 4), (2, 5), (5, 2)]
 
 		def test_init(self):
 			g = dependency_graph()
 			self.assertEqual(h.vectors is h.vectors, True)
 			self.assertEqual(g.vectors is h.vectors, False)
 
+		def test_kahntopological(self):
+			g = dependency_graph(self.straight_graph)
+			self.assertEqual(g.kahn_topological_sort(), [1, 2, 3, 4, 5, 6])
+
+			for _g in (self.cyclic_graph, self.cyclic_graphb):
+				g = dependency_graph(_g)
+				with self.assertRaises(dependency_graph.CYCLIC_GRAPH):
+					g.kahn_topological_sort()
+				
+		def test_topological(self):
+			g = dependency_graph(self.straight_graph)
+			self.assertEqual(g.topological_sort(), [1, 2, 3, 4, 5, 6])
+
+			for _g in (self.cyclic_graph, self.cyclic_graphb):
+				g = dependency_graph(_g)
+				with self.assertRaises(dependency_graph.CYCLIC_GRAPH):
+					g.topological_sort()
+				
 	unittest.main()