Metadata-Version: 2.1
Name: cmgraph
Version: 0.0.1
Summary: Conley Morse Graph: cell maps, Morse graphs, and homological Conley indices for discrete-time dynamical systems.
Author-Email: Marcio Gameiro <marciogameiro@gmail.com>
License: MIT License
         
         Copyright (c) 2026 Marcio Gameiro and the cmgraph authors
         
         Permission is hereby granted, free of charge, to any person obtaining a copy
         of this software and associated documentation files (the "Software"), to deal
         in the Software without restriction, including without limitation the rights
         to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
         copies of the Software, and to permit persons to whom the Software is
         furnished to do so, subject to the following conditions:
         
         The above copyright notice and this permission notice shall be included in all
         copies or substantial portions of the Software.
         
         THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
         IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
         FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
         AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
         LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
         OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
         SOFTWARE.
         
Classifier: Development Status :: 2 - Pre-Alpha
Classifier: Intended Audience :: Science/Research
Classifier: License :: OSI Approved :: MIT License
Classifier: Programming Language :: C++
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3.10
Classifier: Topic :: Scientific/Engineering :: Mathematics
Requires-Python: >=3.10
Provides-Extra: viz
Requires-Dist: matplotlib>=3.5; extra == "viz"
Requires-Dist: graphviz>=0.20; extra == "viz"
Description-Content-Type: text/markdown

# 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

```bash
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

```python
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:

```python
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:

```python
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`](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

| Object / call | Role |
| --- | --- |
| `cm.Model(bounds, map, grid, threads=0)` | Binds a bounding box, a map spec, and a grid spec into the compute–inspect–refine engine. `.size`, `.dimension`, `.bounds`, `.cells_under(key)`. `threads`: cell-map-build worker count (`0` = all cores, default; `1` = serial) — results are bit-identical for any value; env `CMGRAPH_NUM_THREADS` overrides the auto default. |
| `cm.BoxMap(f, batched=True)` | A box→box outer enclosure (or `BoxMap(point_map, padding=[...])` for the non-rigorous point-map path). |
| `cm.BoxMapData(X, Y, padding=..., lipschitz=..., borrow_rings=0)` | A dataset cell map from sampled transitions; empty-cell policy is NO_DATA by default (`borrow_rings=0`) or ring-budgeted collar borrowing (`borrow_rings ≥ 1`, requires a Lipschitz bound). |
| `cm.Grid(size=[...])` / `cm.Grid(subdivisions=k)` | Grid shape spec — anisotropic per-dimension sizes, or `k` uniform binary subdivisions. |
| `model.morse_graph(conley_index=False)` | Compute the Morse graph (GIL released). Returns a `MorseGraph` handle. |
| `mg.summary()` / `mg.morse_sets()` / `mg.cells(n)` / `mg.node_boxes(n)` / `mg.node_stats(n)` | Inspection: node/cell counts, per-node cell **keys**, per-node cell boxes, stats. |
| `mg.order_pairs()` / `mg.reaches(p, q)` | The Morse-graph partial order (reachability on the condensation). |
| `mg.refine(subdivisions= / to_level= / size=, region=, eval=, collar=, recompute=)` | Refine + recompute in place. `region`: `None` (whole grid), `"morse_sets"`, `"invariant_set"`, `mg.morse_set(i)` / `mg.connections(i, j)` handles, or an iterable of cell keys. `to_level` is idempotent. `recompute=False` batches rounds; settle with `mg.recompute()`. |
| `mg.conley_index(node, coefficients=None, want_homology=False, want_full_index_map=False)` | The homological Conley index of a node, on demand (see below). Raises `cm.IndexPairInvalid` when the node does not isolate. |
| `mg.spurious(node, budget=, certify=)` | The spurious-set protocol: refine a node until its recurrence vanishes (spurious) or a budget is spent. |
| `plot.morse_graph(mg, path=...)` / `plot.morse_sets(mg, dims=(0,1), path=...)` | Optional `viz`: Graphviz DOT and matplotlib (headless Agg) with shared node colours. |

### 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`](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):

| Script | Shows |
| --- | --- |
| [`leslie_2d.py`](examples/leslie_2d.py) | 2D Leslie map: rigorous box map, Morse graph + plots |
| [`leslie_3d.py`](examples/leslie_3d.py) | 3D Leslie map: Morse sets projected + a 3D view |
| [`henon.py`](examples/henon.py) | Hénon map: coarse recurrent set merging attractor + exterior saddle |
| [`leslie_dataset.py`](examples/leslie_dataset.py) | dataset-driven (`BoxMapData`) vs the analytic map |
| [`interactive_refinement.py`](examples/interactive_refinement.py) | compute → inspect → refine, state retention via the f-counter |
| [`skip_conley.py`](examples/skip_conley.py) | the skip-homology fast path vs eager index |
| [`conley_index.py`](examples/conley_index.py) | a genuine degree-1 Conley index of the Hénon saddle |

## Documentation

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

## Test

```bash
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`](LICENSE).
