Asked by Hao Sun
on 22 Aug 2017

Are there matlab codes to compute cycle spaces of graphs and digraphs in matlab?

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?

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?

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.

Sign in to comment.

Answer by Andrew Sol
on 28 Mar 2019

Christine Tobler
on 29 Mar 2019

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

Christine Tobler
on 29 Mar 2019

Sign in to comment.

Answer by Andrew Sol
on 30 Mar 2019

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

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 (...

Steven Lord
on 30 Mar 2019

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 0 Comments

Sign in to comment.