Using Tarjan's Algorithm

Strongly Connected Components with Tarjan's Algorithm

When we deal with Directed Graphs we will sometimes find a Strongly Conected Graph. Such graph has a path between every pair of nodes (vertexes) in the graph going on both directions.

When we refer to Strongly Connected Components in a graph, we speak about a group of nodes in the graph that satisfies this condition.

Wikipedia is a good place to find more about it.

In order to get the Strongly Conected Components I will use a Python implementation of Tarjan's Algorithm. The implementation is practically a straightforward translation of the pseudocode shown on the page.

In [1]: 
graph = {
    0:set([1]),
    1:set([3]),
    2:set([1, 4]),
    3:set([0]),
    4:set([2, 5]),
    5:set([])
}
In [2]: 
# Using networkx I will draw a simple graph for demonstration purposes.
# Note: I am starting with networkx, sure there are better ways to create a Directed Graph. This is one.
import matplotlib.pyplot as plt
import networkx as nx
import numpy as np

np.random.seed(0)

G=nx.DiGraph()
for node, edges in graph.items():
    for edge in edges:
        G.add_edge(node, edge)

pos=nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos)
nx.draw_networkx_edges(G, pos, arrows = True)
nx.draw_networkx_labels(G, pos)

plt.axis('off')
plt.show()

The wider end on the adges represent an arrow, indicatin the direction of the relation.

In [3]: 
def tarjan(graph):
    #input: graph G = (V, E)
    #output: Array of strongly connected components (sets of vertices)
    n = len(graph)
    sccs = []
    index = [0]
    indexes = [-1] * n
    lows = [float('Inf')] * n
    S = []

    def strongconnect(v):
        # Set the depth index for v to the smallest unused index
        indexes[v] = index[0]
        lows[v] = index[0]
        index[0] += 1
        S.append(v)

        # Consider successors of v
        for chld in graph[v]:
            if indexes[chld] == -1:
                # Successor chld has not yet been visited; recurse on it
                strongconnect(chld)
                lows[v] = min(lows[v], lows[chld])
            elif chld in S:
                # Successor w is in stack S and hence in the current SCC
                lows[v] = min(lows[v], lows[chld])

        # If v is a root node, pop the stack and generate an SCC
        if lows[v] == indexes[v]:
            scc = set([v])
            w = S.pop()
            while w != v:
                scc.add(w)
                w = S.pop()
            sccs.append(scc)

    for v in graph.keys():
        if indexes[v] == -1:
            strongconnect(v)

    return sccs
In [4]: 
scc = tarjan(graph)
scc
Out[4]:
[{0, 1, 3}, {5}, {2, 4}]
In [5]: 
colors = ['r', 'g', 'b']
for component, color in zip(scc, colors):
    nx.draw_networkx_nodes(G, pos, nodelist = component, node_color = color)
nx.draw_networkx_edges(G, pos, arrows = True)
nx.draw_networkx_labels(G, pos)
plt.axis('off')
plt.show()

This algorithm besides being good for a problem that required just an implementation was very useful in the case where I needed to 'reduce' a graph into a simpler representation (without cycles and extra edges).

Any comments? Let me know on @sergiobuj

social