2
\$\begingroup\$

Here is my code for Tarjan's strongly connected component algorithm. Please point out any bugs, performance/space (algorithm time/space complexity) optimization or code style issues.

from collections import defaultdict
class SccGraph:
    def __init__(self, vertex_size):
        self.out_neighbour = defaultdict(list)
        self.vertex = set()
        self.visited = set()
        self.index = defaultdict(int)
        self.low_index = defaultdict(int)
        self.global_index = 0
        self.visit_stack = []
        self.scc = []
    def add_edge(self, from_node, to_node):
        self.vertex.add(from_node)
        self.vertex.add(to_node)
        self.out_neighbour[from_node].append(to_node)
    def dfs_graph(self):
        for v in self.vertex:
            if v not in self.visited:
                self.dfs_node(v)
    def dfs_node(self, v):
        # for safe protection
        if v in self.visited:
            return
        self.index[v] = self.global_index
        self.low_index[v] = self.global_index
        self.global_index += 1
        self.visit_stack.append(v)
        self.visited.add(v)
        for n in self.out_neighbour[v]:
            if n not in self.visited:
                self.dfs_node(n)
                self.low_index[v] = min(self.low_index[v], self.low_index[n])
            elif n in self.visit_stack:
                self.low_index[v] = min(self.low_index[v], self.index[n])
        result = []
        if self.low_index[v] == self.index[v]:
            w = self.visit_stack.pop(-1)
            while w != v:
                result.append(w)
                w = self.visit_stack.pop(-1)
            result.append(v)
            self.scc.append(result)

if __name__ == "__main__":
    g = SccGraph(5)
    # setup a graph 1->2->3 and 3 -> 1 which forms a scc
    # setup another two edges 3->4 and 4->5
    g.add_edge(1,2)
    g.add_edge(2,3)
    g.add_edge(3,1)
    g.add_edge(3,4)
    g.add_edge(4,5)
    g.dfs_graph()
    print g.scc
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.