Script that finds strongly connected components in a directed graph and visualizes them

graph.txt

0 0 0 0 0 0 0 0 0 0 0 0 A
1 0 0 0 1 0 0 0 0 0 0 0 B
0 1 0 1 1 0 0 0 0 0 0 0 C
1 0 0 0 0 0 0 1 0 0 0 0 D
0 0 1 0 0 0 0 0 0 0 0 0 E
0 0 0 1 0 0 1 0 0 0 0 0 F
0 0 0 0 0 1 0 0 0 0 0 0 G
0 0 0 1 0 0 0 0 0 0 0 0 H
0 0 0 0 0 0 0 0 0 0 0 0 I
0 0 0 0 0 0 0 0 0 0 0 0 J
0 0 0 0 0 0 0 0 0 0 0 0 K
0 0 0 0 0 0 0 0 0 0 0 0 L
A B C D E F G H I J K L

LinkComp.py

# LinkComp - script that finds strongly connected components in a directed graph and visualizes them
# Requires `graph.txt` - adjacency matrix that defines the graph
import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
import re

g = []
ptn = re.compile('[01]')
with open('graph.txt') as f:
    for line in f:
        row = re.findall(ptn, line)
        if row:
            g.append(list(map(int, row)))

g = np.matrix(g)
copy = g.copy()

labels = {i: chr(ord('A') + i) for i in range(len(g))}

def colorer(num):
    amt = 1 / num
    start = 0
    cmap = plt.cm.Paired
    while True:
        yield cmap(start)
        start += amt

def clock():
    cnt = 0
    while True:
        cnt += 1
        yield cnt

prev = [0] * len(g)
post = [0] * len(g)
used = {0}
order = []

gl_clock = clock()

def dfs_time(g, v):
    prev[v] = next(gl_clock)
    for i in range(len(g)):
        if g[v, i] == 1 and i not in used:
            used.add(i)
            dfs_time(g, i)
    post[v] = next(gl_clock)
    order.append(v)

not_ex = set()

def dfs_coll(g, v, used):
    used.add(v)
    for i in range(len(g)):
        if g[v, i] == 1 and i not in used:
            used, g = dfs_coll(g, i, used)
    g[:, v] = 0
    not_ex.add(v)
    return used, g

verts = set(range(len(g)))
rg = g.transpose()

dfs_time(rg, 0)
verts -= used
while verts:
    vert = verts.pop()
    used.add(vert)
    dfs_time(rg, vert)
    verts -= used

comps = []
for i in order:
    if i in not_ex:
        continue
    comp, rg = dfs_coll(rg, i, {i})
    comps.append(comp)

G = nx.from_numpy_matrix(copy, create_using = nx.DiGraph())
pos = nx.spring_layout(G)

color = colorer(len(comps))
for comp in comps:
    nodes = nx.draw_networkx_nodes(G, pos,
                                   nodelist = list(comp),
                                   node_color = next(color))
    nodes.set_edgecolor('black')

nx.draw_networkx_labels(G, pos, labels, font_size = 10)
nx.draw_networkx_edges(G, pos, arrows=True)

plt.axis('off')
fig = plt.gcf()
fig.canvas.set_window_title('Strongly linked components')
plt.show()