3
\$\begingroup\$

As described in his paper, Tarjan's algorithm reports only the nodes of the strongly connected components. For my use, I would also like to also have the edge list of the components (so that I can run Karp's minimum mean cycle algorithm on it)

As a side note, it is rather curious why he did it for the biconnected component case but not the strongly connected component case in the same paper.

For my purpose, I rolled my own modification. In addition to the stack of nodes, I also have a stack of edges. The edges are filtered before entering the stack and are also filtered when leaving the stack to make sure they are really staying within the same strongly connected components.

This code will eventually be converted into C or C++ for efficient implementation. Therefore, my primary goal with this code review is for correctness and performance. I am less concerned with how pythonic the code is, but I wouldn't mind comments along that line.

In particular, I would like to have a confirmation on the correctness of the algorithm as well as the fact that it still runs in linear time, that is, O(|V| + |E|). The argument about the time bounds can be explained by the additional work to maintain the instack numbers takes an extra O(|V|) time, and the extra work to manage the edge stack takes an extra at most O(|E|) as an edge can enter the stack only once.

Without further ado, here is the code, thanks in advance for the reviewing.

class edge:
    def __init__(self, src, dst):
        self.src = src
        self.dst = dst

    def __repr__(self):
        return "%s --> %s" % (self.src, self.dst)

class strongly_connected_components_state:
    def __init__(self, number_of_nodes):
        self.time = 0
        # This represents the time when the node is reached
        self.start_time = [None] * number_of_nodes
        # This represents whether a node is in the stack
        # 0 implies it is never pushed on the stack
        # 1 implies it is currently on the stack
        # 2 implies it is currently being popped from the stack but we have not reported the strongly connected component yet
        # 3 implies it left the stack
        self.instack = [0] * number_of_nodes
        # This represents, among all the nodes that are not currently declared as a strongly connected component
        # The one with the smallest start time that can be reached through its subtree only.
        self.low = [None] * number_of_nodes
        self.node_stack = []
        self.edge_stack = []

def strongly_connected_components(number_of_nodes, edges):
    adjacency_list = [[] for _ in range(0, number_of_nodes)]
    for edge in edges:
        adjacency_list[edge.src].append(edge)
    states = strongly_connected_components_state(number_of_nodes)
    for node in range(0, number_of_nodes):
        if states.start_time[node] is None:
            strongly_connected_components_helper(node, adjacency_list, states)

def strongly_connected_components_helper(node, adjacency_list, states):
    states.start_time[node] = states.time
    states.time = states.time + 1
    states.low[node] = states.start_time[node]
    states.node_stack.append(node)
    states.instack[node] = 1
    for edge in adjacency_list[node]:        
        if states.start_time[edge.dst] is None:
            # All the tree edges enters the edge stack
            states.edge_stack.append(edge)
            strongly_connected_components_helper(edge.dst, adjacency_list, states)
            if states.low[edge.src] > states.low[edge.dst]:
                states.low[edge.src] = states.low[edge.dst]
        elif states.instack[edge.dst] == 1:
            # So are all the edges that may end up in the strongly connected component
            # We might encounter a back edge in this branch, and back edges always end up in a
            # strongly connected component.
            # But we might also encounter a cross edge or a forward edge in this branch, in that case
            # the edge might cross two strongly connected components, and there is no good way
            # to tell at this point.
            states.edge_stack.append(edge)
            if states.low[edge.src] > states.start_time[edge.dst]:
                states.low[edge.src] = states.start_time[edge.dst]
        else:
            # Otherwise the edge is known to point to some other strongly connected component
            # This is an edge we can safely skip from entering the edge stack
            if not states.instack[edge.dst] == 3:
                raise ValueError()
    if states.start_time[node] == states.low[node]:
        connected_component_nodes = []
        connected_component_edges = []
        while True:
            stack_node = states.node_stack.pop()
            # The node is marked as "being popped", not quite done with popping
            states.instack[stack_node] = 2
            connected_component_nodes.append(stack_node)
            if node == stack_node:
                break
        while True:
            # I claim that all edges within the strongly connected component must be currently at the 
            # top of the stack
            edge = states.edge_stack.pop()
            # I claim that states.instack[edge.src] == 2
            if not states.instack[edge.src] == 2:
                raise ValueError()
            # The edge could be forward edge or cross edge to other strongly connected component
            # Therefore we check if the destination of the edge is within the current strongly connected component
            if states.instack[edge.dst] == 2:
                connected_component_edges.append(edge)
            # The popping should stop after we have emptied the stack (in case the node is the root of the depth first search)
            # or after the tree edge to node is found. We are just leaving the depth first search for node, so it is 
            # impossible for us to have a forward edge to node, therefore the time condition confirms it is the tree edge
            if len(states.edge_stack) == 0 or (edge.dst == node and states.start_time[edge.src] < states.start_time[edge.dst]):
                break
        print("connected component nodes: %s" % connected_component_nodes)
        print("connected component edges: %s" % connected_component_edges)
        for connected_component_node in connected_component_nodes:
            states.instack[connected_component_node] = 3

def main():
    edges = [
        edge(1, 0),
        edge(2, 1),
        edge(3, 2),
        edge(2, 3),
        edge(0, 4),
        edge(4, 1),
        edge(5, 4),
        edge(6, 5),
        edge(5, 6),
        edge(6, 2),
        edge(7, 6),
        edge(7, 7),
    ]
    strongly_connected_components(8, edges)
    return 0

if __name__ == "__main__":
    main()
\$\endgroup\$
5
  • \$\begingroup\$ Your creation of class serves no real purpose here. \$\endgroup\$
    – hjpotter92
    Dec 21, 2020 at 9:26
  • \$\begingroup\$ Thanks for your attention! Now I learn about namedtuple. \$\endgroup\$
    – Andrew Au
    Dec 21, 2020 at 18:44
  • \$\begingroup\$ I have found a bug and fixed it, when I pop from the edge stack, it is possible that the edge stack is empty. That could happen if I have a graph with just a single node. \$\endgroup\$
    – Andrew Au
    Dec 21, 2020 at 20:23
  • \$\begingroup\$ The fixed version can be found here: github.com/cshung/MiscLab/blob/master/MinCostFlowPrototype/… \$\endgroup\$
    – Andrew Au
    Dec 21, 2020 at 21:20
  • \$\begingroup\$ I need to reorder the assertion that the edge popping from the stack must be coming from the current strongly connected component after determining it is not a tree edge. In hindsight, obviously, the tree edge leading to 'node' cannot come from the same connected component. \$\endgroup\$
    – Andrew Au
    Dec 22, 2020 at 20:12

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.