Skip to contents

Compute Gradient Flow Complex Using Trajectory-First Approach

Source: R/gfc_flow.R
compute.gfc.trajectory.Rd

Computes basins of attraction by tracing gradient flow trajectories rather than growing basins outward from extrema. This approach treats gradient flow lines as the fundamental geometric primitives, with basins emerging as the collection of vertices along trajectories sharing the same endpoints. compute.gfc.flow() is kept as a backward-compatible deprecated alias.

Usage

compute.gfc.trajectory(
  adj.list,
  weight.list,
  y,
  density = NULL,
  modulation = c("CLOSEST", "NONE", "DENSITY", "EDGELEN", "DENSITY_EDGELEN"),
  edge.length.quantile.thld = 0.9,
  long.edge.fallback = c("allow_and_flag", "allow", "forbid"),
  apply.relvalue.filter = TRUE,
  min.rel.value.max = 1.1,
  max.rel.value.min = 0.9,
  apply.maxima.clustering = TRUE,
  apply.minima.clustering = TRUE,
  max.overlap.threshold = 0.15,
  min.overlap.threshold = 0.15,
  apply.geometric.filter = TRUE,
  p.mean.nbrs.dist.threshold = 0.9,
  p.mean.hopk.dist.threshold = 0.9,
  p.deg.threshold = 0.9,
  min.basin.size = 10L,
  min.n.trajectories = 0L,
  hop.k = 2L,
  store.trajectories = TRUE,
  max.trajectory.length = 10000L,
  symmetric.seeding = TRUE,
  tie.breaking = TRUE,
  verbose = FALSE
)

compute.gfc.flow(
  adj.list,
  weight.list,
  y,
  density = NULL,
  modulation = c("CLOSEST", "NONE", "DENSITY", "EDGELEN", "DENSITY_EDGELEN"),
  edge.length.quantile.thld = 0.9,
  long.edge.fallback = c("allow_and_flag", "allow", "forbid"),
  apply.relvalue.filter = TRUE,
  min.rel.value.max = 1.1,
  max.rel.value.min = 0.9,
  apply.maxima.clustering = TRUE,
  apply.minima.clustering = TRUE,
  max.overlap.threshold = 0.15,
  min.overlap.threshold = 0.15,
  apply.geometric.filter = TRUE,
  p.mean.nbrs.dist.threshold = 0.9,
  p.mean.hopk.dist.threshold = 0.9,
  p.deg.threshold = 0.9,
  min.basin.size = 10L,
  min.n.trajectories = 0L,
  hop.k = 2L,
  store.trajectories = TRUE,
  max.trajectory.length = 10000L,
  symmetric.seeding = TRUE,
  tie.breaking = TRUE,
  verbose = FALSE
)

Arguments

adj.list

List of integer vectors. Each element adj.list[[i]] contains the 1-based indices of vertices adjacent to vertex i.

weight.list

List of numeric vectors. Each element weight.list[[i]] contains the edge weights (distances) corresponding to adj.list[[i]].

y

Numeric vector of function values at each vertex.

density

Optional numeric vector of density values at each vertex. Required if modulation is "DENSITY" or "DENSITY_EDGELEN". Ignored for "CLOSEST".

modulation

Character string specifying gradient modulation strategy. One of "NONE", "DENSITY", "EDGELEN", "DENSITY_EDGELEN", or "CLOSEST". Default is "CLOSEST". See Details for descriptions of each option.

edge.length.quantile.thld

Numeric in (0,1]. Quantile threshold for edge length filtering during trajectory computation. For non-"CLOSEST" modulations, edges longer than this quantile are not traversed. For "CLOSEST", long.edge.fallback controls what happens when all improving neighbors exceed the threshold. Default is 0.9.

long.edge.fallback

Character policy used by "CLOSEST" when no improving edge is at or below the edge-length threshold. "allow_and_flag" preserves the historical shortest-improving-edge fallback and marks the returned telemetry for attention; "allow" preserves the same path without the attention flag; and "forbid" makes the threshold hard and terminates the trajectory at that vertex. All policies report observed fallback counts. Default is "allow_and_flag".

apply.relvalue.filter

Logical. Whether to filter extrema by relative value. Default is TRUE.

min.rel.value.max

Numeric. Minimum relative value (value/mean(y)) for retaining maxima. Default is 1.1.

max.rel.value.min

Numeric. Maximum relative value for retaining minima. Default is 0.9.

apply.maxima.clustering

Logical. Whether to cluster and merge maxima based on basin overlap. Default is TRUE.

apply.minima.clustering

Logical. Whether to cluster and merge minima. Default is TRUE.

max.overlap.threshold

Numeric in \([0,1]\). Overlap distance threshold for merging maxima basins. Default is 0.15.

min.overlap.threshold

Numeric in \([0,1]\). Overlap distance threshold for merging minima basins. Default is 0.15.

apply.geometric.filter

Logical. Whether to filter by geometric characteristics. Default is TRUE.

p.mean.nbrs.dist.threshold

Numeric in \([0,1]\). Percentile threshold for mean neighbor distance (maxima only). Default is 0.9.

