44 次查看(过去 30 天)
显示 更早的评论
Sim 2024-6-17,14:25
编辑: Sim 2024-6-18,13:28
采纳的回答: Christine Tobler
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 个评论 显示 -2更早的评论隐藏 -2更早的评论
显示 -2更早的评论隐藏 -2更早的评论
请先登录,再进行评论。
请先登录,再回答此问题。
采纳的回答
Christine Tobler 2024-6-17,18:24
编辑:Christine Tobler 2024-6-17,18:25
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
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 个评论 显示 3更早的评论隐藏 3更早的评论
显示 3更早的评论隐藏 3更早的评论
Sim 2024-6-17,19:30
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2129351-join-subgraphs-into-a-new-graph#comment_3188656
Thanks a lot @Christine Tobler! I tried to reply to both of you in a combined comment under the @Steven Lord's answer... Yes, I understand that there will be multi-edges, that I can then "remove" through simplify(Gall), but I did not get exactly the part about "With only numbers, you would need to indicate in some way which nodes should be merged together". Aren't the X and Y nodes coordinates - as in my case - sufficient to correctly combine/join my subgraphs?
Christine Tobler 2024-6-17,19:54
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2129351-join-subgraphs-into-a-new-graph#comment_3188716
If the X and Y coordinates are unique to each node, then they would be sufficient. But graph won't do anything using these automatically, so you would have to use them to find unique indices over all the nodes from all the subgraphs.
For example:
xy = [];
xy = [xy; G1.Nodes.X, G1.Nodes.Y];
xy = [xy; G2.Nodes.X, G2.Nodes.Y];
% and so on
allXY = unique(xy, 'rows');
[~, ind1] = ismember([G1.Nodes.X, G1.Nodes.Y], allXY, 'rows');
G1.Nodes.Name = string(ind1)
% so on for other subgraphs
Here I'm making a global map using all node coordinates, and then assigning node names using indices into this map. After that, you can use
% Initialize a graph with the names corresponding to all indices
Gall = graph([], [], [], string(1:size(allXY, 1))');
% Insert the edges from each subgraph
Gall = addedge(Gall, G1.Edges)
Sim 2024-6-17,20:59
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2129351-join-subgraphs-into-a-new-graph#comment_3188821
Thanks a lot @Christine Tobler! I hope I understood and interpreted correctly what you suggested:
% 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));
% Plot all the single/disjoint Subgraphs
figure('position',[400 400 700 600],'Color',[1 1 1]);
hold on
for i = 1:9
p(2) = plot(Gpath{i},'XData',Gpath{i}.Nodes.X,'YData',Gpath{i}.Nodes.Y,'EdgeColor','m','NodeColor','m');
p(2).EdgeAlpha = 1;
p(2).LineWidth = 5;
p(2).NodeLabel = {};
p(2).DisplayName = sprintf('Subgraph %d',i);
end
p(1) = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y,'EdgeColor','k','NodeColor','k');
p(1).EdgeAlpha = 1;
p(1).LineWidth = 1;
p(1).NodeFontSize = 14;
p(1).DisplayName = 'Original Graph';
title('All the single/disjoint Subgraphs', 'FontSize',20)
legend
axis off
% Christine Tobler solution
xy = [];
for i = 1 : 9
xy = [xy; Gpath{i}.Nodes.X, Gpath{i}.Nodes.Y];
end
allXY = unique(xy, 'rows');
for i = 1 : 9
ind1 = [];
[~, ind1] = ismember([Gpath{i}.Nodes.X, Gpath{i}.Nodes.Y], allXY, 'rows');
Gpath{i}.Nodes.Name = string(ind1);
end
Gall = graph([], [], [], string(1:size(allXY, 1))');
for i = 1 : 9
Gall = addedge(Gall, Gpath{i}.Edges);
end
% Plot the joint Subgraphs, i.e. the new Graph "Gall"
figure('position',[400 400 700 600],'Color',[1 1 1]);
hold on
p(3) = plot(simplify(Gall),'XData',allXY(:,1),'YData',allXY(:,2),'LineWidth',5,'EdgeColor','m','NodeColor','m');
p(3).EdgeAlpha = 1;
p(3).LineWidth = 5;
p(3).NodeLabel = {};
p(3).DisplayName = sprintf('Joint Subgraphs');
p(1) = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y,'EdgeColor','k','NodeColor','k');
p(1).EdgeAlpha = 1;
p(1).LineWidth = 1;
p(1).NodeFontSize = 14;
p(1).DisplayName = 'Original Graph';
title('Christine Tobler solution', 'FontSize',20)
legend
axis off
Sim 2024-6-18,13:25
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2129351-join-subgraphs-into-a-new-graph#comment_3189411
编辑:Sim 2024-6-18,13:28
Thanks a lot! This process saved me a looooot of time (and stress!).. :-) Also, my original figure that I produced with the disjoint Subgraphs was around 135 MB once printed (with exportgraphics), and now it is "just" 17 MB... A big improvement! :-)
A big thank to both of you, @Christine Tobler and @Steven Lord, for your suggestions!!
请先登录,再进行评论。
更多回答(1 个)
Steven Lord 2024-6-17,16:30
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.
1 个评论 显示 -1更早的评论隐藏 -1更早的评论
显示 -1更早的评论隐藏 -1更早的评论
Sim 2024-6-17,19:23
此评论的直接链接
https://ww2.mathworks.cn/matlabcentral/answers/2129351-join-subgraphs-into-a-new-graph#comment_3188641
编辑:Sim 2024-6-17,19:35
Thanks a lot to both of you @Steven Lord and @Christine Tobler, for your nice answers!
Given the following subgraphs:
addpath('/.../subtightplot');
subplot = @(m,n,p) subtightplot (m, n, p, [0 0], [0 0], [0 0]);
% 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
figure('position',[400 400 700 600],'Color',[1 1 1]);
for i = 1:9
subplot(3,3,i)
hold on
p(1) = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y,'LineWidth',1,'EdgeColor','k','NodeColor','k');
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(1).DisplayName = 'Original Graph';
% p(2).DisplayName = sprintf('Subgraph %d',i);
axis off
end
I would like to join the yellow paths, which are stored as Subgraphs, i.e. Gpath{1}, Gpath{2}, ..., Gpath{9}, into a (new) Graph which is formed by the same nodes and edges of all the yellow Subgraphs, i.e. I would like to get the following (new) Graph, which I guess will have multi-edges somewhere due to the overlap of Subgraphs:
Inspired by both of your solutions, I tried the following piece of code:
Gall = graph;
for i = 1 : 9
Gall = addedge(Gall, Gpath{i}.Edges);
end
figure
plot(Gall,'XData',Gall.Nodes.X,'YData',Gall.Nodes.Y);
However, the command addedge, does not pass the X and Y coordinates of the nodes to the (new) Graph, "Gall". Therefore, I get the following error:
Error using .
Unrecognized table variable name 'X'.
Error in indexing (line 130)
out = subsref(nodeprop, S);
Error in untitled2 (line 46)
plot(Gall,'XData',Gall.Nodes.X,'YData',Gall.Nodes.Y);
How can I correct that error? :-)
请先登录,再进行评论。
请先登录,再回答此问题。
另请参阅
标签
- subgraph
- graph
- join
- connect
- merge
- graph theory
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
发生错误
由于页面发生更改,无法完成操作。请重新加载页面以查看其更新后的状态。
选择网站
选择网站以获取翻译的可用内容,以及查看当地活动和优惠。根据您的位置,我们建议您选择:。
您也可以从以下列表中选择网站:
美洲
- América Latina (Español)
- Canada (English)
- United States (English)
欧洲
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom(English)
亚太
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 简体中文Chinese
- English
- 日本Japanese (日本語)
- 한국Korean (한국어)
联系您当地的办事处