MATLAB Answers

Hao Sun
0

Are there matlab codes to compute cycle spaces of graphs?

Asked by Hao Sun
on 22 Aug 2017
Latest activity Commented on by Christine Tobler on 1 Apr 2019
Are there matlab codes to compute cycle spaces of graphs and digraphs in matlab?

  0 Comments

Sign in to comment.

6 Answers

Answer by 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

Sign in to comment.


Answer by 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

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.

Sign in to comment.


Answer by 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

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.

Sign in to comment.


Answer by 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

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

Sign in to comment.


Answer by 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

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);

Sign in to comment.


Answer by 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

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.

Sign in to comment.