## 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.

```
graph = {
0:set([1]),
1:set([3]),
2:set([1, 4]),
3:set([0]),
4:set([2, 5]),
5:set([])
}
```

```
# 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.

```
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
```

```
scc = tarjan(graph)
scc
```

```
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