finding degree and neighbor of each vertex in a subgraph H but indexing according to original graph
4 次查看(过去 30 天)
显示 更早的评论
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
0 个评论
回答(2 个)
Dyuman Joshi
2023-7-5
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
plot(H)
%Indices of neighbors of the 6th node
z1=neighbors(H, 6)'
%Access the names of the neighbors of the 6th node
H.Nodes(z1,:)
Another case -
%Indices of neighbors of the 4th node
z2=neighbors(H,4)'
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,:)
%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)'
It can be referred from the error what the expected input is.
H.Nodes(z3,:)
0 个评论
Christine Tobler
2023-7-5
编辑:Christine Tobler
2023-7-5
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
H.Nodes
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")'
neighbors(H, "8")'
If you need to convert between numbers and strings containing numbers, you can use:
num = 8;
string(num)
str = "3";
double(str)
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 个评论
Dyuman Joshi
2023-10-9
@Urvashi - Did you try the above answer(s) on your data?
If not, why not? If yes, then what is the problem you are facing?
Christine Tobler
2023-10-11
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
% 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
H.Nodes
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)))
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!