Join Subgraphs into a new Graph
5 ビュー (過去 30 日間)
古いコメントを表示
Is there a way or function in Matlab to merge/connect/join a number of Subgraphs into a new Graph?
The following code shows that starting from a Graph, we can extract Subgraphs. What I am looking for is a function to go to the opposite direction, i.e. given a set of (likely overlapping) Subgraphs, join/conncet/nerge them into a new Graph. Is it possible somehow?
clear all; clc; close all;
% Creata a Graph
s = [1 1 1 3 3 6 7 8 9 10 4 12 13 5 15 16 17 18 19 19 20 20 17 24 25 4 27 28 29];
t = [2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30];
G = graph(s,t);
% Node ID: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
G.Nodes.X = [2 1 3 2 4 4 5 4 5 4 5 1 3 3 5 6 7 6 8 7 9 8 9 8 9 10 1 1 0 1]';
G.Nodes.Y = [2 1 3 9 3 5 8 12 13 18 21 15 18 21 0 2 8 12 15 20 10 22 18 5 4 4 5 8 12 23]';
% Extract the Subgraphs from the "Original Graph"
Gpath{1} = subgraph(G,shortestpath(G,4,14));
Gpath{2} = subgraph(G,shortestpath(G,4,26));
Gpath{3} = subgraph(G,shortestpath(G,4,30));
Gpath{4} = subgraph(G,shortestpath(G,3,10));
Gpath{5} = subgraph(G,shortestpath(G,3,28));
Gpath{6} = subgraph(G,shortestpath(G,3,21));
Gpath{7} = subgraph(G,shortestpath(G,17,12));
Gpath{8} = subgraph(G,shortestpath(G,17,23));
Gpath{9} = subgraph(G,shortestpath(G,17,26));
% Figure
hold on
p(1) = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y,'LineWidth',1,'EdgeColor','k','NodeColor','k');
p(1).DisplayName = 'Original Graph';
for i = 1:9
p(2) = plot(Gpath{i},'XData',Gpath{i}.Nodes.X,'YData',Gpath{i}.Nodes.Y,'EdgeColor','y','NodeColor','y');
p(2).NodeLabel = {};
p(2).EdgeAlpha = 1;
p(2).LineWidth = 5;
p(2).DisplayName = sprintf('Subgraph %d',i);
end
legend('Location','eastoutside')
0 件のコメント
採用された回答
Christine Tobler
2024 年 6 月 17 日
編集済み: Christine Tobler
2024 年 6 月 17 日
Here's a quick example based on a guess at how you would like to merge the graphs:
G1 = graph(["A" "B" "C"], ["B" "C" "D"]);
G2 = graph(["A" "B" "C" "E"], "D");
tiledlayout(1, 2);
nexttile
plot(G1);
nexttile
plot(G2);
% Make new, combined graph:
Gall = graph;
Gall = addedge(Gall, G1.Edges);
Gall = addedge(Gall, G2.Edges);
figure
plot(Gall)
Note I have given every node a string label. This simplifies the work quite a lot, since it means graph will be combining the correct nodes with each other, even if they're not used in the same order in each of the subgraphs. With only numbers, you would need to indicate in some way which nodes should be merged together.
Also, you may notice there are now two edges between node C and D, since this edge was in both G1 and G2. If you're graph isn't supposed to have multiple edges at all, you can remove this duplication by calling simplify(Gall). Otherwise, you would need some kind of labeling on the edges so that we can distinguish if an edge is just appearing multiple times, or if it's two different types of edges.
5 件のコメント
その他の回答 (1 件)
Steven Lord
2024 年 6 月 17 日
G1 = graph(randi(10, 20, 1), randi(10, 20, 1));
G2 = graph(randi(10, 20, 1), randi(10, 20, 1));
Here I have two random graphs, each with 10 nodes and up to 20 edges.
subplot(1, 2, 1)
plot(G1)
title("G1")
subplot(1, 2, 2)
plot(G2)
title("G2")
When you say you want to join these, how do you want to join them? Which nodes in G1 should connect to nodes in G2? Or do you just want to join them into a forest, where each node in G2 is renumbered to avoid conflict with the nodes that already exist in G1?
G3 = G1;
G3 = addedge(G3, G2.Edges+numnodes(G1));
figure
plot(G3)
title("G3")
Or do you want each node in the joined graph to connect to any node that it was connected to in either G1 or G2?
G4 = G1;
G4 = addedge(G4, G2.Edges);
figure
plot(G4)
title("G4")
Also, FYI, rather than plotting each graph anew I'd consider using highlight to highlight them in the plot of the existing graph.
参考
カテゴリ
Help Center および File Exchange で Graph and Network Algorithms についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!