Whilst investigating a networked cellular automata I thought it would be useful to know what all the loops of connected cells in the network, (or "graph"),were.

A little googling and I found mention of Johnsons algorithm as being the most efficient and decided to implement it. I searched and found that the most readable description was in Johnsons original paper.

### Strongly Connected Components

You first need to split any graph into Strongly Connected Components, (sub-graphs where all nodes are interconnected), then run the algorithm on each SCC in turn. I had already written a Python example on Rosetta Code that used tarjans algorithm to split a graph into SCC's and incorporated that in the code below.

### Johnson's pseudocode

This is on page 3 of his paper and because it was written in the seventies, it is a little dated in its use of labels and in how it scopes variables. My initial translation stuck to the nested gunctions syntax, and used more nonlocal statements for name access.

### Testing

In my searches I found a Wolfram Demonstration web page that uses the algorithm to show the cycles found in graphs where the graph generated can be controlled by sliders. I scraped a few graph examples from the page with their results and wrote a short, external script that turned the text cut-n-pasted from that page into Python representations of the adjacency matrix and resultant cycles. I also generated an adjacency list from the adjacency matrix .

Given an adjacency matrix list-of-lists of either zero or one then trhe following code created the adjacency list:

adj_lst = [[i for i, cell in enumerate(row) if cell] for row in adj_mat]

The examples with the web-scraped cycles is imported in then the following code generates the graph cycles and compares the result with that scraped from the Wolfram site.

### Visualisation

Nothing like diagrams to show the interconnection of nodes with directed edges, so I use graphviz run under the Spyder IDE for output.

For each example the following is shown in the output:

- A list of lists where each sublist shows node numbers that traverse a cycle in the graph. (It is
*assumed*that the last node is connected to the first of its cycle). - A graphviz plot of the full graph. (Nodes are constrained to be positioned in numerical order on one line).

## The Code

