CODEWITHSUNDEEP
pythonmathgraphcounting
Tweej
Tweej

Reputation: 153

Finding all closed loops in a graph

I am trying to write a Python code which will identify all of the closed loops within an arbitrary graph.

By a closed loop, I mean a loop which visits no vertex more than once, with the exception of the vertex the loop starts on (in the case of this picture, DGHD is an example, as is BCDB, or BCEFDB, or etc).

I tried doing this with matrix multiplication, writing the graph as a matrix with 1s where 2 verticies are connected, and a 0 where they aren't, and putting them to the nth power, however this will take into account non closed loops also.

This person seems to have had the same job, but managed to solve it:

I was wondering if there was any advice on which direction to take?

Upvotes: 4

Views: 5548

Answers (1)

Chris Swierczewski
Chris Swierczewski

Reputation: 759

NetworkX is a popular Python package for working with graphs included in many scientific Python distributions. It includes some algorithms for computing graph cycles. In particular, simple_cycles(DiGraph) would answer your question.

One caveat to this approach is that you have to convert your graph into a digraph. This means that every edge of your undirected graph will become a cycle in your directed version. (An undirected edge becomes two directed edges.) You can simply filter the output to only contain cycles of length three or greater.

Here's an example using the graph you linked to:

from networkx import Graph, DiGraph, simple_cycles

# construct a graph using a dict: {node:[connected_nodes]}
G = Graph(
    {'A':['B','G','H'],
     'B':['A','C','D'],
     'C':['B','D','E'],
     'D':['B','C','E','F','G', 'H'],
     'E':['C','D','F'],
     'F':['D','E','G'],
     'G':['A','D','F','H'],
     'H':['A','D','G'],
    }
)

# optional: draw the graph for verification
#labels = dict(zip(G.nodes(),G.nodes()))
#networkx.draw_networkx(G,labels=labels)

# simple_cycles only accepts DiGraphs. convert G to a bi-directional
# digraph. note that every edge of G will be included in this list!
DG = DiGraph(G)
list(simple_cycles(DG))

The (truncated) output is:

[['B', 'D', 'H', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'G', 'A'],
 ['B', 'D', 'H', 'A', 'G', 'F', 'E', 'C'],
 ['B', 'D', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'H', 'A'],
 ['B', 'D', 'F', 'G', 'A'],
 ['B', 'D', 'F', 'E', 'C'],
 ['B', 'D', 'G', 'F', 'E', 'C'],
 ...
]

If you'd prefer to implement this yourself without using NetworkX simple_cycles() uses Johnson's algorithm. (See Donald B. Johnson, Finding All the Elementary Circuits of a Directed Graph, SIAM J. Comput., 4(1), 77–84)

Upvotes: 6

Related Questions