File Exchange

cyclebasis

version 1.1 (3.21 KB) by Ben Petschel

Ben Petschel (view profile)

Find a basis for the cycle subspace of a graph/network.

Updated 29 Jul 2018

This can be used for finding the linearly independent equations derived from Kirchhoff's second law. This function finds a set of fundamental cycles that will correspond to linearly independent circuit conservation equations.

Example: fundamental cycles of complete graph on 4 vertices including self-loops at each vertex:

cyclebasis(ones(3,3),'path') % returns {1,2,[1,2,3],3}

See the help text for more details.

Cite As

Ben Petschel (2020). cyclebasis (https://www.mathworks.com/matlabcentral/fileexchange/24561-cyclebasis), MATLAB Central File Exchange. Retrieved .

Ben Petschel

Ben Petschel (view profile)

Hi Andrew, both answers are correct. There can be many different cycle bases found depending on which spanning tree is computed. There is no guarantee that the cycles returned by my program are the "smallest" such cycles.

Andrew Sol

Andrew Sol (view profile)

Hello. Try create list of cycles for this adjancency matrix. A=([0, 1, 0, 0, 0, 0, 1, 0;
1, 0, 0, 1, 0, 0, 0, 0;
0, 0, 0, 0, 1, 1, 1, 0;
0, 1, 0, 0, 1, 0, 0, 1;
0, 0, 1, 1, 0, 1, 1, 0;
0, 0, 1, 0, 1, 0, 0, 0;
1, 0, 1, 0, 1, 0, 0, 1;
0, 0, 0, 1, 0, 0, 1, 0]);
I think, that instead cycle 3,5,6,7 must be 3,5,6.

Ben Petschel

Ben Petschel (view profile)

Hi Sagiv,

Thanks for reporting this error. There was a problem where some edges were not being added to the complement of the spanning forest, which I've fixed now.

Sagiv Eliyahu

Sagiv Eliyahu (view profile)

Hi Ben,

It seems like there is errors with some cases.
Suppose I have a 6X6 Adjacency matrix of a complete graph - this case is OK and I get 10 circles.
Now suppose matrix(1,6)=matrix(6,1)=0. this case is OK and I get 9 circles.
Now the problem begins:
suppose also matrix(1,5)=matrix(5,1)=0. this case is not OK and I get 7 circles instead of 8.
suppose also matrix(1,4)=matrix(4,1)=0. this case is also not OK and I get 4 circles instead of 7.
suppose also matrix(1,3)=matrix(3,1)=0. this case is suddenly OK and I get 6 circles .

The weird thing: its happening only for the first column / row. If you replace '1' with other digit, it won't happen.
Can you explain this?

Thanks!

Ben Petschel

Ben Petschel (view profile)

John, I couldn't replicate your problem. Could you post an example?

John Simpson

John Simpson (view profile)

Seems to have some minor issues, at least on 2016a. I applied it to a tree and it returned a 1x6 cell array. All the cells were empty.

Joao Henriques

Joao Henriques (view profile)

Works as advertised! Good work ;)