Search code examples
pythonloopsnetworkx

Python Networkx detecting loops/circles

Given the following example:

Is there a possibilty to detect a loop in the network (I1, I2,I3, C6, C7, I5)?

I tried: simple_cycles → it works fine with 3 nodes, but not with more than 3.

I would need to detect the circle with all nodes and the "input" node ("I1") and the "output" ("I3").

Solution

  • I recreated your graph as such:

    import networkx as nx

g = nx.DiGraph([('P', 'I0'), ('I0', 'I1'), ('I1', 'I2'),
                ('I2', 'I3'), ('I1', 'I5'), ('I5', 'C7'),
                ('C7', 'C6'), ('C6', 'I3'), ('I3', 'C9')])

    You were searching for simple cycles but there is none in the above graph:

    >>> list(nx.simple_cycles(g))
[]

    so you have to search for cycles in the undirected graph. You have to cast your graph to an undirected graph. For undirected graphs, the cycle_basis function is what you seem to need:

    >>> nx.cycle_basis(g.to_undirected())
[['I5', 'C7', 'C6', 'I3', 'I2', 'I1']]