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