cmgraph — Conley Morse Graph

High-performance C++20 + pybind11 package that computes cell maps, Morse graphs, and homological Conley indices for discrete-time dynamical systems, from either a continuous map (given as an outer-enclosure box map) or a sampled dataset.

The compiled core (cmgraph._core) carries the whole pipeline — outer-approximation cell map ⟶ strongly connected components ⟶ Morse decomposition + partial order ⟶ (on demand) cubical relative homology and the Leray-reduced index map. The Python surface is a thin, ergonomic layer over it. Cells are exposed as stable keys (Python ints) that survive refinement.

Install

pip install .            # core (no plotting dependencies)
pip install ".[viz]"     # + matplotlib and graphviz for cmgraph.plot

• import cmgraph needs no third-party runtime dependency. numpy is used for numeric outputs when it is importable and is otherwise optional (outputs fall back to nested Python lists; cell keys are always Python ints).
• Plotting backends (matplotlib, graphviz) are the optional viz extra: import cmgraph and import cmgraph.plot both succeed without them, and each plot function raises a clear pip install cmgraph[viz] hint only when called without its backend.
• Build stack: scikit-build-core + CMake + pybind11, C++20 (GCC 11+, Clang 13+), Python 3.10+. The package version is single-sourced from pyproject.toml.

Quickstart — Leslie 2D end to end

import math
import cmgraph as cm

TH1 = TH2 = 20.0; PHI = 0.1; P = 0.7
_up = lambda v: math.nextafter(v, math.inf)
_dn = lambda v: math.nextafter(v, -math.inf)

def leslie_box(box):
    """Outward-rounded interval enclosure of the 2D Leslie map (a genuine outer bound)."""
    (xlo, xhi), (ylo, yhi) = box
    ulo = _dn(_dn(TH1 * xlo) + _dn(TH2 * ylo)); uhi = _up(_up(TH1 * xhi) + _up(TH2 * yhi))
    slo = _dn(xlo + ylo); shi = _up(xhi + yhi)
    elo = _dn(math.exp(_dn(-PHI * shi))); ehi = _up(math.exp(_up(-PHI * slo)))
    prods = [ulo * elo, ulo * ehi, uhi * elo, uhi * ehi]
    return [[_dn(min(prods)), _up(max(prods))], [_dn(P * xlo), _up(P * xhi)]]

model = cm.Model(
    bounds=[[-0.001, 90.0], [-0.001, 70.0]],
    map=cm.BoxMap(leslie_box, batched=False),
    grid=cm.Grid(size=[128, 128]),
)

mg = model.morse_graph()          # fast path: Morse graph, no homology
print(mg.summary())               # node count, per-node cell counts, partial order
mg.morse_sets()                   # per-node cell KEYS (stable across refinement)

Refine, inspect, retain state

Refinement mutates the engine in place and keeps the cached image box of every cell that already exists — only newly created cells trigger a map evaluation. The per-round report's f-evaluation count proves it:

report = mg.refine(subdivisions=1, region="morse_sets")   # subdivide + recompute in place
# For a box map (BoxMap), every new leaf is evaluated exactly once and no old cell is
# re-evaluated, so the per-round f-evaluation count equals the number of new leaves:
assert report["f_evaluations"] == report["new_leaves"]     # unchanged cells are not re-evaluated

For a dataset map (BoxMapData), children that fall in an empty region are classified NO_DATA and are not counted as evaluations, so the identity above becomes f_evaluations == new_leaves - (NO_DATA children); the retention guarantee (old cells are never re-evaluated) is unchanged.

Conley index on demand

A Morse set typically does not isolate at a coarse resolution, so conley_index raises a recoverable cm.IndexPairInvalid (refine the offending set and retry). Guard the call:

try:
    ci = mg.conley_index(node=0)                       # RCF of the Leray-reduced f* over Z/5
    ci = mg.conley_index(node=0, want_homology=True)   # + relative homology H_*(P1, P0)
    ci = mg.conley_index(node=0, coefficients="Z")     # arithmetic over Q, integer homology
except cm.IndexPairInvalid:
    ...   # node 0 does not isolate at this resolution — refine it first

The full refine-to-isolate loop that drives a Morse set to a valid index pair and computes a genuine degree-1 Conley index lives in examples/conley_index.py.

Rigor contract

The library's own arithmetic is rigorous: every conversion from a floating-point image box to integer cells rounds outward, so the computed cell map is a genuine outer approximation of the true dynamics.

