Kosaraju's Algorithm to find strongly connected components in a directed graph

strongly_connected_components.py

class SCC():
    
    def __init__(self, graph):
        self.graph = graph
        self.time = 0
        self.visited = []
        self.finish_times = {}
    
    def transpose_graph(self):
        g_rev = {}
        for u, v in self.graph.items():
            for node in v:
                if node in g_rev:
                    g_rev[node].append(u)
                    
                else:
                    g_rev[node] = [u]
                    
        self.reverse_graph = g_rev
        
        return g_rev
    
    def iterative_dfs(self, start, graph=None):
        if graph is None:
            graph = self.graph
            
        stack = [start]
        time = self.time
        scc = set()

        visited = self.visited
        finish_times = self.finish_times

        while stack:
            v = stack[-1] # don't pop -- needed to find backtracking
            if v not in visited:
                visited.append(v)

            finished = True
            if graph.get(v) is not None:
                for n in graph[v]: # v's neighbors
                    if n not in visited:
                        finished = False
                        stack.append(n)
                        scc.add(n)

            # done with v's neighbors
            if finished and stack:
                u = stack.pop() # backtracking
                if u not in finish_times:
                    time += 1
                    finish_times[u] = time

                    
        self.visited = visited
        self.finish_times = finish_times
        self.time = time
        
        return scc

    def iterative_dfs_loop(self, graph=None, order=None):
        
        if graph is None:
            graph = self.graph

        visited = self.visited
        components = {}

        if order is None:
            order = sorted(graph.keys())[::-1]

        for node in order:
            if node not in visited:
                leader = node
                scc = self.iterative_dfs(node, graph=graph)

                components[leader] = scc
                
        self.visited = visited

        return components
    
    def __call__(self):
        g_rev = self.transpose_graph()
        
        _ = self.iterative_dfs_loop(g_rev)
        
        self.initial_finish_times = self.finish_times
        self.time = 0
        self.visited = []
        
        order = sorted(self.finish_times.items(), key=operator.itemgetter(1))[::-1]
        order = [node for node, time in order]
        
        components = self.iterative_dfs_loop(order=order)

        return components