Cyclebasis function for graphs not working

I have the following graph, with the corresponding cycle generation using cycle basis:

Matlab generates makes a mistake with the third cycle giving:

2 9 5 13 11 12 when it should be 2 9 5 13 12.

s = [  1     4     6     3    10     2     9     5     8     7     1    11    12     3    12    13     4    11    13];
t = [ 4     6     3    10     2     9     5     8     7     1    11    12     2    12    13     8    11    13     5];

G = graph(s,t);
plot(G)

[cycles,edgecycles] = cyclebasis(G);
cycles

cycles = 7x1 cell array
    {[        1 4 11]}
    {[   1 7 8 13 11]}
    {[2 9 5 13 11 12]}
    {[     2 10 3 12]}
    {[   3 6 4 11 12]}
    {[        5 8 13]}
    {[      11 12 13]}

Answer 1

[Christine Tobler]

Yes, cyclebasis returns a fundamental cycle basis, but not necessarily the one with the shortest cycle lengths. See the documentation's "more about" section: "However, cyclebasis is not guaranteed to return the shortest possible fundamental cycle basis."

[Allan]

I'm confused because the same section also states that an edge cannot be transversed twice.

In this problem we get the edge 11-12 transversed twice, for the third cycle and last cycle.

[Christine Tobler]

I'm assuming you mean this statement from the doc:

"For each edge that is not in the minimum spanning tree, there exists one fundamental cycle which is composed of that edge, its end nodes, and the path in the minimum spanning tree that connects them."

It's separating the edges into two types, those that are in the chosen minimum spanning tree, and those that are not. Only the ones that are not in that tree appear in only one of the cycles.

Here's an example:

G = graph([1:4], [2:4 1]);
G = addedge(G, [4:6], [5:6 3]);

p = plot(G);

cyclebasis(G)

ans = 2x1 cell array
    {[1 2 3 4]}
    {[3 4 5 6]}

Here the edge (3, 4) is a part of two cycles - but this is all right. In fact, I don't think it's possible to find two cycles here without any overlapping edges.

So what is this minimum spanning tree? A tree that would lead to the cycles above is the following:

t = rmedge(G, [1 5], [2 6]); % a minimum spanning tree
figure;
p = plot(G);
highlight(p, t)

You can see two edges are missing, (1,2) and (5, 6), each of which makes one of the cycles above when combined with the tree itself. For example, take edge (1, 2) and combine it with the shortest path inside the tree connecting nodes 1 and 2. This makes for the cycle (1, 2, 3, 4, 1).

[Allan]

Ahhh I see, so there are instances where the algorithm is not garaunteed because of the problem itself. Thank you