Compute a tube-lens corridor between two vertices in a weighted graph

Computes the weighted shortest path \(\gamma_{uv}\) between two vertices, forms a graph-metric tube around that path with radius equal to a fraction of the path length, and intersects that tube with the endpoint lens \(d(u,w) \le |\gamma_{uv}|\) and \(d(v,w) \le |\gamma_{uv}|\).

Optionally, the function also computes the stricter excess-filtered variant that keeps only vertices satisfying \(d(u,w) + d(v,w) - |\gamma_{uv}| \le \tau\).

Usage

compute.tube.lens.corridor(
  adj.list,
  weight.list,
  start.vertex,
  end.vertex,
  path.relative.radius = 0.1,
  excess.tol = NA_real_,
  mode = c("base", "excess", "both")
)

Arguments

adj.list: A list of integer vectors describing graph adjacency with 1-based vertex ids.
weight.list: A list of numeric vectors of edge lengths aligned with adj.list.
start.vertex: Integer scalar giving the first endpoint (1-based).
end.vertex: Integer scalar giving the second endpoint (1-based).
path.relative.radius: Non-negative scalar. The tube radius is computed as path.relative.radius * path.length.
excess.tol: Optional non-negative scalar giving the excess tolerance \(\tau\). If omitted for mode = "excess" or "both", it defaults to the computed tube radius.
mode: Character string; one of "base", "excess", or "both".

Value

A list with components:

path.vertices: Weighted shortest path between the endpoints.
path.arc.length: Normalized arc-length coordinate of each path vertex in path.vertices, ranging from 0 at start.vertex to 1 at end.vertex.
path.length: Length of that path.
tube.radius: Absolute tube radius used for the path-centered tube.
excess.tolerance: Excess tolerance used when the excess variant is requested.
tube.vertices: Vertices in the path-centered tube.
tube.geodesic.distances: Geodesic distance from each tube vertex to the path.
corridor.vertices: Vertices in the tube-lens corridor.
t.balance: Balanced longitudinal coordinate for each vertex in corridor.vertices, normalized to [0,1].
harmonic.t: Harmonic longitudinal coordinate for each vertex in corridor.vertices, normalized to [0,1].
distance.to.path: Geodesic distance from each corridor vertex to the shortest path centerline.
excess: Geodesic excess d(u,w) + d(v,w) - path.length for each vertex in corridor.vertices.
excess.vertices: Vertices in the excess-filtered corridor, or NULL when mode = "base".
selected.vertices: The primary selected set for the requested mode.
mode: The requested mode.