6
$\begingroup$

My graph is

g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 4 <-> 5, 5 <-> 6, 6 <-> 7, 
   7 <-> 0, 0 <-> 1, 6 <-> 8, 8 <-> 3, 3 <-> 9, 9 <-> 15, 15 <-> 14, 
   14 <-> 13, 13 <-> 2, 4 <-> 12, 12 <-> 11, 11 <-> 10, 10 <-> 9}, 
  VertexLabels -> "Name"]

enter image description here

HighlightGraph[g, #, GraphHighlightStyle -> "Thick"] & /@ 
 FindFundamentalCycles[g]

enter image description here

But actually this four cycle is expected.How can I get it?

enter image description here

This a bug of FindFundamentalCycles or I have a bad comprehension about it?


Updat1:

I find a post same to me topic.But this solution will give a unexpected result.


Update2: I realize this is a unanswerable.Let's see a example:

We get g1:

g1 = PlanarGraph[{2, 1, 3, 5, 4}, {1 <-> 2, 2 <-> 5, 5 <-> 4, 4 <-> 1,
    1 <-> 3, 3 <-> 5}, 
  VertexCoordinates -> {{0, 0}, {1, 0}, {1, 1}, {1, 2}, {2, 0}}, 
  VertexLabels -> "Name"]

![enter image description here

So as this topic.The cycle 1-2-5-3-1 and 1-4-5-3-1 is expected.And let change a layout:

g2 = PlanarGraph[{4, 1, 2, 5, 3}, {1 <-> 2, 2 <-> 5, 5 <-> 4, 4 <-> 1,
    1 <-> 3, 3 <-> 5}, 
  VertexCoordinates -> {{0, 0}, {1, 0}, {1, 1}, {1, 2}, {2, 0}}, 
  VertexLabels -> "Name"]

![enter image description here

In this layout,the cycle 1-2-5-4-1 and 1-3-5-2-1 is expected.Note the cylce 1-4-5-3-1 in this graph,is a Unexpected in this layout.But I just change the layout..

Since so,let we try to understand what is a fundamental cycles(cycle basis).The @Martin Büttner have a mention about this.Yeah.I think so now.This is a manual operation for the fundamental cycles by the FindSpanningTree.

tree = FindSpanningTree[g];
edge = EdgeList@GraphDifference[g, tree];
HighlightGraph[g, FindCycle[EdgeAdd[tree, #]], 
   GraphHighlightStyle -> "Thick"] & /@ edge

enter image description here

We can see,this result is same to we use FindFundamentalCycles[] and this rule apply to other graph.

$\endgroup$
8
$\begingroup$

I believe what you're seeing is a valid solution. Fundamental cycles are defined with respect to a spanning tree. In fact, the documentation says about FindFundamentalCycles:

FindFundamentalCycles uses the result of FindSpanningTree as the default spanning tree.

A fundamental cycle is then defined as a cycle that uses one edge not in the tree and the corresponding unique path through the tree. Let's look at the spanning tree:

HighlightGraph[g, FindSpanningTree@g, GraphHighlightStyle -> "Thick"]

enter image description here

We can see that your output is consistent with this spanning tree. The fundamental cycles correspond to the missing edges, {10, 11}, {14, 15}, {6, 8} and {5, 6}, respectively.

You can also convince yourself that these fundamental cycles do indeed form a valid cycle basis: by taking the symmetric difference between cycles 3 and 4, you'll obtain the cycle you're looking for.

Of course this means that the set of fundamental cycles is not unique. Start from a different spanning tree, and you'll get different cycles. I suppose what you're looking for is a set of fundamental cycles with minimal overall length (or weight). Unfortunately, it doesn't appear that FindFundamentalCycles comes with any options to look for such a solution specifically (or to use a different spanning tree as the basis). If I find some time later, I'll try to code up a solution for this, but at least I hope I've convinced you that this behaviour is not a bug.

In the meantime have a look at Wikipedia which describes a polynomial-time algorithm to find a minimal cycle basis. However, it seems that this isn't necessarily a fundamental cycle basis. According to the subsequent section finding a minimum-weight fundamental cycle basis is actually NP-hard. I guess which route you're taking here depends on what your actual goal is.

$\endgroup$
  • $\begingroup$ Perhaps one could write a custom function that takes the graph and the spanning tree and gives the corresponding fundamental cycles (doesn't seem too messy). Then the options of FindSpanningTree could be used to tweak the results. $\endgroup$ – Kellen Myers Mar 18 '16 at 20:58
  • $\begingroup$ I have updated it and thanks for your help. $\endgroup$ – yode Mar 19 '16 at 3:40
  • $\begingroup$ @KellenMyers I have done what you mean. $\endgroup$ – yode Mar 19 '16 at 3:42

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.