MATLAB: Calculate connected graph components of “merged graphs” (graph union)

conncompgraphgraph theory

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?

Best Answer

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