p.mean.hopk.dist.threshold

Numeric in \([0,1]\). Percentile threshold for hop-k distance. Default is 0.9.

p.deg.threshold

Numeric in \([0,1]\). Degree percentile threshold. Default is 0.9.

min.basin.size

Integer. Minimum basin size to retain. Default is 10.

min.n.trajectories

Integer. Minimum number of basin trajectories to retain the basin. Default is 0.

hop.k

Integer. Hop distance for computing summary statistics. Default is 2.

store.trajectories

Logical. Whether to store full trajectory information in the result. Default is TRUE.

max.trajectory.length

Integer. Maximum trajectory length (vertices) before stopping. Prevents infinite loops in degenerate cases. Default is 10000.

symmetric.seeding

Logical. If TRUE, additionally seed trajectories from local maxima (descending) to make the trajectory seeding symmetric with respect to minima and maxima.

tie.breaking

Logical. If TRUE, preserve the historical behavior of adding tiny random noise to globally tied response values before flow construction. Set to FALSE when connected plateaus have already been contracted and only nonadjacent equal values remain.

verbose

Logical. Whether to print progress messages. Default is FALSE.

Value

A list of class "gfc.flow" containing basin and trajectory information. The long.edge.fallback component records the selected policy, per-vertex ascent/descent fallback and blocked-step flags, trajectory step counts, and basin source-vertex counts. See the original function documentation for full details.

Details

The algorithm proceeds as follows:

  1. Identify all local minima using neighborhood comparison

  2. From each local minimum, trace an ascending trajectory following the selected modulation strategy until reaching a local maximum

  3. Optionally (default), seed local maxima with descending trajectories and map them into canonical min-to-max orientation

  4. Assign trajectory vertices to both endpoint basins

  5. For any unvisited vertices, trace both ascending and descending trajectories, joining them at that vertex

  6. Apply the filtering/merging pipeline (relative value filtering, overlap-based clustering, geometric filtering)

Retained extrema are numbered by descending basin size.

Modulation Options

The modulation parameter controls how the next vertex is selected at each step of the trajectory:

"NONE"

Standard steepest ascent/descent. Selects the neighbor maximizing the function difference \(|y(u) - y(v)|\). This is the classical gradient flow approach but may cause basin jumping near separatrices when adjacent basins have very different gradient magnitudes.

"DENSITY"

Density-modulated flow. Multiplies the gradient by vertex density to prefer higher-density regions: \(\rho(u) \cdot \Delta y\).

"EDGELEN"

Edge-length modulated flow. Multiplies the gradient by a KDE-based edge length weight that down-weights atypically long edges: \(w(d(v,u)) \cdot \Delta y\). This prevents basin jumping through outlier edges but still uses a multiplicative score that can be dominated by extreme gradient contrasts.

"DENSITY_EDGELEN"

Combined density and edge-length modulation.

"CLOSEST"

Lexicographic closest ascending neighbor rule. This implements a two-level selection:

  1. Filter to ascending neighbors \(u\) satisfying \(y(u) > y(v)\).

  2. Among those ascending neighbors, select the one with minimum edge distance \(d(v,u)\).

Equal edge lengths are resolved by the smaller target-vertex identifier. This approach minimizes basin-jumping errors by taking the smallest step that makes progress. Unlike multiplicative scores, the lexicographic rule cannot be overridden by extreme gradient contrasts between adjacent basins. When every improving edge exceeds the standard edge-length threshold, long.edge.fallback determines whether the shortest such edge is used.

Lifecycle

This exported name is retired and always raises a gflow_basin_lifecycle_error. Historical arguments and return descriptions below document archived calls, not a runnable estimator. Use create.basin.complex with method = "trajectory_flow" and translate controls explicitly. See gflow-migration.

This exported name is retired and always raises a gflow_basin_lifecycle_error. Historical arguments and return descriptions below document archived calls, not a runnable estimator. Use create.basin.complex with method = "trajectory_flow" and translate controls explicitly. See gflow-migration.

See also

compute.gfc for the extrema-first approach

Examples

if (FALSE) { # \dontrun{
## Create a simple graph
adj.list <- list(
  c(2L, 3L),
  c(1L, 3L, 4L),
  c(1L, 2L, 4L),
  c(2L, 3L)
)
weight.list <- list(
  c(1.0, 1.5),
  c(1.0, 1.2, 1.0),
  c(1.5, 1.2, 1.0),
  c(1.0, 1.0)
)
y <- c(0.5, 1.2, 0.8, 2.0)

## Standard steepest ascent (may have basin jumping issues)
result.steep <- compute.gfc.trajectory(adj.list, weight.list, y,
                                 modulation = "NONE")

## Edge-length modulated (reduces but doesn't eliminate jumping)
result.edgelen <- compute.gfc.trajectory(adj.list, weight.list, y,
                                   modulation = "EDGELEN")

## Closest ascending neighbor (lexicographic, no tuning needed)
result.closest <- compute.gfc.trajectory(adj.list, weight.list, y,
                                   modulation = "CLOSEST")
} # }