How can I find if edges in a subgraph SG appear inside/belong to a graph G?

1 view (last 30 days)
Sim
Sim on 25 Jan 2022
Commented: Sim on 26 Jan 2022
How can I find if edges in a subgraph SG appear inside/belong to a graph G?
I have this example with a graph G:
s = [1 1 2 2 2 3 3 3];
t = [2 3 3 4 5 6 7 5];
x = [0 0 1 0 4 3 1];
y = [0 1 0 4 5 0 -1];
G = graph(s,t);
G.Nodes.X = x'; G.Nodes.Y = y';
plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y)
From the graph G I "extract" a subgraph SG, i.e.:
SG = subgraph(G,[2 3 5 6])
figure
plot(SG,'XData',SG.Nodes.X,'YData',SG.Nodes.Y)
Now I would like to find the edges of SG inside/which belong to G. The answer should be:
edges_in_G =
2 3
2 5
3 5
3 6
% which correspond to
edges_in_SG =
1 2
1 3
2 3
2 4
How to do it since the nodes in the subgraph SG are renumbered (compared to the graph G)?
  4 Comments

Sign in to comment.

Accepted Answer

Jon
Jon on 25 Jan 2022
You can name the edges in G and then the corresponding edges in the subgraph will have the same names as those in the main graph. So something like this:
s = [1 1 2 2 2 3 3 3];
t = [2 3 3 4 5 6 7 5];
x = [0 0 1 0 4 3 1];
y = [0 1 0 4 5 0 -1];
G = graph(s,t);
G.Nodes.X = x'; G.Nodes.Y = y';
% Name the edges, column name in edge table must be "Names"
G.Edges.Names = {'a','b','c','d','e','f','g','h'}'
plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y)
% From the graph G I "extract" a subgraph SG, i.e.:
SG = subgraph(G,[2 3 5 6])
figure
plot(SG,'XData',SG.Nodes.X,'YData',SG.Nodes.Y)
% find out which edges in SG are in G
idl = ismember(G.Edges.Names,SG.Edges.Names)
inG = G.Edges.Names(idl)
  3 Comments
Sim
Sim on 26 Jan 2022
thanks a lot @Jon!
the only thing is that I have a graph of around 5000 edges and 9000 nodes..... probably I need to use a name/label with numbers instead of letters, or a combination of numbers and letters?... thanks :)
EDITED: I found a simple (and "automatic") way to name all the edges:
G.Edges.Names = compose('edge_%d',1 : numedges(G))';
In case other people are interested, I just rewrite here your entire solution, since it was fragmented in different comments:
% code from @Jon (with a very tiny modification)
close all; clc;
s = [1 1 2 2 2 3 3 3];
t = [2 3 3 4 5 6 7 5];
x = [0 0 1 0 4 3 1];
y = [0 1 0 4 5 0 -1];
% create the graph G
G = graph(s,t);
G.Nodes.X = x'; G.Nodes.Y = y';
% name the edges, column name in edge table must be "Names"
G.Edges.Names = compose('edge_%d',1 : numedges(G))';
% extract a subgraph SG from the graph G
SG = subgraph(G,[2 3 5 6]);
% plot G and SG
figure
h = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y);
labeledge(h,1:numel(G.Edges.Names),G.Edges.Names)
figure
h = plot(SG,'XData',SG.Nodes.X,'YData',SG.Nodes.Y);
labeledge(h,1:numel(SG.Edges.Names),SG.Edges.Names)
% show edges of SG and find out which edges in SG are in G
edges_in_SG = SG.Edges.EndNodes
idl = ismember(G.Edges.Names,SG.Edges.Names);
inG = G.Edges.Names(idl)
edges_in_G = G.Edges.EndNodes(idl,:)
% results from @Jon
edges_in_SG =
1 2
1 3
2 3
2 4
inG =
4×1 cell array
{'edge_3'}
{'edge_5'}
{'edge_6'}
{'edge_7'}
edges_in_G =
2 3
2 5
3 5
3 6

Sign in to comment.

More Answers (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!