# Commits

committed 4e84146

Fixed topological sort edge case, added some more unittests

• Participants
• Parent commits 6a89628

# File 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()`