Skip to contents

Compute Gradient Flow Complex

Source: R/compute_gfc.R
compute.gfc.Rd

This function computes the initial basins of attraction for a gradient flow and applies a sequence of filtering and merging operations to produce a refined basin structure. The refinement process includes filtering by relative values, clustering and merging similar extrema, and removing extrema based on geometric characteristics.

Usage

compute.gfc(
  adj.list,
  edge.length.list,
  fitted.values,
  edge.length.quantile.thld = 0.9,
  min.rel.value.max = 1.1,
  max.rel.value.min = 0.9,
  max.overlap.threshold = 0.15,
  min.overlap.threshold = 0.15,
  p.mean.nbrs.dist.threshold = 0.9,
  p.mean.hopk.dist.threshold = 0.9,
  p.deg.threshold = 0.9,
  min.basin.size = 10,
  expand.basins = TRUE,
  hop.k = 2,
  apply.relvalue.filter = TRUE,
  apply.maxima.clustering = TRUE,
  apply.minima.clustering = TRUE,
  apply.geometric.filter = TRUE,
  with.trajectories = FALSE,
  verbose = FALSE,
  modulation = "CLOSEST",
  density = NULL,
  rtcb.params = NULL,
  min.n.trajectories = 0L,
  store.trajectories = with.trajectories,
  max.trajectory.length = 10000L,
  symmetric.seeding = TRUE
)

Arguments

adj.list

Adjacency list representation of the graph structure

edge.length.list

List of edge lengths corresponding to the adjacency list

fitted.values

Numeric vector of fitted values at each vertex

edge.length.quantile.thld

Numeric value in (0, 1] specifying the quantile of the graph's edge length distribution to use as a threshold for basin construction. This parameter prevents "basin jumping" pathology by excluding long edges that may cause trajectories to skip over intermediate critical points.

min.rel.value.max

Minimum relative value threshold for maxima (default: 1.1)

max.rel.value.min

Maximum relative value threshold for minima (default: 0.9)

max.overlap.threshold

Overlap threshold for clustering maxima (default: 0.15)

min.overlap.threshold

Overlap threshold for clustering minima (default: 0.15)

p.mean.nbrs.dist.threshold

Threshold for mean nearest neighbors distance percentile (default: 0.9)

p.mean.hopk.dist.threshold

Threshold for mean hop-k distance percentile (default: 0.9)

p.deg.threshold

Threshold for degree percentile (default: 0.9)

min.basin.size

Minimum basin size threshold. Extrema with basins containing fewer than this many vertices are removed. Default is 10.

expand.basins

Logical indicating whether to expand basins to cover all graph vertices (default: TRUE). When TRUE, vertices not covered by any retained basin are assigned to the nearest basin based on shortest path distance in the weighted graph. This ensures complete coverage after filtering removes spurious extrema.

hop.k

Parameter for hop-k distance calculation in summary (default: 2)

apply.relvalue.filter

Logical indicating whether to apply relative value filtering (default: TRUE)

apply.maxima.clustering

Logical indicating whether to cluster and merge maxima (default: TRUE)

apply.minima.clustering

Logical indicating whether to cluster and merge minima (default: TRUE)

apply.geometric.filter

Logical indicating whether to apply geometric filtering (default: TRUE)

with.trajectories

Set to TRUE for the function to return gradient trajectories.

verbose

Logical indicating whether to print progress messages (default: FALSE)

modulation

Character scalar controlling how basins/trajectories are constructed. Supported modes are:

"CLOSEST"

Trajectory-first construction (default). At each step, follow the shortest adjacent edge that gives strict monotone progress (\(y(u) > y(v)\) for ascent and \(y(u) < y(v)\) for descent).

"GEODESIC"

Extrema-first geodesic basin construction via compute.basins.of.attraction. Basins are grown from local extrema using monotone reachability with the edge-length quantile constraint.

"RTCB"

Extrema-first relaxed trajectory-constrained basin construction. Uses an n.min-limited candidate region, constrained multi-label path search with Option 1/2 monotonicity controls, and boundary-aware tolerance scheduling. Parameters are supplied via rtcb.params.

"NONE"

Trajectory-first steepest rule. Choose the monotone neighbor maximizing \(|y(u)-y(v)|\).

"DENSITY"

Trajectory-first density-modulated rule. Choose the monotone neighbor maximizing \(\rho(u)\,|y(u)-y(v)|\). Requires density.

"EDGELEN"

Trajectory-first edge-length-modulated rule. Choose the monotone neighbor maximizing an edge-weighted gradient score that down-weights long edges.

"DENSITY_EDGELEN"

Trajectory-first combined density and edge-length modulation. Requires density.

"GEODESIC" and "RTCB" return a "basins_of_attraction" object. All other modes dispatch to compute.gfc.trajectory and return a "gfc.flow" object.

density

Optional density vector used by density-modulated trajectory modes.

rtcb.params

Optional named list of parameters for modulation = "RTCB". Supported fields are n.min, m.min, q.min, run.max, tau0, kappa, k.max, h.max, d.path.max, eta.step, epsilon.d, eps.num, sink.prune, sink.prune.max.iter, and max.paths.per.sink.

min.n.trajectories

Minimum trajectory count threshold used in trajectory-based mode.

store.trajectories

Logical; store trajectories in trajectory-based mode.

max.trajectory.length

Maximum trajectory length in trajectory-based mode.

symmetric.seeding

