Constructs the Morse-Smale complex of a function defined on graph vertices

Constructs the Morse-Smale complex of a function defined on graph vertices

Usage

graph.MS.cx(graph, hop.list = NULL, core.graph, Ey)

Arguments

graph

A list representing the graph adjacency list. Each element of the list should be an integer vector specifying the neighboring vertex indices for a given vertex. The vertex indices should be 1-based.

hop.list

Optional list of hop constraints for gradient flow. If NULL, no constraints are applied. If provided, should contain hop information for each vertex.

core.graph

A list representing the core graph adjacency list used to constrain gradient flow paths. Each element should be an integer vector of 1-based neighbor indices.

Ey

A numeric vector of function values at vertices.

Value

An R list of class "graphMScx" with the following components:

• trajectories: A list where element i contains the gradient flow trajectory for vertex i (both descending and ascending paths)

• lmax_to_lmin: A list where element i contains indices of local minima connected to the i-th local maximum by gradient trajectories

• lmin_to_lmax: A list where element i contains indices of local maxima connected to the i-th local minimum by gradient trajectories

• local_maxima: Integer vector containing indices of all local maxima

• local_minima: Integer vector containing indices of all local minima

• procell_keys: List of integer pairs (max_idx, min_idx) identifying each pro-cell

• procells: List where element i contains all vertices in the i-th pro-cell

• cells: List where cells[[i]] contains the connected components of pro-cell i after removing its defining extrema

Details

This function computes gradient flow trajectories and Morse-Smale complex components for a function Ey defined on vertices of a graph G = pIG_k^h(X).

Key concepts and definitions:

1. Gradient Flow Trajectories:

   • For each vertex v, computes ascending and descending trajectories

   • Ascending trajectory follows steepest ascent path to local maximum

   • Descending trajectory follows steepest descent path to local minimum

   • Trajectories are constrained to valid paths in core graph pIG_k(X)

2. Morse-Smale Pro-cells:

   • A pro-cell is defined by a pair (M,m) where M is a local maximum and m is a local minimum

   • Contains all vertices that lie on gradient trajectories starting at m and ending at M

   • Formally: pro-cell(M,m) = {v \(\in\) V | there exists a trajectory through v from m to M}

3. Morse-Smale Cells:

   • Connected components of pro-cells after removing their defining extrema

   • For pro-cell(M,m), compute components of subgraph induced by: vertices in pro-cell(M,m) \ {M,m}

   • Unlike classical Morse theory, cells may not be disjoint

Implementation Overview:

1. Trajectory Computation: a. For each vertex v:

   • Compute ascending trajectory following steepest ascent

   • Compute descending trajectory following steepest descent

   • Store endpoints as local extrema

   • Update connectivity maps between extrema

2. Pro-cell Construction:

   • During trajectory computation, for each vertex v:

     • If trajectory connects local minimum m to maximum M

     • Add all trajectory vertices to pro-cell(M,m)

3. Cell Decomposition:

   • For each pro-cell(M,m): a. Remove M and m from vertex set b. Compute connected components of remaining subgraph c. Each component is a Morse-Smale cell

This function computes the Morse-Smale complex components:

• Gradient flow trajectories following steepest ascent/descent paths

• Local extrema (maxima and minima) of the function

• Morse-Smale pro-cells: sets of vertices whose trajectories flow from a specific minimum to a specific maximum

• Morse-Smale cells: connected components of pro-cells with extrema removed

The function converts indices between R's 1-based and C++'s 0-based systems. All returned indices are 1-based following R convention.

Note

Unlike classical Morse-Smale complexes on manifolds, the cells of the graph Morse-Smale complex may not be disjoint.