finding degree and neighbor of each vertex in a subgraph H but indexing according to original graph

3 次查看（过去 30 天）
Urvashi
Urvashi 2023-7-5
评论： Christine Tobler 2023-10-11
I have a graph G with vertex set V=[1:10];
s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G=graph(s,t);
G.Nodes.Name=string(1:numnodes(g))';
I want to find degree and neighbor of each vertex of a subset of V i.e., S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
when computing neighbors, I want that neighbor index should be according to original graph G. For ex:
plot(H) %it plot H correctly
neighbors(H, 6)'
it returns value 1,7 and I want 1,8 acc to G

请先登录，再回答此问题。

回答（2 个）

Dyuman Joshi
Dyuman Joshi 2023-7-5
Ran in:
The output you get is the index of nodes which are neighbors to the input and not the name of the node.
And the input to the function is the index of the node, not the Node name.
V = 1:10;
s = [1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t = [2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G = graph(s,t);
G.Nodes.Name=string(1:numnodes(G))';
figure
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
H.Nodes
ans = 7×1 table
Name _____ {'1'} {'2'} {'3'} {'4'} {'5'} {'6'} {'8'}
plot(H)
%Indices of neighbors of the 6th node
z1=neighbors(H, 6)'
z1 = 1×2
1 7
%Access the names of the neighbors of the 6th node
H.Nodes(z1,:)
ans = 2×1 table
Name _____ {'1'} {'8'}
Another case -
%Indices of neighbors of the 4th node
z2=neighbors(H,4)'
z2 = 1×3
3 5 7
You can observe that here that the output, as mentioned above, is the indices, meaning that the 3rd, 5th and 7th node of the graphs are neighbors to the 4th node of the graph.
You will have to access the names via indexing as done below -
%Name of the neighbors of the 7th node
H.Nodes(z2,:)
ans = 3×1 table
Name _____ {'3'} {'5'} {'8'}
%If you try to get the neighbor of 8th node under the assumption that name
%of the node is the input, you will get an error
z3=neighbors(H,8)'
Error using graph/validateNodeID
Numeric node IDs must be positive integers not greater than the number of nodes in the graph (7).

Error in graph/neighbors (line 17)
id = validateNodeID(G, nodeid);
It can be referred from the error what the expected input is.
H.Nodes(z3,:)
Christine Tobler
Christine Tobler 2023-7-5
编辑：Christine Tobler 2023-7-5
Ran in:
I think the easiest will be to build on what you started by giving the nodes in graph G names which are just the string version of their numbers.
% This block is just your code from above, so I can use the variables later on.
s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G=graph(s,t);
G.Nodes.Name=string(1:numnodes(G))';
% I want to find degree and neighbor of each vertex of a subset of V i.e.,
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
% when computing neighbors, I want that neighbor index should be according to original graph G. For ex:
plot(H) %it plot H correctly
neighbors(H, 6)' %it returns value 1,7 and I want 1,8 acc to G
ans = 1×2
1 7
H.Nodes
ans = 7×1 table
Name _____ {'1'} {'2'} {'3'} {'4'} {'5'} {'6'} {'8'}
In graph H, node 7 has name "8". The number 7 is just counting up all nodes in H, while the name "8" is the index from graph G. So you can call neighbors with either of these, depending on whether you put the input in quotations:
neighbors(H, "6")'
ans = 1×2 string array
"1" "8"
neighbors(H, "8")'
ans = 1×3 string array
"4" "5" "6"
If you need to convert between numbers and strings containing numbers, you can use:
num = 8;
string(num)
ans = "8"
str = "3";
double(str)
ans = 3
All this should be fine for smaller graphs, for very large graphs the conversion to/from string might slow you down. Let me know if this is your case, I can add some (less compact) code for that case.
  3 个评论
显示 1更早的评论
Christine Tobler
Christine Tobler 2023-10-11
Ran in:
All right, here's a variant that uses a numeric array of indexes instead of strings containing numbers. This should be more efficient, but is also less intuitive, as you need to be careful to distinguish between an index into the original graph and its projection into the subgraph.
% This block is just your code from above, so I can use the variables later on.
s=[1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 6, 6];
t=[2, 3, 6, 10, 7, 9, 4, 5, 5, 8, 8, 7, 8, 10];
G=graph(s,t);
G.Nodes.ID=(1:numnodes(G))'; % Set a different variable name than Name, which must be string
plot(G)
% I want to find degree and neighbor of each vertex of a subset of V i.e.,
S=[1,2,3,4,5,6,8];
H=subgraph(G,S);
h2g = H.Nodes.ID; % h2g(i) tells us the node id of node i in H, in the original graph G.
g2h = zeros(1, numnodes(G));
g2h(h2g) = 1:numnodes(H); % g2h is the reverse transformation.
g2h
g2h = 1×10
1 2 3 4 5 6 0 7 0 0
% If node i in G is part of
% when computing neighbors, I want that neighbor index should be according to original graph G. For ex:
plot(H, NodeLabel=string(h2g)) %it plot H correctly
h2g(neighbors(H, g2h(6))) %it returns value 1,7 and I want 1,8 acc to G
ans = 2×1
1 8
H.Nodes
ans = 7×1 table
ID __ 1 2 3 4 5 6 8
In graph H, node 7 is what was node 8 in graph G. The number 7 is just counting up all nodes in H, while the number 8 is the index from graph G. So when you call neighbors on H using the indexes from G, you need to (a) transform the input from indexing into G to indexing into H and (b) transform the output from node IDs in H to node IDs in G:
h2g(neighbors(H, g2h(8)))
ans = 3×1
4 5 6
Please let me know if this improves speed for your cases of large graphs.

请先登录，再进行评论。

类别

在 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!

Translated by