Как я могу найти круговые отношения в графе с Python и Networkx? - PullRequest
7 голосов
/ 21 февраля 2012

Считайте, что у меня есть следующий график:

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

Какой самый простой способ обнаружить, что A -> B -> C -> A является круговым отношением? Есть ли такая функция, уже встроенная в NetworkX или другая простая в использовании библиотека Python?

Ответы [ 2 ]

9 голосов
/ 21 февраля 2012

networkx.simple_cycles делает это для вас.

>>> 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']]
5 голосов
/ 21 февраля 2012

Используйте Поиск в глубину для обнаружения циклов на графике.

...