GraphTheory[GeometricGraphs]
NearestNeighborGraph
construct a nearest neighbor or knearest neighbor graph
FarthestNeighborGraph
construct a farthest neighbor or kfarthest neighbor graph
Calling Sequence
Parameters
Options
Description
Definition
Examples
Compatibility
NearestNeighborGraph( P, opts )
NearestNeighborGraph( P, k, opts )
FarthestNeighborGraph( P, opts )
FarthestNeighborGraph( P, k, opts )
P

Matrix or list of lists representing set of points
k
(optional) integer
opts
(optional) one or more options as specified below
directed : truefalse
Specifies whether the resulting graph should be directed or undirected. If directed, an arc exists from a to b if b is among the k nearest or furthest neighbors, depending on which routine was called. If undirected, an edge exists between a to b whenever an arc would exist in either direction in the directed case. The default is false.
norm : positive real or one of Euclidean or infinity.
Specifies the norm to be used in computing distances. The default is 2, the Euclidean norm.
For more information on norms, see LinearAlgebra[Norm].
vertices : list of integers, strings or symbols
Specifies the vertices to be used in the generated graph.
weighted : true or false
If weighted=true, the result is a weighted graph whose edge weights correspond to the distance between points using the specified norm. Default is false.
The NearestNeighborGraph(P,opts) command returns a nearest neighbor graph for the point set P.
The NearestNeighborGraph(P,k,opts) command returns a knearest neighbor graph for the point set P.
The FarthestNeighborGraph(P,opts) command returns a farthest neighbor graph for the point set P.
The FarthestNeighborGraph(P,k,opts) command returns a kfarthest neighbor graph for the point set P.
The parameter P must be a Matrix or list of lists representing a set of points.
Let $P$ be a set of points in an arbitrary number of dimensions and $p$ be a norm.
The directed nearest neighbor graph is the graph in which an arc exists from $a$ to $b$ if $b$ is the nearest point to $a$ in $P$ according to norm $p$.
The directed knearest neighbor graph is the directed graph in which an arc exists from $a$ to $b$ if $b$ is among the $k$ nearest to $a$ in $P$ according to norm $p$.
The undirected nearest neighbor graph and nearest neighbor graphs are obtained from their directed equivalents by simply converting all arcs to undirected edges.
The farthest and kfarthest neighbor graphs are defined similarly by replacing "nearest" with "farthest" in the definition.
The nearest neighbor graph is not guaranteed to be connected.
The (undirected) nearest neighbor graph has the following relationships with other graphs:
The nearest neighbor graph is a subgraph of the Gabriel graph.
The nearest neighbor graph is a subgraph of the sphere of influence graph.
Generate a set of random twodimensional points and draw a nearest neighbor graph and a 2nearest neighbor graph.
$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$
$\mathrm{with}\left(\mathrm{GeometricGraphs}\right)\:$
$\mathrm{points}\u2254\mathrm{LinearAlgebra}:\mathrm{RandomMatrix}\left(60\,2\,\mathrm{generator}=0..100.\,\mathrm{datatype}=\mathrm{float}\left[8\right]\right)$
${\mathrm{points}}{\u2254}\begin{array}{c}\left[\begin{array}{cc}{9.85017697341803}& {82.9750304386195}\\ {86.0670183749663}& {83.3188659363996}\\ {64.3746795546741}& {73.8671607639673}\\ {57.3670557294666}& {2.34399775883031}\\ {23.6234264844933}& {52.6873367387328}\\ {47.0027547350003}& {22.2459488367552}\\ {74.9213491558963}& {62.0471820220718}\\ {92.1513434709073}& {96.3107262637080}\\ {48.2319624355944}& {63.7563267144141}\\ {90.9441877431805}& {33.8527464913022}\\ {\vdots}& {\vdots}\end{array}\right]\\ \hfill {\text{60 \xd7 2 Matrix}}\end{array}$
$\mathrm{NNG}\u2254\mathrm{NearestNeighborGraph}\left(\mathrm{points}\right)$
${\mathrm{NNG}}{\u2254}{\mathrm{Graph\; 1:\; an\; undirected\; unweighted\; graph\; with\; 60\; vertices\; and\; 42\; edge(s)}}$
$\mathrm{DrawGraph}\left(\mathrm{NNG}\right)$
Generate a directed k nearest neighbor graph for k=3 on the same data.
$\mathrm{kNNG}\u2254\mathrm{NearestNeighborGraph}\left(\mathrm{points}\,3\,\mathrm{directed}\right)$
${\mathrm{kNNG}}{\u2254}{\mathrm{Graph\; 2:\; a\; directed\; unweighted\; graph\; with\; 60\; vertices\; and\; 180\; arc(s)}}$
$\mathrm{DrawGraph}\left(\mathrm{kNNG}\right)$
Draw the farthest neighbor graph on the same data.
$\mathrm{FNG}\u2254\mathrm{FarthestNeighborGraph}\left(\mathrm{points}\right)$
${\mathrm{FNG}}{\u2254}{\mathrm{Graph\; 3:\; an\; undirected\; unweighted\; graph\; with\; 60\; vertices\; and\; 58\; edge(s)}}$
$\mathrm{DrawGraph}\left(\mathrm{FNG}\right)$
The GraphTheory[GeometricGraphs][NearestNeighborGraph] and GraphTheory[GeometricGraphs][FarthestNeighborGraph] commands were introduced in Maple 2020.
For more information on Maple 2020 changes, see Updates in Maple 2020.
See Also
GeometricGraphs
GraphTheory[GeometricGraphs][SphereOfInfluenceGraph]
Download Help Document
What kind of issue would you like to report? (Optional)