5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Problem exist in ver 10.4 and ver 11.0 $\endgroup$ – Wjx Aug 21 '16 at 15:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Quantum_Oli Aug 21 '16 at 16:34
5
$\begingroup$

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}} *)
|improve this answer|||||
$\endgroup$
  • $\begingroup$ You perfectly solved the problem I have and extended it! $\endgroup$ – Wjx Aug 21 '16 at 23:18
  • $\begingroup$ 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? $\endgroup$ – yode Aug 22 '16 at 1:18
  • $\begingroup$ Funny. :) I cannot remove that edges weight .WeightedGraphQ[Fold[RemoveProperty[{#1,#2},EdgeWeight]&,g,EdgeList[g]]] $\endgroup$ – yode Aug 22 '16 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.