# -*- coding: utf-8 -*- """ Created on Sat Nov 14 14:00:33 2020 @author: Paddy3118 """ from collections import defaultdict from pprint import pprint as pp from graphviz import Digraph as GV # conda install python-graphviz class Graph_scc: "Directed Graph_scc Tarjan's strongly connected components algorithm" def __init__(self, name, adj_lst): self.name = name self.adj_lst = adj_lst # map node vertex to direct connections self.graph = {n:c for n, c in enumerate(adj_lst)} self.tarjan_algo() self.scc = sorted(sorted(s) for s in self.scc) def _visitor(self, this, low, disc, stack): ''' Recursive function that finds SCC's using DFS traversal of vertices. Arguments: this --> Vertex to be visited in this call. disc{} --> Discovery order of visited vertices. low{} --> Connected vertex of earliest discovery order stack --> Ancestor node stack during DFS. ''' disc[this] = low[this] = self._order self._order += 1 stack.append(this) for neighbr in self.graph[this]: if neighbr not in disc: # neighbour not visited so do DFS recurrence. self._visitor(neighbr, low, disc, stack) low[this] = min(low[this], low[neighbr]) # Prior connection? elif neighbr in stack: # Update low value of this only if neighbr in stack low[this] = min(low[this], disc[neighbr]) if low[this] == disc[this]: # Head node found of SCC top, new = None, [] while top != this: top = stack.pop() new.append(top) self.scc.append(new) def tarjan_algo(self): ''' Recursive function that finds strongly connected components using the Tarjan Algorithm and function _visitor() to visit nodes. ''' self._order = 0 # Visitation order counter disc, low = {}, {} stack = [] self.scc = [] # SCC result accumulator for vertex in sorted(self.graph): if vertex not in disc: self._visitor(vertex, low, disc, stack) self._disc, self._low = disc, low def simple_cycles(gr, _print=False): def circuit(v): "https://www.cs.tufts.edu/comp/150GA/homeworks/hw1/Johnson%2075.PDF" nonlocal all_found, A, a_len, B, blocked, stack, s def unblock(u, B, blocked): #nonlocal B, blocked blocked[u] = False for w in B[u].copy(): B[u].discard(w) if blocked[w]: unblock(w, B, blocked) f = False # Found stack.append(v) blocked[v] = True #%% L1 for w in A[v]: if w == s: found = stack # + [s] if min(found) == found[0]: # remove rotations all_found.append(found[::]) if _print: print(f"found {found}") f = True elif not blocked[w]: if circuit(w): f = True #%% L2 if f: unblock(v, B, blocked) else: for w in A[v]: B[w].add(v) stack.remove(v) return f # end def circuit ... all_found = [] A = gr.adj_lst.copy() # adjacency list a_len = len(A) stack = [] for scc in gr.scc: for s in scc: # Start vertex (lowest numbered) blocked = [False for _ in range(a_len)] B = defaultdict(set) # Block map circuit(s) return all_found #%% Graph with cycles class Graph(): def __init__(self, name, adj_lst): self.name = name self.adj_lst = adj_lst gr = Graph_scc(name, adj_lst) self.scc = gr.scc # strongly connected components self.cycles = simple_cycles(gr) def _XXto_gv(self): """ Output via Graphviz displayable in Spyder and Jupyter IDE's. Ref: https://graphviz.readthedocs.io/en/stable/manual.html """ g = GV(self.name, filename='_tarjan.gv') g.body.extend(["layout=circo"]) g.graph_attr['label'] = self.name # Colour strongly connected components groupcount = len(self.scc) for i, gnodes in enumerate(self.scc, 1): for gn in gnodes: g.node(f"N{gn}", color=f"{i/groupcount} 1 1") # #g.graph_attr['splines'] = 'ortho' #g.graph_attr['nodesep'] = '0.8' g.node_attr['shape'] = 'circle' for n, conns in enumerate(self.adj_lst): for c in conns: g.edge(f"N{n}", f"N{c}") #else: # g.node(f"N{n}") return g def _to_gv(self): """ Output via Graphviz displayable in Spyder and Jupyter IDE's. Ref: https://graphviz.readthedocs.io/en/stable/manual.html """ g = GV(self.name, filename='_tarjan.gv') g.graph_attr['label'] = self.name #g.graph_attr['rankdir'] = 'LR' g.graph_attr['ranksep'] = '1.5' g.graph_attr['splines'] = 'ortho' # All nodes in one line using fake edges. g.node_attr['shape'] = 'circle' node_count = len(self.adj_lst) for i in range(node_count - 1): g.edge(f"N{i}", f"N{i + 1}", style='invis') # g.edge_attr['stye'] = 'solid' g.edge_attr['constraint'] = 'false' # Colour strongly connected components groupcount = len(self.scc) for i, gnodes in enumerate(self.scc, 1): for gn in gnodes: g.node(f"N{gn}", color=f"{i/groupcount} 1 1", shape='circle', width='0.3', height='0', fontsize='10', margin='0.02') # #g.graph_attr['nodesep'] = '0.8' #g.node_attr['shape'] = 'circle' for n, conns in enumerate(self.adj_lst): for c in conns: g.edge(f"N{n}", f"N{c}", style="solid", constraint="false") #else: # g.node(f"N{n}") return g if 0: # __name__ == '__main__': adj_lst = [ [2, 3], [2, 3], [0, 1], [1], ] adj_lst = [ [], [0, 5], [1, 7], [], [], [7], [], [2, 4], ] gr = Graph_scc('Ex', adj_lst) pp(gr.adj_lst) cycles = simple_cycles(gr) print(cycles) if __name__ == '__main__': # Examples scraped from https://demonstrations.wolfram.com/EnumeratingCyclesOfADirectedGraph/ from graph_cycles_test_gen import example for n, ex in enumerate(example): nodes, cycles, adj_mat, adj_lst = ex gr = Graph(f"Ex{n}", adj_lst) print(gr.name, gr.cycles) assert gr.cycles == cycles display(gr._to_gv()) print('\n')

### The Output

Ex0 [[0, 3, 2], [2, 4, 3]]

Ex1 [[0, 2], [0, 3, 1, 2], [1, 2], [1, 3]]

Ex2 [[0, 5, 2], [0, 5, 4, 2]]

Ex3 [[0, 1, 6], [0, 1, 6, 5], [0, 1, 6, 5, 2], [0, 1, 6, 5, 4, 2], [0, 5], [0, 5, 2], [0, 5, 2, 6], [0, 5, 4, 1, 6], [0, 5, 4, 2], [0, 5, 4, 2, 6], [1, 6, 5, 4], [2, 6, 5], [2, 6, 5, 4]]

Ex4 [[1, 5, 7, 2], [2, 7]]

**END.**

## No comments:

## Post a Comment