Problem with EdgeWeight and FindCycle?

Question

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?

Answer 1

Short answer. Not a bug.

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}} *)