Detect Adaptive Local Extrema in a Graph

Identifies local maxima or minima in a graph based on vertex function values. For each vertex, examines neighbors in increasing graph distance up to a maximum radius. Accepts an extremum when sufficiently many neighbors have strictly lower (for maxima) or higher (for minima) values before the first neighbor that violates this condition.

Usage

detect.adaptive.extrema(
  adj.list,
  weight.list,
  y,
  max.radius,
  min.neighborhood.size,
  detect.maxima = TRUE,
  custom.prefix = NULL
)

Arguments

adj.list

A list where each element contains integer indices of vertices adjacent to the corresponding vertex. Must have length equal to the number of vertices in the graph.

weight.list

A list where each element contains numeric weights of edges from the corresponding vertex. weight.list[[i]][j] is the weight of the edge from vertex i to vertex adj.list[[i]][j].

y

A numeric vector of function values at each vertex. Must have the same length as adj.list.

max.radius

Positive numeric value specifying the maximum radius for neighborhood search.

min.neighborhood.size

Positive integer specifying the minimum number of neighbors, excluding the center, required for a vertex to be considered an extremum.

detect.maxima

Logical; if TRUE (default), detect local maxima; if FALSE, detect local minima.

custom.prefix

Character string to use as prefix for extrema labels. If NULL (default), uses "M" for maxima and "m" for minima.

Value

An object of class "gflow_local_extrema", which is a list containing:

vertices

Integer vector of vertex indices identified as extrema

values

Numeric vector of function values at the extrema

radii

Numeric vector of neighborhood radii where extremum property holds

neighborhood_sizes

Integer vector of neighborhood sizes, excluding the center

neighborhood_vertices

List of integer vectors of accepted neighbors, excluding the center

graph_diameter

Graph diameter estimate returned by the backend

is_maxima

Logical vector indicating whether each extremum is a maximum (TRUE) or minimum (FALSE)

type

Character vector with values "Maximum" or "Minimum" for each extremum

labels

Character vector of labels for each extremum (e.g., "M1", "M2" for maxima)

detect.maxima

Scalar logical recording the requested detection type, including when no extrema are found

Details

The radius reported for an extremum is the distance to its last accepted neighbor. A vertex can qualify at a smaller radius even if a more distant vertex within max.radius has a more extreme value. Equal function values violate the strict comparison. Neighbors at equal graph distance are processed individually by the current backend, so the accepted neighborhood can contain only part of a distance shell.

This function replaces gflow::detect.local.extrema(). It differs from dgraphs::detect.local.extrema(), which tests the full radius, allows equal function values, and includes the center in neighborhood counts. The result classes and S3 methods are separate.

The implementation uses a C++ backend for computational efficiency, particularly beneficial for large graphs.

See also

summary.gflow_local_extrema for summarizing results, plot.gflow_local_extrema for visualization

Examples

# Create a simple chain graph
adj.list <- list(c(2), c(1,3), c(2,4), c(3,5), c(4))
weight.list <- list(c(1), c(1,1), c(1,1), c(1,1), c(1))
y <- c(1, 3, 2, 5, 1)  # Function values with peaks at vertices 2 and 4

# Detect maxima
maxima <- detect.adaptive.extrema(adj.list, weight.list, y,
                               max.radius = 2,
                               min.neighborhood.size = 2)
print(maxima$vertices)  # Should identify vertices 2 and 4

# Detect minima
minima <- detect.adaptive.extrema(adj.list, weight.list, y,
                               max.radius = 2,
                               min.neighborhood.size = 2,
                               detect.maxima = FALSE)
print(minima$vertices)  # Should identify vertices 1, 3, and 5