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.

1 Download

Updated 29 Jul 2018

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.

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.

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?

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.

Works as advertised! Good work ;)

Updates

1.1

Fixed a bug where some edges could be missing from the complement of the spanning forest which could cause there to be fewer cycles than expected.

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