Обнаружение циклов в взвешенном ориентированном графе с Python - PullRequest
Новая
       1

Обнаружение циклов в взвешенном ориентированном графе с Python

0 голосов
/ 11 апреля 2020

Я довольно новичок в Python (это мой первый код), и мне интересно, как я могу найти все циклы в ориентированном графе ВЕСА.

Я видел Как обнаружить цикл в ориентированном графе с Python? (для графов без весов), но я не понял, почему между 'C' и 'D' дважды упоминается грань и почему существует g.addEdge ( 'A', 'B') (это ребро упоминалось выше).

Я пытался писать код без весов самостоятельно (у меня есть ребра между «1» и «2», с весом 2 «1» и «3», с весом 7 «2» и «3», с весом -2 «2» и «4», с весом -4 «3» и «1», с весом 7 «3» и «4», с весом 3 «4» и «3», с весом 3) но я не понимаю, почему все мои циклы начинаются с вершины "3" и как писать код с весами.

Мой код для ориентированного графа без весов: 


edges = [('1', '2'),('1', '3'),('2', '3'),('2', '4'),('3', '1'),('3', '4'),('4', '3')]

G = nx.DiGraph(edges)

for cycle in nx.simple_cycles(G):
    print(cycle)

и вывод: 

['3', '4']
['3', '1']
['3', '1', '2', '4']
['3', '1', '2']

И я хочу что-то вроде этого: 

['3', '4'] weight 6
['3', '1'] weight 11
['3', '1', '2', '4'] weight 5
['3', '1', '2'] weight 4

Большое спасибо!

...