0

I am pretty new in Python (it is my first code) and I am wondering how can I find all cycles in a WEIGHTED directed graph.

I saw How to detect a cycle in a directed graph with Python? (for graphs without weights), but I did not understand, why there is an edge between 'C' and 'D' mentioned twice and why there is g.addEdge('A', 'B') (this edge is mentioned above).

I tried to write code without weights on my own (I have edges between
'1' and '2', with weight 2
'1'and '3', with weight 7
'2' and '3', with weight -2
'2' and '4', with weight -4
'3'and '1', with weight 7
'3'and '4', with weight 3
'4' and '3', with weight 3)
but I do not understand, why all my cycles starts with vertex "3" and how to write a code with weights.

My code for directed graph without weights is: 


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)

and output is: 

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

And I want something like this: 

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

Thanks a lot!

I love math
  • 1
  • 1
  • The weights do not matter for finding cycles. – Dani Mesejo Apr 11 '20 at 09:10
  • All the cycles on your graph *include* vertex 3, nothing strange about that. If you understand the definition of cycle you can quickly verify it on a drawing. A cycle doesn't *start* on a given vertex, it is a sequence of vertices. – al-dev Apr 11 '20 at 09:19
  • @DaniMesejo yes, I know. But I want to find cycles with their costs. I need to proof that in my graph, there are no negative cycles (I need to show it for all possible cycles in graph). I found code which writes if there is or there is not a negative cycle, but it does not write, how many negative cycles there is and their cost. – I love math Apr 11 '20 at 09:19
  • So you already have a code that finds all cycles, right? – Dani Mesejo Apr 11 '20 at 09:21
  • @al-dev is it possible to explain, why python chose 3 and it did not start with 1 (and write all cycles containing 1), then 2 (and write all cycles containing 2) etc.? – I love math Apr 11 '20 at 09:22
  • @DaniMesejo I think I have. :) I wrote it above and it found all cycles so I assume that it works right. :) I want to know, how to find cycles WITH WEIGHTS. :) – I love math Apr 11 '20 at 09:24
  • So once you have all cycles compute the cost for each of those. Note that your question as it stands is very confusing, please add input and expected output (a small graph and the output you want from it, together with what you have done) – Dani Mesejo Apr 11 '20 at 09:26
  • Your program outputs `['1', '2', '4', '3'] ['1', '2', '3'] ['1', '3'] ['3', '4']` for me, so I don't really understand your statement 'Python chose 3'. If you get a different output and wonder why you should look at the implementation of `simple_cycles` in the networkx library. I have v2.2. But I don't think that's really relevant to your problem. [1,2,3] is the same cycle as [2,3,1]. Does that make sense? You can rotate them however you like. – al-dev Apr 11 '20 at 09:29
  • @DaniMesejo I edited my question. I appologize for confusing. – I love math Apr 11 '20 at 09:38
  • @al-dev I just wondered why it choose 3 (in my case) - it is my first code in python and I tried to understand how it works. :) But it is not relevant to my problem - you are right. – I love math Apr 11 '20 at 09:40
  • No problem! Good luck. – al-dev Apr 11 '20 at 10:40

0 Answers0