Làm cách nào để tìm các mối quan hệ tròn trong biểu đồ bằng Python và Networkx?

Question

Cân nhắc tôi có đồ thị sau:

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

cách dễ nhất để thấy rằng A là gì -> B -> C -> A được một mối quan hệ hình tròn? Có một hàm như vậy đã được tích hợp sẵn trong NetworkX hay một thư viện Python dễ sử dụng khác không?

Answer 1

networkx.simple_cycles thực hiện điều này cho bạn.

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

Sử dụng Depth-First Search để phát hiện các chu kỳ trong biểu đồ.