Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Say I have a simple multigraph like so:

edges = {DirectedEdge[a, b], DirectedEdge[b, c], DirectedEdge[c, a]};
g = Graph[Join[edges, edges]]

enter image description here

FindCycle has no trouble discovering a length-3 cycle, however it unexpectedly fails to find the length-6 cycle that takes "two laps" around the vertices.

FindCycle[g, {3}]
FindCycle[g, {6}]

(* output:
  {{a \[DirectedEdge] b, b \[DirectedEdge] c, c \[DirectedEdge] a}}
  {}
*)

I initially just assumed Mathematica did not have the capability to fully support multigraphs like this, but FindEulerianCycle happily identifies the length-6 cycle as expected:

FindEulerianCycle[g]

(* output:
  {{a \[DirectedEdge] b, b \[DirectedEdge] c, c \[DirectedEdge] a, 
    a \[DirectedEdge] b, b \[DirectedEdge] c, c \[DirectedEdge] a}}
*)

It seems bizarre that FindEulerianCycle[g] can find a length-n cycle yet FindCycle[g, {n}] returns nothing.

So my questions are: Is there a good way (using FindCycle or otherwise) to properly handle "multi-cycles" (which are not Eulerian in general)? Is the observed behavior a bug or is there something convincing in the documentation that indicates it's by design?

share|improve this question
    
I presume Mathematica searches for "simple cycles," i.e., no repetitions of vertexes, even though the EulerianCycle is somehow found. An Eulerian cycle in a directed graph can of course pass through the same vertex more than once. –  David G. Stork Jan 3 at 1:03
    
Note too: FindPostmanTour[g] gives the full Eulerian cycle for your case. –  David G. Stork Jan 3 at 1:09
1  
in documentation, FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles. –  halmir Jan 4 at 16:18
    
Ah, indeed, there it is buried at the end of the "Background" section. Nice find, @halmir. If you want to submit that as an answer I'll accept it. –  latkin Jan 4 at 22:17

1 Answer 1

up vote 1 down vote accepted

Check the background section of FindCycle documentation:

FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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