Calculate connected graph components of "merged graphs" (graph union)

9 views (last 30 days)
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
Sim
Sim on 20 Nov 2019
Edited: Sim on 20 Nov 2019
Thanks a lot Christine for your answer!
You are right, I did not specify exactly.... I meant a graph union , where vertices (nodes) V and edges (links) E of the graph union are:
In general, I would need a graph union where
  • All the vertices' coordinates of both G1 and G2 are preserved ( = same vertices' coordinates in H).
  • In case of common vertices and edges between G1 and G2 , once I calculate conncomp(), it should "be aware" of common vertices and edges, resulting in connected components between G1 and G2 .
  • In case of disjoint components ( = not overallpping vertices or edges) of G1 and G2 , the union graph H should include the disjoint components.
Guillaume
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.

Sign in to comment.

Accepted Answer

Guillaume
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
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.
Sim
Sim on 20 Nov 2019
Many thanks! Yes, you are right, I should have embeded the coordinates to the graph objects for avoiding that separate variables went up and down the code :) ...Super! ...Also, the elapsed time, which is quite relevant for my specific case, is very similar to my solution's one (mine is tiny tiny bit faster)
% Guillaume solution
Elapsed time is 0.628412 seconds.
% Sim solution
Elapsed time is 0.491974 seconds.
Thank you very much Guillaume! :)

Sign in to comment.

More Answers (0)

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!