• B1 — the box handed to your map is the cell's real box widened outward (directed rounding + k-ulp margin), so f(box_true(c)) ⊆ f(box_given(c)).
• B2 — your enclosure box is converted to the union of every cell it meets under outward, closed-cube rounding, so enclosure ⊆ |F(c)|.

What the library cannot verify is your map itself. The rigor of the result therefore rests on the path you choose:

• cm.BoxMap(f) — rigorous iff f is a true outer enclosure. f must map a box to a box that contains the image of every point in it: f(box) ⊇ image(box). The examples build these by interval arithmetic with outward rounding and each documents why the bound holds. (A libm caveat: bounding a transcendental like exp by a fixed outward ulp widening assumes the platform libm is accurate to ≤ 1 ulp — true on glibc ≥ 2.28 and the macOS system libm; a looser libm needs more ulps.)
• cm.BoxMap(point_map, padding=[...]) — non-rigorous. A convenience that samples a point map at cell corners and inflates by a fixed padding. It is an outer approximation only if the padding dominates the map's sub-cell variation (this is not checked).
• cm.BoxMapData(X, Y, padding=...) — non-rigorous unless dominated. Builds a cell map from sampled transitions x_i → y_i: the image of a cell is the convex hull of the images of the samples in it, inflated by padding. It is an outer approximation only if the padding (or a supplied lipschitz=... bound, which makes each image a ball around every sample) dominates the sub-cell variation.

Rigor propagates: given a valid box map, the cell map, Morse decomposition, and Conley indices all carry the outer-approximation guarantees of the combinatorial-dynamics literature.

API tour

Conley-index output form

conley_index returns, per homology degree, the rational canonical form of the Leray reduction of the induced index map f*, computed over a field. The default field is 𝔽₅ (coefficients=None); pass coefficients="Z/p", ("Z/p", p), or an int prime p for another prime, or coefficients="Z" for arithmetic over ℚ with integer relative homology (torsion reported). want_homology=True adds H_*(P1, P0); want_full_index_map adds the full (unreduced) f* matrices. The RCF over any prime presents the shift- equivalence class of f* (Franks–Richeson 2000) canonically and index-pair-independently.

Practical scale and dimension limits

• Dimension: typical d = 2–4; supported to d = 8, hard cap d = 16. The Morse-graph pipeline is viable to the cap; collar-based index pairs and cubical homology are practically confined to d ≲ 8–10 by the 3^d closure factors.
• Cells: up to ~10⁸ leaves; use the implicit edge mode at large scale (edges dominate memory). Keys pack into 128 bits at these depths (Key128), narrower grids use uint64.

Performance & parallelism

The cell-map build parallelizes deterministically (Model(threads=...), default all cores): map evaluation over cells for C++ analytic oracles, plus CSR coverage assembly for any map. Results are bit-identical to serial for any thread count. Measured cell-map- build speedup ≥ 3× at 8 threads on a 6-physical-core Intel Mac (Leslie 2D/3D, ~10⁶ cells); Python-callback maps evaluate serially under the GIL (batch them; a C++ oracle is the hot path). Reproduce with python scripts/benchmark.py. Full numbers, latencies, memory-per- cell vs design §4, and the honest (d, depth, N) envelope: docs/performance.md.

Examples

All scripts are standalone, headless, and deterministic (python examples/<name>.py; outputs go to $CMGRAPH_EXAMPLE_OUTDIR, default a temp dir):

Documentation

• docs/index.md — documentation entry point.
• Design records (the theory reference): docs/design/01-data-structures.md, 02-engine.md, 03-index-pair-isolation.md, 04-conley-index-map.md.
• docs/annotations.md — the A1–A10 structural-annotation audit map.
• docs/performance.md — measured parallel speedup, latencies, and the memory/scale envelope (reproduce with scripts/benchmark.py).

Test

pytest tests/            # Python + example integration tests

C++ unit tests run through CTest from a -DCMGRAPH_BUILD_TESTS=ON CMake build.

Persistence (planned)

Saving and loading the full computed state (grid keys, image caches, Morse graph) is a planned future feature, not shipped in this version. The design does not preclude it: the flat-array data structures (design 01 §2.2 / §6) are laid out so a versioned save/load can be added without changing the core. For now, re-run the pipeline from the model spec.

License

MIT — see LICENSE.