Wie kann ich mit Python und Networkx kreisförmige Beziehungen in einem Diagramm finden?

Question

Angenommen, ich habe das folgende Diagramm:

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

Was ist der einfachste Weg, um festzustellen, dass A -> B -> C -> A eine Kreisbeziehung ist?Gibt es eine solche Funktion, die bereits in NetworkX oder einer anderen einfach zu verwendenden Python-Bibliothek integriert ist?

Answer 1

networkx.simple_cycles erledigt dies für Sie.

>>> 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')
>>> nx.simple_cycles(G)
[['A', 'B', 'C', 'A']]

Answer 2

Verwenden Sie Tiefensuche , um Zyklen in einem Diagramm zu erkennen.