Day 95: Strongly connected components

We say that two nodes U and V in a directed graph belong to the same strongly connected component [SCC], if there exists path from U to V and path from V to U.

The algorithm that finds all SCCs is surprisingly simple and quite clever.

1. run a depth-first search [DFS] on graph G — and remember time when DFS finished searching from the node
2. create a graph G’ by reversing edge directions in G
3. run DFS on graph G’ in the order given by descending times
4. all the nodes reachable from node U in step #3 form a single SCC

What is the most interesting about this algorithm is why and how it works?

Look at picture. The graph G contains thee SCCs numbered as 1, 2, 3. When we contract every component in G into a single node, we get a new graph T that is directed and acyclic.

When DFS searches G from node U, it stops when all the nodes within U’s component were exhausted [or possibly later if it was possible to reach another SCC from U].

And if you look at the graph T, the finishing times for components will be time(1)=3, time(2)=2, time(3)=1. Then the second DFS is forced to run in the order 1, 2, 3 on a reversed graph G’/T’.

This time DFS stops exactly at the moment when all the nodes within the current strongly connected component were exhausted.

https://github.com/coells/100days

https://notebooks.azure.com/coells/libraries/100days

algorithm

def strongly_connected_components(graph):
    times, _ = depth_first_search(graph.nodes(), graph)
    _, components = depth_first_search(
        reversed(times), 
        graph.reverse()
    )
    return components

def depth_first_search(nodes, graph):
    times, components, explored = [], [], set()
    for node in nodes:
        component = []
        stack = [(False, node)]
        while stack:
            complete, i = stack.pop()
            # check if already processed
            if complete:
                times.append(i)
                continue
            elif i in explored:
                continue
            # mark the node
            component.append(i)
            explored.add(i)
            # search in depth
            stack.append((True, i))
            stack.extend((False, i) for i in graph[i])
        if component:
            components.append(component)
    return times, components

graph #1

graph = nx.DiGraph()
graph.add_nodes_from(range(6))
graph.add_edges_from([
    (0, 1), (1, 2), (2, 0), 
    (3, 4), (4, 5), (5, 3),
    (0, 5), (2, 3),
])

> strongly_connected_components(graph)
[[0, 2, 1], [5, 4, 3]]

graph #2

graph = nx.DiGraph()
graph.add_nodes_from(range(7))
graph.add_edges_from([
    (0, 1), (1, 2), (2, 0), 
    (0, 3), (3, 4), (4, 0),
    (0, 5), (5, 6), (6, 0),
])

> strongly_connected_components(graph)
[[0, 6, 5, 4, 3, 2, 1]]

graph #3

graph = nx.DiGraph()
graph.add_nodes_from(range(7))
graph.add_edges_from([
    (0, 2), (2, 4), (4, 6), (6, 0),
    (0, 1), (2, 3), (4, 5), (6, 7),
])

> strongly_connected_components(graph)
[[0, 6, 4, 2], [7], [5], [3], [1]]