Merge Clustered Basins of Attraction with Trajectory Preservation

Merges basins of attraction for local extrema that belong to the same cluster, creating a hierarchical basin structure where each cluster is represented by a single basin with its highest-valued (for maxima) or lowest-valued (for minima) extremum as the representative. The function preserves complete gradient flow information including predecessors and terminal extrema for all absorbed basins, enabling complete trajectory reconstruction in downstream analyses.

Usage

# S3 method for class 'clustered.basins'
merge(x, y, extrema.type, edgelen.list = NULL, ...)

Arguments

x: An object of class "basins_of_attraction" returned by compute.basins.of.attraction with gradient basin structures including predecessors and terminal extrema. This object contains the original basin structure before merging.
y: An object returned by cluster.local.extrema containing cluster assignments and basin metadata for the extrema type to be merged.
extrema.type: Character string specifying which type of extrema were clustered. Must be either "max" for local maxima or "min" for local minima. This should match the extrema.type used in the clustering step.
edgelen.list: Optional list of numeric vectors containing edge lengths, with the same structure as the adjacency list. Used to compute geodesic paths between absorbed and representative extrema. If NULL, hop distances are used.
...: Additional arguments (currently ignored).

Value

An object of class "basins_of_attraction" with the same structure as the input x but with clustered basins merged. The object contains:

lmin_basins

List of basin structures for local minima (merged if extrema.type = "min"). Each basin now includes:

Standard basin components (vertex, value, hop_idx, basin_df, etc.)
predecessors: Integer vector for trajectory reconstruction
terminal_extrema: Vector of terminal extrema indices
absorbed_extrema: List of absorbed basin structures (if any)

lmax_basins

List of basin structures for local maxima (merged if extrema.type = "max"), with the same structure as lmin_basins.

n_vertices

Total number of vertices in the graph.

y

Copy of the input function values.

merge.info

List containing detailed information about the merging operation with components:

extrema.type

Type of extrema that were merged ("max" or "min").

n.clusters

Number of clusters identified.

n.merged

Number of clusters that involved merging (size > 1).

cluster.representatives

Named character vector mapping cluster IDs to representative basin labels.

absorbed.extrema

Data frame with one row per absorbed extremum containing columns:

absorbed.label: Original label of the absorbed extremum.
absorbed.vertex: Vertex index of the absorbed extremum.
absorbed.value: Function value at the absorbed extremum.
representative.label: Label of the representative basin that absorbed this extremum.
representative.vertex: Vertex index of the representative.
representative.value: Function value at the representative.
y.barrier: Height of monotonicity barrier crossed.
cluster.id: Cluster identifier.

basin.size.changes

Data frame showing how basin sizes changed due to merging, with columns label, original.size, merged.size, size.increase.

Details

When multiple local extrema have highly overlapping or nested basins of attraction, they often represent the same geometric feature fragmented by noise or sampling artifacts. This function addresses the problem by consolidating such extrema into unified basin structures while maintaining complete trajectory information.

We begin by identifying cluster representatives according to a natural ordering principle. For maxima, we select the extremum with the largest function value as the representative, since it corresponds to the highest point in the cluster. For minima, we select the extremum with the smallest function value, corresponding to the lowest point. This choice ensures that the representative captures the most extreme manifestation of the geometric feature.

The merged basin is constructed as the set-theoretic union of all basins within the cluster. This union represents the complete region of influence for the geometric feature. We preserve the basin structure of the representative extremum but extend its vertex set to include all vertices from absorbed basins. Critically, we maintain the complete gradient flow structure by storing absorbed basins as hierarchical substructures.

For each absorbed extremum, we preserve its complete original basin structure including the predecessor map and terminal extrema. This enables reconstruction of gradient trajectories that terminate at absorbed extrema. Additionally, we compute absorption metadata including the geodesic path connecting the absorbed extremum to the representative and the height of the monotonicity barrier crossed during absorption. This information proves essential for gradient flow cell analysis, where trajectories may pass through or terminate at absorbed extrema.

The hierarchical structure supports flexible downstream analyses. For strict monotonicity testing, trajectories can be truncated at absorbed extrema. For permissive analyses, trajectories can be extended through absorbed extrema using the stored geodesic paths, with appropriate flagging of monotonicity violations. The absorption metadata enables assessment of spuriousness, as extrema absorbed over small barriers are more likely to be noise artifacts.

The output object retains the structure of a standard basins of attraction result but includes additional hierarchical metadata. This design ensures compatibility with existing analysis pipelines while providing the complete information needed for advanced gradient flow analyses.

Examples

if (FALSE) { # \dontrun{
# Compute gradient basins of attraction
basins <- compute.basins.of.attraction(adj.list, weight.list, y)

# Generate basin summary
basin.df <- summary(basins, edgelen.list)

# Cluster local maxima
max.clusters <- cluster.local.extrema(basins,
                                      edgelen.list,
                                      extrema.type = "max",
                                      overlap.threshold = 0.15)

# Merge clustered basins with trajectory preservation
merged.basins <- merge.clustered.basins(basins,
                                        max.clusters,
                                        extrema.type = "max",
                                        edgelen.list = edgelen.list)

# Examine merge information
print(merged.basins$merge.info$absorbed.extrema)

# Access absorbed basin structures for trajectory reconstruction
rep.basin <- merged.basins$lmax_basins[[1]]
if (length(rep.basin$absorbed_extrema) > 0) {
  absorbed <- rep.basin$absorbed_extrema[[1]]
  cat("Absorbed extremum at vertex:", absorbed$vertex, "\n")
  cat("Original basin size:", nrow(absorbed$original_basin_df), "\n")
  cat("Y barrier crossed:", absorbed$absorption_info$y_barrier, "\n")

  # Can still reconstruct trajectories in absorbed basin
  v <- absorbed$original_basin_df[1, 1]  # Pick a vertex
  traj <- extract.gradient.trajectory.from.structure(absorbed, v)
}

# For gradient flow cell analysis
# Trajectories terminating at absorbed extrema can be identified
absorbed.vertices <- sapply(rep.basin$absorbed_extrema, function(a) a$vertex)
# Check if any terminal extrema are absorbed
absorbed.terminals <- intersect(rep.basin$terminal_extrema, absorbed.vertices)
} # }