Skip to contents

Computes Local Extrema Hop Neighborhoods in a Graph Function

Source: R/extrema_utils.R
compute.extrema.hop.nbhds.Rd

Identifies local extrema (minima and maxima) of a function defined on a graph and computes their extremum hop neighborhoods. For each extremum, this function determines the maximum hop distance at which it maintains its extremum property and identifies boundary vertices where this property is first violated.

Usage

compute.extrema.hop.nbhds(adj.list, weight.list, y)

Arguments

adj.list

A list where each element contains the indices of vertices adjacent to vertex i. The list should be 1-indexed (as is standard in R).

weight.list

A list of the same structure as adj.list, where each element contains the weights of edges connecting vertex i to its adjacent vertices.

y

A numeric vector containing function values at each vertex of the graph.

Value

A list with two components:

lmin.hop.nbhds

A list of hop neighborhoods for local minima. Each neighborhood is a list containing:

  • vertex: The vertex index (1-indexed) that is a local minimum

  • hop.idx: The maximum hop distance at which the minimum property holds

  • nbhd.df: A matrix with two columns - vertex indices and their hop distances from the minimum

  • nbhd.bd.df: A matrix with two columns - boundary vertex indices and their function values

lmax.hop.nbhds

A list with the same structure as lmin.hop.nbhds, but for local maxima

Details

A local extremum is a vertex whose function value is more extreme (higher for maxima, lower for minima) than all its adjacent neighbors. The hop neighborhood analysis extends this concept by examining how far the extremum property persists across the graph structure.

For each extremum, the function computes:

  • Its maximum hop radius (hop_idx) where it remains a strict extremum

  • All vertices within this hop radius and their distances

  • The boundary vertices at hop_idx + 1 where the extremum property is first violated

This information is useful for identification of spurious local extrema.

See also

compute.graph.basin.complex for computing the basin complex of extrema, graph.watershed for watershed segmentation based on extrema.

Examples

adj.list <- list(c(2, 3), c(1, 3, 4), c(1, 2, 4), c(2, 3))
weight.list <- list(c(1, 1), c(1, 1, 1), c(1, 1, 1), c(1, 1))
y <- c(0.5, 0.2, 0.8, 0.3)

result <- compute.extrema.hop.nbhds(adj.list, weight.list, y)
names(result)
result$extrema_df[, c("label", "vertex", "value")]