Create a Gradient Flow Basin Complex on a Weighted Graph

Constructs a comprehensive topological analysis of a scalar function defined on a graph through identification, clustering, and simplification of gradient flow basins. The function identifies local extrema (minima and maxima), constructs monotonic basins around them, clusters similar basins based on their overlap, and creates a cell complex representing their relationships.

Usage

create.basin.cx(
  adj.list,
  weight.list,
  y,
  basin.merge.overlap.thld = 0.1,
  min.asc.desc.cell.size.thld = 1,
  min.asc.asc.cell.size.thld = 1,
  min.desc.desc.cell.size.thld = 1,
  graph.params = list()
)

Arguments

adj.list: List of integer vectors. Each vector contains indices of vertices adjacent to the corresponding vertex. Indices should be 1-based.
weight.list: List of numeric vectors. Each vector contains weights of edges corresponding to adjacencies in adj.list.
y: Numeric vector of length \(n\), the response values at each graph vertex.
basin.merge.overlap.thld: Numeric value between 0 and 1 specifying the threshold for basin overlap distance below which basins should be merged (default: 0.1). Lower values result in more conservative merging.
min.asc.desc.cell.size.thld: Minimum size threshold for ascending-descending cells (default: 1). Cells with fewer vertices are excluded.
min.asc.asc.cell.size.thld: Minimum size threshold for ascending-ascending cells (default: 1). Cells with fewer vertices are excluded.
min.desc.desc.cell.size.thld: Minimum size threshold for descending-descending cells (default: 1). Cells with fewer vertices are excluded.
graph.params: List of graph parameters.

Value

An object of class "basin_cx" containing:

basins: A list with elements ascending (minima) and descending (maxima), each containing the merged basins following clustering.
local_extrema: A data frame with vertex indices, types (maximum/minimum), labels, and function values for all extrema.
original_y: The original input function values.
harmonic_predictions: Numeric vector of repaired function values after simplification.
cluster_assignments: A named vector showing which cluster each original basin was assigned to.
cluster_mappings: A data frame showing the mapping between original basin labels and merged basin labels.
initial_basin_cx: The original basin complex before clustering and merging.
cells: A cell complex structure with ascending-descending, ascending-ascending, and descending-descending cells representing basin intersections.
basins_df: A data frame summarizing all basins with properties like extremum vertex, function value, relative span, and size.
lmin_basins_df, lmax_basins_df: Data frames containing only minima or maxima basins.
*_dist_mat, *_overlap_dists: Various distance and similarity matrices between basins.

Details

This function performs the following key operations:

Detects local extrema (minima and maxima) on the graph
Constructs monotonic basins around each extremum
Clusters similar basins based on their vertex overlap
Merges basins within clusters to simplify the analysis
Constructs a cell complex from intersections between basins

Each basin represents a region of the graph where the function values change monotonically (either increasing or decreasing) from the local extremum. Basins are labeled as "mx" for minima and "Mx" for maxima, where x is a sequential number.

The cell complex represents intersections between basins and provides insights into the topological structure of the function on the graph. Three types of cells are created:

Ascending-descending cells: Intersections between minimum and maximum basins
Ascending-ascending cells: Intersections between two minimum basins
Descending-descending cells: Intersections between two maximum basins

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

Examples

if (FALSE) { # \dontrun{
# Create a graph with adjacency list and weights
adj_list <- list(c(2,3), c(1,3,4), c(1,2,5), c(2,5), c(3,4))
weight_list <- list(c(1,2), c(1,1,3), c(2,1,2), c(3,1), c(2,1))

# Define a function on vertices
y <- c(2.5, 1.8, 3.2, 0.7, 2.1)

# Create basin complex
basin_cx <- create.basin.cx(adj_list, weight_list, y, basin.merge.overlap.thld = 0.15)

# Examine results
summary(basin_cx)

# Visualize original vs. simplified function
plot(basin_cx, type = "comparison")

# Extract vertices from a specific basin
m1_vertices <- get_basin_vertices(basin_cx, "m1")
} # }