Is a bug about the FindFundamentalCycles?

Question

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"]

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

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

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"]

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"]

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

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

Answer 1

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"]

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.