Skip to contents

Compute Basins of Attraction for Local Extrema

Source: R/compute_basins_of_attraction.R
compute.basins.of.attraction.Rd

This function identifies all local extrema in a weighted graph and computes their basins of attraction. A basin of attraction for a local extremum consists of all vertices reachable via monotone paths: ascending paths for minima and descending paths for maxima.

Usage

compute.basins.of.attraction(
  adj.list,
  weight.list,
  y,
  edge.length.quantile.thld = 0.9,
  with.trajectories = FALSE
)

Arguments

adj.list

A list of integer vectors representing the graph's adjacency structure. Element i contains the indices of vertices adjacent to vertex i. Indices should be 1-based.

weight.list

A list of numeric vectors containing edge weights. Element i contains weights corresponding to the edges in adj.list[[i]]. Must have the same structure as adj.list.

y

A numeric vector of function values at each vertex. The length must equal the number of vertices (i.e., length(adj.list)).

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.

The parameter is always interpreted as a quantile. For example, edge.length.quantile.thld = 0.75 means that only edges with length at or below the 75th percentile are used during basin construction; edges longer than this threshold are excluded.

Common values:

  • 0.50: Use only edges at or below median length (conservative)

  • 0.75: Use edges at or below third quartile (moderate)

  • 0.90: Exclude only the longest 10\

  • 1.00: Use all edges, no constraint (original behavior)

During basin construction, an edge is traversed only if both the monotonicity condition is satisfied AND the edge length does not exceed the computed threshold. This geometric constraint is essential when the graph contains edges spanning large distances relative to local neighborhood scales.

with.trajectories

Set to TRUE for the function to return gradient trajectories.

Value

An object of class "basins_of_attraction" containing:

lmin_basins

A list of basin structures for local minima. Each structure contains:

  • vertex: The vertex index (1-based)

  • value: Function value at the vertex

  • hop_idx: Maximum hop distance within the basin

  • basin_df: Matrix with columns (vertex, hop_distance) for all basin members

  • basin_bd_df: Matrix with columns (vertex, y_value) for boundary vertices

lmax_basins

A list of basin structures for local maxima with the same structure as lmin_basins

n_vertices

Total number of vertices in the graph

y

Copy of the input function values

Details

The basin of attraction captures the region of influence for each local extremum. For a local minimum, the basin includes all vertices from which the function value strictly increases along every edge of the path leading back to the minimum. Similarly, for a local maximum, the basin includes vertices from which the function value strictly decreases along paths to the maximum.

The algorithm performs a breadth-first search from each local extremum, exploring only those edges that maintain the monotonicity property. A vertex belongs to the basin if there exists at least one monotone path connecting it to the extremum. The search continues until no new vertices satisfying the monotonicity constraint can be reached.

Each basin structure returned by the function contains the extremum vertex index, its function value, the maximum hop distance within the basin, a complete mapping of all basin vertices to their hop distances from the extremum, and a boundary map identifying vertices adjacent to but outside the basin.

The function uses 0-based indexing internally for C++ compatibility but returns results with 1-based indexing following R conventions.

Note

The parameter must satisfy 0 < edge.length.quantile.thld <= 1. Values outside this range will trigger an error. To disable edge length filtering entirely, use edge.length.quantile.thld = 1.0.

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

summary.basins_of_attraction for generating summary statistics

Examples

if (FALSE) { # \dontrun{
# Create a simple graph
adj.list <- list(
  c(2, 3),      # vertex 1 connects to 2, 3
  c(1, 3, 4),   # vertex 2 connects to 1, 3, 4
  c(1, 2, 4),   # vertex 3 connects to 1, 2, 4
  c(2, 3)       # vertex 4 connects to 2, 3
)

weight.list <- list(
  c(1.0, 1.0),
  c(1.0, 1.0, 1.0),
  c(1.0, 1.0, 1.0),
  c(1.0, 1.0)
)

# Function values with one minimum and one maximum
y <- c(5.0, 2.0, 3.0, 6.0)

# Compute basins
basins <- compute.basins.of.attraction(adj.list, weight.list, y)

# Examine structure
print(basins)

# Access individual basins
if (length(basins$lmin_basins) > 0) {
  min_basin <- basins$lmin_basins[[1]]
  cat("Minimum at vertex:", min_basin$vertex, "\n")
  cat("Basin size:", nrow(min_basin$basin_df), "\n")
}
} # }