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

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)?

[Matt J]

If SG is a subgraph of G, then obviously all of its nodes and edges belong to G. That's what it means to be a subgraph.

[Sim]

Yes yes, true... but once I "extract" a subgraph SG from a graph G, I then need to retrieve some properties of the edges in the initial graph G, which I stored in a table T similar to this one:

T = [table2array(G.Edges) rand(numedges(G),5)];
T =

            1            2     0.075854     0.011902      0.26297      0.15238    0.0046342
            1            3      0.05395      0.33712      0.65408      0.82582      0.77491
            2            3       0.5308      0.16218      0.68921      0.53834       0.8173
            2            4      0.77917      0.79428      0.74815      0.99613      0.86869
            2            5      0.93401      0.31122      0.45054     0.078176     0.084436
            3            5      0.12991      0.52853     0.083821      0.44268      0.39978
            3            6      0.56882      0.16565      0.22898      0.10665      0.25987
            3            7      0.46939      0.60198      0.91334       0.9619      0.80007

Therefore, if I use the edges in SG, i.e.:

edges_in_SG = 
            1 2
            1 3
            2 3 
            2 4

to retrieve the properties contained in the table T, I do not select the correct edges.... I should instead use the corresponding edges in G, i.e.:

edges_in_G =
            2 3
            2 5
            3 5
            3 6   

By using "edges_in_G" I can therefore select the right rows in T, i.e.:

>> [~,idx] = ismember(edges_in_G, T(:,1:2), 'rows')

idx =

     3
     5
     6
     7

>> T(idx,:)

ans =

            2            3       0.5308      0.16218      0.68921      0.53834       0.8173
            2            5      0.93401      0.31122      0.45054     0.078176     0.084436
            3            5      0.12991      0.52853     0.083821      0.44268      0.39978
            3            6      0.56882      0.16565      0.22898      0.10665      0.25987

[Jon]

Hi I'm glad that approach worked for you. Good idea for the automatic generation of unique edge names. Thanks for putting all of the pieces together so the answer is clearer. Good luck with your project.

[Sim]

thanks ;)

Answer 1

[Jon]

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)

[Jon]

You can also label the edges in the plot

% plot the two graphs with edges labeled with their names
figure
h = plot(G,'XData',G.Nodes.X,'YData',G.Nodes.Y);
labeledge(h,1:numel(G.Edges.Names),G.Edges.Names)

figure
% plot the two graphs with edges labeled with their names
h = plot(SG,'XData',SG.Nodes.X,'YData',SG.Nodes.Y);
labeledge(h,1:numel(SG.Edges.Names),SG.Edges.Names)

[Jon]

Oh, I just saw that you want the edges in G listed by their end nodes, you can do this, using the logical index idl from above and

idl = ismember(G.Edges.Names,SG.Edges.Names)
edges_in_G = G.Edges.EndNodes(idl,:)

edges_in_G =

2 3

2 5

3 5

3 6

[Sim]

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