Are there matlab codes to compute cycle spaces of graphs?

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

Answer 1

[Christine Tobler]

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?

Answer 2

[Andrew Sol]

Hello. I work with graphs. In topic:

https://la.mathworks.com/matlabcentral/answers/353565-are-there-matlab-codes-to-compute-cycle-spaces-of-graphs

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]

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.

Answer 3

[Andrew Sol]

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]

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.

Answer 4

[Andrew Sol]

Christina, i have a graph:

https://ibb.co/Qvp2XBr

https://ibb.co/LSZg9nK

For this graph i must get cycles (loops/contours):

3213

3243

1241

1341

347653

[Christine Tobler]

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

Answer 5

[Andrew Sol]

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

[Christine Tobler]

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

Answer 6

[Andrew Sol]

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]

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.