5
$\begingroup$

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?

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – David G. Stork Jan 3 '15 at 1:03
  • $\begingroup$ Note too: FindPostmanTour[g] gives the full Eulerian cycle for your case. $\endgroup$ – David G. Stork Jan 3 '15 at 1:09
  • 2
    $\begingroup$ in documentation, FindCycle returns simple cycles, while FindHamiltonianCycle, FindEulerianCycle, and FindFundamentalCycles return specific types of cycles. $\endgroup$ – halmir Jan 4 '15 at 16:18
  • $\begingroup$ 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. $\endgroup$ – latkin Jan 4 '15 at 22:17
3
$\begingroup$

Check the background section of FindCycle documentation:

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

A simple cycle has no repeating vertices.

Improve this answer
$\endgroup$
  • $\begingroup$ This answer is not useful at all. It is not an answer, it's just copying from the documentary, while leaves the question open. It seems that neither of the proposed functions solves the question. $\endgroup$ – Mario Krenn Mar 25 '19 at 5:12
  • 1
    $\begingroup$ @NicoDean Since OP accepted at least he finds it useful. But yes, though I'm not using graphs so much, this answer would probably benefit from some further explanation. $\endgroup$ – Kuba♦ Mar 25 '19 at 7:12
  • $\begingroup$ @NicoDean It is an answer, as it explains that only simple cycles (i.e. cycles with no repeating vertices or edges) are returned. You should also read the comment thread under the main question. OP specifically asked for halmir's comment to be posted as an answer. $\endgroup$ – Szabolcs Mar 25 '19 at 7:59
6
+50
$\begingroup$

We can find cycles which have repeated vertices (but not repeated edges) by using the line graph:

lg = LineGraph[g]

enter image description here

FindCycle[LineGraph[g], Infinity, All]

enter image description here

The difficulty with multigraphs

One big remaining problem is that Mathematica's graph API does not make it possible to distinguish between parallel edges. Edges are referred to by their endpoints. There are two edges a -> b in this graph, but both are referred to as a -> b.

We can translate the vertex names of the line graph back to the edges of the original graph, but the cycle specifications will be ambiguous:

asc = AssociationThread[VertexList[lg], EdgeList[g]];
Replace[
 FindCycle[LineGraph[g], Infinity, All] /. DirectedEdge -> Rule,
 asc,
 {3}
 ]

enter image description here

As a workaround, do not attempt to refer to edges by their name (endpoints). Simply refer to them by their index, which conveniently coincides with the vertex name in the line graph.

The typical limitation from not being able to distinguish edges is that one can't use graph properties with multigraphs (PropertyValue is ambiguous about which parallel edge is being referred to).

Cycles in multigraphs are another example of how this becomes a problem. I have personally run into this problem when working with cycle bases of multigraphs.

I have reported this serious limitation to Wolfram Support on multiple occasions, but I have not heard back so far anything concrete about whether this would ever be fixed. (It was confirmed that the message was passed on to the developers.) It would clearly require very large changes to the Graph framework.

Other packages handle this issue either by identifying edges through their index (igraph does this, and also Mathematica functions like EdgeCycleMatrix effectively do this) or by adding a unique tag to each edge (networkx does this).

Improve this answer
$\endgroup$

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.