Calculate connected graph components of "merged graphs" (graph union)
9 views (last 30 days)
Show older comments
I have two graphs, G1 and G2, and I would need to calculate the connected graph components conncomp() of the "merged graph" G1+G2.
Here an example:
% Create G1
s = [1 1 2 3 4 4 6 7 8];
t = [2 5 3 5 6 7 9 9 9];
x = [1 1 1 2 2 2 3 3.5 3];
y = [1 2 3 4 1 3 4 3.5 3];
G1 = graph(s,t);
% Create G2
s2 = [1 2 3 4 1];
t2 = [2 3 4 1 5];
x2 = [1.5 1.5 3.5 3.5 1];
y2 = [1.5 3.5 3.5 1.5 1];
G2 = graph(s2,t2);
% Plot G1 and G2
hold on
plot(G1,'XData',x,'YData',y,'linewidth',2,'MarkerSize',2);
plot(G2,'XData',x2,'YData',y2,'linewidth',2,'MarkerSize',2);
hold off
% Calculate conncomp of G1 and of G2
bin = conncomp(G1)
bin = conncomp(G2)
Here below what I would like to get:
% Calculate conncomp of the merged graph G1+G2
bin = conncomp(G1+G2)
Initially, I was thinking to add all the nodes of the smallest graph into the largest one using addnode(), and then calculate conncomp(), but I am not sure about it anymore since I would need to modify iteratively both graphs for several times and calculate the resulting conncomp() after eavery graphs modification....
Any idea about a possible way to do it?
3 Comments
Guillaume
on 20 Nov 2019
How is the nodes union computed? Is Node 1 of G1 the same as Node 1 of G2? Or is it Nodes that have the same X and Y coordinates that are the same? I think it's the latter you're interested in. If so, I'd recommend to make the X and Y properties of the Nodes table of each graph.
Accepted Answer
Guillaume
on 20 Nov 2019
Assuming you want that identical nodes are nodes with the same X and Y coordinates, then first I'd add these coordinates to the Nodes tables of each graph:
% Create G1
s = [1 1 2 3 4 4 6 7 8];
t = [2 5 3 5 6 7 9 9 9];
x = [1 1 1 2 2 2 3 3.5 3];
y = [1 2 3 4 1 3 4 3.5 3];
G1 = graph(s,t);
% Create G2
s2 = [1 2 3 4 1];
t2 = [2 3 4 1 5];
x2 = [1.5 1.5 3.5 3.5 1];
y2 = [1.5 3.5 3.5 1.5 1];
G2 = graph(s2,t2);
%Add X and Y to Nodes tables:
G1.Nodes.X = x(:); G1.Nodes.Y = y(:);
G2.Nodes.X = x2(:); G2.Nodes.Y = y2(:);
You can then compute the unions based on these X and Y:
mergedXY = union(G1.Nodes{:, {'X', 'Y'}}, G2.Nodes{:, {'X', 'Y'}}, 'rows'); %compute union of XY of each graph
mergedNodes = array2table(mergedXY, 'VariableNames', {'X', 'Y'}); %Nodes table of merged graph
[~, remapG1] = ismember(G1.Nodes{:, {'X', 'Y'}}, mergedXY, 'rows'); %find where the original nodes of G1 have landed in the union
[~, remapG2] = ismember(G2.Nodes{:, {'X', 'Y'}}, mergedXY, 'rows'); %find where the original nodes of G2 have landed in the union
mergedEdges = table([remapG1(G1.Edges.EndNodes); remapG2(G2.Edges.EndNodes)], 'VariableNames', {'EndNodes'}); %merge the edges while remapping the nodes according to where they are in the union
G = simplify(graph(mergedEdges, mergedNodes)); %create graph remove duplicated edges and loops
figure;
plot(G, 'XData', G.Nodes.X, 'YData', G.Nodes.Y);
3 Comments
Guillaume
on 20 Nov 2019
It's more or less the same as I have done. Just more complicated :)
Since in your case the x and y coordinates are essential properties of the graph I recommend that you embed them the graph object as I have done, so you don't have to carry separate variables around.
More Answers (0)
See Also
Categories
Find more on Graph and Network Algorithms in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!