Graph Gradient Flow Analysis

Analyzes the structure of a function defined on a weighted graph by computing gradient trajectories, basins, and Morse-Smale pro-cells. This function identifies local extrema (minima and maxima) and constructs trajectories that follow the gradient of the function across the graph.

The gradient flow computation relies on a scale parameter that defines the local neighborhood size for each vertex, within which the gradient direction is determined. Trajectories are constructed by following these gradient directions to connect local minima to local maxima.

Usage

construct.graph.gradient.flow(
  adj.list,
  weight.list,
  y,
  scale,
  quantile.scale.thld = 0.025,
  with.trajectories = FALSE
)

Arguments

adj.list

List of integer vectors where adj.list[[i]] contains the indices of vertices adjacent to vertex i (using 1-based indexing).

weight.list

List of numeric vectors where weight.list[[i]][j] is the weight of the edge from vertex i to adj.list[[i]][j].

y

Numeric vector of function values at each graph vertex.

scale

Numeric vector of positive scale values for each vertex, controlling the local neighborhood size for gradient computation and extrema detection. If a single value, it is replicated for all vertices.

quantile.scale.thld

Numeric scalar between 0 and 1. Scale values are truncated to the interval (0, quantile(scale, prob = quantile.scale.thld)). Default is 0.025.

with.trajectories

Logical; if TRUE, trajectory information is included in the output. Default is FALSE.

Value

An object of class "ggflow" containing:

local_extrema

Data frame with columns:

vertex_index

Integer; vertex index (1-based)

is_maximum

Integer; 1 for maxima, 0 for minima

label

Character; automatically generated label (e.g., "M1", "m2")

fn_value

Numeric; function value at the extremum

trajectories

List of trajectories (NULL if with.trajectories = FALSE). Each trajectory contains:

vertices

Integer vector of vertex indices forming the trajectory

type

Character string: "LMIN_LMAX", "LMIN_ONLY", "LMAX_ONLY", or "UNKNOWN"

label

Character; trajectory label based on endpoints

basins

List with two components:

ascending

List of basins around local minima

descending

List of basins around local maxima

Each basin contains:

local_min/local_max

Integer; index of extremum vertex

vertices

Integer vector; vertices in the basin

label

Character; basin label

cells

List of gradient flow pro-cells. Each cell contains:

local_min

Integer; index of local minimum vertex

local_max

Integer; index of local maximum vertex

vertices

Integer vector; vertices in the pro-cell

label

Character; cell label

Details

The gradient flow computation uses the scale parameter to determine the local neighborhood for each vertex. For a vertex v, the algorithm finds all shortest paths of length <= scale[v] starting at v, and selects the path with the steepest rate of change in function value. This approach ensures that the gradient direction is determined at an appropriate scale for each part of the graph.

The returned pro-cells partition the graph into regions, where each region contains trajectories flowing from a specific local minimum to a specific local maximum. This decomposition provides insight into the topological structure of the function defined on the graph.

See also

summary.ggflow basins.merge, replace.basin.label

Examples

if (FALSE) { # \dontrun{
# Create a simple grid graph
n <- 10
adj.list <- list()
weight.list <- list()

# Build grid adjacency (simplified example)
for(i in 1:(n*n)) {
  neighbors <- integer()
  weights <- numeric()

  # Add horizontal neighbors
  if(i %% n != 1) {
    neighbors <- c(neighbors, i-1)
    weights <- c(weights, 1.0)
  }
  if(i %% n != 0) {
    neighbors <- c(neighbors, i+1)
    weights <- c(weights, 1.0)
  }

  adj.list[[i]] <- neighbors
  weight.list[[i]] <- weights
}

# Define a function on the graph (e.g., a Gaussian peak)
coords <- expand.grid(x = 1:n/n, y = 1:n/n)
z <- exp(-10 * ((coords$x - 0.5)^2 + (coords$y - 0.5)^2))

# Compute gradient flow
flow <- construct.graph.gradient.flow(
  adj.list,
  weight.list,
  z,
  scale = 2.0,
  with.trajectories = TRUE
)

# Examine results
print(flow$local_extrema)
summary(flow)
} # }