Skip to contents

Compute Gradient Flow Information for Vertices in a Graph

Source: R/graph_gradient_flow_basins.R
compute.graph.gradient.flow.Rd

Analyzes the gradient flow structure of a weighted graph by computing basins of attraction for local maxima and minima, determining flow directions at each vertex, and identifying ambiguous vertices that belong to multiple basins.

Usage

compute.graph.gradient.flow(
  adj.list,
  weight.list = NULL,
  y,
  lmax.list,
  lmin.list,
  verbose = FALSE
)

Arguments

adj.list

List where adj.list[[i]] contains indices of vertices adjacent to vertex i. Must be a valid adjacency list representation.

weight.list

List where weight.list[[i]] contains positive weights of edges from vertex i to corresponding vertices in adj.list[[i]]. If NULL, uniform weights of 1 are used.

y

Numeric vector of values at each vertex. Must have the same length as adj.list.

lmax.list

List of local maxima information. See lmax.basins for format details.

lmin.list

List of local minima information. See lmin.basins for format details.

verbose

Logical; if TRUE, prints progress messages during computation. Default is FALSE.

Value

A list with the following components:

flow_directions

List where each element describes the gradient flow at a vertex.

lmax_basin_assignment

Integer vector indicating which maximum basin each vertex belongs to, with NA for unassigned vertices

lmin_basin_assignment

Integer vector indicating which minimum basin each vertex belongs to, with NA for unassigned vertices

ambiguous_vertices

Integer vector of vertices that belong to multiple basins of the same type

basin_stats

List containing statistics about the basins: - n_max_basins: Number of maximum basins - n_min_basins: Number of minimum basins - coverage: Proportion of vertices assigned to at least one basin - max_basin_sizes: Named vector of maximum basin sizes - min_basin_sizes: Named vector of minimum basin sizes

Details

The function performs the following steps:

  • Computes basins of attraction for all local maxima using lmax.basins

  • Computes basins of attraction for all local minima using lmin.basins

  • Assigns each vertex to appropriate basins, identifying conflicts

  • Determines gradient flow directions based on neighboring values

  • For unassigned vertices, attempts to infer basin membership from neighbors

Gradient flow directions indicate the steepest ascent and descent paths from each vertex. When edge weights are provided, they influence the determination of these paths by scaling the effective gradients.

References

Morse, M. (1934). The Calculus of Variations in the Large. American Mathematical Society.

Forman, R. (1998). Morse theory for cell complexes. Advances in Mathematics, 134(1), 90-145.

See also

lmax.basins, lmin.basins, set.boundary

Examples

if (FALSE) { # \dontrun{
# Create example graph
adj.list <- list(c(2), c(1,3), c(2,4,5), c(3), c(3))
y <- c(0.2, 0.5, 0.8, 1.0, 0.1)

# Define extrema
lmax.list <- list(list(lmax=4, vertices=c(4), label="peak"))
lmin.list <- list(list(lmin=5, vertices=c(5), label="valley"))

# Compute gradient flow
flow_info <- compute.graph.gradient.flow(adj.list, NULL, y,
                                         lmax.list, lmin.list)

# Examine results
print(flow_info$basin_stats)
} # }