2 problem with new graph functions in Matlab 2015b

Hi dear all; I want to using graph theory to analyse a circuit. So at first I should determine the graph and its weights then find its spanning tree by the new function in 2015b. My goal is to obtain fundamental cut set of the graph by its tree branches and I have 2 problem: 1- I can not define 2 parallel edge in my direct graph and 2- There is no algorithm yet in Matlab to obtain fundamental cut set matrix of a graph by its tree branches.

Best Regards for your Answers. Reza Amini

[Steven Lord]

By "parallel edge" do you mean you want two edges connecting the same pair of nodes? That would create a multigraph, which is a special type of graph, and one that MATLAB does not support. If that is what you mean, I recommend submitting an enhancement request through Support for this functionality (so we can track the number of requests.)

[Steven Lord]

FYI as of release R2018a you can work with multigraphs that have multiple edges between two nodes.

G = digraph;
G = addedge(G, [1 1 2 2 2 3], [1 2 1 1 3 2]);
plot(G)

There are two edges from 2 to 1 and one from 1 to 2.

Answer 1

[Christine Tobler]

Sorry this is kind of a late answer. There is no function to compute the fundamental cut set from a minimum spanning tree in MATLAB, but here's how to compute it yourself:

% Construct a random graph and plot it:
rng default; g = graph(sprandn(10, 10, 0.5), 'upper');
plot(g);

% Compute the minimum spanning tree of g:
t = minspantree(g);
plot(t);

% Choose an edge of the minimum spanning tree, here I choose (7, 10)
% Compute the two separated sets of nodes appearing if (7, 10) is removed from t:
tcut = rmedge(t, 7, 10);
bins = conncomp(tcut);

% Now, find all edges of g that connect a node from the first set 
% to a node of the second set:
[s, t] = findedge(g);
inCutSet = bins(s) ~= bins(t);
sCutSet = s(inCutSet);
tCutSet = t(inCutSet)

% Plot g again, and highlight all edges in the fundamental cut set:
p = plot(g);
highlight(p, sCutSet, tCutSet);

For your question (1), do you mean that you want two edges both connecting node 3 and node 4, for example? This is not possible in the current graph class, which only supports simple graphs. For the purpose of this example, you could construct a graph using only the edge of smallest weight for each parallel edge - the minimum spanning tree would be the same.

[Fatah Bouchebbah]

Hello Christine Tobler, I have the same problem as (1). I want to remove all edges that connect two specific nodes except the smallest one. I am a new matlab developper. Could you help me with that, please?

[Christine Tobler]

Hi Fatah Bouchebbah,

Sorry, I just saw your question now when browsing through old posts. Here's a short example of how to do what you are looking for:

>> st = [1 2; 3 4; 1 2; 3 5];
>> w = [0.5; 0.7; 0.1; 0.4];
>> g = digraph(st(:, 1), st(:, 2), w);
Error using matlab.internal.graph.MLDigraph
Duplicate edges not supported.

>> [stUnique, ~, ind] = unique(st, 'rows');
>> wUnique = splitapply(@min, w, ind);
>> g = digraph(stUnique(:, 1), stUnique(:, 2), wUnique);
>> g.Edges

ans =

    3×2 table

      EndNodes    Weight
      ________    ______

      1    2      0.1   
      3    4      0.7   
      3    5      0.4

Answer 2

[Walter Roberson]

Graph theory is only concerned with whether nodes are connected or not, and is not concerned with whether edges are parallel or not. Parallel or not might make a difference in how you choose what data to pass to the graph theory routines, but does not make a difference to those routines.