Logical; in trajectory-based mode, additionally seed trajectories from local maxima using descending flow.

Value

A list of class "basins_of_attraction" with the following components:

basins

The refined basins object containing:

lmax_basins

Named list of maximum basins, where names correspond to labels (M1, M2, ...) from the summary. Each basin contains a vertex (the extremum location) and basin_df (data frame of basin vertices with gradient flow information).

lmin_basins

Named list of minimum basins, with analogous structure and labels (m1, m2, ...).

y

Numeric vector of function values at each vertex.

adj.list

Adjacency list representation of the graph structure.

edge.length.list

List of edge lengths corresponding to the adjacency list.

n.vertices

Integer giving the number of vertices in the graph.

hop.k

The hop distance parameter used for summary statistics.

summary

A standardized data frame with one row per retained extremum. Core columns are: label, vertex, value, rel.value, type, basin.size.raw, basin.size.exp, hop.index, p.mean.nbrs.dist, p.mean.hopk.dist, degree, and deg.percentile. For compatibility, aliases basin.size, hop.idx, deg, and p.deg are also provided. Minima are labeled m1, m2, ... in order of increasing value; maxima are labeled M1, M2, ... in order of decreasing value.

max.overlap.dist

Symmetric matrix of pairwise overlap distances between maximum basins, with row and column names matching the summary labels. Returns NULL if fewer than two maxima remain after refinement.

min.overlap.dist

Symmetric matrix of pairwise overlap distances between minimum basins, with row and column names matching the summary labels. Returns NULL if fewer than two minima remain after refinement.

max.vertices.list

Named list of integer vectors containing vertex indices for each maximum basin. Names match basin labels from the summary.

min.vertices.list

Named list of integer vectors containing vertex indices for each minimum basin. Names match basin labels from the summary.

expanded.max.vertices.list

If expand.basins = TRUE, a named list of expanded maximum basins covering all graph vertices. Otherwise NULL.

expanded.min.vertices.list

If expand.basins = TRUE, a named list of expanded minimum basins covering all graph vertices. Otherwise NULL.

stage.history

A data frame recording the number of maxima and minima before and after each refinement stage, facilitating reproducible reporting.

parameters

A named list of all parameter values used in the refinement process, enabling exact replication and automated report generation.

If modulation != "GEODESIC", the function returns a "gfc.flow" object from compute.gfc.trajectory.

Details

The refinement process consists of several stages. First, the function computes the initial basins of attraction using the gradient flow structure. These basins capture the regions of influence for each local extremum in the fitted surface.

The relative value filtering stage removes extrema whose values are too close to the center of the fitted-value distribution. The relative-value denominator is mean(y) across all modulation values. Maxima with relative values below min.rel.value.max and minima with relative values above max.rel.value.min are eliminated. This step focuses subsequent analysis on prominent features of the fitted surface.

The clustering stage identifies groups of similar extrema based on basin overlap. When basins share a substantial portion of their vertices, their corresponding extrema likely represent the same underlying feature. The max.overlap.threshold and min.overlap.threshold parameters control the sensitivity of this clustering for maxima and minima respectively.

After clustering, the merging stage combines basins within each cluster into a single basin. The merged basin inherits the extremum with the most extreme value within the cluster. This reduces redundancy in the basin structure while preserving the essential geometric features.

The geometric filtering stage removes extrema whose basins exhibit unusual structural characteristics. Basins with high values of mean hop-k distance or degree percentiles may represent spurious features or boundary artifacts. The thresholds p.mean.hopk.dist.threshold and p.deg.threshold determine which basins to retain based on these geometric measures. Additionally, basins with fewer than min.basin.size vertices are removed as they lack sufficient statistical support.

When expand.basins = TRUE, an additional step assigns uncovered vertices to their nearest retained basin. After filtering spurious extrema, some vertices may not belong to any retained basin. These are reassigned based on shortest path distance in the weighted graph, ensuring complete coverage for downstream analyses that require every vertex to have a basin assignment.

Each filtering stage can be disabled by setting the corresponding logical parameter to FALSE, allowing users to customize the refinement pipeline for specific applications.

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 = "geodesic_reachability" and translate controls explicitly. See gflow-migration.

See also

generate.refinement.report for automated report generation, expand.basins.to.cover for the basin expansion algorithm

Examples

if (FALSE) { # \dontrun{
# Compute refined basins with default parameters
result <- compute.gfc(adj.list,
                                 edge.length.list,
                                 fitted.values,
                                 edge.length.quantile.thld = 0.9,
                                 verbose = TRUE)

# Access the refined basins and summary
refined.basins <- result$basins
basin.summary <- result$summary

# View stage history
print(result$stage.history)

# Generate methods paragraph
report <- generate.refinement.report(result)
cat(report)

# Use custom thresholds for more aggressive filtering
result <- compute.gfc(adj.list, edge.length.list, fitted.values,
                                 edge.length.quantile.thld = 0.9,
                                 min.rel.value.max = 1.2,
                                 max.rel.value.min = 0.8,
                                 min.basin.size = 10,
                                 expand.basins = TRUE,
                                 p.mean.hopk.dist.threshold = 0.85,
                                 verbose = TRUE)

# Skip clustering steps
result <- compute.gfc(adj.list, edge.length.list, fitted.values,
                                 edge.length.quantile.thld = 0.9,
                                 apply.maxima.clustering = FALSE,
                                 apply.minima.clustering = FALSE,
                                 verbose = TRUE)
} # }