nearest

Nearest neighbors within radius

collapse all in page

Syntax

nodeIDs = nearest(G,s,d)
nodeIDs = nearest(G,s,d,Name,Value)
[nodeIDs,dist] = nearest(___)

Description

example

nodeIDs = nearest(G,s,d) returns all nodes in graph G that are within distance d from node s. If the graph is weighted (that is, if G.Edges contains a variable Weight), then those weights are used as the distances along the edges in the graph. Otherwise, all edge distances are taken to be 1.

example

nodeIDs = nearest(G,s,d,Name,Value) uses additional options specified by one or more name-value pair arguments. For example, if G is a weighted graph, then nearest(G,s,d,'Method','unweighted') ignores the edge weights in graph G and instead treats all edge weights as 1.

example

[nodeIDs,dist] = nearest(___) additionally returns the distance to each of the nearest neighbors, such that dist(j) is the distance from source node s to the node nodeIDs(j). You can use any of the input argument combinations in previous syntaxes.

Examples

collapse all

Open Live Script

Create and plot a graph with weighted edges.

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

Determine which nodes are within a radius of 15 from node 1.

nn = nearest(G,1,15)
nn = 9×1

     5
     7
     2
     3
     4
     6
     8
    12
     9

Highlight the source node as green and the nearest neighbors as red.

highlight(p,1,'NodeColor','g')
highlight(p,nn,'NodeColor','r')

Open Live Script

Create and plot a graph with weighted edges.

s = [1 1 1 2 2 6 6 7 7 3 3 9 9 4 4 11 11 8];
t = [2 3 4 5 6 7 8 5 8 9 10 5 10 11 12 10 12 12];
weights = [10 10 10 10 10 1 1 1 1 1 1 1 1 1 1 1 1 1];
G = graph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Determine which nodes are within a radius of 5 from node 3, and return the distance to each node.

[nn,dist] = nearest(G,3,5)
nn = 9×1

     9
    10
     5
    11
     4
     7
    12
     6
     8


dist = 9×1

     1
     1
     2
     2
     3
     3
     3
     4
     4
Open Live Script

Create and plot a directed graph with weighted edges.

s = {'a' 'a' 'a' 'b' 'c' 'c' 'e' 'f' 'f'};
t = {'b' 'c' 'd' 'a' 'a' 'd' 'f' 'a' 'b'};
weights = [1 1 1 2 2 2 2 2 2];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight)

Determine the nearest nodes within a radius of 1 from node 'a', measured by outgoing path distance from node 'a'.

nn_out = nearest(G,'a',1)
nn_out = 3x1 cell
    {'b'}
    {'c'}
    {'d'}

Determine all of the nodes that have incoming paths leading to node 'a' by specifying the radius as Inf.

nn_in = nearest(G,'a',Inf,'Direction','incoming')
nn_in = 4x1 cell
    {'b'}
    {'c'}
    {'f'}
    {'e'}

Input Arguments

collapse all

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

Source node, specified as a node index or a node name in one of the forms in this table.

ValueExample
Scalar node index1
Character vector node name'A'
String scalar node name"A"

Example: nearest(G,3,1)

Example: nearest(G,'a',5)

Neighbor distance radius, specified as a numeric scalar.

Example: nearest(G,3,1)

Example: nearest(G,'a',2.5)

Name-Value Pair Arguments

Specify optional comma-separated pairs of Name,Value arguments. Name is the argument name and Value is the corresponding value. Name must appear inside quotes. You can specify several name and value pair arguments in any order as Name1,Value1,...,NameN,ValueN.

Example: [nodeIDs,dist] = nearest(G,s,5,'Method','unweighted','Direction','incoming')

Note

The 'Direction' option can only be specified with directed graphs.

Direction of distance measurement, specified as the comma-separated pair consisting of 'Direction' and one of the options in this table.

OptionDescription
'outgoing' (default)Distances are calculated using paths going out from source node s.
'incoming'Distances are calculated using paths coming in to source node s.

Example: nearest(G,s,d,'Direction','incoming')

Shortest path algorithm, specified as the comma-separated pair consisting of 'Method' and one of the options in this table.

OptionDescription
'auto' (default)

The 'auto' option automatically selects the algorithm:

  • 'unweighted' is used for graph and digraph inputs with no edge weights.

  • 'positive' is used for all graph inputs that have edge weights, and requires the weights to be nonnegative. This option is also used for digraph inputs with nonnegative edge weights.

  • 'mixed' is used for digraph inputs whose edge weights contain some negative values. The graph cannot have negative cycles.

'unweighted'

Breadth-first computation that treats all edge weights as 1.

'positive'

Dijkstra algorithm that requires all edge weights to be nonnegative.

'mixed' (only for digraph)

Bellman-Ford algorithm for directed graphs that requires the graph to have no negative cycles.

While 'mixed' is slower than 'positive' for the same problem, 'mixed' is more versatile as it allows some edge weights to be negative.

Note

For most graphs, 'unweighted' is the fastest algorithm, followed by 'positive' and 'mixed'.

Example: nearest(G,s,d,'Method','positive')

Output Arguments

collapse all

Nearest neighbor node IDs, returned as node indices if s is numeric, or as node names if s is a node name. The nodes are sorted from nearest to furthest. nodeIDs is empty if no nodes are within the specified distance. nodeIDs never contains the source node s even if the graph has self-loops.

Use H = subgraph(G,[s; nodeIDs]) to extract a subgraph of the nearest neighbors from the original graph G.

Neighbor distances, returned as a vector. dist(j) is the distance from source node s to neighboring node nodeIDs(j).

See Also

| | | | |

Topics

Introduced in R2016a

MATLAB Documentation

Support