# Problem with EdgeWeight and FindCycle?

I'm still trying to program something to illustrate the resistence network simplifying process when encountering this:

Graph[{1 <-> 2, 2 <-> 3, 3 <-> 1, 1 <-> 4, 2 <-> 6},
EdgeWeight -> {1, 2, 3, 4, 5}] // (FindCycle[#, {3}] &)


{}

Delete EdgeWeight then everything will be fine. Is this a bug?

• Problem exist in ver 10.4 and ver 11.0 – Wjx Aug 21 '16 at 15:38
• It's not a bug. There is just no cycle with a total weight of 3 in the graph you have given. Try instead FindCycle[#, {6}] and it will return the cycle 1-2-3-1. – Quantum_Oli Aug 21 '16 at 16:34

Detailed answer. From the reference page of FindCycle, section "Details":

For weighted graphs, FindCycle[g, k] gives all cycles with total weights less than k.

The behavior of FindCycle[g, {k}] for weighted graphs, which is OP's situation, does not appear to be explicitly mentioned in the documentation. However, the corresponding usage line,

FindCycle[g, {k}] finds a cycle of length exactly k.

gives a hint: for a weighted graph, this syntax will give us all cycles with total weights exactly k.

This is what happens:

edges = {1 <-> 2, 2 <-> 3, 3 <-> 1, 1 <-> 4, 2 <-> 6};

edgesweight = {1, 2, 3, 4, 5};
FindCycle[Graph[edges, EdgeWeight -> edgesweight], {3}]
(* {} *)

FindCycle[Graph[edges, EdgeWeight -> edgesweight], {6}]
(* {{1 <-> 2, 2 <-> 3, 3 <-> 1}} *)

edgesweight = {1, 1, 1, 4, 5};
FindCycle[Graph[edges, EdgeWeight -> edgesweight], {6}]
(* {} *)

FindCycle[Graph[edges, EdgeWeight -> edgesweight], {3}]
(* {{1 <-> 2, 2 <-> 3, 3 <-> 1}} *)


Additional remark. The confusion may come from the meaning of "length" in the usage lines. It does not mean the number of edges, but rather the total weights of the cycle.

The second example above shows that the number of edges of the cycle can be less than its length. We have respectively 3 and 6.

Conversely, in the following,

edgesweight = {0, 0, 1, 4, 5};
FindCycle[Graph[edges, EdgeWeight -> edgesweight], {1}]
(* {{1 <-> 2, 2 <-> 3, 3 <-> 1}} *)


the number of edges of the cycle is greater than its length, we have respectively 3 and 1.

Note that the length of the cycle can also be negative:

edgesweight = {-1, -1, 1, 4, 5};
FindCycle[Graph[edges, EdgeWeight -> edgesweight], {-1}]
(* {{1 <-> 2, 2 <-> 3, 3 <-> 1}} *)

• You perfectly solved the problem I have and extended it! – Wjx Aug 21 '16 at 23:18
• I have to say it look so counter-intuitive.I mean if we don't know the total weights,then we cannot get that cycle? – yode Aug 22 '16 at 1:18
• Funny. :) I cannot remove that edges weight .WeightedGraphQ[Fold[RemoveProperty[{#1,#2},EdgeWeight]&,g,EdgeList[g]]] – yode Aug 22 '16 at 1:28