Commits

David Jones committed 66cb6a7

adding graphs file.

Comments (0)

Files changed (1)

+
+class Edge(object):
+    def __init__(self, v, w):
+        self.v, self.w = v, w
+    
+
+class Graph(object):
+    def __init__(self, number_vertices):
+        self.number_vertices = number_vertices
+        self.vertices = range(number_vertices)
+        self.edges = [list() for v in self.vertices]
+
+    def add_edge(self, edge):
+        self.edges[edge.v].append(edge.w)
+
+
+    def __repr__(self):
+        output = []
+        for vertex, edge in enumerate(self.edges):
+            output.append("%d:  %s" % (vertex, edge))
+        return "\n".join(output)
+
+    def get_edge_iterator(self, v):
+        for w in self.edges[v]:
+            yield w
+
+def reverse(graph):
+    result = Graph(graph.number_vertices)
+    for v in graph.vertices:
+        for w in graph.get_edge_iterator(v):
+            result.add_edge(Edge(w, v))
+    return result
+
+
+class KosarajuStrongComponents(object):
+    def __init__(self):
+        pass
+
+    def calculate(self, graph):
+        self.graph = graph
+        self.postorder = [0] * graph.number_vertices
+        self.count = 0
+        self.component_count = 0
+
+        self.id = [-1] * graph.number_vertices
+        reversed = reverse(graph)
+        for v in graph.vertices:
+            if self.id[v] == -1:
+                self.dfs(graph, v)
+        
+        self.reverse_postorder = self.postorder
+        self.id = [-1] * graph.number_vertices
+        print "reverse_postorder"
+        print self.reverse_postorder
+        self.count = 0
+        self.component_count = 0
+
+        for v in xrange(graph.number_vertices - 1, -1, -1):
+            t = self.reverse_postorder[v]
+            if self.id[t] == -1:
+                self.dfs(graph, t)
+                self.component_count += 1
+
+    def dfs(self, graph, w):
+        self.id[w] = self.component_count
+        for t in graph.get_edge_iterator(w):
+            if (self.id[t] == -1):
+                self.dfs(graph, t)
+            self.postorder[t] = self.count
+        self.count += 1
+        
+
+if __name__ == "__main__":
+    graph = Graph(10)
+    for i in xrange(5):
+        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))
+
+    print graph
+    print "reversed"
+    
+    print reverse(graph)
+
+    k = KosarajuStrongComponents()
+    k.calculate(graph)
+
+    print k.id
+