Jak znaleźć relacje kołowe na wykresie z Python i Networkx?

Question

Rozważmy Mam następujący wykres:

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

Co jest najprostszym sposobem, aby stwierdzić, że -> B -> C -> A jest okrągły relacja? Czy istnieje taka funkcja wbudowana w NetworkX lub inną łatwą w użyciu bibliotekę Python?

Answer 1

networkx.simple_cycles robi to za Ciebie.

>>> 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

Użyj Depth-First Search do wykrywania cykli na wykresie.