One hop nearest neighbor in a graph

Hi,

nodeIDs = nearest( G , s , d ) returns all nodes in graph G that are within distance d from node s. But how do we find out one hop away neighbors (just closest nodes only) within a distance, in a graph? I mean the nearest neighbour of a vertex in a graph within a distance must be connected through an edge. (only one edge)

thanks!

Answer 1

[Chunru]

% Example graph
s = [1 1 1 1 1 2 2 2 3 3 3 3 3];
t = [2 4 5 6 7 3 8 9 10 11 12 13 14];
weights = randi([1 10],1,13);
G = graph(s,t,weights);
p = plot(G,'Layout','force','EdgeLabel',G.Edges.Weight);

% All edges from node 1
eid = outedges(G, 1) 

eid = 5×1

1 2 3 4 5

% info for edges from the node
e = G.Edges(eid, :)

e = 5×2 table
    EndNodes    Weight
    ________    ______

     1    2       8   
     1    4       8   
     1    5       3   
     1    6       4   
     1    7       8   

% min distance
[~, idx] = min(e.Weight)

idx = 3

e(idx, :)

ans = 1×2 table
    EndNodes    Weight
    ________    ______

     1    5       3   

min_node = e(idx, 1).EndNodes(2)

min_node = 5

min_dist = e.Weight(idx, 1)

min_dist = 3

Answer 2

[Steven Lord]

Find the neighbors of the node in the undirected graph then compute the distances between the specified node and its neighbors. Let's take an example: the buckyball graph.

b = bucky;

Update the adjacency matrix with some random weights and make it symmetric.

b = b.*randi(10, size(b));
b = (b + b.')/2;

Make the graph.

g = graph(b);

Find the neighbors of node 42.

n = neighbors(g, 42)

n = 3×1

8 41 43

Find the distances from node 42 to the neighbor nodes.

d = distances(g, 42, n)

d = 1×3

6.0000 1.5000 7.0000

Check with the original sparse matrix.

b(n, 42)

ans = 
   (1,1)       6.0000
   (2,1)       1.5000
   (3,1)       7.0000

If you later want to use a directed graph you may need to use successors or predecessors instead of neighbors.