Compute Graph Geodesic Distances — graph.geodesic.distances • dgraphs

Compute exact shortest-path distances on a supplied graph, or on a graph constructed from coordinates. These graph distances may approximate a continuous geometric distance; construction alone does not make them exact manifold geodesics. Supply exactly one of graph and points.

Usage

graph.geodesic.distances(
  graph = NULL,
  vertices = NULL,
  stage = "final",
  distance = c("length", "hop"),
  points = NULL,
  graph.type = NULL,
  k = NULL
)

Arguments

graph: A dgraph. Construction arguments cannot accompany a graph.
vertices: Optional unique 1-based vertex indices, in output order. NULL selects all vertices; an empty vector returns a zero-by-zero matrix. Paths may traverse vertices outside the selected subset.
stage: Stored graph stage; defaults to "final". Coordinate input permits only "final".
distance: "length" sums stored lengths (and errors if absent). "hop" explicitly counts edges instead.
points: Finite numeric matrix or data frame, with one point per row and at least one row and column. Cannot accompany graph.
graph.type: Construction for coordinate input: "sknn" (default when omitted) or "mst". Symmetric kNN links a pair if either endpoint selects the other, without pruning or connectivity repair. MST builds a Euclidean minimum spanning tree, retaining zero-length edges for coincident points.
k: Required number of other neighbors for "sknn", with 1 <= k < n. Not accepted for "mst". In particular, k = 1 still constructs a symmetric kNN graph; it never switches to an MST.

Value

A numeric square matrix in the requested vertex order; unreachable pairs have infinite distance. Zero-length edges remain traversable. Row names from points, or adjacency labels from graph, label the matrix when present.

Details

For repeated calculations or more construction options, build a graph separately and supply it via graph. Coordinate construction uses untransformed Euclidean distances. The exact symmetric-neighbor search evaluates all pairs; MST construction uses a dense Prim search with quadratic time and linear auxiliary storage. Selected-vertex output has length(vertices)^2 entries; all-pairs output has n^2 entries.

Examples

graph <- create.graph("chain", 5)
graph.geodesic.distances(graph, vertices = c(1, 5))
#>      [,1] [,2]
#> [1,]    0    4
#> [2,]    4    0
graph.geodesic.distances(create.graph("cycle", 5), distance = "hop")
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    0    1    2    2    1
#> [2,]    1    0    1    2    2
#> [3,]    2    1    0    1    2
#> [4,]    2    2    1    0    1
#> [5,]    1    2    2    1    0
X <- matrix(c(0, 0, 1, 10), ncol = 1)
graph.geodesic.distances(points = X, graph.type = "mst")
#>      [,1] [,2] [,3] [,4]
#> [1,]    0    0    1   10
#> [2,]    0    0    1   10
#> [3,]    1    1    0    9
#> [4,]   10   10    9    0
graph.geodesic.distances(points = X, graph.type = "sknn", k = 1)
#>      [,1] [,2] [,3] [,4]
#> [1,]    0    0    1   10
#> [2,]    0    0    1   10
#> [3,]    1    1    0    9
#> [4,]   10   10    9    0