Construct Monotonic Ascent DAG (MADAG) from a Source Vertex

Constructs a Monotonic Ascent DAG rooted at a specified local minimum vertex. The MADAG captures all vertices reachable via monotonically ascending paths, enabling identification of reachable maxima (cells) and enumeration of trajectories within each cell.

Usage

construct.madag(
  adj.list,
  weight.list,
  y,
  source.vertex,
  max.trajectories.per.cell = 10000L,
  compute.path.counts = TRUE,
  enumerate.trajectories = TRUE,
  edge.length.quantile.thld = 1,
  min.cell.support = 1L,
  verbose = FALSE
)

Arguments

adj.list: List of integer vectors. Each element adj.list[[i]] contains the 1-based indices of vertices adjacent to vertex i.
weight.list: List of numeric vectors. Each element weight.list[[i]] contains the edge weights (distances) corresponding to adj.list[[i]].
y: Numeric vector of function values at each vertex.
source.vertex: Integer. The 1-based index of the source vertex (typically a local minimum) from which to construct the MADAG.
max.trajectories.per.cell: Integer. Maximum number of trajectories to enumerate per cell. If exceeded, trajectories are not enumerated (use sampling instead). Default is 10000.
compute.path.counts: Logical. Whether to compute path counts for trajectory counting without full enumeration. Default is TRUE.
enumerate.trajectories: Logical. Whether to enumerate trajectories during construction (up to max.trajectories.per.cell). Default is TRUE.
edge.length.quantile.thld: Numeric in \((0,1]\). Quantile threshold for edge length filtering. Edges longer than this quantile are excluded. Default is 1.0 (no filtering).
min.cell.support: Integer. Minimum cell support size to retain. Default is 1.
verbose: Logical. Whether to print progress messages. Default is FALSE.

Value

A list of class "madag" containing:

source.vertex: The 1-based index of the source vertex.
source.value: The y value at the source vertex.
reachable.vertices: Integer vector of 1-based indices of all vertices reachable from source via ascending paths.
reachable.maxima: Integer vector of 1-based indices of local maxima reachable from source (sinks of the MADAG).
predecessors: Named list where predecessors[[as.character(v)]] contains the 1-based indices of monotonic predecessors of vertex v.
successors: Named list where successors[[as.character(v)]] contains the 1-based indices of monotonic successors of vertex v.
topological.order: Integer vector of vertices in topological order (source first, sinks last).
path.count.from.source: Named integer vector where path.count.from.source[[as.character(v)]] is the number of distinct paths from source to v.
path.count.to.sinks: Named integer vector where path.count.to.sinks[[as.character(v)]] is the number of distinct paths from v to any sink.
cells: List of cell structures, one for each reachable maximum. Each cell contains: min.vertex, max.vertex, min.value, max.value, support, n.trajectories, explicitly.enumerated, bottlenecks, n.clusters.
n.vertices: Number of vertices in the MADAG.
n.cells: Number of cells (reachable maxima).

Details

The MADAG is a directed acyclic graph where edges connect vertices u to v when (u,v) is an edge in the original graph and y[v] > y[u]. The DAG is rooted at the specified source vertex (typically a local minimum) and contains all vertices reachable via monotonically ascending paths.

For each reachable vertex, the MADAG tracks all monotonic predecessors (enabling trajectory enumeration) and successors. Vertices with no successors in the MADAG are local maxima (sinks), defining the cells of the Morse-Smale decomposition.

Unlike smooth manifold settings where trajectory uniqueness is guaranteed by ODE theory, discrete graphs can have multiple trajectories passing through the same vertex, leading to multi-valued cell memberships.

Examples

if (FALSE) { # \dontrun{
## Create a simple graph
adj.list <- list(
  c(2L, 3L),
  c(1L, 3L, 4L),
  c(1L, 2L, 4L),
  c(2L, 3L)
)
weight.list <- list(
  c(1.0, 1.5),
  c(1.0, 1.2, 1.0),
  c(1.5, 1.2, 1.0),
  c(1.0, 1.0)
)
y <- c(0.5, 1.2, 0.8, 2.0)

## Construct MADAG from vertex 1 (local minimum)
madag <- construct.madag(adj.list, weight.list, y, source.vertex = 1L)

## Print summary
print(madag)
} # }