# Commits

committed 2a53596

Fixed a broken implementation of cyclic checking in topological sort

• Participants
• Parent commits 4e84146
• Branches default

# File dependency_graph.py

• Ignore whitespace
` 				for m in self.parents_of(n): # for each node m with an edge from n to m do`
` 					visit(m) # visit(m)`
` 				L.append(n) # add n to L`
`-			else:`
`+			elif n not in L:`
` 				raise dependency_graph.CYCLIC_GRAPH("Cycle discovered during topological sort")`
` 		for n in S:`
` 			visit(n)`
` 		"""Perform a depth-first topological sort"""`
` 		return self._topological_sort()`
` `
`+	def sort_into_levels(self):`
`+		TS = self.topological_sort()`
`+		print "Found sort", TS`
`+		for n in TS:`
`+			print "--------\nTesting", n`
`+			ancestors = self.ancestors_of(n)`
`+			`
`+`
` 	@property`
` 	def feedback_arc_set(self):`
` 		raise NotImplementedError`
` 			g = dependency_graph(self.straight_graph)`
` 			self.assertEqual(g.kahn_topological_sort(), [1, 2, 3, 4, 5, 6])`
` `
`+			g = dependency_graph(self.double_ends)`
`+			g.kahn_topological_sort()`
`+`
` 			for _g in (self.cyclic_graph, self.cyclic_graphb):`
` 				g = dependency_graph(_g)`
` 				with self.assertRaises(dependency_graph.CYCLIC_GRAPH):`
` 			g = dependency_graph(self.straight_graph)`
` 			self.assertEqual(g.topological_sort(), [1, 2, 3, 4, 5, 6])`
` `
`+			g = dependency_graph(self.double_ends)`
`+			g.topological_sort()`
`+`
` 			for _g in (self.cyclic_graph, self.cyclic_graphb):`
` 				g = dependency_graph(_g)`
` 				with self.assertRaises(dependency_graph.CYCLIC_GRAPH):`
` 					g.topological_sort()`
`+`
`+		def test_leveler(self):`
`+			g = dependency_graph(self.double_ends)`
`+			print g.sort_into_levels()`
` 				`
` 	unittest.main()`