pythonalgorithmgraph-theorynetworkx

How can I find circular relations in a graph with Python and Networkx?

Consider I have the following graph:

A -> B
B -> C
C -> D
C -> A

What is the easiest way to find that A -> B -> C -> A is a circular relation? Is there such a function already built into NetworkX or another easy to use Python library?

Solution

  • networkx.simple_cycles does this for you.

    >>> import networkx as nx
>>> G = nx.DiGraph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> G.add_edge('C', 'D')
>>> G.add_edge('C', 'A')
>>> print(list(nx.simple_cycles(G)))
[['B', 'C', 'A']]