## Are there matlab codes to compute cycle spaces of graphs?

### Hao Sun (view profile)

on 22 Aug 2017
Latest activity Commented on by Christine Tobler

### Christine Tobler (view profile)

on 1 Apr 2019
Are there matlab codes to compute cycle spaces of graphs and digraphs in matlab?

### Christine Tobler (view profile)

on 22 Aug 2017

There is no direct method to compute this in MATLAB's graph classes. From reading the wiki page, it seems that the following will construct a basis of the cycle space:
g = graph(bucky);
t = minspantree(g, 'Type', 'forest');
nonTreeEdges = setdiff(g.Edges.EndNodes, t.Edges.EndNodes, 'rows');
cycles = cell(size(nonTreeEdges, 1), 1);
for ii=1:length(cycles)
src = nonTreeEdges(ii, 1); tgt = nonTreeEdges(ii, 2);
cycles{ii} = [tgt shortestpath(t, src, tgt)];
end
Is this output what you were looking for? I expect this could become costly for graphs with many edges - perhaps there is some other format that would be more useful for your application?

### Andrew Sol (view profile)

on 28 Mar 2019

Hello. I work with graphs. In topic:
you find solution for cycles, includes in nodes.
But this does not work always.
For example, i have adjancency matrix:
0 1 1 1 0 0 0
1 0 1 1 0 0 0
1 1 0 1 1 0 0
1 1 1 0 0 0 1
0 0 1 0 0 1 0
0 0 0 0 1 0 1
0 0 0 1 0 1 0
And in your code i get cycles:
[3 2 1 3]
[4 2 1 4]
[4 3 1 4]
[7 6 5 3 1 4 7]
But i must have:
3213
3243
1241
1341
347653
What's problem with this code?

Christine Tobler

### Christine Tobler (view profile)

on 28 Mar 2019
Just so we're on the same page, my code provides a Cycle basis, meaning that any cycle in the graph can be computed by combining the cycles in this basis (every cycle in the graph can be written as a "symmetric difference" of cycles in the basis, that is, by combining cycles from the cycle basis). I'm not making any claims about returning a specific basis there.
I think that the outputs of my function satisfy that definition? I think one of your first four outputs can be constructed from the other three, so is not needed to form a basis. My fourth output is not the nicest (making it as short as possible would be simpler to readl), but it seems correct to me.
I don't know much about cycle basis, I'm really just going by that wikipedia page. Please let me know if this makes sense to you.

### Andrew Sol (view profile)

on 28 Mar 2019

Christina, this code, in my opinion, is one of the fastest and at the same time compact solutions. But it would be great if he found all the fundamental loops so that they would not have to be obtained later from other cycles. The speed and compactness of your algorithm is important for my research on ultra-large graphs. As an example, you can use my adjacency matrix to correct the code and get the result I'm talking about.

Christine Tobler

### Christine Tobler (view profile)

on 29 Mar 2019
Can you give me a definition of what you are looking for? I can't really extrapolate from that one example to a change in the algorithm.

### Andrew Sol (view profile)

on 29 Mar 2019

Christina, i have a graph:
For this graph i must get cycles (loops/contours):
3213
3243
1241
1341
347653

Christine Tobler

### Christine Tobler (view profile)

on 29 Mar 2019
Yes, but without a definition of which cycles you want for a general graph, I can't recommend an algorithm for computing these.

### Andrew Sol (view profile)

on 30 Mar 2019

Trying to figure it out. Kristina, tell me how to build a spanning tree for a directed graph in MATLAB?

Christine Tobler

### Christine Tobler (view profile)

on 1 Apr 2019
Computing the minimum spanning tree is only supported for undirected graph. Here's how to get an undirected graph from a digraph:
gundir = graph(A + A');
t = minspantree(gundir);

### Andrew Sol (view profile)

on 30 Mar 2019

Christina, I want to build a multigraph with parallel branches, as shown in the figure:
https://la.mathworks.com/help/examples/matlab/win64/PickOrCombineMultipleGraphEdgesExample_01.png
https://la.mathworks.com/help/matlab/ref/graph.simplify.html
But MATLAB gives the error:
Error using matlab.internal.graph.MLGraph
Duplicate edges not supported.
Error in matlab.internal.graph.constructFromEdgeList (line 125)
G = underlyingCtor (double (s), double (t), totalNodes);
Error in graph (line 287)
matlab.internal.graph.constructFromEdgeList (...

Steven Lord

### Steven Lord (view profile)

on 30 Mar 2019
Multigraph support was added in release R2018a. If you're using an older release and want to create a multigraph you will need to upgrade.