File Exchange

image thumbnail

cyclebasis

version 1.1 (3.21 KB) by Ben Petschel
Find a basis for the cycle subspace of a graph/network.
5.0
2 Ratings

3 Downloads

Updated 29 Jul 2018

View Version History

View License

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 (2021). cyclebasis (https://www.mathworks.com/matlabcentral/fileexchange/24561-cyclebasis), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (7)

Ben Petschel

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

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

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

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

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

John Simpson

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

Works as advertised! Good work ;)

MATLAB Release Compatibility
Created with R2009a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

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

Start Hunting!