implements tarjan s algorithm for finding strongly connected components in a graph https en wikipedia orgwikitarjan27sstronglyconnectedcomponentsalgorithm pylint disabletoofewpublicmethods a directed graph used for finding strongly connected components runs tarjan set all node index to none given a vertex adds all successors of the given vertex to the same connected component set the depth index for v to the smallest unused index consider successors of v successor w has not yet been visited recurse on it successor w is in stack s and hence in the current scc if w is not on stack then v w is a crossedge in the dfs tree and must be ignored note the next line may look odd but is correct it says w index not w lowlink that is deliberate and from the original paper if v is a root node pop the stack and generate an scc start a new strongly connected component pylint disable too few public methods a directed graph used for finding strongly connected components runs tarjan set all node index to none given a vertex adds all successors of the given vertex to the same connected component set the depth index for v to the smallest unused index consider successors of v successor w has not yet been visited recurse on it successor w is in stack s and hence in the current scc if w is not on stack then v w is a cross edge in the dfs tree and must be ignored note the next line may look odd but is correct it says w index not w lowlink that is deliberate and from the original paper if v is a root node pop the stack and generate an scc start a new strongly connected component
from algorithms.graph.graph import DirectedGraph



class Tarjan:
    
    def __init__(self, dict_graph):
        self.graph = DirectedGraph(dict_graph)
        self.index = 0
        self.stack = []

        
        
        for vertex in self.graph.nodes:
            vertex.index = None

        self.sccs = []
        for vertex in self.graph.nodes:
            if vertex.index is None:
                self.strongconnect(vertex, self.sccs)

    def strongconnect(self, vertex, sccs):
        
        
        vertex.index = self.index
        vertex.lowlink = self.index
        self.index += 1
        self.stack.append(vertex)
        vertex.on_stack = True

        
        for adjacent in self.graph.adjacency_list[vertex]:
            if adjacent.index is None:
                
                self.strongconnect(adjacent, sccs)
                vertex.lowlink = min(vertex.lowlink, adjacent.lowlink)
            elif adjacent.on_stack:
                
                
                
                
                
                vertex.lowlink = min(vertex.lowlink, adjacent.index)

        
        if vertex.lowlink == vertex.index:
            
            scc = []
            while True:
                adjacent = self.stack.pop()
                adjacent.on_stack = False
                scc.append(adjacent)
                if adjacent == vertex:
                    break
            scc.sort()
            sccs.append(scc)