Compute Harmonic Extension of Trajectory Coordinates

Extends arc-length coordinates from a geodesic trajectory to a tubular neighborhood via the discrete harmonic (Laplace) equation. The resulting coordinates provide a smooth parameterization of the neighborhood that respects the graph structure.

Usage

compute.harmonic.extension(
  adj.list,
  weight.list,
  trajectory,
  tube.radius = 2,
  tube.type = c("hop", "geodesic"),
  use.edge.weights = TRUE,
  max.iterations = 1000L,
  tolerance = 1e-08,
  basin.restriction = NULL,
  verbose = TRUE
)

Arguments

adj.list

Graph adjacency list (1-based indexing).

weight.list

Edge weight list (edge lengths).

trajectory

Integer vector of trajectory vertices in order from minimum to maximum (1-based indexing).

tube.radius

Numeric; radius of tubular neighborhood. Interpretation depends on tube.type.

tube.type

Character; type of radius measurement. One of:

"hop"

Combinatorial distance: count of edge traversals. Fast (BFS), but treats all edges equally.

"geodesic"

Geometric distance: sum of edge weights along shortest path. Respects edge lengths, excluding geometrically distant vertices even if few hops away.

use.edge.weights

Logical; if TRUE (default), use inverse edge length as Laplacian weights for the harmonic solver. If FALSE, use unit weights.

max.iterations

Integer; maximum iterations for Gauss-Seidel solver.

tolerance

Numeric; convergence tolerance for solver.

basin.restriction

Optional integer vector of vertices to restrict the tubular neighborhood. If NULL, no restriction is applied.

verbose

Logical; print progress information.

Value

An object of class "harmonic_extension" containing:

trajectory

Trajectory vertices (1-based).

trajectory.coords

Arc-length coordinates for trajectory vertices.

trajectory.length

Total geodesic length of trajectory.

tubular.vertices

All vertices in tubular neighborhood (1-based).

hop.distances

Hop distance from trajectory for each tubular vertex.

geodesic.distances

Geodesic distance from trajectory for each tubular vertex.

nearest.traj.idx

Index (1-based) into trajectory of the nearest trajectory vertex for each tubular vertex.

extended.coords

Harmonic extension coordinates for all tubular vertices, in same order as tubular.vertices.

n.iterations

Number of solver iterations.

final.max.change

Final maximum coordinate change (convergence).

tube.radius

Tube radius used.

tube.type

Type of radius used ("hop" or "geodesic").

Details

The harmonic extension is computed by solving the discrete Laplace equation with Dirichlet boundary conditions. Trajectory vertices have fixed coordinates determined by their arc-length position along the path. Non-trajectory vertices in the tubular neighborhood receive coordinates via the unique harmonic function that matches the boundary conditions.

The choice of tube.type affects which vertices are included:

Hop-based

Includes all vertices reachable in at most tube.radius edge traversals. Simple and fast, but may include geometrically distant vertices connected by long edges.

Geodesic-based

Includes all vertices within geodesic distance tube.radius from the trajectory. Respects the metric structure of the graph, excluding vertices that are geometrically far even if topologically close.

For graphs with highly variable edge lengths, geodesic-based neighborhoods typically provide more geometrically meaningful results.

See also

select.max.density.trajectory, cell.trajectories

Examples

adj.list <- list(c(2), c(1, 3), c(2, 4), c(3))
weight.list <- list(1, c(1, 1), c(1, 1), 1)
trajectory <- c(1, 2, 3, 4)

hext.hop <- compute.harmonic.extension(
  adj.list, weight.list,
  trajectory = trajectory,
  tube.radius = 1,
  tube.type = "hop",
  verbose = FALSE
)

hext.geo <- compute.harmonic.extension(
  adj.list, weight.list,
  trajectory = trajectory,
  tube.radius = 0.75,
  tube.type = "geodesic",
  verbose = FALSE
)

c(length(hext.hop$tubular.vertices), length(hext.geo$tubular.vertices))