FarthestNeighborGraph - Maple Help

GraphTheory[GeometricGraphs]

 NearestNeighborGraph
 construct a nearest neighbor or k-nearest neighbor graph
 FarthestNeighborGraph
 construct a farthest neighbor or k-farthest neighbor graph

 Calling Sequence NearestNeighborGraph( P, opts ) NearestNeighborGraph( P, k, opts ) FarthestNeighborGraph( P, opts ) FarthestNeighborGraph( P, k, opts )

Parameters

 P - Matrix or list of lists representing set of points k - (optional) integer opts - (optional) one or more options as specified below

Options

 • 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.
 • 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.

Description

 • The NearestNeighborGraph(P,opts) command returns a nearest neighbor graph for the point set P.
 • The NearestNeighborGraph(P,k,opts) command returns a k-nearest 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 k-farthest neighbor graph for the point set P.
 • The parameter P must be a Matrix or list of lists representing a set of points.

Definition

 • 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 k-nearest 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 k-farthest 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.

Examples

Generate a set of random two-dimensional points and draw a nearest neighbor graph and a 2-nearest neighbor graph.

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $\mathrm{with}\left(\mathrm{GeometricGraphs}\right):$
 > $\mathrm{points}≔\mathrm{LinearAlgebra}:-\mathrm{RandomMatrix}\left(60,2,\mathrm{generator}=0..100.,\mathrm{datatype}=\mathrm{float}\left[8\right]\right)$
 ${\mathrm{points}}{≔}\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}\\ {⋮}& {⋮}\end{array}\right]\\ \hfill {\text{60 × 2 Matrix}}\end{array}$ (1)
 > $\mathrm{NNG}≔\mathrm{NearestNeighborGraph}\left(\mathrm{points}\right)$
 ${\mathrm{NNG}}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 60 vertices and 42 edge\left(s\right)}}$ (2)
 > $\mathrm{DrawGraph}\left(\mathrm{NNG}\right)$

Generate a directed k nearest neighbor graph for k=3 on the same data.

 > $\mathrm{kNNG}≔\mathrm{NearestNeighborGraph}\left(\mathrm{points},3,\mathrm{directed}\right)$
 ${\mathrm{kNNG}}{≔}{\mathrm{Graph 2: a directed unweighted graph with 60 vertices and 180 arc\left(s\right)}}$ (3)
 > $\mathrm{DrawGraph}\left(\mathrm{kNNG}\right)$

Draw the farthest neighbor graph on the same data.

 > $\mathrm{FNG}≔\mathrm{FarthestNeighborGraph}\left(\mathrm{points}\right)$
 ${\mathrm{FNG}}{≔}{\mathrm{Graph 3: an undirected unweighted graph with 60 vertices and 58 edge\left(s\right)}}$ (4)
 > $\mathrm{DrawGraph}\left(\mathrm{FNG}\right)$

Compatibility

 • The GraphTheory[GeometricGraphs][NearestNeighborGraph] and GraphTheory[GeometricGraphs][FarthestNeighborGraph] commands were introduced in Maple 2020.