Commits

David Jones  committed 4333fa7

fixed what should have been a bug.

  • Participants
  • Parent commits 88df317

Comments (0)

Files changed (1)

             yield w
 
 def reverse(graph):
+    """Return the reverse of a directed graph"""
     result = Graph(graph.number_vertices)
     for v in graph.vertices:
         for w in graph.get_edge_iterator(v):
         self.count = 0
         self.component_count = 0
 
+        # do a reverse topological sort
         self.id = [-1] * graph.number_vertices
         reversed = reverse(graph)
         for v in reversed.vertices:
             if self.id[v] == -1:
                 self.dfs(reversed, v)
         
-        self.reverse_postorder = self.postorder
+        self.reverse_postorder = list(self.postorder)
         self.id = [-1] * graph.number_vertices
         print "reverse_postorder"
         print self.reverse_postorder
         
 
 if __name__ == "__main__":
-    graph = Graph(10)
-    for i in xrange(5):
+    graph = Graph(1000)
+    for i in xrange(999):
         graph.add_edge(Edge(i,i+1))
     graph.add_edge(Edge(5, 0))
     for i in xrange(5,9):
         graph.add_edge(Edge(i,i+1))
-
+    graph.add_edge(Edge(9,7))
     print graph
     print "reversed"
     
     k.calculate(graph)
 
     print k.id
+
+    print "done"