Are there matlab codes to compute cycle spaces of graphs?
2 views (last 30 days)
Show older comments
Are there matlab codes to compute cycle spaces of graphs and digraphs in matlab?
0 Comments
Answers (6)
Christine Tobler
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?
0 Comments
Andrew Sol
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?
1 Comment
Christine Tobler
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
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.
1 Comment
Christine Tobler
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
on 29 Mar 2019
Christina, i have a graph:
For this graph i must get cycles (loops/contours):
3213
3243
1241
1341
347653
1 Comment
Christine Tobler
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
on 30 Mar 2019
Trying to figure it out. Kristina, tell me how to build a spanning tree for a directed graph in MATLAB?
1 Comment
Christine Tobler
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:
A = adjacency(g);
gundir = graph(A + A');
t = minspantree(gundir);
Andrew Sol
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 (...
1 Comment
Steven Lord
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.
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!