Cyclebasis function for graphs not working

5 views (last 30 days)
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]}

Accepted Answer

Christine Tobler
Christine Tobler on 30 Apr 2024
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."
  3 Comments
Christine Tobler
Christine Tobler on 30 Apr 2024
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
Allan on 1 May 2024
Ahhh I see, so there are instances where the algorithm is not garaunteed because of the problem itself. Thank you

Sign in to comment.

More Answers (0)

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2023a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!