Commits

Shu Zong Chen committed 2a53596

Fixed a broken implementation of cyclic checking in topological sort

  • Participants
  • Parent commits 4e84146

Comments (0)

Files changed (1)

File dependency_graph.py

 				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()