Metadata-Version: 2.4
Name: franken-networkx
Version: 0.2.3
Classifier: Development Status :: 4 - Beta
Classifier: Intended Audience :: Science/Research
Classifier: Intended Audience :: Developers
Classifier: License :: OSI Approved :: MIT License
Classifier: Operating System :: POSIX :: Linux
Classifier: Operating System :: MacOS
Classifier: Operating System :: Microsoft :: Windows
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: Implementation :: CPython
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Python :: 3 :: Only
Classifier: Programming Language :: Python :: 3.10
Classifier: Programming Language :: Python :: 3.11
Classifier: Programming Language :: Python :: 3.12
Classifier: Programming Language :: Python :: 3.13
Classifier: Topic :: Scientific/Engineering
Classifier: Topic :: Scientific/Engineering :: Information Analysis
Classifier: Topic :: Scientific/Engineering :: Mathematics
Classifier: Topic :: Software Development :: Libraries
Classifier: Topic :: Software Development :: Libraries :: Python Modules
Classifier: Typing :: Typed
Requires-Dist: networkx>=3.4
Requires-Dist: numpy>=1.24
Requires-Dist: numpy>=1.24 ; extra == 'all'
Requires-Dist: scipy>=1.10 ; extra == 'all'
Requires-Dist: numpy>=1.24 ; extra == 'numpy'
Requires-Dist: scipy>=1.10 ; extra == 'scipy'
Requires-Dist: pytest>=7 ; extra == 'test'
Requires-Dist: hypothesis ; extra == 'test'
Requires-Dist: networkx>=3.4 ; extra == 'test'
Requires-Dist: pytest-benchmark ; extra == 'test'
Requires-Dist: numpy>=1.24 ; extra == 'test'
Requires-Dist: scipy>=1.10 ; extra == 'test'
Requires-Dist: pandas>=2.0 ; extra == 'test'
Provides-Extra: all
Provides-Extra: numpy
Provides-Extra: scipy
Provides-Extra: test
License-File: LICENSE
Summary: High-performance Rust-backed graph library with standalone and NetworkX backend modes
Keywords: graph,network,networkx,rust,performance,backend
Author: FrankenNetworkX Contributors
License: MIT
Requires-Python: >=3.10
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM
Project-URL: CI, https://github.com/Dicklesworthstone/franken_networkx/actions
Project-URL: Changelog, https://github.com/Dicklesworthstone/franken_networkx/blob/main/CHANGELOG.md
Project-URL: Documentation, https://github.com/Dicklesworthstone/franken_networkx/tree/main/docs
Project-URL: Homepage, https://github.com/Dicklesworthstone/franken_networkx
Project-URL: Issues, https://github.com/Dicklesworthstone/franken_networkx/issues
Project-URL: Repository, https://github.com/Dicklesworthstone/franken_networkx

# FrankenNetworkX

<div align="center">
  <img src="franken_networkx_illustration.webp" alt="FrankenNetworkX — Rust-backed drop-in replacement for NetworkX">
</div>

<div align="center">

[![PyPI](https://img.shields.io/pypi/v/franken-networkx.svg)](https://pypi.org/project/franken-networkx/)
[![Python](https://img.shields.io/pypi/pyversions/franken-networkx.svg)](https://pypi.org/project/franken-networkx/)
[![License: MIT](https://img.shields.io/badge/License-MIT-yellow.svg)](LICENSE)
[![Rust 2024](https://img.shields.io/badge/rust-2024_edition-orange.svg)](rust-toolchain.toml)

</div>

**FrankenNetworkX is a Rust-backed NetworkX-compatible graph library with a measured, incomplete drop-in surface.** Use it as a standalone library with the familiar NetworkX API, or wire it in as a `networkx>=3.0` backend so supported calls dispatch into Rust without call-site changes.

```bash
pip install franken-networkx
```

No Rust toolchain is needed: prebuilt ABI3 wheels are published on PyPI for Linux (`x86_64`, `aarch64`, `musllinux`), macOS (`x86_64`, `arm64`), and Windows (`x86_64`) for Python 3.10+. Source builds remain available for developers modifying Rust internals (see [Development](#development)).

---

## TL;DR

### The Problem

NetworkX is the canonical Python graph library: rich, correct, comprehensive, and slow on anything that isn't toy-sized. Its pure-Python adjacency, Python-level inner loops, and per-call dict bookkeeping turn graph analytics over even modest graphs (10⁵–10⁶ nodes) into multi-minute affairs. Most "alternatives" pay for speed in compatibility: they expose a different API, change tie-break behavior, lose attribute fidelity, or drop entire algorithm families.

### The Solution

FrankenNetworkX is a Rust port of NetworkX that treats **observable behavior** as a hard constraint. Graph mutation semantics, iteration order, tie-break choices, exception classes, error message wording, and serialization round-trip behavior are all part of the contract. Where pure-Python NetworkX would call `dict[unhashable]`, FrankenNetworkX raises the same `TypeError`. Where NetworkX iterates a `dict_keys` in insertion order, FrankenNetworkX does too. Where NetworkX returns a generator, FrankenNetworkX returns a generator, not a list with a different repr.

That contract is checked by a Python parity test suite of about 1,100 files, by NetworkX's own test suite run with fnx as the backend, by a curated Rust differential conformance harness, and by five generated audit ledgers (coverage matrix, raw-vs-public, delegation, upstream divergence, API ergonomics). The coverage matrix is regenerated and drift-checked on every DSR quality run; the other four are regenerated on demand. The current structural surface result achieves complete coverage: the pinned NetworkX 3.6.1 FeatureUniverse has 4,129 strictly present paths out of 4,129 applicable paths (100.0%), with 0 partial and 0 missing.

### Why FrankenNetworkX?

| Feature | NetworkX 3.x | FrankenNetworkX |
|---|---|---|
| Backing language | Pure Python | Rust 2024 (`#![forbid(unsafe_code)]`) |
| Graph types | `Graph`, `DiGraph`, `MultiGraph`, `MultiDiGraph` | Same four core types; class/member signature gaps are measured in `docs/coverage.md` |
| Adjacency storage | nested `dict` | deterministic `IndexMap`-based, insertion-order preserving |
| GIL release on heavy work | n/a (pure Python) | yes; hundreds of `py.allow_threads(...)` sites |
| Declared import/signature surface | NetworkX 3.6.1 FeatureUniverse | **4,129 / 4,129 strictly present**; 0 partial, 0 missing (the classifier rejects shapes declared only through `__signature__`/`__module__` metadata, on classes and functions) |
| NetworkX's own test suite, fnx as backend | 6,816 tests pass on plain NetworkX 3.6.1 (0 fail) | **6,815 pass, 0 fail, 0 error** with fnx as the backend (2026-09-24; 80 skipped against plain NetworkX's 78 skipped and 1 xfailed). `artifacts/upstream_suite/ratchet_v1.json` holds that floor with no allowed failures, and DSR fails on any failure |
| Backend-dispatch surface | n/a | **313** algorithms registered in `backend.py` |
| Tie-break determinism | implicit | explicit **CGSE** (13-variant `TieBreakPolicy`) |
| Complexity audit | none | `ComplexityWitness` per call, length-prefixed Blake3 decision-path ledger |
| Strict vs hardened parsing | n/a | mode-aware `CgsePolicyEngine` with fail-closed defaults |
| Durable conformance artifacts | n/a | RaptorQ erasure-coded sidecars with decode-proof receipts |
| Fuzz harness | none | **33** cargo-fuzz binaries across parsers + algorithm families |
| Quality gate | project CI | **DSR** (`dsr quality --tool franken_networkx`): fmt → check → clippy `-D warnings` → Rust tests (11 crates, conformance fixture replay included) → fuzz smoke (33 targets) → docs/examples/coverage drift → generated-report checks → NetworkX's own suite → the full Python parity suite; see [Quality Gates](#quality-gates) |

---

## Why a Port, Not a Wrapper?

There are several existing approaches to "faster NetworkX." Each has tradeoffs the FrankenNetworkX design rejects.

| Approach | What it does | Why we didn't choose it |
|---|---|---|
| **Subclassing or monkey-patching nx graphs with C/Cython adjacency** | Replace specific hot loops with native code, leave the rest in Python. | Doesn't move the cost: nested Python dicts still dominate memory and cache behavior. Algorithm-level work happens in pure Python. GIL stays held. |
| **Wrapping a separate Rust/C++ graph engine and copying data in/out** | Convert nx graphs into a foreign representation, run algorithms there, convert results back. | The conversion is the entire workload for short-running algorithms. Attribute fidelity gets lost. Tie-break behavior diverges. Algorithm coverage is sparse. |
| **Rewriting in Rust with a "Rust-idiomatic" API** | Build a clean-slate Rust graph library with its own type system. | Users have to rewrite. The behavioral oracle (NetworkX) becomes invisible. Iteration order drift makes results non-portable. |
| **FrankenNetworkX** | Port algorithms into native Rust, preserve NetworkX-observable behavior on implemented paths, and measure every declared import/signature path against the pinned reference. | This is the design target, not a completed full-surface claim: the live FeatureUniverse records present, partial, missing, n/a, and reasoned exclusions. |

The discipline difference is enforced by tooling, not goodwill:

- The Python parity suite (`tests/python/`, about 1,100 files) compares fnx-vs-nx call by call across thousands of fixtures, including iteration order, exception class, and error wording. The DSR quality run executes the whole suite in guarded shards (`scripts/run_python_parity_suite.py`; 68,318 passed and 0 failed on 2026-09-24).
- The generated coverage matrix under `docs/` is compared on every DSR quality run, so `__all__` drift, a signature change, or an export that gains a directly visible NetworkX route fails it.
- The CGSE complexity-witness ledger gives every algorithm execution a reproducible length-prefixed Blake3 receipt, so behavioral parity can be regression-locked, not just spot-checked.

### Comparison with other "faster graphs"

| Library | API style | Drop-in for nx? | Tie-break parity? | Coverage | Notes |
|---|---|---|---|---|---|
| **NetworkX** | nx.* | n/a | n/a (reference) | comprehensive | Pure Python; the behavioral oracle for everything below. |
| **igraph** (`python-igraph`) | `Graph` class with its own methods | no; different method names, different return types | no; internal node IDs are integer indices, often re-numbered | strong for the algorithms it supports | Mature, fast, C core. Different conceptual model: vertices are dense integer indices, not arbitrary labels. |
| **graph-tool** | `Graph` with vertex/edge property maps | no; C++/Python hybrid API | no | strong for analytics + statistics | Boost-backed, very fast, but requires a custom build pipeline (no PyPI wheel). |
| **rustworkx** | `PyGraph`/`PyDiGraph` with integer node IDs | partial; explicit conversion API | no; integer-index based | growing | High-quality Rust core; intentionally not a drop-in replacement. |
| **graspologic** / **networkx-cuda** / **cugraph** | various, often GPU-backed | partial; mostly nx-shaped but algorithm coverage varies widely | varies | varies | Often optimize the inner loop of specific algorithms (PageRank, BFS, connected components) but require additional toolchains (CUDA, conda channels). |
| **FrankenNetworkX** | `fnx.*` compatibility layer + backend dispatch | **near-complete**; 100% strict import/signature coverage and every test of NetworkX's own suite that runs in backend mode passing, with fallback on unsupported paths | scoped; explicit CGSE `TieBreakPolicy` on owned paths | 4,129 present / 0 partial / 0 missing applicable paths; 313 backend-dispatchable algorithms | Pre-built ABI3 wheels. The generated FeatureUniverse states every gap and exclusion. |

The honest summary: if the only thing you need is "PageRank on a huge graph as fast as possible" and you don't care about API shape or tie-break semantics, igraph or graph-tool or a GPU library may beat fnx on raw throughput for that single call. If you have an existing NetworkX codebase and you want it to *just work* without rewriting and without subtle behavior changes, fnx is built for that case.

---

## Design Principles

Five durable principles govern every commit:

1. **Observable behavior is the contract.** "Faster" is never a license to change a return value, a return type, an iteration order, an exception class, or an error message. Anything visible to the caller is part of the API. If a refactor would shift observable behavior, the refactor doesn't ship until the deviation is either reverted or moved into the upstream-divergence ledger as a documented, owner-acknowledged limitation.
2. **Tie-breaks are first-class.** Equivalent answers chosen by hash-order are bugs in waiting. Kernels reproduce NetworkX's iteration and tie-break order exactly; for the reference algorithms CGSE's registry names the governing policy, records it in the `ComplexityWitness`, and hashes the decision path so non-determinism is detectable, not "usually fine."
3. **Failure modes are explicit, not emergent.** Strict mode fails closed on malformed input. Hardened mode applies *bounded* recovery and writes a `DecisionRecord` for every recovery. There is no third mode where a parser silently fixes up bad input without telling anyone.
4. **Profile, prove, repeat.** Every performance optimization comes with a witness: a `cargo flamegraph` artifact, a behavior-isomorphism proof from the conformance corpus, a baseline-vs-after percentile table, and a delta artifact. "It's faster" without a proof artifact is not accepted.
5. **Long-lived artifacts are self-healing.** Conformance reports, performance baselines, and reproducibility ledgers ship with RaptorQ erasure-coded sidecars and decode-drill receipts. Bit-rot doesn't break replay.

Principles 1–3 are enforced by the parity tests and the DSR quality run. Principles 4 and 5 are working practice (per-change measurement artifacts, the RaptorQ durability tooling); no gate enforces them today.

---

## Two Ways to Use It

### 1. Standalone

Replace `networkx` with `franken_networkx` at the import line:

```python
import franken_networkx as fnx

G = fnx.Graph()
G.add_edge("a", "b", weight=3.0)
G.add_edge("b", "c", weight=1.5)
G.add_edge("a", "c", weight=10.0)

# Everything below returns the exact same thing as NetworkX would.
path        = fnx.shortest_path(G, "a", "c", weight="weight")  # ['a', 'b', 'c']
length      = fnx.shortest_path_length(G, "a", "c", weight="weight")  # 4.5
pr          = fnx.pagerank(G, alpha=0.85)
components  = list(fnx.connected_components(G))
btw         = fnx.betweenness_centrality(G)
mst         = fnx.minimum_spanning_tree(G)
```

### 2. NetworkX backend (zero call-site changes)

If you already have a NetworkX codebase, set the backend priority once and supported algorithms dispatch into Rust transparently. Many unsupported algorithms fall back to NetworkX, but fallback is not a blanket full-surface guarantee; check the generated status for the paths your application uses.

```python
import networkx as nx
nx.config.backend_priority = ["franken_networkx"]

# Everything below now runs through FrankenNetworkX for supported algos.
G = nx.path_graph(10_000)
path = nx.shortest_path(G, 0, 9999)
pr   = nx.pagerank(G)
cc   = nx.connected_components(G)

# Or be explicit on a per-call basis:
path = nx.shortest_path(G, 0, 9999, backend="franken_networkx")
```

The backend is registered via Python entry points (`pyproject.toml`) so NetworkX picks it up automatically once `franken-networkx` is installed.

---

## Graph Types

| Type | Direction | Parallel edges | Notes |
|---|---|---|---|
| `fnx.Graph` | undirected | no | The default; `G[u][v]` returns the edge attribute mapping |
| `fnx.DiGraph` | directed | no | `successors` / `predecessors` / `in_degree` / `out_degree` |
| `fnx.MultiGraph` | undirected | yes (keyed by int) | `G[u][v][k]` returns the per-key attribute mapping |
| `fnx.MultiDiGraph` | directed | yes (keyed by int) | Combined directedness + parallel edges |

All four provide the core method surface (`add_node`, `add_edge`, `remove_node`, `subgraph`, `copy`, `to_directed`, `to_undirected`, `edges`, `nodes`, `degree`, `adj`, `__getitem__`, etc.). Exact class/member signature differences are classified as partial in the generated FeatureUniverse rather than rounded up to full parity. MultiGraph variants collapse parallel edges transparently when a simple-graph algorithm is invoked.

```python
import franken_networkx as fnx

D = fnx.DiGraph()
D.add_edges_from([(1, 2, {"w": 3}), (2, 3, {"w": 1}), (1, 3, {"w": 5})])

assert list(D.successors(1)) == [2, 3]
assert D.in_degree(3) == 2
assert fnx.is_directed_acyclic_graph(D)
assert list(fnx.topological_sort(D)) == [1, 2, 3]
```

---

## Algorithm Catalog

FrankenNetworkX implements paths across 25+ algorithm families. The table below is a high-level inventory. The canonical, machine-checked surface list lives in [`docs/coverage.md`](docs/coverage.md) (4,926 qualified NetworkX 3.6.1 FeatureUniverse rows, including explicit exclusions) and [`python/franken_networkx/backend.py`](python/franken_networkx/backend.py) (the 313 algorithms wired into the NetworkX dispatcher).

| Family | Selected Functions |
|--------|--------------------|
| **Shortest path** | `shortest_path`, `all_shortest_paths`, `dijkstra_path`, `bellman_ford_path`, `multi_source_dijkstra`, `bidirectional_dijkstra`, `has_path`, `shortest_path_length`, `average_shortest_path_length`, `single_source_*`, `all_pairs_*`, `astar_path`, `astar_path_length`, `shortest_simple_paths`, `johnson`, `floyd_warshall*`, `find_negative_cycle` |
| **Connectivity** | `is_connected`, `connected_components`, `node_connectivity`, `edge_connectivity`, `minimum_node_cut`, `minimum_edge_cut`, `bridges`, `articulation_points`, `biconnected_components`, `strongly_connected_components`, `kosaraju_strongly_connected_components`, `condensation`, `weakly_connected_components`, `k_edge_components`, `k_edge_subgraphs`, `k_edge_augmentation`, `all_node_cuts`, `local_node_connectivity`, `local_edge_connectivity` |
| **Centrality** | `pagerank`, `betweenness_centrality`, `edge_betweenness_centrality`, `closeness_centrality`, `harmonic_centrality`, `eigenvector_centrality` (+ `_numpy`), `katz_centrality` (+ `_numpy`), `degree_centrality`, `hits`, `voterank`, `load_centrality`, `subgraph_centrality`, `information_centrality`, `second_order_centrality`, `group_betweenness_centrality`, `current_flow_betweenness`, `communicability`, `communicability_betweenness_centrality`, `communicability_exp` |
| **Clustering** | `clustering`, `triangles`, `transitivity`, `average_clustering`, `square_clustering`, `generalized_degree` |
| **Matching** | `max_weight_matching`, `min_weight_matching`, `maximal_matching`, `hopcroft_karp_matching`, `min_edge_cover`, `is_matching`, `is_maximal_matching`, `is_perfect_matching`, `is_edge_cover` |
| **Flow** | `maximum_flow`, `maximum_flow_value`, `minimum_cut`, `minimum_cut_value`, `min_cost_flow*`, `network_simplex`, `stoer_wagner`, `gomory_hu_tree`, `edmonds_karp` |
| **Trees & forests** | `minimum_spanning_tree`, `maximum_spanning_tree`, `partition_spanning_tree`, `random_spanning_tree`, `number_of_spanning_trees`, `is_tree`, `is_forest`, `is_arborescence`, `is_branching`, `maximum_branching`, `minimum_branching`, `greedy_branching`, `SpanningTreeIterator`, `ArborescenceIterator`, `tree_data`, `from_prufer_sequence`, `to_prufer_sequence` |
| **Euler** | `eulerian_circuit`, `eulerian_path`, `is_eulerian`, `has_eulerian_path`, `is_semieulerian`, `eulerize` |
| **Paths & cycles** | `all_simple_paths`, `all_simple_edge_paths`, `cycle_basis`, `simple_cycles`, `find_cycle`, `is_simple_path`, `has_cycle` |
| **Operators** | `complement`, `union`, `intersection`, `compose`, `difference`, `symmetric_difference`, `disjoint_union`, `cartesian_product`, `tensor_product`, `lexicographic_product`, `strong_product`, `power` |
| **Bipartite** | `is_bipartite`, `bipartite.sets`, `bipartite.color`, `bipartite.density`, `bipartite.biadjacency_matrix`, `bipartite.from_biadjacency_matrix`, `bipartite.projected_graph`, `bipartite.weighted_projected_graph` |
| **Coloring** | `greedy_color`, `strategy_*` strategies under `nx.coloring` |
| **Distance** | `diameter`, `radius`, `center`, `periphery`, `eccentricity`, `density`, `barycenter`, `resistance_distance` |
| **Efficiency** | `global_efficiency`, `local_efficiency`, `efficiency` |
| **Traversal** | `bfs_edges`, `bfs_tree`, `bfs_predecessors`, `bfs_successors`, `bfs_layers`, `descendants_at_distance`, `dfs_edges`, `dfs_tree`, `dfs_predecessors`, `dfs_successors`, `dfs_preorder_nodes`, `dfs_postorder_nodes`, `edge_bfs`, `edge_dfs`, `generic_bfs_edges` |
| **DAG** | `topological_sort`, `topological_generations`, `lexicographical_topological_sort`, `dag_longest_path`, `dag_longest_path_length`, `is_directed_acyclic_graph`, `ancestors`, `descendants`, `transitive_closure`, `transitive_reduction`, `immediate_dominators`, `dominance_frontiers`, `antichains`, `is_aperiodic`, `dag_to_branching` |
| **Link prediction** | `common_neighbors`, `jaccard_coefficient`, `adamic_adar_index`, `preferential_attachment`, `resource_allocation_index`, `cn_soundarajan_hopcroft`, `within_inter_cluster` |
| **Reciprocity** | `reciprocity`, `overall_reciprocity` |
| **Graph metrics** | `average_degree_connectivity`, `rich_club_coefficient`, `s_metric`, `wiener_index`, `hyper_wiener_index`, `degree_assortativity_coefficient`, `average_neighbor_degree`, `attribute_assortativity_coefficient`, `attribute_mixing_dict`, `attribute_mixing_matrix`, `degree_mixing_matrix`, `triadic_census`, `all_triads` |
| **Community** | `louvain_communities`, `greedy_modularity_communities`, `label_propagation_communities`, `asyn_fluidc`, `girvan_newman`, `k_clique_communities`, `kernighan_lin_bisection`, `community.modularity` |
| **Isomorphism** | `is_isomorphic`, `could_be_isomorphic`, `fast_could_be_isomorphic`, `faster_could_be_isomorphic`, `GraphMatcher`, `MultiGraphMatcher`, VF2++, tree isomorphism, ISMAGS |
| **Planarity** | `is_planar`, `check_planarity`, `check_planarity_recursive` |
| **Approximation** | `min_weighted_vertex_cover`, `maximum_independent_set`, `max_clique`, `clique_removal`, `large_clique_size`, `treewidth_min_degree`, `treewidth_min_fill_in`, `min_edge_dominating_set`, `traveling_salesman_problem`, `christofides`, `randomized_partitioning`, `one_exchange` |
| **Dominating** | `dominating_set`, `is_dominating_set`, `connected_dominating_set` |
| **Isolates** | `isolates`, `is_isolate`, `number_of_isolates` |
| **Boundary** | `edge_boundary`, `node_boundary` |
| **k-core / k-truss** | `core_number`, `k_core`, `k_shell`, `k_corona`, `k_crust`, `onion_layers`, `k_truss` |
| **Polynomial / spectral** | `tutte_polynomial`, `chromatic_polynomial`, `laplacian_spectrum`, `adjacency_spectrum`, `modularity_spectrum`, `fiedler_vector`, `algebraic_connectivity`, `simrank_similarity`, `google_matrix` |
| **Generators** | `path_graph`, `cycle_graph`, `star_graph`, `wheel_graph`, `complete_graph`, `complete_bipartite_graph`, `complete_multipartite_graph`, `empty_graph`, `petersen_graph`, `tutte_graph`, `random_geometric_graph`, `gnp_random_graph`, `gnm_random_graph`, `fast_gnp_random_graph`, `watts_strogatz_graph`, `barabasi_albert_graph`, `dual_barabasi_albert_graph`, `stochastic_block_model`, `random_regular_graph`, `random_tree` (Prüfer), `navigable_small_world_graph` (Kleinberg), `relaxed_caveman_graph`, `partial_duplication_graph`, `LFR_benchmark_graph`, `LCF_graph`, lattices (grid, hexagonal, triangular, hypercube), social datasets (`karate_club_graph`, `davis_southern_women_graph`, `florentine_families_graph`) |
| **I/O** | `read_edgelist` / `write_edgelist`, `read_weighted_edgelist` / `write_weighted_edgelist`, `read_adjlist` / `write_adjlist`, `read_multiline_adjlist` / `write_multiline_adjlist`, `read_graphml` / `write_graphml`, `read_gml` / `write_gml`, `read_pajek` / `write_pajek`, `read_leda`, `read_gexf` / `write_gexf`, `read_graph6` / `write_graph6`, `read_sparse6` / `write_sparse6`, `node_link_data` / `node_link_graph`, `cytoscape_data` / `cytoscape_graph`, `tree_data` / `tree_graph` |
| **NumPy / SciPy / pandas** | `to_numpy_array`, `from_numpy_array`, `to_scipy_sparse_array`, `from_scipy_sparse_array`, `to_pandas_edgelist`, `from_pandas_edgelist`, `to_pandas_adjacency`, `from_pandas_adjacency`, `attr_matrix`, `incidence_matrix`, `laplacian_matrix`, `adjacency_matrix` |
| **Conversion** | `from_dict_of_dicts`, `to_dict_of_dicts`, `from_dict_of_lists`, `to_dict_of_lists`, `from_edgelist`, `to_edgelist`, `convert_node_labels_to_integers`, `relabel_nodes`, `contracted_nodes`, `contracted_edge`, `identified_nodes`, `quotient_graph`, `line_graph`, `reverse` |
| **Drawing & layout** | `draw`, `draw_spring`, `draw_circular`, `draw_kamada_kawai`, `draw_planar`, `draw_random`, `draw_shell`, `draw_spectral`, `draw_bipartite`, `spring_layout`, `circular_layout`, `kamada_kawai_layout`, `planar_layout`, `random_layout`, `shell_layout`, `spectral_layout`, `bipartite_layout` (delegates to NetworkX + matplotlib) |

The full surface list is in [`docs/coverage.md`](docs/coverage.md). To use a specific algorithm: `from franken_networkx import <name>`. Consult its FeatureUniverse status first: only `present` contributes to the strict portability fraction; every `partial` row states the exact signature, kind, or value gap.

---

## Architecture

```
                ┌──────────────────────────────────────────────────────────┐
                │                Python package: franken_networkx          │
                │   __init__.py  •  backend.py  •  backend_info.py         │
                │   _fnx.pyi (stubs)  •  313 algorithms in backend dispatch│
                └────────────────────────────┬─────────────────────────────┘
                                             │  PyO3 / ABI3-py310
                                             ▼
   ┌──────────────────────────────────────────────────────────────────────────┐
   │                              fnx-python  (cdylib)                        │
   │   lib.rs  •  algorithms.rs  •  digraph.rs  •  generators.rs              │
   │   readwrite.rs  •  views.rs  •  cgse.rs   (releases GIL at hot paths)    │
   └────────┬───────────────────┬────────────────┬───────────────┬────────────┘
            │                   │                │               │
            ▼                   ▼                ▼               ▼
   ┌────────────────┐  ┌─────────────────┐  ┌──────────┐  ┌──────────────┐
   │  fnx-classes   │  │ fnx-algorithms  │  │ fnx-cgse │  │ fnx-readwrite│
   │  Graph,DiGraph │  │ 650+ pub fns:   │  │ TieBreak │  │ edgelist,GML │
   │  Multi*Graph   │  │ shortest path,  │  │ Policy   │  │ GraphML,JSON │
   │  IndexMap adj  │  │ centrality, etc │  │ Witness  │  │ Pajek,GEXF,..│
   └───────┬────────┘  └────────┬────────┘  │ Ledger   │  └──────────────┘
           │                    │           └────┬─────┘
           ▼                    ▼                ▼
   ┌────────────────┐  ┌──────────────────┐  ┌─────────────────────────────┐
   │   fnx-views    │  │  fnx-generators  │  │       fnx-runtime           │
   │  GraphView     │  │ classic, random, │  │  CompatibilityMode          │
   │  DiGraphView   │  │ scale-free,      │  │  (Strict | Hardened)        │
   │  CachedSnap-   │  │ lattice, social  │  │  CgsePolicyEngine           │
   │  cached        │  │ SBM, WS, BA, GNP │  │  DecisionRecord / evidence  │
   └────────────────┘  └──────────────────┘  └─────────────────────────────┘
                                             ┌─────────────────────────────┐
                                             │ fnx-dispatch  fnx-convert   │
                                             │ fnx-conformance fnx-durability│
                                             │ RaptorQ sidecars + scrub    │
                                             └─────────────────────────────┘
```

### The 12 Rust Crates

| Crate | Purpose |
|---|---|
| `fnx-classes` | Core graph types and deterministic adjacency storage (`IndexMap<Node, IndexMap<Neighbor, AttrMap>>`). Attribute storage via `BTreeMap`. Node and edge insertion order is preserved, which matters for tie-break parity. |
| `fnx-views` | Borrowed snapshot wrappers (`GraphView<'a>`, `DiGraphView<'a>`) plus revision-tracking `CachedSnapshotView` / `CachedDiGraphSnapshotView`. Used by the conformance harness and snapshot round-trip layer. The Python-facing live views (`NodeView`, `EdgeView`, `DegreeView`, `AdjacencyView`, `SubgraphView`) are defined in `crates/fnx-python/src/views.rs` as PyO3 classes on top of these primitives. |
| `fnx-dispatch` | Backend registry, dispatch routing, fail-closed decision plumbing for the NetworkX backend protocol. |
| `fnx-convert` | Conversions between graph types, NumPy / SciPy / pandas interop, dict-of-dicts and dict-of-lists round-trips, node-label remapping. |
| `fnx-algorithms` | ~94 KLOC (inline tests included) across 650+ public functions covering shortest path, centrality, connectivity, clustering, matching, flow, trees, community, isomorphism, planarity, polynomials, spectral, traversal, and DAG families. |
| `fnx-generators` | Classic, random, scale-free, lattice, and social graph generators. Deterministic seeded RNG with NetworkX-byte-compatible edge enumeration order where contracted. |
| `fnx-readwrite` | Native Rust parsers and writers for **7 formats**: edgelist, adjlist, GraphML, GML, JSON (node-link), Pajek, GEXF. Cargo-fuzz hardened with 8 dedicated parser fuzzers. Format variants exposed at the Python layer (`read_weighted_edgelist`, `read_multiline_adjlist`, `read_leda`, `read_graph6`, `read_sparse6`) compose the native primitives or delegate to NetworkX for niche formats. |
| `fnx-cgse` | **Canonical Graph Semantics Engine.** 13-variant `TieBreakPolicy` sum type. `ComplexityWitness { n, m, dominant_term, observed_count, policy, seed, decision_path_blake3 }` with length-prefixed Blake3 hashing. `WitnessSink`, `WitnessLedger`, and a V1 policy registry mapping reference algorithms to canonical policies. |
| `fnx-runtime` | `CompatibilityMode::{Strict, Hardened}`, `CgsePolicyEngine`, structured `DecisionRecord`s with evidence terms, fail-closed defaults. |
| `fnx-conformance` | Curated parity harness; fixture replay; differential report generation; structured logs and replay commands; artifact emitters writing to `artifacts/conformance/latest/`. |
| `fnx-durability` | RaptorQ sidecar generation, integrity scrub, decode-proof artifacts for conformance fixture bundles, benchmark baselines, migration manifests, reproducibility ledgers, and long-lived state snapshots. |
| `fnx-python` | PyO3/maturin bindings; the `franken_networkx._fnx` cdylib; ABI3-py310 (one wheel works on Python 3.10+). Releases the GIL via `py.allow_threads(...)` at hundreds of call sites. |

---

## Canonical Graph Semantics Engine (CGSE)

CGSE is the project's core correctness mechanism. It treats algorithmic *tie-breaking* as part of the API contract rather than incidental behavior.

### The 13 Tie-Break Policies

CGSE's policy registry names, for each of the 12 V1 reference algorithms (table below), which policy governs its choices when multiple equally-correct answers exist. The kernels implement that order directly — they do not take a policy parameter — and the witness records the registered policy:

```rust
pub enum TieBreakPolicy {
    LexMin,                              // lex-min node/edge label
    LexMax,                              // lex-max node/edge label
    InsertionOrder,                      // adjacency-list order
    ReverseInsertionOrder,               // reverse adjacency-list order
    WeightThenLex,                       // weight ↑ then lex-min label
    WeightThenInsertionOrder,            // weight ↑ then FIFO insertion (Dijkstra)
    LexThenWeight,                       // lex-min label then weight ↑
    DeterministicHash { seed: u64 },     // reproducible but order-agnostic
    DegreeMinThenLex,                    // min-degree node, ties lex-min
    DegreeMaxThenLex,                    // max-degree node, ties lex-min
    DfsPreorder,                         // DFS pre-order
    BfsLevelLex,                         // BFS level, within-level lex-min
    EdgeKeyLex,                          // multigraph edge key lex-min
}
```

Defined in [`crates/fnx-cgse/src/lib.rs:37`](crates/fnx-cgse/src/lib.rs). Each policy has a short stable identifier used in ledger entries and serialized artifacts.

The `WeightThenInsertionOrder` variant is the one NetworkX actually exhibits in its heap-driven shortest-path algorithms (`heapq` + `itertools.count()` as a per-push monotonic counter). fnx's Dijkstra uses the same scheme: a `DijkstraState { dist, seq, node }` struct whose `Ord` impl tie-breaks equal-distance entries by the insertion-counter `seq`. The choice of `WeightThenInsertionOrder` over `WeightThenLex` for Dijkstra is intentional: matching NetworkX byte-for-byte beats insertion-order-independent reproducibility for the project's drop-in-compatibility contract. The CGSE V1 registry now records this honestly.

### Complexity-class reference

The 10 dominant-term strings recognized by `fnx_cgse::analytic_upper_bound(term, n, m)`. Use them to interpret the `dominant_term` field of a `ComplexityWitness`:

| Term | Closed form | Typical algorithms |
|---|---|---|
| `n` | `n` | `degree_centrality`, `is_isolate`, single-node lookups |
| `m` | `m` | `eulerian_circuit`, edge-only scans |
| `n_plus_m` | `n + m` | BFS, DFS, `connected_components`, `topological_sort`, articulation points |
| `n_log_n` | `n · ⌈log₂ n⌉` | sorting-based reductions, lex-min element selection |
| `n_plus_m_log_n` | `(n + m) · ⌈log₂ n⌉` | Dijkstra with binary heap |
| `n_m` | `n · m` | Bellman-Ford, Brandes betweenness |
| `n_squared` | `n²` | dense-matrix shortest-paths, dense centrality |
| `n_m_alpha` | `n · m · α(n,m)` | Edmonds' max-weight matching, union-find-amortized algorithms |
| `m_log_m` | `m · ⌈log₂ m⌉` | Kruskal's MST (edge sort dominates) |
| `m_log_n` | `m · ⌈log₂ n⌉` | Prim's MST with binary heap |

If you build your own algorithm on top of fnx and want to participate in the witness ledger, pick the term that bounds your worst-case observed-op count, return it in the witness, and the runtime's complexity-bound verifier will catch any regression.

### The V1 policy registry

The `v1_policy_registry()` table pins a canonical tie-break policy and dominant complexity term for each of the 12 *reference* algorithms, the V1 set whose tie-break behavior is contractually frozen. Source: `ReferenceAlgorithm::policy` and `::dominant_complexity` in [`crates/fnx-cgse/src/lib.rs`](crates/fnx-cgse/src/lib.rs).

| Family | Reference algorithm | Tie-break policy | Dominant complexity |
|---|---|---|---|
| shortest_path | `dijkstra` | `WeightThenInsertionOrder` | `n_plus_m_log_n` |
| shortest_path | `bellman_ford` | `InsertionOrder` | `n_m` |
| traversal | `bfs` | `InsertionOrder` | `n_plus_m` |
| traversal | `dfs` | `InsertionOrder` | `n_plus_m` |
| matching | `max_weight_matching` | `WeightThenLex` | `n_m_alpha` |
| matching | `min_weight_matching` | `WeightThenLex` | `n_m_alpha` |
| connectivity | `connected_components` | `LexMin` | `n_plus_m` |
| connectivity | `strongly_connected_components` | `InsertionOrder` | `n_plus_m` |
| trees | `kruskal` | `WeightThenLex` | `m_log_m` |
| trees | `prim` | `WeightThenLex` | `m_log_n` |
| euler | `eulerian_circuit` | `InsertionOrder` | `m` |
| dag | `topological_sort` | `InsertionOrder` | `n_plus_m` |

The choice of `InsertionOrder` for `bfs`/`dfs`/`bellman_ford`/`topological_sort` is exactly the NetworkX behavior: those algorithms iterate adjacency in the order the user inserted edges, and `IndexMap` preserves that. The choice of `WeightThenInsertionOrder` for Dijkstra matches NetworkX's `heapq + itertools.count()` pattern (a monotonic per-push counter is the secondary key, so equal-weight frontier entries pop in FIFO order). The choice of `WeightThenLex` for Kruskal / Prim / matching reflects those algorithms' deterministic edge sort by `(weight, left, right)` labels.

These assignments encode the same tie-break choices a careful reading of the NetworkX source would extract, except now they are machine-readable, versioned in source, and enforceable via the witness ledger. The broader algorithm surface (~550 functions) inherits the appropriate policy via the family the algorithm belongs to.

### Complexity Witnesses

The V1 reference algorithms (Dijkstra, Bellman-Ford, BFS, DFS, max- and min-weight matching, connected and strongly connected components, Kruskal, Prim, Eulerian circuit, topological sort) emit a structured `ComplexityWitness` capturing `n`, `m`, observed operation count, the policy identifier, and a length-prefixed Blake3 hash over the decision path. Witnesses can be drained from a `WitnessLedger` for offline audit, regression-locking, or reproducibility checks. The wider surface (650+ kernels) does not emit witnesses yet; as of 2026-09-15 there are 24 `cgse_begin` sites in `fnx-algorithms`, and wiring proceeds per family.

### Strict vs Hardened Modes

Two compatibility doctrines, both available at runtime:

- **Strict**: maximize observable compatibility for V1 scoped APIs. No behavior-altering repairs. Malformed input fails closed with structured error context.
- **Hardened**: preserve the API contract while applying bounded defensive recovery for malformed inputs and hostile edge cases. Useful when ingesting graphs from adversarial sources.

The mode is configured via `fnx.config`, scoped context managers, or per-call reader arguments:

<!-- skip-verify: illustrative snippet demonstrating hypothetical input files -->
```python skip-verify
import franken_networkx as fnx

# 1. Process-wide configuration (mirrors nx.config):
fnx.config.compatibility_mode = "hardened"  # or fnx.set_compatibility_mode("hardened")

# 2. Scoped context managers (thread-local overrides):
with fnx.config(compatibility_mode="hardened"):
    G = fnx.Graph()
    assert G.mode == "hardened"

with fnx.compatibility_mode("hardened"):
    G = fnx.read_edgelist("adversarial_edges.txt")

# 3. Direct function kwargs on read/parse entry points:
G = fnx.read_graphml("input.graphml", mode="hardened")
assert G.mode == "hardened"

# 4. Audit Evidence Ledger (DecisionRecord):
# Inspect or drain the recovery decisions made during parsing and mutation:
records = G.decision_records()  # or fnx.decision_records(G)
drained = G.drain_decision_records()  # or fnx.drain_decision_records(G)
```

The choice is made through `CgsePolicyEngine` in `fnx-runtime`, which records every action selection as a `DecisionRecord` with evidence terms. In Hardened mode, unknown incompatible features still fail closed to maintain security invariants.

### Why determinism matters

Most NetworkX algorithms have multiple equally-correct answers. Consider `connected_components(G)` on a graph with two components. There is no inherent ordering between the components, and NetworkX's actual answer depends on Python's `dict` iteration order, which depends on insertion order, which depends on whatever sequence of `add_edge` calls produced the graph. Code that does `next(iter(connected_components(G)))` is implicitly depending on this chain.

A "faster" library that returns the same set of components but in a different order silently breaks every caller that depended on the original order. The crash, if any, surfaces far from the swap, usually as a downstream comparison or hash that produces a different result.

CGSE addresses this by making the tie-break *visible*:

```python
import franken_networkx as fnx
from franken_networkx._fnx import cgse  # bound Rust submodule

# Inspect the policy registry: which policy governs which algorithm.
# policy_registry() returns: { "<algorithm>": {"family": ..., "policy": ..., "dominant_complexity": ...} }
registry = cgse.policy_registry()
for algorithm, info in registry.items():
    print(f"{algorithm:30s} → policy={info['policy']:20s} bound={info['dominant_complexity']}")
# dijkstra                       → policy=weight_then_insertion_order bound=n_plus_m_log_n
# bellman_ford                   → policy=insertion_order      bound=n_m
# bfs                            → policy=insertion_order      bound=n_plus_m
# connected_components           → policy=lex_min              bound=n_plus_m
# max_weight_matching            → policy=weight_then_lex      bound=n_m_alpha
# topological_sort               → policy=insertion_order      bound=n_plus_m
# ...

# You can also query an algorithm's canonical policy directly:
print(cgse.algorithm_policy("dijkstra"))      # → TieBreakPolicy.weight_then_insertion_order
print(cgse.algorithm_policy("unknown_algo"))  # → None
print(cgse.reference_algorithms()[:5])        # → ['dijkstra', 'bellman_ford', 'bfs', 'dfs', 'max_weight_matching']
```

### The complexity witness contract

Each reference-algorithm execution emits a `ComplexityWitness`. The actual Rust struct is:

```rust
pub struct ComplexityWitness {
    pub n: usize,                       // node count
    pub m: usize,                       // edge count
    pub dominant_term: String,          // "n_log_n", "n_plus_m_log_n", "n_m", ...
    pub observed_count: u64,            // tie-break decisions + main-loop iterations
    pub policy: TieBreakPolicy,         // which policy governed tie-breaks
    pub seed: Option<u64>,              // RNG seed for randomized algorithms
    pub decision_path_blake3: [u8; 32], // length-prefixed Blake3 over the decision path
}
```

The 10 supported complexity-class terms in `fnx_cgse::analytic_upper_bound` are: `n`, `m`, `n_plus_m`, `n_log_n`, `n_plus_m_log_n`, `n_m`, `n_squared`, `n_m_alpha`, `m_log_m`, `m_log_n`. The analytic upper bound is computed against the term rather than stored in the witness, so the witness stays small and the bound is looked up on demand:

```rust
use fnx_cgse::{collect_witnesses, analytic_upper_bound, ComplexityWitness};

let (result, witnesses): (_, Vec<ComplexityWitness>) = collect_witnesses(|| {
    // any block of fnx algorithm calls; only the CGSE reference kernels emit
    fnx_algorithms::connected_components(&graph)
});

for w in &witnesses {
    if let Some(bound) = analytic_upper_bound(&w.dominant_term, w.n, w.m) {
        assert!(w.observed_count <= bound, "complexity regression!");
    }
}
```

Or use the `verify_complexity_bound(&witness)` and `assert_complexity_within_bounds(&witness)` helpers shipped from `fnx_cgse`. Two runs on the same graph with the same policy produce identical `decision_path_blake3` hashes; any ordering drift manifests as a hash mismatch, making non-determinism a regression-locked property.

This makes complexity regressions a regression-lockable property, not a folklore expectation: `crates/fnx-conformance/tests/cgse_complexity_bound_gate.rs` (landed 2026-09-03) asserts for all 12 V1 reference algorithms that a witness is emitted, matches the pinned registry policy and dominant term, stays within `analytic_upper_bound`, and is hash-identical across runs — with a negative case proving an inflated operation count is rejected. It runs with `cargo test -p fnx-conformance`, which is part of the DSR quality run (see [Quality Gates](#quality-gates)).

### Tie-break policies in action

Different policies on the same algorithm give different, but reproducible, answers:

```python
# Conceptually, fnx ships these per-algorithm. Most users never have to think about it;
# the policy that matches NetworkX's behavior is the default. The visibility matters
# when you're auditing for reproducibility.

# Dijkstra under WeightThenInsertionOrder (the default, matching NetworkX):
# equal-weight frontier entries pop in the order they were inserted (FIFO).
import franken_networkx as fnx

G = fnx.Graph()
G.add_weighted_edges_from([
    ("a", "b", 1.0),
    ("b", "z", 1.0),
    ("a", "z", 3.0),
])
fnx.shortest_path(G, "a", "z", weight="w")

# Under a hypothetical WeightThenLex policy, equal-weight alternatives would
# be broken by lex-min node label instead, giving insertion-order-independent
# results but breaking byte-for-byte parity with NetworkX.
```

You should almost never override the default. The defaults are chosen to match NetworkX. The point is that *which* tie-break is in effect is now a contract, not an emergent property of Python dict layout.

---

## Quick Start

### Install

```bash
# from PyPI (pre-built wheels, no Rust toolchain required)
pip install franken-networkx

# with SciPy for the spectral / sparse-matrix functions (NumPy is always installed)
pip install 'franken-networkx[all]'

# from source (requires Rust nightly + maturin)
git clone https://github.com/Dicklesworthstone/franken_networkx
cd franken_networkx
pip install maturin
maturin develop --release --features pyo3/abi3-py310
```

### Run an algorithm

```python
import franken_networkx as fnx

# Build a small weighted graph
G = fnx.Graph()
G.add_weighted_edges_from([
    ("a", "b", 1.0),
    ("b", "c", 2.0),
    ("a", "c", 5.0),
    ("c", "d", 1.0),
    ("b", "d", 4.0),
])

print(fnx.shortest_path(G, "a", "d", weight="weight"))         # ['a', 'b', 'c', 'd']
print(fnx.shortest_path_length(G, "a", "d", weight="weight"))  # 4.0

# pagerank needs scipy (pip install 'franken-networkx[scipy]'), exactly as nx.pagerank does.
print(sorted(fnx.pagerank(G).items()))
# [('a', 0.229...), ('b', 0.270...), ('c', 0.299...), ('d', 0.200...)]
# (b and c are the degree-3 hubs; a and d are degree-2 leaves of the cluster.)

print(list(fnx.connected_components(G)))
# [{'a', 'b', 'c', 'd'}]
```

### Drop in as a backend

```python
import networkx as nx

# Enable the backend once, application-wide.
nx.config.backend_priority = ["franken_networkx"]

G = nx.erdos_renyi_graph(1_000, 0.01, seed=42)
cc = nx.connected_components(G)              # routes to FrankenNetworkX
pr = nx.pagerank(G)                          # routes to FrankenNetworkX
diam = nx.diameter(G)                        # routes to FrankenNetworkX
```

### Round-trip I/O

```python
import franken_networkx as fnx
from pathlib import Path
from tempfile import TemporaryDirectory

G = fnx.path_graph(5)
with TemporaryDirectory() as directory:
    path = Path(directory) / "graph.xml"
    fnx.write_graphml(G, path)
    H = fnx.read_graphml(path)
    assert sorted(map(str, H.nodes())) == sorted(map(str, G.nodes()))
    assert sorted(tuple(map(str, edge)) for edge in H.edges()) == sorted(
        tuple(map(str, edge)) for edge in G.edges()
    )
```

---

## Tutorial: A Complete Graph Analysis

A walkthrough that goes from raw data to insight using only fnx, demonstrating the end-to-end loop a real user would follow.

### 1. Build or load the graph

```python
import franken_networkx as fnx

# Option A: load Zachary's karate club (a classic ~34-node fixture).
G = fnx.karate_club_graph()

# Option B: load from an edgelist file. Whitespace-separated, with optional
# {"weight": value} attribute literals; exact format match with nx.
# G = fnx.read_edgelist("input.edgelist", create_using=fnx.Graph)

# Option C: build from scratch.
# G = fnx.Graph()
# G.add_edges_from([(0, 1), (1, 2), (2, 0), (3, 4), (4, 5)])

print(G.number_of_nodes(), "nodes,", G.number_of_edges(), "edges")
# 34 nodes, 78 edges
```

### 2. Inspect structural properties

```python
print("density:",  fnx.density(G))         # → 0.139...
print("diameter:", fnx.diameter(G))        # → 5
print("radius:",   fnx.radius(G))          # → 3
print("center:",   sorted(fnx.center(G)))  # → nodes at min eccentricity
print("is_connected:", fnx.is_connected(G))# → True

# Degree distribution.
hist = fnx.degree_histogram(G)
for d, count in enumerate(hist):
    if count:
        print(f"degree {d:2d}: {count}")
```

### 3. Rank nodes by centrality

```python
pr  = fnx.pagerank(G)
btw = fnx.betweenness_centrality(G)
clo = fnx.closeness_centrality(G)

# Top 5 by each measure:
def top5(d, label):
    rows = sorted(d.items(), key=lambda kv: kv[1], reverse=True)[:5]
    print(f"\nTop 5 by {label}:")
    for node, score in rows:
        print(f"  {node!s:>5} → {score:.4f}")

top5(pr,  "PageRank")
top5(btw, "betweenness")
top5(clo, "closeness")
```

For the karate club graph, both centralities surface nodes 0 ("Mr. Hi") and 33 ("Officer"), the two factional leaders. Cross-method agreement is a useful sanity check.

### 4. Detect community structure

```python
# Louvain (modularity-maximizing community detection).
comms = list(fnx.community.louvain_communities(G, seed=7))
print(f"\n{len(comms)} communities (modularity = "
      f"{fnx.community.modularity(G, comms):.4f}):")
for i, c in enumerate(comms):
    print(f"  community {i}: {sorted(c)}")
```

Louvain on the karate club typically finds 3–4 communities with modularity ≈ 0.42, splitting the graph along the actual social-faction lines documented by Zachary in 1977.

### 5. Compute shortest paths between every pair

```python
# all-pairs shortest path lengths (BFS for unweighted graphs).
ap = dict(fnx.all_pairs_shortest_path_length(G))

# Find the two most-distant nodes.
import heapq
furthest = max(
    ((u, v, ap[u][v]) for u in ap for v in ap[u] if u < v),
    key=lambda triple: triple[2],
)
print(f"\nfurthest pair: {furthest[0]} → {furthest[1]}, distance {furthest[2]}")
```

### 6. Export the analysis

```python
# Annotate nodes with PageRank before saving so downstream readers see it.
for node, score in pr.items():
    G.nodes[node]["pagerank"] = score

fnx.write_graphml(G, "karate_annotated.graphml")
print("\n→ wrote karate_annotated.graphml")
```

That entire pipeline is byte-for-byte identical to the corresponding NetworkX code; flip `fnx.` → `nx.` and run it again to verify.

### 7. Verify against the NetworkX oracle

```python
import networkx as nx

# Convert via node-link JSON so attributes are preserved exactly.
data  = fnx.node_link_data(G)
G_nx  = nx.node_link_graph(data)

# Re-run a load-bearing computation on each side and assert agreement.
assert fnx.diameter(G) == nx.diameter(G_nx)
assert {tuple(sorted(c)) for c in fnx.community.louvain_communities(G, seed=7)} == \
       {tuple(sorted(c)) for c in  nx.community.louvain_communities(G_nx, seed=7)}
print("→ fnx ↔ nx agreement verified on diameter + communities")
```

If that assertion fires, please file an issue. That is the contract.

---

## How a Call Flows Through the System

Tracing a natively routed call from the Python call site down to native code and back. The boxes name `pagerank` for concreteness; note that the public `pagerank` route today runs its power iteration in scipy over a natively built CSR (see the Centrality notes), so read the trace as the path a kernel such as `closeness_centrality` or `connected_components` takes:

```
 ┌────────────────────────────────────────────────────────────────────┐
 │  1. User: fnx.pagerank(G, alpha=0.85)                              │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  Python attribute lookup on the franken_networkx
                       │  package surface (__all__ entry).
                       ▼
 ┌────────────────────────────────────────────────────────────────────┐
 │  2. python/franken_networkx/__init__.py — public Python wrapper    │
 │     • Validates types, coerces nx graphs at the boundary if any.   │
 │     • For ~125 functions, checks an "argument shape" — if the      │
 │       caller passed a non-supported flavor (e.g. callable          │
 │       weight, exotic kwarg), routes via                            │
 │       _call_networkx_for_parity(...) and returns nx's answer.      │
 │     • Otherwise calls the bound Rust kernel:                       │
 │       franken_networkx._fnx.pagerank(G, alpha, ...)                │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  PyO3 type marshaling.
                       ▼
 ┌────────────────────────────────────────────────────────────────────┐
 │  3. crates/fnx-python/src/algorithms.rs — PyO3 binding             │
 │     • Borrows the underlying fnx_classes::Graph by reference.      │
 │     • py.allow_threads(|| { ... })  ← GIL released here.           │
 │     • Calls into fnx_algorithms::<kernel>(...); CGSE reference     │
 │       kernels also record a complexity witness.                    │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  Native Rust call.
                       ▼
 ┌────────────────────────────────────────────────────────────────────┐
 │  4. crates/fnx-algorithms/src/...  — native algorithm              │
 │     • Iterates adjacency via IndexMap → deterministic order.       │
 │     • Records observed-op count + tie-break decisions in the       │
 │       CGSE WitnessLedger.                                          │
 │     • Returns Vec<f64> / HashMap<NodeId, f64>.                     │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  Result hand-off.
                       ▼
 ┌────────────────────────────────────────────────────────────────────┐
 │  5. PyO3 conversion — Rust types → PyDict / PyList / PyFloat       │
 │     • GIL is reacquired here.                                      │
 │     • dict iteration order is the order Rust emitted, matching     │
 │       the policy-defined enumeration order.                        │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  Return path back to Python.
                       ▼
 ┌────────────────────────────────────────────────────────────────────┐
 │  6. Python wrapper post-processing (if needed)                     │
 │     • For ~25 "wrapper-patched" functions, post-processes the      │
 │       raw output to match nx iteration order or coerce return      │
 │       types (cataloged in docs/raw_vs_public_audit.md).            │
 │     • Returns the user-visible result.                             │
 └────────────────────────────────────────────────────────────────────┘
```

In NetworkX backend mode (`nx.config.backend_priority = ["franken_networkx"]`), step 1 is preceded by an extra layer: NetworkX's dispatcher checks the supported-algorithm registry (`BackendInterface.can_run` against `_SUPPORTED_ALGORITHMS`), converts the nx graph to an fnx graph via `convert_from_nx`, dispatches to the fnx wrapper, and converts the result back via `convert_to_nx` (which recursively unwraps fnx graphs nested in dicts/lists/tuples/sets).

---

## Compatibility Doctrine

FrankenNetworkX's compatibility contract is not "best-effort similarity." It is a machine-checked guarantee policed by five auto-generated audit ledgers under [`docs/`](docs/):

| Ledger | Purpose |
|---|---|
| [`coverage.md`](docs/coverage.md) | NetworkX 3.6.1 FeatureUniverse: 4,926 qualified paths classified as `present`, `partial`, `missing`, `n/a`, or reasoned `excluded`; per-family strict coverage is reported. A separate appendix classifies the 843 `franken_networkx.__all__` implementation routes. Drift fails the DSR quality run. |
| [`raw_vs_public_audit.md`](docs/raw_vs_public_audit.md) | Every `_raw_X` Rust kernel cross-checked against its public wrapper. Documents the 24 wrapper-patched parity repairs where the public wrapper post-processes raw output to match NetworkX. |
| [`delegation_ledger.md`](docs/delegation_ledger.md) | AST classification of how each public name reaches NetworkX (nx-fallback / mixed-route / py-wrapper / rust-native / rust-reexport). It currently recognises delegation helpers by name, so NetworkX calls made through renamed helpers are under-counted; it is being rebuilt to classify by call-graph reachability plus a runtime frame census (`br-r37-c1-rc0923-epic-honest-measurement-vbneu.2`). |
| [`upstream_divergence_ledger.md`](docs/upstream_divergence_ledger.md) | Unified ledger of `native-parity`, `wrapper-patched`, `intentionally-delegated`, `raw-known-gap`, and `owner-acknowledged-limitation` rows. |
| [`api_ergonomics_audit.md`](docs/api_ergonomics_audit.md) | Signature-level drift detection: parameter names, defaults, and keyword-only contracts compared against NetworkX. |

If you find a behavior that doesn't match NetworkX and isn't listed in `upstream_divergence_ledger.md`, that's a bug, not a feature.

### Exception class hierarchy

FrankenNetworkX re-exports NetworkX's exception classes verbatim so `except nx.NetworkXError:` and `except fnx.NetworkXError:` catch the same instances. 14 of these classes are explicitly listed in `fnx.__all__` and show up as public `CLASS` exports in `docs/coverage.md`. The remaining two (`AmbiguousSolution`, `ExceededMaxIterations`) are not in `__all__` but are still reachable as `fnx.AmbiguousSolution` / `fnx.ExceededMaxIterations` via the package's `__getattr__` fallback to `networkx` (the identity is preserved: `fnx.AmbiguousSolution is nx.AmbiguousSolution`). The actual hierarchy (matches `networkx.exception`):

```
Exception
└── NetworkXException                       (base for everything below)
    ├── NetworkXError                       (general "wrong shape of input")
    ├── NetworkXPointlessConcept            (e.g. centrality on the empty graph)
    ├── NetworkXAlgorithmError              (algorithm-specific precondition violated)
    │   ├── NetworkXUnfeasible              (no feasible solution exists)
    │   │   ├── NetworkXNoPath              (no path between s and t)
    │   │   └── NetworkXNoCycle             (cycle expected but none found)
    │   └── NetworkXUnbounded               (objective unbounded)
    ├── HasACycle                           (cycle present where one is forbidden)
    ├── NetworkXNotImplemented              (also inherits NotImplementedError)
    ├── NodeNotFound                        (node missing from graph)
    ├── AmbiguousSolution                   (multiple valid answers)
    ├── ExceededMaxIterations               (loop hit its iteration cap)
    │   └── PowerIterationFailedConvergence (specifically eigenvector/PageRank failed)
    ├── NetworkXTreewidthBoundExceeded      (chordal — treewidth above the requested bound)
    └── NotATree                            (tree-only algorithm given a non-tree)
```

Important nuances to know about:

- **`NetworkXAlgorithmError` is *not* under `NetworkXError`.** Both are direct children of `NetworkXException`. If you write `except nx.NetworkXError:`, you will not catch `NetworkXNoPath`. Use `NetworkXException` (the broadest catch) or `NetworkXAlgorithmError` (the broadest algorithm catch).
- **`NetworkXNoPath` and `NetworkXNoCycle` are siblings under `NetworkXUnfeasible`**, not direct children of `NetworkXAlgorithmError`. `except nx.NetworkXUnfeasible:` catches both.
- **`NodeNotFound` is under `NetworkXException` directly.** It is *not* a subclass of `NetworkXError`.

The exception-class and error-message parity is part of the DSR quality run (`test_error_messages.py`). If `nx.shortest_path(G, "a", "z")` raises `NetworkXNoPath` with message `"No path between a and z."`, `fnx.shortest_path(G, "a", "z")` must raise the same class with the same wording. Bead cycles like `br-r37-c1-hpeix` and `br-r37-c1-jxvsu` were dedicated to locking missing-source/target wording across 30+ functions.

Why the strict parity: existing NetworkX code routinely does `except nx.NetworkXNoPath:` and inspects `str(e)`. Drifting an exception class or wording subtly breaks downstream pipelines that depend on it.

### Parity coverage today

- Runtime census (2026-09-23, NetworkX frames counted with `sys.monitoring` on the default call path): **35 of 41** commonly used functions execute no NetworkX code — shortest paths, the main centralities (pagerank, betweenness, closeness, harmonic, katz, hits, eigenvector), components, cuts, connectivity, flow, min-cost flow, MST, coloring, isomorphism, planarity, distance measures, cliques, cores, transitive closure.
- Always-NetworkX today: weighted/self-loop `louvain_communities`, `simple_cycles`, `k_components`. (`max_weight_matching`, `min_weight_matching`, `maximum_branching` with its family, and `greedy_modularity_communities` now run networkx's algorithms natively, results identical including order and, for matchings, pair direction.) Several other functions reach NetworkX only for specific argument shapes (custom `flow_func`, user callables, some `k`/`seed` combinations), and 112 submodule callables are NetworkX's own function objects re-exported.
- Wrapper-patched exports — the Rust kernel runs the algorithm but the Python wrapper post-processes output ordering to match NetworkX's iteration semantics — are enumerated with exact counts in `raw_vs_public_audit.md`.
- **1** raw-known-gap row and **1** owner-acknowledged limitation in `upstream_divergence_ledger.md`; the public wrappers hide both behind fallbacks.

---

## Security Doctrine

The project defends against:

- **Malformed graph ingestion.** Every parser (`fnx-readwrite`) is cargo-fuzz hardened with 33 corpus-seeded targets covering edgelist, adjlist, GraphML, GML, JSON, Pajek, GEXF, node-link, attribute-value, and multigraph variants.
- **Attribute confusion.** `CgseValue` is a typed serde-compatible value with a controlled set of variants. GraphML/GML parsers validate keys, scope attributes, reject empty keys, escape `#` in edgelist attrs, and enforce typed parsing (so `bool=0/1` doesn't become an integer downstream).
- **Algorithmic denial vectors.** Algorithms follow NetworkX on non-finite weights (NaN, ±∞) in every mode — shortest-path kernels route such inputs to NetworkX-exact paths rather than guess. The readers fail closed in strict mode on malformed or unknown input (malformed directed flags, namespace-prefix abuse, unknown GraphML attribute types) and apply bounded, logged recovery in hardened mode. Generator size budgets (100,000 nodes; 20,000 for G(n, p)-style random generators; 2,000-node or 1,999,000-edge dense graphs) apply in hardened mode only, where an over-budget size is clamped to the budget with a Python `RuntimeWarning` naming the clamp: strict mode builds every size NetworkX builds, and only a size that overflows `usize` fails closed.
- **Stack-safety on deep graphs.** Traversal-heavy algorithms (DFS, planarity, transitive closure) avoid unbounded recursion.

The minimum security bar (per [AGENTS.md](AGENTS.md)):

1. Threat-model notes for each major subsystem.
2. Fail-closed behavior for unknown incompatible features.
3. Adversarial fixture coverage and fuzz/property tests for high-risk parsers and state transitions.
4. Deterministic audit logs for recoveries and policy overrides.

---

## Durability: RaptorQ Everywhere

Long-lived artifacts emit RaptorQ erasure-coded sidecars and decode-proof receipts. This applies to:

- Conformance fixture bundles
- Benchmark baseline bundles
- Migration manifests
- Reproducibility ledgers
- Long-lived state snapshots

The `fnx-durability` crate produces three artifacts per recovery event: a repair-symbol generation manifest, an integrity scrub report, and a decode-proof receipt. Its unit tests run in the DSR quality run; the scrub + decode-drill over the conformance bundle is run on demand and is not a gate today.

---

## NetworkX Backend Protocol Primer

NetworkX 3.0+ ships a backend protocol that lets third-party libraries accelerate or replace algorithm implementations. FrankenNetworkX implements it through two Python entry points wired up in `pyproject.toml`:

```toml
[project.entry-points."networkx.backends"]
franken_networkx = "franken_networkx.backend:backend_interface"

[project.entry-points."networkx.backend_info"]
franken_networkx = "fnx_backend_info:get_backend_info"
```

(`fnx_backend_info` is a small top-level module shipped in the wheel, so NetworkX can read the backend's metadata without importing the extension while NetworkX itself is still initialising.)

Once the package is installed, NetworkX picks up these entry points automatically. There is nothing to import on the user's side beyond `networkx`.

### What the dispatcher does on each call

For each `nx.<algorithm>(...)` call when `franken_networkx` is in the priority list (or supplied as `backend="franken_networkx"`):

1. NetworkX asks `backend_info.get_backend_info()` for the list of supported algorithms (parsed from `_SUPPORTED_ALGORITHMS` via AST so the metadata side is safe to import while NetworkX itself is still initializing).
2. NetworkX asks `BackendInterface.can_run(name, args, kwargs)` whether fnx will accept the call shape. `can_run` returns `False` for:
   - unsupported algorithm names,
   - argument shapes that fail `inspect.signature(...).bind(...)`,
   - `average_shortest_path_length` with a non-default `method=...`,
   - `node_connectivity` / `edge_connectivity` / `minimum_node_cut` / `minimum_edge_cut` when a custom `flow_func=...` is supplied (fnx's native flow implementation can't honor arbitrary user callables).
3. If `can_run` returns `True`, NetworkX calls `BackendInterface.convert_from_nx(G)` to materialize an fnx graph. The conversion preserves node insertion order via the `_topo_emit_edges_by_adj` helper so adjacency order matches what nx would have iterated.
4. The bound fnx function runs.
5. NetworkX calls `BackendInterface.convert_to_nx(result)`. This recursively unwraps fnx graphs hiding inside dicts, lists, tuples, and sets, so an algorithm that returns `dict[str, fnx.Graph]` (e.g. `gomory_hu_tree` subgraphs) returns `dict[str, nx.Graph]` to the caller.
6. Functions that mutate their input (`relabel_nodes(copy=False)`, `contracted_nodes(copy=False)`, `set_node_attributes`, `double_edge_swap`, ...) follow NetworkX's dispatcher rules. Under `backend_priority` NetworkX does not auto-dispatch them, so they run in NetworkX on your graph. With an explicit `backend="franken_networkx"` on a NetworkX graph, NetworkX converts the graph and fnx mutates the converted copy — NetworkX documents this ("may change behavior by not mutating inputs") for every backend. On an fnx graph they mutate that graph in place, exactly as NetworkX would (`tests/python/test_mutating_dispatchables_state_parity.py`).

### Per-call vs application-wide

```python
import networkx as nx

# Application-wide:
nx.config.backend_priority = ["franken_networkx"]

# Per-call:
demo = nx.path_graph(10)
s, t = 0, 9
nx.shortest_path(demo, s, t, backend="franken_networkx")
```

The application-wide form still falls back to NetworkX for any algorithm fnx doesn't claim. The per-call form raises `NotImplementedError` if fnx doesn't claim the algorithm (you can wrap it yourself if you want a softer fallback).

### Fallback semantics

When `can_run` returns `False`, NetworkX uses the next backend in `backend_priority`, or pure-Python NetworkX itself. This is why FrankenNetworkX is safe to install in an existing nx codebase: in the worst case, you're back to vanilla nx.

---

## The Audit-Ledger System

The five ledgers under `docs/` are generated by scripts under `scripts/`, not written by hand. `coverage.md` is regenerated and compared on every DSR quality run (via `scripts/verify_docs.py`), so drift there fails the gate; the other four are regenerated on demand and can lag the code.

### How a public symbol gets classified

`scripts/generate_coverage_matrix.py` launches an isolated `python -I` reference process, requires the pinned NetworkX 3.6.1, discovers the installed module tree, and enumerates each module from `__all__` or Python's public wildcard namespace rule. It also adds public class members declared by NetworkX classes in their MRO. Each qualified path is compared with the corresponding FrankenNetworkX binding and classified as `present`, `partial`, `missing`, `n/a`, or `excluded`; partial signature/kind/value gaps and every exclusion reason are rendered verbatim.

The same generator retains a separate implementation-route appendix for the 843 names in `franken_networkx.__all__`: `_fnx` binding (`RUST_NATIVE`), Python wrapper (`PY_WRAPPER`), class, constant, and any `_call_networkx_*_for_parity(...)` route. It also cross-references the raw-vs-public and upstream-divergence ledgers.

The output is `docs/coverage.md`. If the pinned reference fingerprint, a qualified path, a classification, or a delegation route drifts, the regenerated file diverges from the committed file and the DSR quality run fails. A path whose shape is only declared through `__signature__`/`__module__` metadata (a class override, a look-alike enum, or a function whose declared signature is not backed by its code or its named forwarding target) is classified `partial`, not `present`.

### The five ledgers and what they catch

- `coverage.md`: *Did anyone add a public symbol without thinking about classification?*
- `raw_vs_public_audit.md`: *Did anyone introduce a parity wrapper without documenting the underlying gap?*
- `delegation_ledger.md`: *Did anyone start delegating to NetworkX without noting it?*
- `upstream_divergence_ledger.md`: *Are intentional divergences from NetworkX still owned?*
- `api_ergonomics_audit.md`: *Did a signature drift in parameter names, defaults, or keyword-only contracts?*

Only the first of these is machine-enforced today; the rest are audits that are as current as their last regeneration.

---

## Quality Gates

The only quality, build and release authority for this repository is DSR (Doodlestein Self-Releaser): `dsr quality --tool franken_networkx`, `dsr build franken_networkx`, `dsr release franken_networkx <version>`. The GitHub Actions workflows under `.github/workflows/` are kept for reference only and are not run.

The quality run executes these checks in order. `dsr quality` reads them from the `franken_networkx` entry of `~/.config/dsr/repos.yaml` on the host; `.dsr/repos.d/franken_networkx.yaml` in this repository mirrors that entry's checks and is the reviewed copy (`dsr quality --tool franken_networkx --dry-run` lists what will actually run):

| # | Check | Command |
|---|---|---|
| 1 | fmt | `cargo fmt --all -- --check` |
| 2 | check | `cargo check --workspace --all-targets` |
| 3 | clippy | `cargo clippy --workspace --all-targets -- -D warnings` |
| 4 | Rust tests | `cargo test` for `fnx-classes`, `fnx-views`, `fnx-dispatch`, `fnx-convert`, `fnx-algorithms`, `fnx-generators`, `fnx-readwrite`, `fnx-durability`, `fnx-runtime`, `fnx-conformance` (including the CGSE complexity-bound gate) and `fnx-cgse` |
| 5 | fuzz smoke | `scripts/fuzz_corpus_replay.py --budget-seconds 10`: the 33 fuzz targets are built on an rch worker with cargo-fuzz's coverage instrumentation (no sanitizer), each replays every committed corpus input and every reproducer under `fuzz/artifacts/<target>/`, then fuzzes for 10 seconds. A panic, an input over 60 s or over 4 GB RSS fails it, and the failing input is written to `fuzz/artifacts/<target>/` for later runs to replay. |
| 6 | docs | `scripts/verify_docs.py`: README/docs links, every Python block in the Markdown and every `examples/*.py` script executed, `docs/coverage.md` drift |
| 7 | Python parity (subset) and generated reports | `scripts/run_pytest_guarded.sh` on `test_instance_dict_memory_leak.py`, `test_error_messages.py`, `test_thread_safety.py`; the drift checks of `docs/coverage.md` (`test_coverage_gaps.py`) and `docs/unused_raw_exposures.md` (`test_unused_raw_exposures.py`); and the generator tests `test_delegation_ledger.py`, `test_raw_vs_public_audit.py`, `test_upstream_divergence_ledger.py`, `test_api_ergonomics_audit.py`, which run those generators and check their output's contracts but do not compare the committed ledgers |
| 8 | NetworkX's own test suite | `scripts/run_upstream_networkx_suite.py`: NetworkX 3.6.1's suite with fnx as the test backend (about 7 minutes), held to `artifacts/upstream_suite/ratchet_v1.json`. It fails on any failure the ratchet does not name with a reason, or when the pass count drops below the ratchet's floor. |
| 9 | Full Python parity suite | `scripts/run_python_parity_suite.py --workers 4`: every `tests/python/test_*.py` file in shards of explicit file lists, each through `scripts/run_pytest_guarded.sh`; fails on any failed, errored or timed-out shard and refuses to start with less than 20 GB free disk. On 2026-09-24: 1,101 files, 68,318 passed, 0 failed, 28 minutes with 4 workers. |

The conformance fixture replay runs inside check 4 (`fnx-conformance`'s `smoke_report_is_stable` replays every fixture against the current build and requires 0 mismatches); the committed reports under `artifacts/conformance/latest/` are refreshed on demand with `cargo run -p fnx-conformance --bin run_smoke`, and `scripts/verify_conformance_freshness.py` checks their age, not their correctness. Not gated, and run on demand: the performance harnesses (their measurement substrate is `br-r37-c1-rc0923-epic-honest-measurement-vbneu.4`), UBS, fuzzing campaigns longer than the smoke budget or under a sanitizer, and the RaptorQ scrub (`br-r37-c1-rc0923-epic-crown-jewels-csmqh.2`).

---

## Testing

The Python parity suite (`pytest tests/python/`) is the canonical truth. It is organized by parity flavor:

- **`test_*_parity.py`**: direct NetworkX-vs-FrankenNetworkX comparisons on fixed inputs.
- **`test_*_conformance.py`**: broad fixture-matrix parity sweeps.
- **`test_*_metamorphic.py`**: algebraic invariants (e.g., shortest-path triangle inequality, max-flow/min-cut duality, degree-sum identity, König's theorem, MST cycle property).
- **`test_*_hypothesis.py`**: property-based testing with `hypothesis` over randomized graphs.
- **`test_*_golden.py`**: frozen output snapshots that lock in current behavior against regression.
- **`test_thread_safety.py`**: concurrent dispatch under GIL release.
- **`test_error_messages.py`**: exception class + wording parity.

Run it through the guarded runner, which caps address space, RSS and wall time (an unguarded whole-suite run once drove a shared host to 148 GB RSS), and prefer targeted files or shards over one monolithic invocation:

```bash
maturin develop --release --features pyo3/abi3-py310
./scripts/run_pytest_guarded.sh tests/python/test_error_messages.py -v
./scripts/run_pytest_guarded.sh tests/python/test_*shortest*path*.py -v   # one family
```

Cross-validate against NetworkX's own test suite with fnx as the backend. The script runs it from a scratch directory under an address-space limit and holds it to the ratchet; `--target` runs one NetworkX test module in seconds:

```bash
.venv/bin/python scripts/run_upstream_networkx_suite.py                    # full run, check the ratchet
.venv/bin/python scripts/run_upstream_networkx_suite.py --target networkx.algorithms.tests.test_dag
.venv/bin/python scripts/run_upstream_networkx_suite.py --update           # after fixes: drop what now passes, raise the floor
```

Do not add `-W ignore` to a manual run: NetworkX's own `test_pajek.py::test_ignored_attribute` then fails on plain NetworkX too.

### Conformance Testing Methodology

The Python test files (about 1,100) implement five complementary testing strategies, each catching a different class of bug:

**1. Direct parity (`test_*_parity.py`).** Fix an input graph, call both `fnx.<func>(G)` and `nx.<func>(G_nx)`, assert equality. Catches "I got the wrong answer." The most basic and most numerous family.

```python
def test_dijkstra_path_parity():
    G_fnx = fnx.path_graph(20)
    G_nx  = nx.path_graph(20)
    assert fnx.dijkstra_path(G_fnx, 0, 19) == nx.dijkstra_path(G_nx, 0, 19)
```

**2. Conformance matrix (`test_*_conformance.py`).** Sweep over a fixture matrix: {path, cycle, complete, star, BA, ER, WS, bipartite} × {small, medium} × {weighted, unweighted}. Catches "I got the wrong answer on a *kind* of graph I didn't think to test individually." The conformance harness inside `fnx-conformance` writes structured logs and replay commands so a mismatch ships with a one-line reproducer.

**3. Metamorphic invariants (`test_*_metamorphic.py`).** These tests don't compare to a reference at all; they assert mathematical identities the algorithm must obey on *any* input. Catches "I got an answer that looks plausible but violates a structural law." Examples shipping today:

- **Shortest path triangle inequality.** `d(a,c) ≤ d(a,b) + d(b,c)` for all triples.
- **Max-flow / min-cut duality.** `max_flow(s,t).value == min_cut(s,t).value` on every directed graph.
- **Degree sum identity.** `sum(degree.values()) == 2 * G.number_of_edges()` on undirected.
- **König's theorem.** `len(max_matching) == len(min_vertex_cover)` on bipartite graphs.
- **MST cycle property.** Removing any MST edge and re-adding the cheapest edge in the resulting cut yields a graph of equal or greater weight.
- **PageRank stochastic invariant.** `sum(pagerank.values()) ≈ 1.0` to numerical tolerance.

**4. Property-based (`test_*_hypothesis.py`).** Use `hypothesis` to synthesize randomized graphs over arbitrary topologies and assert the same parity/metamorphic checks. Catches "I got the right answer on every hand-crafted fixture but miss a weird shape." Hypothesis shrinks failing inputs to minimal counterexamples automatically.

**5. Golden snapshots (`test_*_golden.py`).** Freeze the current output of a sensitive function on a fixed input. Any future change to the algorithm output for that fixed input fails the test loudly. Catches "I refactored the kernel and accidentally changed observable behavior." Used for tie-break-sensitive algorithms (`is_planar` on K3,3 / Petersen / K5, `dag_longest_path` tie-break, directed-distance metrics).

The five flavors live side by side in `tests/python/` and run through the guarded runner in shards; four files are part of the DSR quality run today (see [Quality Gates](#quality-gates)).

Beyond Python: the `fnx-conformance` Rust crate runs a curated *differential* harness comparing fnx outputs against the legacy NetworkX oracle (the pure-Python `legacy_networkx_code/` reference copy) over a hardened fixture matrix. It emits structured JSON logs into `artifacts/conformance/latest/`, which the dashboard generator turns into per-family parity reports that the RaptorQ tooling can encode for replay. It is run on demand, not as a gate.

---

## Performance

The performance doctrine in `AGENTS.md` is profile-first:

1. Baseline: record p50/p95/p99 and memory.
2. Profile: identify real hotspots.
3. Implement one optimization lever.
4. Prove behavior unchanged via conformance + invariant checks.
5. Re-baseline and emit delta artifact.

Hot paths that have already landed through this loop:

- Native-Rust nonfinite-weight scan for the Dijkstra / A* / PageRank +∞ gate.
- Index-based BFS + direct `PySet` emission for `connected_components`.
- Adjacency built from `G.neighbors` rather than `G[u]` for `find_cliques`.
- `square_clustering` bypasses `AtlasView` via `CachedNeighborSets`.
- `core_number` uses an O(|V|) self-loop guard rather than walking O(|E|) edges.
- `greedy_color` default routes through Rust matching NetworkX's `largest_first` tie-breaking.
- `complement` single-pass edge insertion via `extend_edges_unrecorded` / `complement_edges`.
- GIL released at hundreds of `py.allow_threads(...)` sites in `crates/fnx-python/src/algorithms.rs`.
- Sparse `HashMap` / `HashSet` adjacency replacing former O(n²) dense matrices in algorithm internals.

See [`docs/performance.md`](docs/performance.md) for guidance on benchmarking, and `examples/benchmark_comparison.py` for a runnable local A/B against NetworkX.

### Running your own benchmark

```python
import time, statistics, networkx as nx, franken_networkx as fnx

G_nx  = nx.barabasi_albert_graph(50_000, 5, seed=7)
G_fnx = fnx.barabasi_albert_graph(50_000, 5, seed=7)

def time_it(fn, *a, **kw):
    samples = []
    for _ in range(5):
        t0 = time.perf_counter()
        fn(*a, **kw)
        samples.append(time.perf_counter() - t0)
    return statistics.median(samples)

print("nx  pagerank:", time_it(nx.pagerank, G_nx))
print("fnx pagerank:", time_it(fnx.pagerank, G_fnx))

print("nx  cc:",       time_it(lambda g: list(nx.connected_components(g)),  G_nx))
print("fnx cc:",       time_it(lambda g: list(fnx.connected_components(g)), G_fnx))
```

The same script works in backend mode: leave `nx.config.backend_priority = ["franken_networkx"]` set and call only `nx.*`.

### Hot-path design notes

- **Index-based working sets.** Algorithm interiors operate on dense `Vec<usize>` node indices rather than chasing `IndexMap` lookups in tight loops. The index↔label map is built once at the start of a call via `graph.nodes_ordered()` + `graph.get_node_index(name)`.
- **Byte-array visited tracking.** BFS / DFS / SCC / matching kernels use a `vec![false; n]` byte array (≈45 sites), not `HashSet<NodeId>`, for visited tracking. One contiguous allocation per call, cache-friendly inner loops.
- **Min-heap without `Reverse` allocation.** Dijkstra-family algorithms use a custom `DijkstraState { dist: f64, seq: u64, node }` struct whose `Ord` impl reverses the dist comparison; the standard `BinaryHeap` acts as a min-heap with no per-push `Reverse(_)` wrapper.
- **FIFO tie-break in the comparator.** The `seq` insertion counter is the secondary key in `DijkstraState`'s `Ord` impl, so equal-distance entries pop in the order they were pushed (matching NetworkX's `heapq`-with-counter behavior bit-exactly). No post-pass needed.
- **Borrowed PyO3 returns.** `connected_components` emits a `PySet` per component directly from Rust instead of building a Vec first and converting in a second pass, which saves one full pass over the result.

### Cost model: when fnx wins, by how much, and why

The cost of a `fnx.algorithm(G)` call decomposes into four chunks:

| Chunk | Typical scale | Notes |
|---|---|---|
| Python → Rust marshaling | ~5–50 μs base + O(n + m) for graph conversion when a *new* graph is constructed | Reusing an existing fnx graph: ~5 μs total per call (attribute lookup only). Constructing a fresh fnx graph from an nx graph at call time: O(n + m) plus a constant ~5 μs/node, ~3 μs/edge for dict→IndexMap conversion. |
| Native algorithm execution | algorithm-dependent | Performance varies by family and workload; see the dated per-family incumbent comparison and the loss table below for current ratios. |
| Rust → Python return marshaling | O(output size) | A `PyDict::set_item` per entry plus an arc-bumped node label string. Measured 2026-07-25: **~452 ns per `edges(data=True)` entry** and **~27 ns per `nodes(data=True)` / `adjacency()` entry**. NetworkX pays more per entry on the same shapes (758 ns/edge; 1690 ns/node for `to_dict_of_lists`), because it builds the same containers in interpreted code. |
| Wrapper-side post-processing (if any) | O(output size) | Wrapper-patched functions (enumerated in `raw_vs_public_audit.md`) add a single pass over the output for iteration-order normalization. Skipped for exports without a patch. |

**Real-world end-to-end performance — current 2026-07-29 gate.** Five whole jobs
start by loading and cleaning deterministic induced prefixes of the
[SNAP Astro Physics collaboration graph](https://snap.stanford.edu/data/ca-AstroPh.html),
run multiple analysis and subgraph stages, and finish by serializing the result.
The inputs contain 1,000 / 13,410, 5,000 / 77,598, and 10,000 / 143,680
nodes/edges. NetworkX 3.6.1 and FNX run in one pinned invocation for 21
alternating-order rounds, with exact complete-output bytes, loaded-ELF identity,
and separate NetworkX/NetworkX and FNX/FNX nulls. Ratios are NetworkX wall time
divided by FNX wall time; values above 1 favor FNX. Reproduce with
`PYTHONHASHSEED=0 python3 scripts/perf_harness.py realistic-workloads`.

| Whole job | n=1,000 | n=5,000 | n=10,000 | What it means for a user |
|---|---:|---:|---:|---|
| Collaboration cohesion: load → components/core → cohort subgraph → export | **1.4898×** | **1.3232×** | **1.2039×** | FNX finishes this analysis/export pipeline sooner at all three sizes. |
| Hub routing: load → hub rank → SSSP/BFS tree → radius-2 subgraph → export | **1.5457×** | **1.1885×** | **1.2159×** | FNX finishes this routing and two-graph export pipeline sooner at all three sizes. |
| Rich-club analysis: load → rich-club/onion layers → leader subgraph → export | **2.1765×** | **1.8585×** | **1.8392×** | FNX roughly halves the wall time of this compute-heavy pipeline. |
| Link recommendations: load → core rank → Jaccard/preferential scores → export | **1.0973×** | undecidable | **1.2422×** | FNX wins at 1,000 and 10,000 nodes; the 5,000-node gate has no stable separation. |
| Community detection: load → label propagation → largest-community subgraph → assignments/export | **1.6538×** | **1.3622×** | **1.4318×** | FNX completes community detection and result export sooner at all three sizes. |

**Per-family performance — current exact incumbent gates.** The 2026-07-25 baseline uses an
n=2000 / m=8000 random graph and is reproduced with
`python3 scripts/perf_harness.py marshaling`. Rows whose notes carry another size are from the
pure-Python-loop gates and are reproduced with
`python3 scripts/perf_harness.py class1-frontier`. The n=50,000 rows use
`FNX_CLASS1_SIZES=10000,25000,50000`,
`FNX_CLASS1_EDGE_MULTIPLIERS=16`, and
`FNX_CLASS1_FRONTIER_JOBS=onion_layers,k_core`; the average-degree-128
`onion_layers` row uses `FNX_CLASS1_SIZES=1000,5000,10000`,
`FNX_CLASS1_EDGE_MULTIPLIERS=64`, and
`FNX_CLASS1_FRONTIER_JOBS=onion_layers`. All gates run genuine unpatched NetworkX
3.6.1 in the same invocation, prove exact complete-output bytes before timing, record an adjacent
A/A null, and decide only on the complete bootstrap median CI with a 2× log-space margin. The
harness also fails closed unless every CPU in the effective host cpuset stays at
or below 20% busy for five consecutive one-second pre-setup windows and five
consecutive immediate pre-measurement windows, then continuously accounts for
every non-affinity CPU in 300 ms windows throughout timing and rejects
sustained two-window contention; a narrow `taskset` affinity cannot hide
co-tenancy elsewhere on the host.

| Family | fnx vs nx | Notes |
|--------|-----------|-------|
| closeness_centrality | **194.3093× faster** | Native multi-source BFS; n=220 / m=900 |
| rich_club_coefficient | **117.3619× faster** | Native degree scan; n=10,000 / m=40,000 |
| transitive_closure | **92.3164× faster** | Native descendant closure; directed n=200 / m=800 |
| k_core | **127.6491× faster** | Native core filter; n=50,000 / m=800,000 |
| clustering (all nodes) | **36.1146× faster** | Native triangle counting |
| node_connectivity | **30.1588× faster** | Native max-flow; n=220 / m=900 |
| triadic_census | **20.4715× faster** | Native census; directed n=200 / m=800 |
| square_clustering | **18.4067× faster** | Native neighbour-pair scan; n=10,000 / m=40,000 |
| triangles | **14.3397× faster** | Native triangle counting |
| onion_layers | **122.7680× faster** | Native peeling; n=10,000 / m=640,000 |
| faster_could_be_isomorphic | **3.4961× faster** | Native degree/triangle sequence; n=1,200 / m=6,000 |
| dfs_postorder_nodes | **3.0811× faster** | Native traversal; n=1,200 / m=6,000 |
| jaccard_coefficient | **2.4536× faster** | Native neighbour-set intersection; 300 pairs |
| label_propagation_communities | **2.1827× faster** | Native label counting; n=1,200 / m=6,000; re-measured 2026-07-31 vs live nx 3.6.1 (was 2.1485×) |
| minimum_spanning_tree | **1.9947× faster** | Native Kruskal; n=1,200 / m=6,000 |
| erdos_renyi_graph (n=1500) | **12.87–13.15× faster** | Native generator; re-measured 2026-07-31 vs live nx 3.6.1 (was 14.1755×, not reproducible) |
| k_corona | no current admissible ratio | Complete-result incumbent gate awaiting an exclusive host window. Measured 8× on HEAD 2026-08-04 (`br-r37-c1-p80x1.4`) through the harness's own fixture, timing primitives and three-clause gate: **8 of 8 runs decidable at 7.7500–7.8425× (median 7.8154×, 1.2% spread), worst A/A null bias 0.0035 against a 0.0200 ceiling**, complete-result parity 292 bytes SHA-256 `1be0290d…`. The nulls are clean, so the row is not measurement-limited — it is waiting only on the host-wide exclusivity proof, which a shared checkout cannot produce. |
| k_crust | **13.2556× faster** | Native core filter; re-measured 2026-07-31 vs live nx 3.6.1 (was 5.8664×, understated) |
| kosaraju_strongly_connected_components | **4.8474× faster** | Native SCC; re-measured 2026-07-31 vs live nx 3.6.1 (was 4.6519×) |
| minimum_branching | no current admissible ratio | Native branching; the 2026-07-31 re-measure gave 3.9978× but was vetoed by A/A null bias 0.0295 > 0.0200. Re-run 8× on HEAD 2026-08-04 (`br-r37-c1-p80x1.14`) against the same preregistered fixture, with input and complete-output SHA-256 both matching: the effect is stable at 4.2831–4.4494× (median 4.4119×, 3.9% spread) and **6 of 8 runs clear all three clauses**. The 2 vetoes were clause 3 only, once from each arm's null — a single-draw null flake, not a property of the workload. Still not converted: those runs could not carry the host-wide exclusivity proof. |
| partition_spanning_tree | **2.4612× faster** | Native Kruskal with partition constraints; CONFIRMED 2026-07-31 vs live nx 3.6.1 (measured 2.3794×, CI [2.3303, 2.5633] contains the published figure) |
| dfs_successors | **2.3223× faster** | Native traversal; re-measured 2026-07-31 vs live nx 3.6.1 (was 2.1456×) |
| read_graph6 / read_sparse6 | **1.72× / 1.69× faster** | Native decoders; CONFIRMED 2026-07-31 vs live nx 3.6.1 (measured 1.7202× / 1.7069×, both CIs contain the published figures) |
| all_simple_edge_paths | **1.3384× faster** | Native path enumeration; re-measured 2026-07-31 vs live nx 3.6.1 (was 1.3466×) |
| dijkstra_path (weighted) | **7.6077× faster** | Native bidirectional kernel + persistent dense node ids |
| single_source_shortest_path_length | **5.1868× faster** | Native BFS, dict returned from Rust; re-measured 2026-07-31 vs live nx 3.6.1 (was 5.5005×, overstated) |
| all_pairs_shortest_path_length (n=300) | **4.5647× faster** | Algorithmic work dominates |
| single_source_shortest_path | **3.8952× faster** | Native BFS |
| all_pairs_dijkstra_path_length (n=300) | **3.6658× faster** | Algorithmic work dominates |
| subgraph(view) → edges | **3.5212× faster** | Native induced-subgraph walk; re-measured 2026-07-31 vs live nx 3.6.1 (was 3.5719×) |
| dfs_tree | **3.3439× faster** | Native traversal + native result construction |
| single_source_dijkstra_path_length | **3.3325× faster** | Native Dijkstra |
| bfs_tree | **3.2403× faster** | Native traversal + native result construction |
| single_pair_shortest_path | **3.3313× faster** | Native BFS; re-measured 2026-07-31 vs live nx 3.6.1 (was 3.1614×) |
| pagerank | **2.6361× faster** | Native CSR build + SciPy power iteration (the same iteration as `nx.pagerank`); CONFIRMED 2026-07-31 vs live nx 3.6.1 (measured 2.7275×, CI [2.5777, 2.8818] contains the published figure) |
| to_scipy_sparse_array | **2.4758× faster** | Native CSR assembly; re-measured 2026-07-31 vs live nx 3.6.1 (was 2.4073×) |
| to_dict_of_lists | **1.9662× faster** | Native row walk |
| bidirectional_dijkstra | **1.7916× faster** | Native bidirectional kernel; re-measured 2026-07-31 vs live nx 3.6.1 (was 1.8125×) |
| shortest_path (weighted) | **1.8343× faster** | Native weighted-path kernel; re-measured 2026-07-31 vs live nx 3.6.1 (was 1.7684×) |
| all_pairs_shortest_path (n=300) | **1.7624× faster** | Result construction dilutes the kernel win |
| edges(data=True) | **1.5555× faster** | re-measured 2026-07-31 vs live nx 3.6.1 (was 1.6085×) |

**Scalar multigraph degree access — measured 2026-07-27** (2,000 nodes / 1,999
path-shaped edges, 512 exact-string lookups per sample, genuine unpatched NetworkX
3.6.1 side-by-side in the same invocation, with an A/A null control and bootstrap
median-CI gate; reproduce with
`FNX_PERF_ROUNDS=61 python3 scripts/perf_harness.py multigraph-degree-scalar`):

| Surface | fnx vs nx | Bootstrap 95% CI |
|---|---:|---:|
| `MultiGraph.degree[node]` | **1.47× faster** | `1.4389–1.5295×` |
| `MultiDiGraph.degree[node]` | **2.20× faster** | `2.1125–2.2690×` |

**Known remaining measured losses:**

> **Where a row ran is part of the row.** From 2026-08-15 every figure added here
> names the HARNESS that produced it and the machine both arms ran on, because
> neither is recoverable afterwards and both move ratios: two separately
> sanctioned harnesses read one primitive `~2x` apart on the same build with both
> A/A nulls passing (`br-r37-c1-y4r63`), and elsewhere in the fleet worker
> identity alone moved a ratio `13.6x`, also with passing nulls. A passing null
> certifies stationarity within one run; it does not certify that two runs are
> comparable. Rows below that predate this convention do not name their harness —
> that is a gap in those rows, not a verdict on them.

| Surface | fnx vs nx | Cause |
|--------|-----------|-------|
| `G.adj` (bare accessor) | **0.9009×** | Public descriptor access; re-measured 2026-08-04 vs live nx 3.6.1 (was 0.82×). 6/6 runs decidable, 0.8962–0.9079× (1.3% spread), A/A nulls within 0.0035 of 1.0, result parity 7,446,000 bytes. Reproduce with `PYTHONHASHSEED=0 taskset -c 40-43 python3 scripts/perf_harness.py adj-descriptor`. **Figure status: stale** — every lever bead (pc4hk, dyuzb, a5xrj, s3ctn, bmrbc/nic2n) closed and `ey6ob` refuted the descriptor-rebuild reading; the row awaits an admissible re-measure to convert or retire. Open. |
| `len(G.adj)` | **1.65–1.71×** | **Was a loss at `0.7901×` (2026-08-04) and is now a win.** `G.adj` returns a subclass of the native adjacency view, so `__len__` resolves to a C slot instead of a Python frame — `G.nodes` and `G.edges` already did, on the same graph returning the same count (`br-r37-c1-5gam7`, landed 2026-08-08 `f9e3173c3`). Re-measured 2026-08-08 vs live nx 3.6.1 in the same invocation: `1.6548×` CI `1.6447–1.6641×`, dual A/A nulls `1.0004` and `1.0047`, direction unanimous 4/4 (`1.6021/1.6670/1.6625/1.6548`). The identical script on the pre-change build read `0.7624–0.7892×`, so this is measured against its own before. Re-confirmed 2026-08-08 at `1.7097×` CI `1.7055–1.7135×` (nulls within 0.0003 of 1.0); the range spans both admitted runs. Reproduce: balanced `[A B B A A B B A]` square, N=2000, 500 `len()` calls per timed unit, 25 rounds, `taskset`-pinned. |
| `G.has_node(n)` | *not decidable* (present keys) | **The 1.23× win published here earlier on 2026-08-15 is RETRACTED** (`br-r37-c1-7x25w`). It was measured on a harness that ran `gc.collect()` before every timed slot; re-measured on the corrected harness at a rep count where the nulls pass, three draws read `1.0008×` (straddles 1.0), `1.0159×` and `0.9799×` — parity in both directions, so no verdict is claimed. The per-slot collect was worth only ~1% on THIS row (`1.0811×` corrected vs `1.0925×` in defect mode at reps=400), and the ELF also moved under other agents' Rust landings, so the cause of the difference is unattributed rather than assigned. The LEVER is unaffected: the memo still removes the canonical rebuild that is 77.4% of this call's instructions, and its parity tests stand. What was a loss before that lever (`0.7595×`, 2026-08-08) is now parity. **ABSENT keys remain a loss** at `0.6610×`. Earlier context, all superseded: `0.5199×`, `0.4596×`, `0.41×`. Keys already proven present are remembered in a set, so a repeat probe reuses the hash CPython cached in the string object instead of rebuilding and rehashing a canonical `"str:{len}:{s}"` — 77.4% of this call's instructions, by toggle-collect profile. Measured vs live nx 3.6.1 in the same invocation, balanced `[A B B A A B B A]` square, 61 rounds: `1.2297×` CI `1.2048–1.2574×`, A/A nulls `1.0107`/`1.0037`, ELF `1cfe8f2483a780e7`. Prior published figures were correct for their builds: `0.7595×` (2026-08-08), `0.5199×`, `0.4596×`, `0.41×`. **ABSENT keys are a loss and got slightly worse**: `0.6610×`, because a miss pays the set probe and then the canonical path anyway (bounded at ~1.19× of the un-memoised cost, measured). Reproduce: `scripts/balanced_square_ab.py --workload view-reads --only "G.has_node"`. Two independently written harnesses agree on this row — `1.2205×` CI `1.1861–1.2318×` from the view sweep and `1.2297×` from `balanced_square_ab.py`, overlapping CIs on the same ELF. `harness=balanced_square_ab.py` + `ab_view_sweep2.py`, `same_host=thinkstation1`, `rch_worker=none` (both arms in one process; no timing was dispatched to a worker). |
| `n in G` | **1.49–1.68× faster** (present keys) | **Was published at 1.2234×, corrected to a 0.3328× LOSS on 2026-08-14, and is a WIN again since 2026-08-15** — same lever as `G.has_node` above (`br-r37-c1-6n9vm`), which the 2026-08-14 row predates. Four admitted draws vs live nx 3.6.1 in the same invocation, 61 rounds, present string keys: `1.4917×` CI `1.4475–1.5212×`, `1.5622×`, `1.6729×`, `1.6841×` CI `1.6443–1.7174×`, A/A nulls within 0.019 of 1.0, ELF `1cfe8f2483a780e7`. **The range is the honest figure** — the cross-run spread exceeds any single CI, and two of those draws were measured with the row's neighbours running in the same process, which is itself worth ~1.20× on this surface (`br-r37-c1-y4r63`). **CONFIRMED after the substrate fix** (`br-r37-c1-7x25w`): the draws above came from a harness that collected before every timed slot, and re-measuring on the corrected one gives `1.6113×` CI `1.6025–1.6199×`, nulls 1.0092/1.0018, ELF `b6ccaee611a8ef67` — inside the published range, so this row survives a correction that retracted its sibling. ABSENT keys remain a loss at `0.8797×`. `harness=balanced_square_ab.py` + `ab_view_sweep2.py` (kept at `tests/artifacts/perf/20260815-dunder-wrapper-ablations-snowyvalley/`), `same_host=thinkstation1`, `rch_worker=none` (both arms in one process; no timing was dispatched to a worker). |
| `preferential_attachment` | **0.8635×** | Superseded figure: the old 0.5949× row predated the `padm6` fix (91% of the gap); closed re-measure `z00k8` reads 0.8635×. Residual loss is per-call boundary cost — nx's per-pair work is two degree lookups and a multiply. |
| Incremental `add_edge`, one call per edge | **`Graph` 0.90–1.02×, `DiGraph` 1.04–1.07×** without attributes; **0.66× / 0.71×** with `weight=` | Fresh graph of 400 `add_edge` calls per timed op. `Graph` / `DiGraph`: a path on ints from empty `0.8974×` / `1.0389×`, shuffled Barabási–Albert edges on ints `0.9726×` / `1.0477×`, the same with str names `1.0150×` / `1.0721×`, and with `weight=1.0` on every call `0.6568×` / `0.7057×`; every CI within ±0.005 of its median. Measured 2026-09-25, `harness=scripts/balanced_square_ab.py --workload claim-add-edge --calls-per-slot 4`, 41 rounds, live nx 3.6.1 in the same invocation, `taskset -c 46`, ELF `77b10b8813b8f549` (the lazy-mirror lever of `1e484d215`), `same_host=thinkstation1`, 9/9 rows admitted, A/A nulls within 1.0 ± 0.012. The build before that lever, measured the same way, read `0.5828×` / `0.6083×` with `weight=`; before `677b5b977`, `0.44×` / `0.41×`. The attributed calls still lose: each one converts its keyword dict into the native attribute map (`br-r37-c1-olyn6`). Batch constructors remain better per edge. |
| `karate_club_graph` | **1.38–1.42×** | **Was published as a `0.38×` loss and is now a win.** Re-measured 2026-08-08 vs live nx 3.6.1 in two admitted runs: `1.4232×` CI `1.4150–1.4273×` and `1.3812×` CI `1.3745–1.3879×`, dual A/A nulls within 0.0016 of 1.0. The range is the honest figure — the two runs' CIs do not overlap, which is this substrate's cross-run spread rather than either run being wrong. |
| `tutte_graph` | *not decidable* | Measured 2026-08-08 at `1.2860×` but CI `0.9036–1.3563×` STRADDLES 1.0, so no verdict is claimed despite clean A/A nulls (0.9997/0.9997). The published `0.76×` is superseded but not replaced with a number. Split out of the old combined karate/tutte row precisely because the two no longer share a verdict. |
| `read_multiline_adjlist` | **0.7981×** | Parser is not native; still a loss, re-measured 2026-07-31 vs live nx 3.6.1 (was 0.70×) |
| `read_gml` | **0.92×** | GML parse path; CONFIRMED 2026-07-31 vs live nx 3.6.1 (measured 0.9234×, CI [0.9169, 0.9253] contains the published figure) |
| `G.remove_node(n)` | **0.52× → 1.75×** on `Graph`, **0.78× → 1.31×** on `DiGraph`, **0.60× → 0.76×** on `MultiGraph`, **0.32× → 0.45×** on `MultiDiGraph` (n=1,600 → 25,600, non-tail node) | `Graph`/`DiGraph` removal is O(degree), like nx's: the node's slot is tombstoned in O(1) and positions are ranks answered by a Fenwick tree until the next insertion compacts. The per-call cost is a flat ~2.5–3.5 µs, so it loses where nx's removal is cheaper (`Graph` 0.52× / 0.53× at 1.6k / 6.4k nodes, `DiGraph` 0.78× at 1.6k) and wins where nx's grows (`Graph` 1.75× at 25.6k, `DiGraph` 1.78× / 1.31× at 6.4k / 25.6k). `MultiGraph` removal is O(degree) as well (its insertion order tombstones apart from the slots, which are reused), but it loses at every size, 0.60× / 0.60× / 0.76× at 1.6k / 6.4k / 25.6k (median of 3 runs, loadavg ~5). Those graphs are built with `add_edges_from`, which leaves the Python attribute mirrors of the edges empty, and removal skips them when they are; a graph built one `add_edge` at a time fills them and loses more (0.27–0.30×). `MultiDiGraph` removal is O(degree) too (its node table tombstones and its row maps are unordered) and loses more, 0.32× / 0.51× / 0.45×: its String-keyed store frees about seven blocks per incident edge, and cutting its instruction count by 38% moved no wall-clock time; a slot-keyed store like `MultiGraph`'s is the lever left. With an attribute on every edge a removal also updates the Python attribute mirrors of each incident edge (11–17 µs per removal at 1.6k–25.6k; 0.2–0.5× in read-then-remove loops). Measured 2026-09-24 (fresh graph per repetition, 200 removals, min of 3, same process, loaded host, `harness=ad-hoc scaling probe`, `same_host=thinkstation1`). Open: `br-r37-c1-epic-storage-architecture-yr2oc.1`. |
| `MultiGraph`/`MultiDiGraph.get_edge_data(u, v)` (unkeyed) | **0.57–0.62×** per call, flat from 1 to 16 parallel edges; consuming it (items + one attribute read) **0.73–0.89×** | Since 2026-09-24 it returns the pair's live keydict as a real `dict` kept in step with every edge mutation (was 0.2482× → 0.0274× when it rebuilt a dict per call, then a non-`dict` view whose consumption cost 0.16–0.40×). `json`/`pickle`/`copy`/`|` behave as in nx; it is a `dict` subclass that forwards writes to the graph, so `type(d) is dict` is False. Same-process sanity probe, 2026-09-24, loaded host (load 46), no A/A null. |
| Attributed-graph memory | **3.4×** nx's RSS (1.8× via `set_edge_attributes`) | Edge attributes are stored twice (native `AttrMap` + Python dict); unattributed graphs use 0.63× of nx's memory. See "Memory considerations". Sanity measurement, 2026-09-24, no A/A null. |
| Backend mode on an nx graph, conversion cache off | **0.026–0.40×** for cheap kernels | Every call converts the nx graph first (a few µs per edge): `single_source_shortest_path_length` 0.026×, `connected_components` 0.031×, `pagerank` 0.21×, weighted `single_source_dijkstra` 0.40× on a 20k-node BA graph. With NetworkX's default conversion cache on, the same calls win 1.7–17×. Same-process sanity probe, 2026-09-23, no A/A null. Tracked: `br-r37-c1-rc0923-epic-perf-where-we-lose-sfq4w.2`. |
| `G.has_edge(u, v)` / `list(G.neighbors(n))` | int nodes: **1.17–1.42×** / **1.05–1.12×**, except `has_edge` on present edges of a graph whose int nodes arrived out of order (**0.975×**); str nodes: **1.02–1.28×** / **1.05–1.06×**, except `DiGraph.has_edge` on present edges (**0.975×**) | `Graph` and `DiGraph`, 20k-node BA graph, 400 calls per slot. Balanced-square A/B with A/A nulls (`scripts/balanced_square_ab.py --workload claim-has-edge-neighbors --calls-per-slot 128`), every row admitted, pinned to one CPU, thinkstation1, 2026-09-25: int rows ELF `476699fdfcd1`, str rows ELF `73d0af80fbab` from the same harness with str-named nodes. Tracked: `br-r37-c1-rc0923-epic-perf-where-we-lose-sfq4w.3`. |
| `louvain_communities` (weighted) | **0.92×** | Runs NetworkX's own code on weighted input, plus the conversion. Same-process sanity probe, 2026-09-23, no A/A null. |
| `G[u][v]` | **`Graph` 1.09–1.24×, `DiGraph` 1.07–1.09×; `MultiGraph` 0.43–0.50×, `MultiDiGraph` 0.42–0.50×** | Measured 2026-09-25, `harness=scripts/balanced_square_ab.py --workload row-subscript-family --reps 200 --rounds 41 --warmup 60 --calls-per-slot 128`, live nx 3.6.1 in the same invocation, `taskset -c 44`, `same_host=thinkstation1`, node keys of 3 and 2,000 characters (flat in key length on every class). Admitted rows only; the ranges span four invocations, because the same binary moved about 13% between invocations on a loaded host while each CI is under 1%. `Graph` and `DiGraph` rows are the native `AtlasView`, whose `__getitem__` is a C slot with a cached row index; the within-run `DiGraph`/`Graph` ratio went from 0.63–0.64 to 1.00–1.01 when `DiGraph` rows moved onto it (ELF `1c2cb2b1220f7da2`), while the multigraph/`Graph` control held at 0.40–0.41. The multigraph rows still pay stacked Python view layers per subscript. Open for the multigraphs: `br-r37-c1-ey6ob`. |

The `add_edge` row is one call per edge on a fresh graph, so each timed op is stationary: a graph
that grew across timed slots would fail its own A/A null. The native method's own cost, in
instructions per call (callgrind toggled on the method, fresh int graph, slope between 2,000 and
4,000 calls): about 4,200 for `DiGraph` and 4,500 for `Graph` without attributes, 7,000 and 7,200
with one. The CGSE decision ledger still files one record per call; its
cost against the pre-`br-r37-c1-wa1b9` counterfactual reproduces with
`env -u CARGO_TARGET_DIR taskset -c 40-47 cargo test -p fnx-classes --release ledger_record_cost_ab -- --ignored --nocapture`.

Default simple-graph `write_edgelist(data=False)` writes directly from FNX edge
iteration while preserving exact NetworkX bytes. Non-default and multigraph
writer configurations retain their compatibility routes.

---

## Algorithm Implementation Notes

The native algorithm implementations in `fnx-algorithms` favor textbook complexity bounds with one consistent twist: **every tie-break is pinned by a CGSE policy and recorded in the witness ledger**. The notes below cover the most-used families.

### Shortest path

- **Dijkstra.** Standard binary-heap Dijkstra. Internally uses a `DijkstraState { dist: f64, seq: u64, node }` struct whose `Ord` impl reverses the dist comparison (so a max-heap acts as a min-heap, with no per-push `Reverse(_)` wrapper) and tie-breaks equal-distance entries by insertion-counter `seq` to match NetworkX's `heapq`-with-counter behavior exactly. Single-source / multi-source / bidirectional all share the same kernel. The `+∞` and negative-weight gates are short-circuit native scans before the algorithm enters its main loop; invalid input fails fast or delegates to `nx` per the documented contract.
- **Bellman-Ford.** O(VE) relaxation with predecessor reconstruction. Negative-cycle detection scans the last-pass relaxation; the canonical error wording matches NetworkX's exact string (regression-locked in `test_bellman_ford_negative_cycle_message_parity.py`).
- **A*.** Standard heuristic-guided Dijkstra. The heuristic callable contract was tightened in commit [`b7d9e785`](https://github.com/Dicklesworthstone/franken_networkx/commit/b7d9e785) (`franken_networkx-74xw`) to honor NetworkX's exact signature.
- **Johnson all-pairs.** Edge re-weighting via Bellman-Ford + Dijkstra from every source. The inner-dict ordering of `johnson` was specifically locked to NetworkX's order in `br-r37-c1-9l73c`.

### Connectivity

- **Connected components.** Index-based BFS with a packed visited bitset. Emits `PySet` per component directly through PyO3, skipping a Vec → set conversion pass.
- **Strongly connected components.** Tarjan's iterative variant (avoids Rust stack overflow on deep DAGs). Kosaraju is available as `kosaraju_strongly_connected_components` for parity tests where NetworkX uses it specifically.
- **Articulation points / bridges.** Single DFS, parent-tracking, low-link propagation. The DFS visit order is the documented `BfsLevelLex` / `DfsPreorder` variant from CGSE.
- **Node / edge connectivity, min cuts.** Built on max-flow over a residual graph; custom `flow_func` callables are explicitly rejected by `can_run` so nx's slower-but-flexible path takes over when needed.

### Centrality

- **PageRank.** The public `pagerank` builds the adjacency as CSR arrays natively in Rust, then runs the damped power iteration as a scipy sparse matvec mirroring nx's `_pagerank_scipy` float for float (`br-r37-c1-y5y7i`, 2026-05-24); the nonfinite-weight scan and dangling handling stay native. A Rust power-iteration kernel exists as `_fnx.pagerank` but is not on the public route, so `pagerank` requires scipy, exactly as it does in NetworkX.
- **Betweenness.** Brandes' algorithm. Subset variants (`betweenness_centrality_subset`, `edge_betweenness_subset`) share the same accumulator infrastructure.
- **HITS.** Power iteration on the adjacency operator and its transpose. `numpy` variants offload eigensolvers to SciPy with sign/basis tolerance baked into the test layer.
- **Katz / eigenvector / closeness / harmonic.** Standard formulas. `harmonic_centrality` specifically matches NetworkX's set-based dict iteration order (locked in `br-r37-c1-rsom6`).
- **Voterank.** Iterative selection with explicit `LexMin` tie-break.

### Matching

- **Maximum-weight matching.** The public `max_weight_matching` runs `networkx_max_weight_matching_mate`, a step-for-step Rust port of networkx's blossom algorithm (`br-r37-c1-epic-native-algorithms-1g0lj.1`): it makes every order-dependent choice in networkx's order and returns networkx's `mate` insertion order, so on graphs with several optimal matchings it picks networkx's, with networkx's `(u, v)` direction for each pair (an earlier native kernel did neither, `br-r37-c1-kpnc8`). Weights other than ints within ±2⁴⁸ and finite floats keep networkx's own code. `min_weight_matching` is networkx's body over it (the inverted graph built as networkx builds it). Both raise `NetworkXNotImplemented` on directed and multigraph input, as networkx does.
- **Maximal matching.** Greedy with canonical edge enumeration; suitable as a lower-bound approximation.
- **Bipartite matching helpers (`hopcroft_karp_matching`, `eppstein_matching`, `minimum_weight_full_matching`).** Live under `fnx.bipartite.*` and currently delegate to the upstream `networkx.algorithms.bipartite` reference. Tracked in `docs/delegation_ledger.md`.

### Flow

- **Maximum flow.** Edmonds-Karp on the residual graph; the BFS traverses *only* residual neighbors (not the full node set; that bug-fix landed early in the project and is locked by tests).
- **Stoer-Wagner.** Native O(V·E + V²·log V) global min-cut.
- **Gomory-Hu tree.** Native; rejects MultiGraph input with a typed `NetworkXError` matching nx.
- **Min-cost flow.** Successive-shortest-path + Bellman-Ford for negative-edge support; delegates to nx for undirected input (`NetworkXNotImplemented`).
- **Exact-integer network simplex (`fnx_algorithms::network_simplex_int`).** The exact-integer primal network-simplex kernel is a first-class Rust API, re-exported from the `fnx-algorithms` crate root, so sibling Rust consumers can reach the exact min-cost-flow path directly without taking a PyO3 dependency. It is specialised to `i64` demands/capacities/weights — the only byte-exact-integer case — with no `f64` anywhere on the path, so results are exact and reproducible. Originally this pivot logic lived inside the `fnx-python` binding; it was hoisted into `fnx-algorithms` in commit [`6de8937d`](https://github.com/Dicklesworthstone/franken_networkx/commit/6de8937d), and the Python `network_simplex` binding now delegates to this shared kernel, so the Rust API and the Python binding run identical pivot code and produce byte-identical numeric results. The block/Dantzig+Bland entering-edge search and the first-minimiser leaving-edge tie-break (matching Python's `min`) are deterministic and covered by unit tests (`determinism_across_repeated_runs`, `known_integer_optimum`).

### Trees and arborescences

- **MST.** Kruskal's with union-find; `partition_spanning_tree` / `random_spanning_tree` / `number_of_spanning_trees` are exposed.
- **Edmonds' branching.** Native rewrite (commit [`9edb5819`](https://github.com/Dicklesworthstone/franken_networkx/commit/9edb5819)) using explicit `EdmondsMultiDiGraph` + `UnionFind` structures; deterministic edge sort.
- **SpanningTreeIterator / ArborescenceIterator.** Janssens-Sörensen partition scheme for lazy enumeration of all minimum spanning trees / arborescences; the partition logic is module-level and reusable.

### Community

The `fnx.community` submodule mirrors `nx.algorithms.community`. Most algorithms currently route through nx after parity-converting the graph (the `_networkx_graph_for_parity` adapter); the native rewrites are landing one by one.

- **Louvain (`louvain_communities`).** A native Rust kernel (`_raw_louvain_communities`) handles a plain unweighted `fnx.Graph` without self-loops. Every other shape (weights, self-loops, directed, multigraph, nx input) converts and routes through `nx.algorithms.community.louvain_communities`, pinned to the networkx backend so a global `backend_priority` cannot recurse (`br-r37-c1-egjfn`); nx's multi-level Louvain produces wrong partitions against a raw fnx graph, hence the conversion.
- **Label propagation (`label_propagation_communities`).** A Python implementation over native `greedy_color` and adjacency for `fnx.Graph`; multigraph, view and non-fnx inputs route through nx (`br-r37-c1-cy2me`).
- **Greedy modularity (`greedy_modularity_communities`).** Runs `networkx_greedy_modularity_merges`, a step-for-step Rust port of networkx 3.6's Clauset-Newman-Moore loop (`br-r37-c1-epic-native-algorithms-1g0lj.3`): its `MappedQueue` heaps with equal gains broken by node label, as networkx's `_HeapElement` compares them, and the same float arithmetic from the same setup values. The merges are replayed into networkx's `communities` dict, so the result is networkx's: the same communities in the same order, each frozenset built the same way. Measured 12.3–13.4× faster than networkx on 2,000–5,000-node graphs (weighted and unweighted) with identical results; same-process interleaved probe, 3 rounds, A/A null 0.96–1.03, loaded host (load 39), 2026-09-24. Graphs whose node labels are not all `int` or all `str`, weights other than ints within 2⁵³ and floats, and NaN gains keep networkx's own code, which is also the backend-mode fallback, pinned so it cannot recurse. An earlier native route was retired for picking different equal-gain merges (`br-r37-c1-z4rnj`).
- **K-clique communities, Girvan-Newman, asyn_fluidc, Kernighan-Lin bisection.** Mixed: some native, some delegated. Check `docs/delegation_ledger.md` for the canonical state of each.
- **`community.modularity`.** Computed natively against fnx adjacency.

### Isomorphism

- **VF2 / VF2++.** Native no-label VF2++ implementation. With node/edge label callbacks, the algorithm falls back to NetworkX's reference matcher to honor the user-provided callable contract.
- **`could_be_isomorphic` / `fast_could_be_isomorphic` / `faster_could_be_isomorphic`.** Quick degree/clustering invariant checks before invoking the full matcher.

### Planarity

- **`is_planar` / `check_planarity`.** `is_planar` runs Euler and degree bounds and then the native left-right planarity kernel (`is_planar_lr`), so K5, K3,3 and Petersen are decided in Rust. `check_planarity` builds native `PlanarEmbedding` clockwise rotation orders (Boyer-Myrvold edge-addition) and extracts native Kuratowski subgraph counterexamples without NetworkX.

### DAG

- **Topological sort.** Kahn's algorithm with zero-in-degree nodes queued in insertion order (the registry's `InsertionOrder` policy); matches nx's order exactly, including ties.
- **Transitive closure.** O(V·(V+E)) DFS-based, preserves node + edge attributes on the DAG fast path (regression `br-r37-c1-gtkxs`).
- **Dominators.** Cooper-Harvey-Kennedy iterative algorithm: reverse-postorder DFS followed by intersect-by-walking-up until fixpoint. `immediate_dominators` + `dominance_frontiers`.

### Polynomial / spectral

- **Tutte polynomial / chromatic polynomial.** Native straight-line deletion-contraction recursion (exponential time, no memoization; intentional, matching NetworkX's reference behavior on small graphs).
- **Spectral helpers.** `laplacian_spectrum`, `adjacency_spectrum`, `modularity_spectrum`, `fiedler_vector`, `algebraic_connectivity`; built on `scipy.linalg.eigh` / `scipy.sparse.linalg.eigsh`. Solver-method validation (`fiedler_method`) is enforced (`br-r37-c1-pvge4`).

### Generators

- **Random generators (BA, WS, GNP, GNM, fast_GNP).** Deterministic seeded RNG; edge enumeration order matches NetworkX byte-for-byte where contracted (`waxman_graph` is locked byte-for-byte; `erdos_renyi_graph` seed parity is locked).
- **Stochastic block model.** Native; preserves user-supplied `nodelist` order.
- **Random tree (Prüfer).** Native O(n) Prüfer-sequence sampling.
- **Navigable small world.** Native Kleinberg implementation.
- **Lattice generators.** Native Rust `hypercube_graph`; pure-Python `grid_graph`, `hexagonal_lattice_graph`, `triangular_lattice_graph` (compose into native primitives but stay at the Python layer since the cost is dominated by the construction loop, not by per-edge insertion).

---

## Internals Walkthrough

A guided tour of the moving parts in a single algorithm execution. Useful for new contributors and for anyone debugging an edge case.

### Step 1: Python wrapper entry

Every public algorithm name in `franken_networkx.*` resolves through the package's `__getattr__` or its 3 MB, 70,000-line `__init__.py`. A typical wrapper does these things in order:

1. **Argument validation.** Check that the graph is a supported type, that node arguments exist, that weight strings are hashable. Errors raised here use the same class and message as `nx`.
2. **Boundary coercion.** If the user passed an `nx.Graph`, convert it via `_networkx_graph_for_parity` (which uses `_topo_emit_edges_by_adj` to preserve adjacency order).
3. **Argument-shape dispatch.** For ~125 functions, check whether the call shape is one the native fast path handles. If not, route through `_call_networkx_for_parity` or `_call_networkx_submodule_for_parity` and return nx's answer.
4. **GIL-releasing call into the Rust kernel** via `franken_networkx._fnx.<bound_name>`.
5. **Post-processing**, if the function is one of the 24 wrapper-patched ones.

### Step 2: PyO3 binding (`crates/fnx-python/src/algorithms.rs`)

The cdylib re-exports algorithm functions as `#[pyfunction]`s. The `pagerank` binding, which the public wrapper does not currently use because it prefers the scipy route (simplified; the real signature also takes `personalization`, `nstart` and `dangling`, and raises `NetworkXNotImplemented` if any of them is given):

```rust
#[pyfunction]
#[pyo3(signature = (g, alpha=0.85, max_iter=100, tol=1.0e-6, weight="weight"))]
pub fn pagerank(
    py: Python<'_>,
    g: &Bound<'_, PyAny>,            // accepts a fnx graph or an nx graph
    alpha: f64,
    max_iter: isize,
    tol: f64,
    weight: Option<&str>,
) -> PyResult<Py<PyDict>> {
    let graph: PyRef<'_, PyGraph> = g.downcast::<PyGraph>()?.borrow();
    let result: HashMap<String, f64> = py.allow_threads(|| {     // ← GIL released
        fnx_algorithms::pagerank(&graph.inner, alpha, max_iter as usize, tol, weight)
    });
    let dict = PyDict::new(py);                                  // ← GIL reacquired
    for (node, score) in result {
        dict.set_item(node, score)?;
    }
    Ok(dict.into())
}
```

GIL release is critical: without it, concurrent Python threads calling fnx algorithms would serialize on the interpreter lock. With it, each call holds only its own Rust adjacency borrow for the duration.

### Step 3: Native algorithm (`crates/fnx-algorithms/src/lib.rs`)

A Rust kernel builds dense node-index working data from the `IndexMap`-keyed adjacency, runs the algorithm body on indices, and returns the natural result type (`HashMap<String, f64>` for pagerank). The CGSE reference kernels (Dijkstra, Bellman-Ford, BFS/DFS, components, Kruskal, ...) additionally:

1. call `cgse_begin(CgseReferenceAlgorithm::<Name>)` to open a witness sink (a no-op unless witness collection is active);
2. call `cgse_record_decision(...)` at tie-break points;
3. call `cgse_publish(...)` at the end to finalise the witness into the thread-local `WitnessLedger`.

PageRank is not one of them and emits no witness.

### Step 4: Result marshaling

PyO3 walks the returned Rust collection and constructs the corresponding Python container. For a `HashMap<String, f64>` returning a `PyDict`, this is N hash insertions; for a `Vec<HashSet<String>>` returning a list of `PySet`, this is one nested walk.

### Step 5: Witness ledger drain (optional)

If the conformance harness or a Rust integration test wrapped the call in `collect_witnesses(...)`, the `WitnessLedger` is drained at scope exit and the per-call `ComplexityWitness`es are returned to the caller. From normal Python use, the witnesses are emitted into the thread-local ledger but typically not collected: they're available if you want them and don't cost anything if you don't.

### Anatomy of `PyGraph`

The Python-visible `franken_networkx.Graph` is implemented as a PyO3 `#[pyclass]` named `PyGraph` whose state has *two* tiers (simplified below: the real struct has 19 `pub(crate)` fields, the rest being caches, generation counters and index lookasides):

```rust
#[pyclass(module = "franken_networkx", name = "Graph", dict, weakref, subclass)]
pub(crate) struct PyGraph {
    pub(crate) inner: Graph,                                  // the Rust adjacency map
    pub(crate) node_key_map: HashMap<String, PyObject>,        // canonical key → original Py object
    pub(crate) node_py_attrs: HashMap<String, Py<PyDict>>,     // per-node Python attr dict
    pub(crate) edge_py_attrs: HashMap<(String, String), Py<PyDict>>,  // per-edge Python attr dict
    pub(crate) graph_attrs: Py<PyDict>,                        // graph-level attr dict
}
```

The two-tier design is deliberate:

- **`inner: Graph`**: the canonical adjacency the Rust algorithm kernels iterate. Attribute values inside `inner` use `CgseValue` (serde-typed), which is the form algorithms want and which serializers can round-trip without information loss.
- **`node_py_attrs` / `edge_py_attrs` / `graph_attrs`**: *real* Python `PyDict`s that the Python-visible `G.nodes[u]`, `G.edges[u, v]`, and `G.graph` views point to. Mutations like `G[u][v]["weight"] = 2.0` land here first because the user expects standard dict semantics (live views, identity, subclass support). These mirrors are materialised lazily: a graph built natively (generators, batch constructors) keeps its attributes only in `inner` until something reads them through a Python view, so code that asks "does any edge carry this attribute?" must consult `inner` too.
- **`node_key_map`**: preserves the original Python object that became the canonical string key, so iteration returns the same Python object the user passed in (`G.add_node(("a", "b"))` then `list(G.nodes())[0]` returns the *same tuple instance*, not a re-constructed one).

The `_sync_rust_edge_attrs(G)` helper bridges the two: when an algorithm needs current edge attributes, it copies the Python-side dict into `inner` in `CgseValue` form first. This is why a `G[u][v]["weight"] = 2.0` mutation is immediately visible to downstream weighted algorithms, at the cost of a sync pass scoped to the algorithm call.

---

## Working With Attributes

NetworkX's killer feature is arbitrary edge / node / graph attributes. fnx preserves that contract exactly. A few patterns worth knowing.

### Setting attributes at construction time

```python
import franken_networkx as fnx

G = fnx.Graph()
G.add_node("alice", role="engineer", since=2020)
G.add_node("bob",   role="manager",  since=2018)
G.add_edge("alice", "bob", weight=3.0, since=2022, project="franken_networkx")

print(G.nodes["alice"])
# {'role': 'engineer', 'since': 2020}
print(G.edges["alice", "bob"])
# {'weight': 3.0, 'since': 2022, 'project': 'franken_networkx'}
```

### Bulk attribute updates

```python
# Bulk-set node attributes from a dict.
fnx.set_node_attributes(G, {"alice": "Engineering", "bob": "Management"}, "team")

# Bulk-set edge attributes.
fnx.set_edge_attributes(G, {("alice", "bob"): {"status": "active"}})

print(G.nodes["alice"]["team"])     # → "Engineering"
print(G.edges["alice", "bob"])
# {'weight': 3.0, 'since': 2022, 'project': 'franken_networkx', 'status': 'active'}
```

`set_node_attributes` and `set_edge_attributes` are mutation-preserving dispatchables: when called via the NetworkX backend they route into fnx and the mutation lands on the *original* graph.

### Reading edge attributes in algorithms

The `weight=` kwarg on weighted algorithms is the attribute name to read:

```python
# A graph carrying BOTH attributes the examples below read, so each call means
# something different on the same edges. Named `W` rather than `G` so it does not
# shadow the running example graph used by the surrounding sections.
W = fnx.Graph()
W.add_edge("a", "m", weight=1.0, cost=5.0, toll=2.0)
W.add_edge("m", "z", weight=1.0, cost=5.0, toll=2.0)
W.add_edge("a", "z", weight=3.0, cost=1.0, toll=0.0)

fnx.shortest_path(W, "a", "z", weight="cost")     # use the "cost" attribute → ['a', 'z']
fnx.shortest_path(W, "a", "z", weight="weight")   # default                  → ['a', 'm', 'z']
fnx.shortest_path(W, "a", "z", weight=None)       # ignore weights → BFS     → ['a', 'z']
fnx.shortest_path(W, "a", "z", weight=lambda u,v,d: d.get("cost", 1) + d.get("toll", 0))
# ↑ callable form: fnx accepts it but may delegate to nx depending on the algorithm
#   (see docs/delegation_ledger.md for the per-algorithm contract)
```

### Reading attributes from algorithm output

Many algorithms return the original graph's attributes as part of their output. The `SubgraphView` returned by `G.subgraph([...])` shares the underlying attribute store, so mutations propagate. Use `G.subgraph([...]).copy()` to take a snapshot.

### Attribute mutation outside an algorithm call

```python
G.edges["alice", "bob"]["weight"] = 5.0  # direct mutation
# ↑ updates the Python-side attribute dict. The next *weighted* algorithm
#   call (one that reads "weight" or another attribute) invokes
#   _sync_rust_edge_attrs(G) under the hood to push the new value down
#   into the Rust adjacency before running.
```

The sync helper only runs ahead of algorithms that *read* edge attributes (`dijkstra`, `bellman_ford`, weighted matching, and so on), not before every dispatch. If you're profiling an attribute-heavy hot loop and want to amortize the sync cost, the canonical pattern is to batch mutations through `set_edge_attributes(G, {...})` (one sync at the end of the batch) rather than per-mutation `G[u][v][k] = v`.

### Attribute serialization

Attributes survive a round-trip through every native I/O format:

```python
import os, tempfile

# Written into a temp dir so running the docs verifier does not leave files in
# the working tree; in your own code these are just paths.
with tempfile.TemporaryDirectory() as _io_dir:
    fnx.write_graphml(G, os.path.join(_io_dir, "g.xml"))   # types preserved via <data attr.type=...>
    fnx.write_gml(G,     os.path.join(_io_dir, "g.gml"))   # typed scalars
    fnx.write_gexf(G,    os.path.join(_io_dir, "g.gexf"))  # typed attributes
data = fnx.node_link_data(G)      # JSON with type tags
```

The GraphML / GML / GEXF writers all emit typed attribute markers (`long`, `double`, `string`, `boolean`) so type identity survives. JSON node-link uses Python's standard `json` library type mapping.

---

## Cookbook

### Large-graph PageRank

```python
import franken_networkx as fnx

# Build (or load) a 1M-node BA graph.
G = fnx.barabasi_albert_graph(1_000_000, 4, seed=42)

# fnx.pagerank releases the GIL, so this is fine to run from a thread pool.
pr = fnx.pagerank(G, alpha=0.85, max_iter=100, tol=1e-6)

top10 = sorted(pr.items(), key=lambda kv: kv[1], reverse=True)[:10]
```

### Community detection

```python
import franken_networkx as fnx

G = fnx.karate_club_graph()
comms = list(fnx.community.louvain_communities(G, seed=42))
print("#communities:", len(comms))
print("modularity:", fnx.community.modularity(G, comms))
```

### Mixing fnx + nx graph types at the boundary

Every fnx function accepts an `nx.Graph` (or fnx graph) interchangeably; the boundary coerces:

```python
import networkx as nx, franken_networkx as fnx

G_nx  = nx.path_graph(10)
G_fnx = fnx.path_graph(10)

# all four combinations work and return the same answer
fnx.shortest_path(G_nx,  0, 9)
fnx.shortest_path(G_fnx, 0, 9)
nx.shortest_path(G_nx,  0, 9, backend="franken_networkx")
nx.shortest_path(G_fnx, 0, 9, backend="franken_networkx")
```

### Format conversion in one line

```python
import tempfile, pathlib
import franken_networkx as fnx

# Self-contained so the snippet actually runs: it makes its own input and writes
# into a temp dir rather than reading an "input.gml" that has to exist and
# littering four files into the working directory.
with tempfile.TemporaryDirectory() as tmp:
    out = pathlib.Path(tmp)
    seed = fnx.Graph()
    seed.add_edge("a", "b", weight=1.0)
    fnx.write_gml(seed, str(out / "input.gml"))

    converted = fnx.read_gml(str(out / "input.gml"))
    fnx.write_graphml(converted, str(out / "output.xml"))
    fnx.write_edgelist(converted, str(out / "output.edgelist"))
    fnx.write_gexf(converted, str(out / "output.gexf"))
```

### Drawing (delegated to matplotlib via NetworkX)

<!-- skip-verify: matplotlib is an OPTIONAL dependency and is not installed in the
     verification environment, and this snippet writes an image file. Marked with
     the verifier's own `skip-verify` fence tag (scripts/verify_docs.py) rather
     than by relaxing the verifier. -->

```python skip-verify
import franken_networkx as fnx
import matplotlib.pyplot as plt

G = fnx.karate_club_graph()
pos = fnx.spring_layout(G, seed=7)
fnx.draw(G, pos, with_labels=True, node_size=200)
plt.savefig("karate.png", dpi=160)
```

### Inspecting CGSE policy + witness types from Python

```python
import franken_networkx as fnx
from franken_networkx._fnx import cgse

# The 13 tie-break policies are reachable as named constructors:
p = cgse.TieBreakPolicy.weight_then_lex()
print(p.id())                       # "weight_then_lex"

# Per-algorithm canonical policy. Only the 12 reference algorithms have
# entries; unknown algorithms return None.
print(cgse.algorithm_policy("dijkstra"))             # → TieBreakPolicy.weight_then_insertion_order
print(cgse.algorithm_policy("max_weight_matching")) # → TieBreakPolicy.weight_then_lex
print(cgse.algorithm_policy("pagerank"))             # → None (not in the V1 reference set)

# Full V1 registry: { "<algorithm>": {"family": ..., "policy": ..., "dominant_complexity": ...} }
registry = cgse.policy_registry()
print(len(registry), "registered algorithms")        # → 12
print(sorted(registry.keys())[:5])                   # → ['bellman_ford', 'bfs', 'connected_components', 'dfs', 'dijkstra']

# All reference-algorithm identifiers:
print(cgse.reference_algorithms())
# → ['dijkstra', 'bellman_ford', 'bfs', 'dfs', 'max_weight_matching', 'min_weight_matching',
#    'connected_components', 'strongly_connected_components', 'kruskal', 'prim',
#    'eulerian_circuit', 'topological_sort']
```

Witnesses can also be drained from Python. `cgse.collect_witnesses(func)` runs `func()` with the calling thread's ledger armed and returns `(result, witnesses)`:

```python
G = fnx.karate_club_graph()
components, witnesses = cgse.collect_witnesses(lambda: list(fnx.connected_components(G)))
w = witnesses[0]
print(w.policy.id(), w.dominant_term, w.n, w.m, w.observed_count)   # lex_min n_plus_m 34 78 34
print(len(w.decision_path_hash))                                     # 64 (Blake3, hex)

# Same graph, same policy → same decision-path hash. Any drift is a regression.
_, again = cgse.collect_witnesses(lambda: list(fnx.connected_components(G)))
assert again[0].decision_path_hash == w.decision_path_hash

# A kernel outside the reference set emits nothing rather than a fabricated receipt.
assert cgse.collect_witnesses(lambda: fnx.degree_centrality(G))[1] == []
```

From the public Python surface, witnesses currently surface for connected components, BFS/DFS edges and trees, Kruskal's `minimum_spanning_tree`, Bellman-Ford, the DFS-based strongly-connected count, topological sort (the parity-exact native `topological_generations` Kahn kernel is instrumented), `dijkstra_path` on both simple undirected and directed graphs (the parity-exact single-pair early-exit kernels behind the wrapper emit), and — since 2026-09-04 — `eulerian_circuit` on simple undirected graphs (the native Hierholzer kernel was made nx-copy-order-parity and the wrapper now routes through it; `br-r37-c1-rc-cgse-witness-routes-obp8v`). The remaining public routes reach code that does not emit: Euler's directed and multigraph shapes keep delegating or use fnx-python-local kernels, multigraph-shape Dijkstra variants route through fnx-python-local kernels, and matching delegates to NetworkX for tie-break parity (`br-r37-c1-kpnc8`). The Rust level additionally exposes `fnx_cgse::collect_witnesses` and the `WitnessLedger` JSONL serializer, which the conformance harness uses for the artifacts under `artifacts/conformance/latest/`.

---

## When to Use FrankenNetworkX (and When Not To)

**Use it when:**

- You have an existing NetworkX codebase and the per-call cost dominates wall-clock time. Set `nx.config.backend_priority = ["franken_networkx"]` and you're done.
- You want determinism *and* speed. The CGSE tie-break contract means rerunning the same analysis on the same graph gives byte-identical output across runs and across machines.
- You're shipping graph analytics as part of a long-lived pipeline where iteration-order drift would be a quiet correctness bug downstream.
- You're doing research on graph algorithms and want a reproducibility audit trail per algorithm execution (the `ComplexityWitness` ledger).
- You're parsing graphs from untrusted sources and want strict-vs-hardened ingestion semantics, not "best-effort don't crash."

**Don't use it when:**

- You're working with graphs that fit comfortably in pure-Python NetworkX (< 10⁴ nodes, single-shot analysis) and you'd rather not add a Rust dependency. NetworkX is excellent at that scale.
- You need GPU acceleration. Look at cugraph / pylibraft.
- You need a different API entirely (igraph's vertex-index model, graph-tool's property-map model) and aren't tied to NetworkX semantics.
- You're targeting a Python runtime older than 3.10. ABI3-py310 means 3.10 is the floor.
- You need exotic backends (Neo4j, distributed graphs across machines). This is an in-memory graph algorithms library.

---

## Advanced Topics

### Backend dispatch from an `nx.Graph` you can't easily convert

If you're working in a third-party library that hands you `nx.Graph` instances, the easiest path is:

```python
import networkx as nx

# Pretend this came from a library that only speaks nx.
third_party_graph = nx.karate_club_graph()

# Either: globally — shown, not executed here, because setting it GLOBALLY is
# process-wide and would change dispatch for every later example in this file.
#
#     nx.config.backend_priority = ["franken_networkx"]

# Or: with a context manager (NetworkX >= 3.4), which scopes the change.
with nx.config(backend_priority=["franken_networkx"]):
    pr = nx.pagerank(third_party_graph)
```

The backend dispatcher converts the nx graph at the dispatch boundary; the original graph is unchanged.

### Converting an fnx graph to an nx graph

Three options, in increasing fidelity:

```python
import franken_networkx as fnx
import networkx as nx

G = fnx.path_graph(5)

# Quickest: identity-of-shape via edgelist.
nx_view  = nx.Graph(list(G.edges()))

# Full attribute round-trip via node-link JSON.
data     = fnx.node_link_data(G)
nx_full  = nx.node_link_graph(data)

# Topology-preserving via adjacency walk (used internally by the backend
# convert_to_nx path; respects insertion order).
from franken_networkx.readwrite import _from_nx_graph  # private helper for parity
```

For most users, the second option is what you want: it preserves graph-level, node-level, and edge-level attributes.

### Witness ledger artifacts

The conformance harness writes one `*.report.json` per fixture into `artifacts/conformance/latest/` (120 in the current snapshot, dated 2026-09-09). Each report carries `{suite, fixture_id, fixture_name, fixture_source_hash, mode, seed, passed, reason_code, mismatches[], mismatch_taxonomy, strict_violation_count, hardened_allowlisted_count, threat_class, duration_ms, replay_command, witness}`. Summary artifacts (dashboard, flake quarantine) carry a RaptorQ sidecar (`*.raptorq.json`) and a decode-proof receipt (`*.recovered.json`); the per-fixture reports do not. The structured log is `structured_logs.jsonl`, one line per event.

### RuntimePolicy at the Rust layer

`RuntimePolicy` lives in `fnx-runtime` and bundles the compatibility mode, an allowlist of safe operations, a Bayesian admission posterior, a loss-matrix for decision-theoretic action selection, and an append-only `EvidenceLedger`. It is *not* a global; it is constructed per call so behavior is reproducible from the decision log alone:

```rust
use fnx_runtime::{RuntimePolicy, CompatibilityMode, DecisionAction, EvidenceTerm};

let mut policy = RuntimePolicy::hardened();
assert_eq!(policy.mode(), CompatibilityMode::Hardened);
assert!(policy.allows("bounded_diagnostic_enrichment"));

// Algorithms / parsers can record decisions into the policy's evidence ledger:
policy.record(
    "read_graphml",                       // operation
    DecisionAction::FullValidate,         // action selected
    0.7,                                  // incompatibility probability
    "parser warning observed",            // rationale
    vec![                                 // evidence terms (signal/value/llr)
        EvidenceTerm {
            signal: "warning_count".into(),
            observed_value: "1".into(),
            log_likelihood_ratio: 0.3,
        },
    ],
);

for record in policy.decision_log().records() {
    println!("{:?}", record);
}
```

From Python, the mode is set with `fnx.config.compatibility_mode`, the `fnx.compatibility_mode(...)` context manager, or a reader's `mode=` keyword (see "Strict vs Hardened Modes"); the readers are where the modes currently behave differently. Algorithm kernels do not yet branch on the mode.

### Thread safety

Algorithm calls release the GIL during their inner loops, with the following consequences:

- Concurrent reads of the same graph from multiple Python threads are safe (each one borrows the underlying Rust adjacency by reference).
- Concurrent writes are *not* safe. `Graph` mutation is `&mut self` in Rust; Python-side, the mutation paths take a write borrow internally, and `_sync_rust_edge_attrs` tolerates concurrent borrow with bounded retry, but neither is a substitute for application-level synchronization on a shared graph.
- The `tests/python/test_thread_safety.py` suite exercises the concurrent-read contract specifically; concurrent Dijkstra calls from a thread pool over a shared graph is the canonical pattern.

---

## Examples

| File | What it shows |
|---|---|
| [`examples/basic_usage.py`](examples/basic_usage.py) | Standalone graph construction, algorithms, and round-trips. |
| [`examples/backend_mode.py`](examples/backend_mode.py) | NetworkX backend dispatch with zero call-site changes. |
| [`examples/social_network.py`](examples/social_network.py) | Community detection and centrality on a small social graph. |
| [`examples/benchmark_comparison.py`](examples/benchmark_comparison.py) | Lightweight local comparison vs NetworkX. |

---

## Documentation

| Page | Audience |
|---|---|
| [docs/quickstart.md](docs/quickstart.md) | First-time users; standalone usage |
| [docs/backend.md](docs/backend.md) | Existing NetworkX users; backend dispatch |
| [docs/migration.md](docs/migration.md) | Side-by-side NetworkX → FrankenNetworkX patterns |
| [docs/algorithms.md](docs/algorithms.md) | Algorithm reference summary |
| [docs/performance.md](docs/performance.md) | Performance notes and benchmarking |
| [docs/coverage.md](docs/coverage.md) | Auto-generated NetworkX 3.6.1 FeatureUniverse (4,926 qualified rows) plus FNX route appendix |
| [docs/raw_vs_public_audit.md](docs/raw_vs_public_audit.md) | Wrapper-patched parity repairs |
| [docs/delegation_ledger.md](docs/delegation_ledger.md) | All parity-helper delegation routes |
| [docs/upstream_divergence_ledger.md](docs/upstream_divergence_ledger.md) | Native-parity / wrapper-patched / delegated / gap rows |
| [docs/api_ergonomics_audit.md](docs/api_ergonomics_audit.md) | Signature-drift report |
| [docs/contributing.md](docs/contributing.md) | Development setup |
| [AGENTS.md](AGENTS.md) | Guide for AI coding agents working in this repo |
| [docs/planning/COMPREHENSIVE_SPEC_FOR_FRANKENNETWORKX_V1.md](docs/planning/COMPREHENSIVE_SPEC_FOR_FRANKENNETWORKX_V1.md) | V1 specification |
| [docs/planning/FEATURE_PARITY.md](docs/planning/FEATURE_PARITY.md) | Family-by-family parity inventory |
| [docs/planning/EXISTING_NETWORKX_STRUCTURE.md](docs/planning/EXISTING_NETWORKX_STRUCTURE.md) | Upstream NetworkX structure catalog |
| [docs/planning/EXHAUSTIVE_LEGACY_ANALYSIS.md](docs/planning/EXHAUSTIVE_LEGACY_ANALYSIS.md) | Legacy-path audit the conformance harness targets |

---

## Development

```bash
# clone
git clone https://github.com/Dicklesworthstone/franken_networkx
cd franken_networkx

# install build deps
pip install maturin pytest hypothesis networkx numpy scipy

# dev loop: debug build, edit, repeat
maturin develop --features pyo3/abi3-py310

# release build (recommended for benchmarks)
maturin develop --release --features pyo3/abi3-py310

# run tests (guarded: memory and time limits; target files or shards)
./scripts/run_pytest_guarded.sh tests/python/test_error_messages.py -v

# verify docs
python3 scripts/verify_docs.py

# build a wheel
maturin build --release

# Rust-side checks
cargo fmt --check
cargo clippy --workspace --all-targets -- -D warnings
cargo test --workspace
```

ABI3 builds a single wheel that works on Python 3.10, 3.11, 3.12, and 3.13; no per-version matrix is needed.

### Building from source on a fresh machine

```bash
# Rust toolchain (nightly, pinned by rust-toolchain.toml)
curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh -s -- -y
. "$HOME/.cargo/env"
rustup component add rustfmt clippy

# Python build deps
python3 -m venv .venv && source .venv/bin/activate
pip install --upgrade pip
pip install maturin pytest hypothesis networkx numpy scipy

# Clone + build
git clone https://github.com/Dicklesworthstone/franken_networkx
cd franken_networkx
maturin develop --release --features pyo3/abi3-py310

# Smoke test
python -c "import franken_networkx as fnx; G = fnx.path_graph(5); print(fnx.shortest_path(G, 0, 4))"
```

Cold build time on a modern laptop (16-core, 32 GB): about 4 minutes for a release build. Incremental builds run in seconds for most edits.

### Cross-compilation notes

Release wheels are built by DSR (`dsr build franken_networkx`) on its Linux, macOS and Windows build hosts. For local cross-compilation, `maturin build --release --target=...` works if you have the corresponding Rust target installed (`rustup target add ...`). The cdylib doesn't have any platform-specific code paths today.

### Editor / IDE setup

The project ships a `rust-toolchain.toml` so `rust-analyzer` and `rustfmt` honor the pinned nightly. For VS Code, install:

- `rust-lang.rust-analyzer`
- `tamasfe.even-better-toml`
- `vadimcn.vscode-lldb` for debugging

For Python, `pylance` or `pyright` will pick up the type stubs from `python/franken_networkx/_fnx.pyi` automatically.

---

## Troubleshooting

Top issues and their fixes.

### `ImportError: cannot import name '_fnx' from 'franken_networkx'`

The cdylib didn't build or didn't get installed. Cause and fix:

- **You installed from source but the build silently failed.** Re-run `maturin develop --release --features pyo3/abi3-py310` and read the full output.
- **A stale wheel from a previous build is shadowing the new one.** `pip uninstall franken-networkx && pip install franken-networkx`.
- **You're on Python < 3.10.** ABI3-py310 means 3.10 is the floor; upgrade Python.

### Backend isn't dispatching: `nx.shortest_path` still slow

```python
import networkx as nx
nx.config.backend_priority = ["franken_networkx"]
# Now call nx.shortest_path(G, ...)
```

If still slow, check:

```python
import franken_networkx
print(franken_networkx.__version__)        # PyPI's current release is 0.2.1

import networkx as nx
print(nx.config.backend_priority)          # should contain "franken_networkx"

# Did NetworkX actually pick up the entry point?
import importlib.metadata as im
print([e.name for e in im.entry_points(group="networkx.backends")])
# → should include "franken_networkx"
```

If the entry point isn't visible, your install is broken. Reinstall.

### `NotImplementedError: BackendInterface has no attribute '<name>'`

The algorithm isn't in `_SUPPORTED_ALGORITHMS` and you passed `backend="franken_networkx"` explicitly (the per-call form raises rather than falling back). Fix: drop the explicit kwarg and rely on `backend_priority`-based fallback, or call `fnx.<name>` directly.

### A result that doesn't match NetworkX

Reproduce both sides:

```python
import networkx as nx, franken_networkx as fnx
G_nx  = nx.path_graph(10)
G_fnx = fnx.path_graph(10)
print(nx.shortest_path(G_nx, 0, 9))
print(fnx.shortest_path(G_fnx, 0, 9))
```

If they differ and the difference isn't in `docs/upstream_divergence_ledger.md`, it's a bug. Please open an issue with `franken_networkx.__version__` and `networkx.__version__`.

### `RuntimeError: dictionary changed size during iteration`

You mutated a graph while iterating it. `fnx` matches NetworkX's behavior exactly here: iteration views are live, and mutating during iteration raises. Use `list(G.nodes())` to snapshot.

### "Stale wheel" detected during pytest

The conformance test layer detects a previously-installed fnx wheel with a mismatched API surface and skips backend-dispatch tests rather than report spurious failures (`br-r37-c1-...` cycle, see `tests/python/test_backend_dispatch_recursion_parity.py`). Fix: rebuild with `maturin develop --release`.

### Performance is worse than NetworkX for tiny graphs (< 50 nodes)

Expected. The dispatch + PyO3 marshaling cost dominates for graphs that small. Use NetworkX directly, or just accept the constant overhead. fnx wins at scale, not on micro-benchmarks.

### Multiprocessing crashes with `_fnx` segfaults

PyO3 extension modules need to be re-imported in each spawned process. Use `multiprocessing.set_start_method("spawn")` (not `fork`) on macOS and most modern Linux setups.

---

## Environment Variables

Standard Rust / Python build-time and runtime variables that are useful when working with FrankenNetworkX:

| Variable | Effect |
|---|---|
| `CARGO_TARGET_DIR=...` | Standard cargo override; useful for sharing the target directory between local and CI builds. Speeds up incremental rebuilds dramatically when building from source repeatedly. |
| `RUSTFLAGS="-C target-cpu=native"` | Build a wheel tuned for the current CPU. Meaningful for the `numpy`/`scipy`-adjacent paths and any SIMD-friendly inner loop. Don't use for distributable wheels. |
| `PYO3_PYTHON=/path/to/python` | Build against a specific Python interpreter. Useful for multi-venv setups. |
| `MATURIN_PEP517_ARGS=--release --features pyo3/abi3-py310` | Force a release build when `pip install` from source. |

The library reads no `FNX_*` environment variables at runtime (the test and benchmark harnesses have their own, e.g. `FNX_TEST_MAX_RSS_MB`). The compatibility mode is configured in-process: `fnx.config.compatibility_mode` / `fnx.set_compatibility_mode(...)` (process-wide), `fnx.compatibility_mode(...)` (thread-local context), or a reader's `mode=` keyword.

---

## Reproducibility Recipe

Bit-for-bit reproducible graph analytics with fnx. The recipe below is usable as the spine of a regression-locked pipeline.

### 1. Pin the inputs

```python
import os, hashlib, atexit, shutil, tempfile, franken_networkx as fnx

# In your pipeline GRAPH_INPUT is your own dataset:
#
#     GRAPH_INPUT = "datasets/snapshot_2026Q2.edgelist"
#
# The recipe below is executable as written, so it stands up a tiny stand-in
# and removes it at exit — later steps in this section read it back.
_pinned_dir = tempfile.mkdtemp(prefix="fnx-readme-")
atexit.register(shutil.rmtree, _pinned_dir, True)
GRAPH_INPUT = os.path.join(_pinned_dir, "snapshot.edgelist")
with open(GRAPH_INPUT, "w") as f:
    f.write("a b\nb c\nc a\n")

# Compute and log the SHA-256 of the input. Any drift here is the first
# place to look if reproducibility breaks downstream.
with open(GRAPH_INPUT, "rb") as f:
    digest = hashlib.sha256(f.read()).hexdigest()
print(f"input sha256: {digest}")
```

### 2. Pin the build

```python
import franken_networkx, networkx, sys
print("fnx:    ", franken_networkx.__version__)
print("nx:     ", networkx.__version__)
print("python: ", sys.version.split()[0])

# Optionally also pin the Rust commit the wheel was built from. If
# you're using a release wheel, the version is the contract; if you're
# building from source, capture `git rev-parse HEAD` in CI.
```

### 3. Pin the runtime mode

```python
# Default is Strict. For ingest of trusted data this is what you want.
# For ingest from a hostile source you may want Hardened; but pick
# one mode per pipeline run and log it.
print("compat mode: Strict (default)")
```

### 4. Run the analysis

```python
G = fnx.read_edgelist(GRAPH_INPUT, create_using=fnx.Graph)
pr = fnx.pagerank(G, alpha=0.85, max_iter=100, tol=1e-6)
```

Insertion-ordered adjacency means the same input, fnx version and seed give the same traversal order and the same tie-breaks. `pagerank` itself runs its power iteration in SciPy (like `nx.pagerank`), so its floating-point output is as reproducible as your SciPy/BLAS build is across machines; the CGSE-registered algorithms (see "The V1 policy registry") additionally carry a decision-path hash you can compare.

### 5. Hash the output

```python
import json
canonical = json.dumps(sorted(pr.items()), sort_keys=True)
out_digest = hashlib.sha256(canonical.encode()).hexdigest()
print(f"output sha256: {out_digest}")

# Lock this digest in a regression test. If it ever changes without a
# version bump, that's a bug in fnx or in your input pipeline.
```

### 6. Optional: harvest the CGSE witness

For Rust-side audit, drain `WitnessLedger` and serialize as JSONL. The hash of the witness JSONL bundle is a stronger reproducibility receipt than the algorithm output alone: two runs that produce the same algorithm output but different witness hashes are *suspicious* (it usually means the algorithm took a different path through equally-correct choices, indicating a non-determinism leak).

This recipe is what powers the project's own conformance gate (G5) and performance SLO gate (G6).

---

## Migration From NetworkX: Patterns

A reference catalog of common NetworkX patterns and their fnx equivalents. The migration is almost always trivial; the patterns below cover the edge cases that aren't.

### Pattern: `import networkx as nx` → no change (backend mode)

```python
# Before
import networkx as nx
G = nx.karate_club_graph()
print(nx.shortest_path(G, 0, 33))

# After (just enable the backend at startup)
import networkx as nx
nx.config.backend_priority = ["franken_networkx"]   # ← one line
G = nx.karate_club_graph()
print(nx.shortest_path(G, 0, 33))
```

### Pattern: `import networkx as nx` → `import franken_networkx as nx` (standalone mode)

<!-- skip-verify: an illustrative Before/After fragment. Executing it would rebind
     `nx` to franken_networkx for every later block in this file, since
     scripts/verify_docs.py concatenates the blocks into one script. -->

```python skip-verify
# Before
import networkx as nx

# After: drop-in alias, NetworkX still importable for exception classes
import franken_networkx as nx
```

This works unchanged for paths marked `present` in `docs/coverage.md`. Paths marked `partial` may still execute through a wrapper or NetworkX fallback, but their documented signature, binding-kind, or value gap means they are not claimed as drop-in portable.

### Pattern: type checks on `nx.Graph`

<!-- skip-verify: illustrative Before/After fragment — `g` is a stand-in for the
     caller's own graph and the bodies are literal `...`. -->

```python skip-verify
# Before
if isinstance(g, nx.Graph): ...

# After: fnx graphs are NOT subclasses of nx.Graph; use duck typing or
# the __networkx_backend__ attribute fnx graphs carry.
if hasattr(g, "__networkx_backend__") or isinstance(g, nx.Graph):
    ...
# Or convert at the boundary:
if not isinstance(g, nx.Graph):
    g = nx.Graph(g.edges(data=True))   # or use fnx.node_link helpers
```

### Pattern: pickling

```python
# Before
import pickle
pickle.dumps(nx.path_graph(5))   # works

# After
import pickle, franken_networkx as fnx
pickle.dumps(fnx.path_graph(5))  # also works; fnx graphs are pickleable
```

### Pattern: subclassing `nx.Graph`

```python
# Before
class MyGraph(nx.Graph):
    def my_method(self): ...

# After: fnx.Graph is a PyO3 #[pyclass(subclass)] so Python subclassing
# works, but you can't override Rust-side methods. Override at the
# Python wrapper layer (the public algorithm surface).
class MyGraph(fnx.Graph):
    def my_method(self): ...
```

### Pattern: NetworkX-only algorithms via fallback

<!-- skip-verify: `some_obscure_algorithm` is a deliberately fictional stand-in,
     and this fragment sets backend_priority GLOBALLY, which would change dispatch
     for every later block in this file. -->

```python skip-verify
# Before: calling an algorithm fnx doesn't natively support
import networkx as nx
nx.config.backend_priority = ["franken_networkx"]
# nx will fall through to its own implementation for unsupported algorithms
result = nx.some_obscure_algorithm(G)   # → pure-Python nx
```

If you want to *force* the nx implementation for a single call (e.g., for an A/B comparison), drop the `backend=` kwarg or override `backend_priority` temporarily with `nx.config(backend_priority=[]):` context manager.

### Pattern: existing test suites

Run your existing nx-based test suite against fnx by setting the backend priority in `conftest.py`:

```python
# tests/conftest.py
import networkx as nx
import franken_networkx  # ensure the entry point registers
nx.config.backend_priority = ["franken_networkx"]
```

If any test fails after the change, you've found either a fnx bug worth reporting or an instance of `docs/upstream_divergence_ledger.md` your code was relying on.

---

## Production Deployment Notes

A practical checklist for shipping fnx in production.

### Dependency pinning

```toml
# requirements.txt or pyproject.toml [tool.poetry.dependencies]
franken-networkx = "==0.2.1"
networkx = ">=3.0,<4.0"
```

Pin fnx exactly during early development (0.x). The fnx parity guarantee includes "we won't change observable behavior of a supported algorithm without a version bump", and pinning gives you that guarantee in your dependency graph.

### Wheel selection

PyPI (release 0.2.1) ships pre-built ABI3 wheels for:

- Linux x86_64 (manylinux_2_17 / manylinux2014)
- Linux aarch64 (manylinux_2_17 / manylinux2014)
- Linux x86_64 musl (musllinux_1_2)
- macOS x86_64 (10.12+)
- macOS arm64 (11.0+)
- Windows x86_64

PyPI has no sdist yet. On other platforms (FreeBSD, embedded Linux variants), build from a source checkout; the build is cargo-driven, so it works anywhere Rust nightly works.

### Memory considerations

Without attributes the slot/IndexMap adjacency is denser than NetworkX's dict-of-dicts: 112 MiB against NetworkX's 177 MiB (0.63×) for 200k nodes and 800k edges. **Attributes currently cost more than in NetworkX**, because an attributed edge is stored twice — as a native `AttrMap` the kernels read and as the Python dict users see. Same graph with one float attribute per edge: 944 MiB against NetworkX's 276 MiB (3.4×) when built with `add_edges_from` or `add_weighted_edges_from`, 500 MiB (1.8×) when the attribute is added afterwards with `set_edge_attributes` (Python dicts then materialise lazily). Measured 2026-09-24, RSS delta of one build per process, `same_host=thinkstation1`, no A/A null (a sanity measurement, not a gate).

Budget accordingly for large attributed graphs; a single attribute store is on the storage roadmap (`br-r37-c1-epic-storage-architecture-yr2oc`).

### Multiprocessing

The `_fnx` cdylib is safe to import from multiple Python processes. Standard caveats apply:

- Use `multiprocessing.set_start_method("spawn")` on macOS (default since 3.8) and modern Linux.
- Graphs do not share memory across processes; serialize via `pickle`, JSON node-link, or write to a file.
- Each process initializes its own thread-local CGSE witness ledger.

### Async / threading

- fnx algorithm calls release the GIL during native execution. Using a `ThreadPoolExecutor` to run algorithms concurrently on independent graphs is the correct pattern.
- Calls that mutate a *shared* graph from multiple threads are not safe; serialize the mutator from a single thread.
- `asyncio` works trivially; algorithm calls are blocking, so wrap them with `loop.run_in_executor(None, fn, args)`.

### Logging and tracing

```python
import logging
logging.basicConfig(level=logging.INFO)
# Rust-side `log` records are forwarded into Python's logging module (pyo3-log)
# under the logger name "franken_networkx".
logging.getLogger("franken_networkx").setLevel(logging.DEBUG)
```

Logging is sparse: 11 Rust call sites in all (ten in shortest-path kernels at INFO, `add_node` at DEBUG). `add_edge`, `remove_edge` and `remove_node` do not log: resolving the logger cost about 500 instructions per call on those paths. There is no `tracing` instrumentation and `RUST_LOG` is not read; configure levels through Python's `logging`. The backend dispatch layer does not log dispatch decisions today.

### Container image notes

If you're shipping fnx inside a Docker image, a minimal layer set:

```dockerfile
FROM python:3.12-slim
RUN pip install --no-cache-dir franken-networkx
# Optional SciPy (NumPy is a required dependency and already installed)
RUN pip install --no-cache-dir 'franken-networkx[all]'
```

The wheels are self-contained; no apt packages needed. Final image cost is ~80 MB beyond the base Python image.

---

## Style Guide for Code That Uses fnx

How to write code that flips cleanly between fnx and nx without surprises.

### Prefer `fnx.X(G)` to `G.X()` where both exist

<!-- skip-verify: a style illustration on a stand-in `G`, and its second line is
     labelled as not universally available, so it cannot execute either. -->

```python skip-verify
# Both work, but the module-level form is the documented contract.
fnx.shortest_path(G, "a", "z")        # preferred
G.shortest_path("a", "z")              # not all graph types expose this
```

### Don't rely on private internals

The audit ledgers track the *public* surface. Anything starting with `_` (e.g. `fnx._fnx`, `fnx._sync_rust_edge_attrs`, `fnx.backend._SUPPORTED_ALGORITHMS`) is not part of the contract and may move between releases.

### Catch the broadest reasonable exception

<!-- skip-verify: a Good/Bad style illustration on a stand-in `G`; parts of it are deliberately wrong by design. -->

```python skip-verify
# Brittle (won't catch NetworkXNoPath, since it's under NetworkXUnfeasible)
try:
    path = fnx.shortest_path(G, s, t)
except fnx.NetworkXError:   # ← does NOT catch NetworkXNoPath!
    ...

# Correct
try:
    path = fnx.shortest_path(G, s, t)
except fnx.NetworkXNoPath:
    ...
# Or, if you want a catch-all
except fnx.NetworkXException:
    ...
```

### Use named kwargs for keyword-only parameters

<!-- skip-verify: a Good/Bad style illustration on a stand-in `G`; parts of it are deliberately wrong by design. -->

```python skip-verify
# Good
fnx.shortest_path(G, "a", "z", weight="weight")
fnx.pagerank(G, alpha=0.85, max_iter=100, tol=1e-6)

# Bad: positional args past 2 are fragile, fnx mirrors nx's keyword-only contract
fnx.pagerank(G, 0.85, 100, 1e-6)   # works today, may not tomorrow
```

### Don't iterate views during mutation

Same rule as NetworkX:

<!-- skip-verify: a Good/Bad style illustration on a stand-in `G`; parts of it are deliberately wrong by design. -->

```python skip-verify
# Bad
for u in G.nodes():
    if G.degree(u) == 0:
        G.remove_node(u)        # raises RuntimeError mid-iteration

# Good
isolates = list(fnx.isolates(G))
for u in isolates:
    G.remove_node(u)
```

### Snapshot views before subprocess transfer

`G.subgraph([...])` returns a view, not a fresh graph. If you want to pickle it or pass it across an async boundary, call `.copy()`:

<!-- skip-verify: a Good/Bad style illustration on a stand-in `G`; parts of it are deliberately wrong by design. -->

```python skip-verify
sub = G.subgraph(important_nodes)         # view; aliases G
sub_copy = G.subgraph(important_nodes).copy()  # standalone graph
pickle.dumps(sub_copy)                    # ← this is what you want for IPC
```

---

## Real-World Use Cases

A non-exhaustive list of problems fnx fits well, drawn from the project's design rationale.

### Network security analytics

- **Attack-graph centrality:** PageRank or betweenness over a graph of network hosts + attacker pivots, to identify chokepoints whose hardening cuts the most attack paths.
- **Reachability queries:** `has_path` / `bidirectional_shortest_path` over a permission graph.
- **Anomaly detection:** community-detection drift between two time-windowed snapshots of the same logical graph.

CGSE matters here because the analytics output drives alerting; an iteration-order drift becomes a false-positive flood.

### Knowledge graph and RAG retrieval

- **Entity-relationship traversal:** `bfs_layers` / `descendants_at_distance` over an entity-relation graph for K-hop neighborhood expansion.
- **Salience ranking:** PageRank-style scoring of entities to prioritize what to feed an LLM context window.
- **Schema-aware similarity:** Jaccard / Adamic-Adar over the relation graph for entity linking.

fnx's GIL-released algorithm calls let a server handle multiple concurrent retrieval queries against a shared in-memory graph.

### Bioinformatics and molecular graphs

- **Cycle and clique analysis:** `find_cliques` (Bron-Kerbosch with the native bitset fast path), `k_truss`, `core_number` over protein-interaction networks.
- **Shortest-pathway analysis:** Dijkstra over metabolic networks weighted by reaction enthalpy.
- **Isomorphism:** VF2 / VF2++ for subgraph matching in chemical structure search.

The conformance gate guarantees that an analysis published last year and rerun today produces byte-identical results.

### Recommendation systems and social analytics

- **Link prediction:** `adamic_adar_index`, `preferential_attachment`, `resource_allocation_index` over user-item bipartite graphs.
- **Community detection at scale:** Louvain / greedy modularity over follower graphs (both currently route through nx for exact behavioral parity).
- **Pagerank-style ranking:** personalized PageRank for content recommendation.

### Compiler and program analysis

- **Dominator computation** (`immediate_dominators`, `dominance_frontiers`) for SSA construction.
- **Loop and natural-region detection** via `simple_cycles` and `strongly_connected_components`.
- **Reachability and constant-propagation** via `transitive_closure` and `topological_sort`.

The CHK iterative dominator algorithm is exactly what production compilers use.

### Workflow and dependency analysis

- **Topological scheduling:** `topological_sort` / `lexicographical_topological_sort` over a DAG of build steps.
- **Critical-path identification:** `dag_longest_path` for project-planning longest-duration chains.
- **Cycle detection in declared dependencies:** `simple_cycles` over a config dependency graph.

### Geographic and routing systems

- **Shortest-path queries** with custom cost functions: `astar_path` with a Haversine heuristic over a road-network graph.
- **Network resilience:** `articulation_points` / `bridges` to identify single-points-of-failure in transit networks.
- **Catchment analysis:** `single_source_shortest_path_length` to compute drive-time isochrones.

### Adversarial graph ingestion

Parsing untrusted graphs (e.g. social-network exports from third-party tools) benefits from the strict-vs-hardened mode toggle and the fuzz-hardened parsers. The repository carries 33 cargo-fuzz targets. Every DSR quality run replays their committed corpora and fuzzes each target for 10 seconds (on 2026-09-24: 4.76 million executions, 361 CPU-seconds, no failures; the slowest targets, the random generators and polynomial metrics, managed only 709 and 1,364 executions). Treat the parsers as fuzz-exercised rather than fuzz-proven, and apply your own resource limits before feeding `read_graphml(untrusted_path)` to a public-facing service.

---

## Observability

For long-running pipelines, the witness ledger and decision log are the canonical observability surface:

- **`artifacts/conformance/latest/structured_logs.jsonl`**: one JSON line per algorithm call. Fields include `{algorithm, fixture, n, m, observed_count, duration_ms, witness_hash, mismatch_reason?}`. Drainable by `jq`.
- **`artifacts/perf/latest/perf_baseline_matrix_v1.json`**: p50/p95/p99 + memory for every algorithm family in the SLO matrix.
- **`artifacts/perf/latest/slo_gate_report_v1.json`**: pass/fail status for each SLO row plus the delta from baseline.
- **RaptorQ sidecars (`*.raptorq.json`) and decode receipts (`*.recovered.json`)**: paired with each of the above so artifacts survive partial-corruption events.

For Python-side observability:

```python
import logging
logging.basicConfig(level=logging.INFO)
# Rust `log` records (a few shortest-path kernels at INFO, some mutations at
# DEBUG) arrive through pyo3-log under the logger name "franken_networkx".
logging.getLogger("franken_networkx").setLevel(logging.DEBUG)
```

There are no `tracing` spans and `RUST_LOG` is not read. The backend dispatch layer does not log its decisions today; to see whether a call dispatched, compare `type(result)` or time the call.

---

## Limitations

FrankenNetworkX is honest about what it does not do today:

- **Drawing is delegated.** `draw`, `draw_*`, and the matplotlib-backed layout functions delegate to NetworkX/matplotlib. Layout *math* (`spring_layout`, `kamada_kawai_layout`, etc.) is also delegated. We do not own matplotlib rendering.
- **`check_planarity` certificates are native.** Both the boolean `is_planar` and `check_planarity` certificates (`PlanarEmbedding` rotation orders for planar graphs and Kuratowski subgraph counterexamples for non-planar graphs) are computed natively in Rust; the Python PlanarEmbedding container preserves NetworkX structure checks.
- **Some functions still run NetworkX code.** Seven always do on their default path (matching, branchings, weighted Louvain, greedy modularity, `simple_cycles`, `k_components`); others do for specific argument shapes (user callables, custom `flow_func`, exotic format variants). See "Parity coverage today".
- **Release status.** PyPI's current release is `0.2.1` (2026-09-09): ABI3 wheels for Linux (`x86_64`, `aarch64`, `musllinux x86_64`), macOS (`x86_64`, `arm64`) and Windows (`x86_64`), Python 3.10+. The `v0.2.2` GitHub release carries only a Linux x86_64 wheel and an sdist, and `main` has moved well past both; the next PyPI release is tracked in `br-r37-c1-rc0923-ship-head-pypi-all-platforms-euaqe`.
- **Performance gates run on Linux only.** Cross-platform correctness comes from the release builds, not from a performance gate.
- **No 3rd-party graph DB integration.** This is a graph *algorithms* library; it does not connect to Neo4j, JanusGraph, etc. Use it on in-memory graphs.

---

## FAQ

**Is it really a drop-in replacement?**
Across the pinned 3.6.1 declared import-and-signature FeatureUniverse, all 4,129 applicable paths are strictly present (100.0%), with 0 partial and 0 missing. The 313 algorithms in `backend.py` are the dispatch registry, not a proof that every NetworkX path or behavior is covered; behavioral claims remain scoped to their conformance fixtures.

**Why are iteration orders such a big deal?**
NetworkX users often write code that implicitly depends on `dict` insertion order or BFS visit order or `connected_components` set ordering. If a "faster NetworkX" returns the same set of correct answers but in a different order, downstream code breaks subtly. CGSE + the parity tests + the iteration-order audit ledger collectively make iteration order a first-class API contract.

**Do I need a Rust toolchain?**
No: prebuilt ABI3 wheels on PyPI support Linux, macOS, and Windows for Python 3.10+. Only contributors developing Rust internals or building from source need `rustup` and the nightly toolchain pinned in `rust-toolchain.toml`.

**What's the ABI3 story?**
The native extension uses `pyo3/abi3-py310`. One wheel works for Python 3.10, 3.11, 3.12, 3.13, and 3.14+. No per-Python-version build matrix is needed.

**Is it thread-safe?**
Algorithm calls release the GIL at hundreds of call sites and operate on borrowed adjacency. Concurrent reads are safe. Concurrent writes are not. `Graph` mutation is `&mut self` in Rust, and `_sync_rust_edge_attrs` tolerates concurrent borrow with bounded retry but is not a substitute for application-level synchronization on shared graphs. The `tests/python/test_thread_safety.py` suite exercises the concurrent-read contract.

**What's "Strict" vs "Hardened"?**
A runtime mode in `fnx-runtime::CompatibilityMode`. Strict maximizes byte-for-byte NetworkX compatibility on V1-scoped APIs and fails closed on malformed input. Hardened preserves the API contract while applying bounded defensive recovery; useful when ingesting adversarial graphs from untrusted sources. Both modes record every action selection as a `DecisionRecord` in an evidence ledger.

**What's CGSE?**
The **Canonical Graph Semantics Engine**: a Rust crate (`fnx-cgse`) that makes tie-breaking, complexity witnesses, and policy registries first-class. Its registry names which of the 13 `TieBreakPolicy` variants governs each reference algorithm's choices; every reference-algorithm call emits a length-prefixed-Blake3 `ComplexityWitness` that can be drained from a `WitnessLedger` for offline reproducibility audits.

**Why not just use `networkx[backend=cugraph]` / igraph / graph-tool?**
Use them if they fit. cugraph requires CUDA; igraph and graph-tool have different APIs and don't preserve nx tie-break behavior. The niche FrankenNetworkX fills is "I have an nx codebase, I want it faster, I do not want to think about tie-breaks or rewrite anything."

**Does the backend mode work with `nx.config.backend_priority` *and* explicit `backend="..."` kwargs?**
Yes. The list-form controls the default; the per-call kwarg overrides it. fnx's `BackendInterface.can_run` honors both paths the same way; for unsupported algorithms or unsupported argument shapes, the call falls through.

**What happens to graph mutations made through the backend?**
The same as with any NetworkX backend. With `backend_priority`, NetworkX does not auto-dispatch functions that mutate their input (`relabel_nodes(copy=False)`, `contracted_nodes`, `set_node_attributes`, the edge swaps, ...), so they run in NetworkX on your graph. With an explicit `backend="franken_networkx"` on a NetworkX graph, NetworkX converts the graph and the mutation lands on the converted copy, not on your graph; NetworkX's dispatcher documents this for all backends. Called on an fnx graph (or directly as `fnx.<function>`), they mutate that graph exactly as NetworkX would, including seeded edge swaps producing NetworkX's graph for the same seed.

**How are NaN edge weights handled?**
Exactly as NetworkX handles them, in every mode. The Dijkstra / A* / PageRank paths use a native Rust non-finite-weight scan as a fast pre-check and route NaN/±∞-weighted inputs to NetworkX-exact code, so the result (including NetworkX's own NaN semantics) matches `nx`. The strict/hardened modes currently change reader behaviour only; there is no NaN coercion.

**Why do some functions return an iterator and others a list?**
Because NetworkX does. The contract is that `fnx.<func>` returns the exact same Python type as `nx.<func>`: generators stay generators, dict_values stays dict_values, list stays list. This was specifically locked for `all_shortest_paths` (`br-r37-c1-6atv8`).

**Can I run an algorithm under a non-default tie-break policy?**
The Rust-level API in `fnx-algorithms` is parameterized by `TieBreakPolicy`, so yes, but the Python wrappers fix the canonical policy that matches NetworkX. Switching policies at the Python layer is not exposed today; the use case (reproducibility audits on the same algorithm under different policies) is a Rust-level integration test pattern, not a user-facing API.

**Does `pip install franken-networkx` install NetworkX too?**
Yes. `networkx>=3.0` is a hard dependency. fnx's wrapper layer imports nx for exception classes, the dispatch protocol, and the fallback path on unsupported argument shapes.

**Is there a no-NetworkX build?**
Not currently. fnx re-exports NetworkX's exception classes and some objects by identity, and the remaining NetworkX-bound routes (see "Parity coverage today") need nx available. A "pure fnx" mode would require porting those routes to native code.

---

## Common Pitfalls

Pitfalls real users have hit, in roughly descending order of frequency.

### "Why is `nx.shortest_path` not faster after I installed franken-networkx?"

You probably forgot to enable the backend:

```python
import networkx as nx
nx.config.backend_priority = ["franken_networkx"]   # ← required
```

Installing the wheel doesn't automatically rewire `nx.*`; the user is in charge of enabling the backend. This is intentional (otherwise installing the wheel would silently change behavior of every NetworkX program on the machine).

### "My algorithm result has the same set of items but in a different order between runs"

`fnx` shouldn't be the cause; CGSE pins iteration order. If you see drift, the cause is almost always a Python-side issue:

- You're iterating a `dict` constructed from a `set` (sets have hash-randomized iteration order in CPython unless `PYTHONHASHSEED` is fixed).
- You're collecting `connected_components` into a `set` of `frozenset`s and printing them; the print order depends on `frozenset.__hash__`, not on fnx.

Use `list(...)` end-to-end and the order will be deterministic.

### "My benchmark shows fnx is *slower* than networkx"

For very small graphs (< 100 nodes / single-shot analysis), the PyO3 marshaling cost can exceed the algorithm cost. Three suggestions:

- **Use a release build.** `maturin develop --release --features pyo3/abi3-py310`. Debug builds are 5–20× slower.
- **Amortize the marshaling.** A single `fnx.pagerank(G)` call pays the marshaling once; calling it 1000 times in a loop pays it 1000 times. Reuse the result.
- **Use the standalone API, not backend dispatch, when you know the algorithm is supported.** Direct `fnx.pagerank(G)` skips the dispatcher overhead.

#### Known Performance Trade-offs and Inverted Operations

Analytics kernels are where fnx wins (the per-family table above ranges from about 1.3× to 194×; whole jobs 1.1–2.2×). The class core and the backend boundary are where it loses. Figures below are same-process sanity probes from 2026-09-23 on a loaded shared host (load 30–70), unless a harness is named — the direction and the growth pattern are reliable, the decimals are not:

| Operation | Workload / shape | fnx vs NetworkX | Root cause | Status |
|---|---|---|---|---|
| `remove_node(u)`, any node but the last | `Graph`/`DiGraph`, n = 1.6k → 25.6k, ~4n edges | **0.52× → 1.75×** / **0.78× → 1.31×** (O(degree) per removal) | flat ~2.5–3.5 µs per call: `Graph` still loses at 1.6k and 6.4k nodes, wins at 25.6k | **Open** — `br-r37-c1-epic-storage-architecture-yr2oc.1` (multigraph classes) |
| `remove_node(u)`, any node but the last | `MultiGraph`, n = 1.6k → 25.6k, ~4n edges | 0.60× → 0.76× (O(degree) per removal); 0.27–0.30× when built one `add_edge` at a time | a constant per call; a graph built edge by edge also pays its edges' Python attribute mirrors | Open — same bead; mirrors: `br-r37-c1-wzoa7`, `br-r37-c1-rc0923-epic-perf-where-we-lose-sfq4w.1` |
| `remove_node(u)`, any node but the last | `MultiDiGraph`, n = 1.6k → 25.6k, ~4n edges | 0.32× → 0.45× (O(degree) per removal) | the String-keyed store frees ~7 blocks per incident edge | Open — same bead (slot-keyed store) |
| `remove_node` on a graph with edge attributes, with a single-node read between removals | `Graph`/`DiGraph`, n = 1.6k → 25.6k, one attribute per edge | 0.2–0.5× | each removal updates the Python attribute mirrors of the incident edges | Open |
| `copy.copy(G)` | n = 10 → 10k | 1.34× → **0.0031×** (O(n)); attr dicts not shared as in nx | fnx copies the graph, nx aliases it | Open — `br-r37-c1-epic-storage-architecture-yr2oc.3` |
| attributed graph memory | 800k edges, 1–2 edge attrs | **3.4–4.3× nx's RSS** (unattributed: 0.63×) | two attribute stores (Python dicts + native) | Open — `br-r37-c1-rc0923-epic-perf-where-we-lose-sfq4w.1` |
| backend mode, cold conversion | nx graph, 80k edges, cheap kernel (BFS, components, sssp, dijkstra) | converting costs 0.12–0.34× of networkx's own run (0.66 µs per edge topology-only, 1.5 at 400k edges; attributes copied only as networkx's hints ask), so `should_run` lets networkx run a cheap kernel's first calls (~1.0×) and converts once the graph's calls have paid for it; 20 repeated calls 1.04–6.9×, warm cache 1.7–47× | conversion still builds one Python tuple per edge (0.3 µs/edge target not met) | Open — `…sfq4w.2` |
| `G.has_edge(u, v)`, present edge | `Graph`/`DiGraph`, n = 20k, int nodes added out of order; `DiGraph` with str nodes | 0.975× / 0.975× | three hash probes (u, v, the edge) where nx does two dict lookups | Open — `…sfq4w.3` |
| `G[u][v]` | `MultiGraph` / `MultiDiGraph`, direct edge-keydict probe | 0.42–0.50× (`Graph` 1.09–1.24× and `DiGraph` 1.07–1.09× win; 2026-09-25, admissible, see the per-surface table) | the multigraph row and cell are stacked Python view layers; `Graph`/`DiGraph` rows are the native C-slot `AtlasView` | Open — `br-r37-c1-ey6ob` |
| `MultiGraph`/`MultiDiGraph.get_edge_data(u, v)` | unkeyed, 1–16 parallel edges | 0.57–0.62× per call, flat in parallel edges; consumption 0.73–0.89× | a registry lookup per call where nx does two dict lookups; the keydict itself is a real `dict` (2026-09-24) | Open (per-call cost) |


### "I called `G.add_edge(0, 1)` and then `G[0][1]['weight'] = 5` but `nx.shortest_path(G, 0, 1, weight='weight', backend='franken_networkx')` returned the wrong path"

This is a known sync subtlety. `_sync_rust_edge_attrs(G)` runs transparently before weighted-algorithm dispatch, but if you're doing direct `G[u][v][k] = v` mutation outside of any algorithm call and then querying `G.adj[u][v][k]`, you may see stale Python-side state. The fix landed in beads `br-r37-c1-sjf4t` and `br-r37-c1-0x9pd`; if you see this on the latest version, please file an issue.

### "MultiGraph edge keys of `0`, `0.0`, and `False` are colliding"

This is intentional. fnx matches Python's `hash(0) == hash(0.0) == hash(False)` dict-key semantics. If you want distinct edges, use distinct keys (e.g. `0`, `1`, `2`).

### "I'm getting `NetworkXNotImplemented` on a function I thought was supported"

A few functions accept the *graph type* but not the *argument shape* you provided. Examples:

- `min_cost_flow` rejects undirected input (matches nx).
- `gomory_hu_tree` rejects MultiGraph input.
- `node_connectivity(G, flow_func=my_callable)` rejects the custom callable; drop the `flow_func` kwarg or call the nx version directly.

Check `docs/upstream_divergence_ledger.md` for the canonical list.

### "`verify_docs.py` says generated docs validation failed"

The public surface changed and `docs/coverage.md` no longer matches it; the printed diff shows which classification moved. Regenerate with `python scripts/generate_coverage_matrix.py` and commit the result with the change that caused it. Read the diff first: a row moving to `partial` or an export moving to `NX_DELEGATED` is a real change in what fnx provides, not noise.

---

## Citations and Algorithm References

The algorithm implementations and design decisions trace to a specific body of literature. Treat this as a reading list more than a complete bibliography.

### Graph algorithms

- **Dijkstra, E. W. (1959).** *A note on two problems in connexion with graphs.* Numerische Mathematik 1.
- **Bellman, R. (1958).** *On a routing problem.* Quarterly of Applied Mathematics 16.
- **Floyd, R. W. (1962).** *Algorithm 97: Shortest path.* Comm. ACM 5(6).
- **Johnson, D. B. (1977).** *Efficient algorithms for shortest paths in sparse networks.* JACM 24(1).
- **Hart, Nilsson, Raphael (1968).** *A formal basis for the heuristic determination of minimum cost paths.* IEEE TSCC.
- **Brandes, U. (2001).** *A faster algorithm for betweenness centrality.* Journal of Mathematical Sociology 25(2).
- **Tarjan, R. E. (1972).** *Depth-first search and linear graph algorithms.* SIAM J. Computing 1(2).
- **Tarjan, R. E. (1974).** *A note on finding the bridges of a graph.* Inf. Proc. Letters 2.
- **Kosaraju, S. R. (1978).** Unpublished; canonical statement in Aho, Hopcroft, Ullman.
- **Boyer, J., & Myrvold, W. (2004).** *On the cutting edge: Simplified O(n) planarity by edge addition.* JGAA 8(3). The basis of the native `check_planarity` embedding and Kuratowski-certificate path.
- **Cooper, K. D., Harvey, T. J., & Kennedy, K. (2001).** *A simple, fast dominance algorithm.* Rice University TR. The algorithm `immediate_dominators` actually uses.
- **Stoer, M., & Wagner, F. (1997).** *A simple min-cut algorithm.* JACM 44(4).
- **Edmonds, J. (1967).** *Optimum branchings.* J. Res. Nat. Bur. Stand.
- **Edmonds, J. (1965).** *Paths, trees, and flowers.* Canad. J. Math 17. (Blossom algorithm for maximum-weight matching.)
- **Edmonds, J., & Karp, R. M. (1972).** *Theoretical improvements in algorithmic efficiency for network flow problems.* JACM 19(2).
- **Goldberg, A. V., & Radzik, T. (1993).** *A heuristic improvement of the Bellman-Ford algorithm.* AML 6.
- **Hopcroft, J. E., & Karp, R. M. (1973).** *An n^{5/2} algorithm for maximum matchings in bipartite graphs.* SIAM J. Computing 2(4).
- **Cordella, Foggia, Sansone, Vento (2004).** *A (sub)graph isomorphism algorithm for matching large graphs.* IEEE TPAMI 26(10). (VF2.)
- **Jüttner, A., & Madarasi, P. (2018).** *VF2++: An improved subgraph isomorphism algorithm.* Discrete Applied Mathematics 242.
- **Newman, M. E. J. (2006).** *Modularity and community structure in networks.* PNAS 103(23). (Greedy modularity.)
- **Blondel et al. (2008).** *Fast unfolding of communities in large networks.* J. Stat. Mech. (Louvain.)
- **Maslov, S., & Sneppen, K. (2002).** *Specificity and stability in topology of protein networks.* Science 296(5569). (`random_reference`.)
- **Janssens, G., & Sörensen, K. (2005).** A partition scheme used by the spanning-tree / arborescence iterators.

### Generators

- **Erdős, P., & Rényi, A. (1959).** *On random graphs I.* Publ. Math. Debrecen 6.
- **Watts, D. J., & Strogatz, S. H. (1998).** *Collective dynamics of "small-world" networks.* Nature 393.
- **Barabási, A.-L., & Albert, R. (1999).** *Emergence of scaling in random networks.* Science 286.
- **Kleinberg, J. (2000).** *The small-world phenomenon: an algorithmic perspective.* (`navigable_small_world_graph`.)
- **Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983).** *Stochastic blockmodels.* Social Networks 5.
- **Lancichinetti, A., Fortunato, S., & Radicchi, F. (2008).** *Benchmark graphs for testing community detection.* PRE 78. (LFR benchmark.)
- **Frucht, R. (1949).** Construction underlying the named small graphs (Frucht, Tutte, Petersen) shipped as fixed generators.

### Systems infrastructure

- **Birch, J. (2013).** *RaptorQ codes: A practical look.* IETF RFC 6330 codifying the erasure code used in `fnx-durability`.
- **O'Hearn, P. W. (2018).** *Continuous reasoning: Scaling the impact of formal methods.* LICS. The doctrinal background for the "fail closed under uncertainty" stance encoded in `RuntimePolicy`.
- **`indexmap` crate** by bluss et al. The ordered hash-map underlying every fnx adjacency structure.
- **`blake3` crate** by Connor / O'Connor / Aumasson / Neves. The hash function backing the decision-path fingerprint in `WitnessSink`.
- **PyO3 / Maturin.** The Python ↔ Rust binding and packaging stack (Konstin / messense et al.).

Most of these papers are open-access; search by author + year. The NetworkX project's algorithm docstrings (in `legacy_networkx_code/` in this repo) cite the same primary sources and are a good cross-reference.

**Can I contribute an algorithm?**
See *About Contributions* below. The short version: bug reports are welcome, PRs that demonstrate a fix are welcome as illustrations, but I won't merge community PRs directly.

**Where do I file a bug?**
[GitHub Issues](https://github.com/Dicklesworthstone/franken_networkx/issues). Please include a minimal reproducer that calls both `nx.<func>` and `fnx.<func>` (or `nx.<func>(..., backend="franken_networkx")`), the exact mismatch, your NetworkX version, and the FrankenNetworkX version (`franken_networkx.__version__`).

---

## Memory Model and Data Layout

Understanding the internals helps when you want to reason about cost or attribute semantics.

### Adjacency

The actual storage layout for each graph type splits adjacency from attribute storage. This differs from NetworkX's nested-dict layout and is more cache-friendly:

```rust
// crates/fnx-classes/src/lib.rs and digraph.rs (abbreviated; revision-keyed caches omitted)
pub struct Graph {
    mode:        CompatibilityMode,                   // Strict | Hardened
    revision:    u64,                                 // bumped on every structural mutation
    node_order:  FxIndexMap<String, usize>,           // name → slot; iteration order = insertion order
    slot_names:  Vec<Option<String>>,                 // slot → name (None = tombstoned)
    node_attrs:  Vec<AttrMap>,                        // slot → node attrs
    free_slots:  Vec<usize>,                          // tombstoned slots awaiting reuse/compaction
    adj_indices: Vec<Vec<usize>>,                     // slot → neighbor slots, insertion-ordered
    edges:       FxIndexMap<(usize, usize), AttrMap>, // slot-canonical (min, max) → edge attrs
    edge_index_endpoints: Vec<(usize, usize)>,        // edge slot → string-canonical orientation
    runtime_policy: RuntimePolicy,
    // plus revision-keyed caches (all-int weights, per-neighbour edge slots)
}

pub struct DiGraph {
    // the same slot layout, with succ_indices / pred_indices in place of adj_indices
    // plus CSR and all-int-weight caches
}

pub struct MultiGraph {
    mode:       CompatibilityMode,
    revision:   u64,
    storage:    MgSlabStorage,                        // slab of (u, v, key) → attrs with per-node rows
    runtime_policy: RuntimePolicy,
    edge_count: usize,
    // plus an integer-adjacency cache
}
```

Three design choices fall out of this layout:

- **Insertion order everywhere.** The node and edge maps are `IndexMap`s and the integer adjacency rows are plain `Vec`s appended in insertion order, so iteration order is the order the user built the graph. This is the structural guarantee that lets fnx match NetworkX's iteration order without sorting.
- **Adjacency and edge attributes live in separate containers.** Adjacency lookups (`G[u]`, `G.neighbors(u)`) walk integer rows and never touch attribute payloads. Edge-attribute mutations (`G[u][v]["weight"] = 2`) are constant-time on the index-canonical `(min, max)` key and don't disturb the neighbor iteration order. The edge map is keyed by node slot, and a removal frees its slot instead of renumbering, so the map is rekeyed only when the store compacts: at the first insertion after a run of removals, or once freed slots outnumber live nodes. On `Graph`/`DiGraph` the node order itself tombstones too, so a removal costs O(degree). `MultiGraph` keeps reusing freed slots and tombstones a separate insertion-order list, so its removal is O(degree) as well; `MultiDiGraph`'s node table tombstones and its String-keyed row maps are unordered, so its removal is O(degree) too (`br-r37-c1-epic-storage-architecture-yr2oc.1`).
- **`DiGraph` keeps `succ_indices` and `pred_indices` as separate adjacency rows.** `in_degree(v)` and `out_degree(v)` are O(1) lookups, not full edge walks.

The `revision` counter is incremented on every mutation; the cached snapshot views in `fnx-views` and the Python view classes carry the revision they last saw, so view invalidation is a single integer compare.

### Node identity

Python node labels are canonicalized to a Rust `String` by `node_key_to_string` in `crates/fnx-python/src/lib.rs`. The canonicalization:

- Passes through Python strings unchanged.
- Stringifies integers and booleans to mirror Python's `hash(True) == hash(1)`, `hash(False) == hash(0)` collisions, so an edge added with `key=0` and one added with `key=False` resolve to the same edge (matching NetworkX's dict-based key semantics).
- Collapses floats with integer value into their integer canonical so that `hash(1) == hash(1.0)` parity holds for dict-keyed paths (matching NetworkX).
- Falls back to `repr()` for other hashable Python values (tuples, frozensets, custom objects), preserving distinctness across IEEE-754 special floats (`NaN`, `±Inf`, `1.5`, `1e20`).

This canonicalization is the entire reason MultiGraph edge keys with `key=0`, `key=0.0`, and `key=False` collide into a single edge (tracked in commit history as `br-r37-c1-edgekeyint`). The known limitation: distinct Python types whose `repr()` collides (e.g. user-defined classes returning the same string from `__repr__`) will collide as nodes in fnx. See `docs/upstream_divergence_ledger.md` for the full set of int/str/float canonicalization caveats.

### Attribute storage

In the native store, edge and node attributes live in `BTreeMap<String, CgseValue>`. `CgseValue` has five variants: `Bool`, `Int` (i64), `Float` (f64), `String`, and `Map` (nested, string-keyed). Anything else a user stores — `None`, lists, tuples, arbitrary objects — is kept exactly in the Python-side attribute dict the user sees; the native store holds a string form of it, so kernels that need a number check the value rather than trust the variant.

Native readers and writers (`fnx-readwrite`) map typed format values (`bool`, `long`, `double`) onto these variants and reject malformed type tags in strict mode.

### Node order preservation

Node insertion order is preserved across the entire graph lifecycle, with two important caveats:

- **`G.copy()` follows the NetworkX contract.** Node and adjacency insertion order are preserved; each node/edge gets a fresh attribute dict whose *values* are shared with the original (not deep-copied).
- **`copy.copy(G)` does not yet match NetworkX.** NetworkX's shallow copy shares the attribute dicts with the original and costs O(1); fnx's copies the structure (O(n)) and shares only `G.graph` (`br-r37-c1-epic-storage-architecture-yr2oc.3`).

### Views

The Python view classes (`NodeView`, `EdgeView`, `DegreeView`, `AdjacencyView`, `SubgraphView`) are defined in `crates/fnx-python/src/views.rs` on top of the borrowed snapshot primitives in `fnx-views`. Views are *live*: mutations to the underlying graph are visible through them. They carry a revision counter so they can invalidate themselves cheaply when the graph changes underneath them. `SubgraphView` is the structure operators (`union`, `intersection`, `difference`, `compose`) accept transparently; they don't materialize a fresh graph unless asked to.

### Edge attribute semantics

Edge attributes are held twice: the Python attribute dict (what `G.edges[u, v]` returns, holding the original objects) and the native `CgseValue` form the kernels read:

| Python type | Native `CgseValue` | Notes |
|---|---|---|
| `bool` | `Bool` | Python's `True == 1` is honoured where NetworkX relies on it (e.g. unit-weight checks) |
| `int` (i64 range) | `Int` | larger ints stay exact in the Python dict |
| `float` (including `NaN`/`±Inf`) | `Float` | non-finite weights are routed to NetworkX-exact code paths |
| `str` | `String` | |
| `dict[str, T]` | `Map` | nested |
| `None`, `list`, `tuple`, other objects | `String` (a string form) | the Python dict keeps the original object; it is the one users and serializers see |

The contract is *NetworkX parity*: anywhere NetworkX accepts an arbitrary Python value as an edge attribute, fnx accepts it too and returns the same object. What a format round-trip preserves follows NetworkX's reader/writer for that format; the per-format parity tests compare against it.

The `_sync_rust_edge_attrs(G)` helper is the wraparound that pushes Python-side attribute mutations like `G[u][v]["weight"] = 2.0` down into the Rust adjacency map. This is invoked transparently from algorithm wrappers; you only need to know about it if you're profiling the cost of an attribute-heavy hot loop.

### EdgeKey canonicalization

For undirected graphs, edges are canonicalized to `(u, v)` with `u <= v` lex-order so `G[u][v]` and `G[v][u]` find the same entry. For directed graphs, the source/target order is preserved. For MultiGraph variants, the inner edge key (`0, 1, 2, …` or user-supplied) is canonicalized through `edge_key_lookup_string`, collapsing `0`, `0.0`, and `False` to a single canonical (mirroring Python's dict-key hash collisions on those values).

---

## Threat Model

The security doctrine in `AGENTS.md` covers four threat surfaces:

| Surface | Threat | Mitigation |
|---|---|---|
| **Parser input** | Malformed GraphML / GML / GEXF / JSON / edgelist / Pajek crashes the process or escalates to memory corruption. | `#![forbid(unsafe_code)]` workspace-wide. 8 cargo-fuzz parser targets with persisted corpora; every DSR quality run replays each corpus and fuzzes each target for 10 seconds (check 5). Strict mode rejects malformed input; hardened mode applies bounded recovery (e.g., default attribute, skip malformed node) and logs the recovery as a `DecisionRecord`. |
| **Attribute confusion** | Attacker-supplied attribute tricks downstream code into treating a string as a number, or smuggling a callable through a deserialized graph. | `CgseValue` is a closed-variant sum type. Parsers reject mixed-type lists where the format spec forbids them. Boolean parsing accepts only the spec's literal forms (`0/1/"true"/"false"` per format). |
| **Algorithmic denial** | Adversarial graphs trigger pathological behavior (Dijkstra-with-`-∞`, A*-with-`NaN`-heuristic, planarity bombs, super-linear matching). | Algorithms that can't handle non-finite or negative weights either reject the input fast-closed or delegate to a slower-but-correct nx path. The complexity-witness ledger turns observed-vs-bound mismatches into a test failure (`cargo test -p fnx-conformance`). Stack-safety for deep DFS / planarity / transitive-closure paths. |
| **Reproducibility loss** | A future release silently changes algorithm output and breaks downstream pipelines. | RaptorQ-encoded conformance + perf artifact bundles. Decode-drill proofs. Golden snapshots locked in `tests/python/test_*_golden.py`. CGSE policy registry pinned in source. `docs/coverage.md` drift fails the DSR quality run. |

---

## Roadmap

In rough priority order (`bv --robot-triage` shows the current bead backlog):

1. **Strict/Hardened runtime mode exposure** (shipped in `br-r37-c1-9a8bo`). Process-wide and thread-local mode switches via `fnx.config` and context managers, read kwargs, `DecisionRecord` ledger, and 24+24 parity/recovery fixtures.
2. **One quality authority that runs the whole evidence set.** GitHub Actions is retired (its last run, `34406228506` on 2026-09-09, was green); DSR is now the only quality and release authority. It runs the full Python parity suite, the conformance crate's tests with the fixture replay, NetworkX's own test suite (held to a ratchet) and a fuzz smoke over all 33 targets. What `br-r37-c1-rc0923-epic-evidence-authority-hhj5p.1` still needs is a recorded DSR run of the whole set that passes on main, and one that fails on a planted failure.
3. **Native planar embedding & Kuratowski counterexamples** (shipped in `br-r37-c1-rc-planar-embedding-kernel-07rh8` / `br-r37-c1-rc-planarity-integration-cb6sb`). `check_planarity` builds its `PlanarEmbedding` rotation orders and extracts Kuratowski subgraph certificates natively in Rust.
4. **Performance proof artifacts per SLO row (E3)** so every algorithm family in `docs/performance.md` has a profile-and-prove witness on file.
5. **Tail closure on the remaining NetworkX-bound exports.** On the default path, 35 of 41 commonly used functions executed no NetworkX code in the 2026-09-23 census; since then `maximum_branching` and its family, `max_weight_matching`, `min_weight_matching` and `greedy_modularity_communities` run natively too. The always-NetworkX ones today are weighted/self-loop Louvain, `simple_cycles` and `k_components`, and several functions still reach NetworkX for specific argument shapes. Move them to native kernels while preserving the parity contract.
6. **Release cadence.** Ship `main` to PyPI (current release: `0.2.1`); subsequent 0.x releases should land only after the parity, conformance, and SLO gates are green.

---

## Glossary

- **CGSE (Canonical Graph Semantics Engine).** The Rust crate (`fnx-cgse`) and runtime policy machinery (`fnx-runtime`) that pin tie-break policy and emit complexity witnesses.
- **Complexity witness.** A `ComplexityWitness { n, m, dominant_term, observed_count, policy, seed, decision_path_blake3 }` receipt emitted per algorithm execution, drainable from a `WitnessLedger` for audit.
- **Compatibility mode (Strict vs Hardened).** Two-mode runtime contract: Strict fails closed on malformed input; Hardened applies bounded recovery and records every recovery as a `DecisionRecord`.
- **Conformance harness.** The `fnx-conformance` crate; replays curated graph fixtures through fnx and the legacy NetworkX oracle, emitting a structured report under `artifacts/conformance/latest/`.
- **Coverage matrix.** The `docs/coverage.md` ledger, auto-generated from pinned NetworkX 3.6.1 by `scripts/generate_coverage_matrix.py`. It classifies 4,926 qualified paths as present, partial, missing, n/a, or reasoned excluded, reports per-family strict coverage, and retains the `franken_networkx.__all__` route analysis as an appendix.
- **Decision-path hash (`decision_path_blake3`).** A length-prefixed Blake3 hash of the sequence of tie-break decisions an algorithm made. Used to detect non-determinism.
- **Delegation ledger.** `docs/delegation_ledger.md`; enumerates every `_call_networkx_*_for_parity` route (public exports that intentionally fall back to NetworkX for specific argument shapes).
- **Fail-closed.** A policy choice in `fnx-runtime`: on uncertain input, raise rather than guess. The default in Strict mode.
- **PY_WRAPPER / RUST_NATIVE / NETWORKX_HELPER.** The three runtime-route categories in the coverage matrix's runtime ledger.
- **RaptorQ sidecar.** An RFC 6330 erasure-coded shadow file written alongside a long-lived artifact (conformance bundle, perf baseline, migration manifest). Combined with a scrub report and a decode-proof receipt to make the artifact self-healing.
- **TieBreakPolicy.** The 13-variant Rust enum in `fnx-cgse` that pins how an algorithm resolves equally-correct choices.
- **Upstream divergence ledger.** `docs/upstream_divergence_ledger.md`; unified record of `native-parity`, `wrapper-patched`, `intentionally-delegated`, `raw-known-gap`, and `owner-acknowledged-limitation` rows.
- **Witness ledger.** A scoped collector inside `fnx-cgse`; you push an algorithm execution into it and drain `ComplexityWitness` receipts at the end of a scope.

---

## References and Inspiration

- **NetworkX.** Hagberg, A., Schult, D., & Swart, P. (2008). *Exploring network structure, dynamics, and function using NetworkX*. SciPy 2008. <https://networkx.org/>. The behavioral oracle for every algorithm in this project; a reference copy ships in `legacy_networkx_code/`.
- **PyO3 + Maturin.** <https://pyo3.rs/> and <https://www.maturin.rs/>. The Python ↔ Rust binding layer and build tool.
- **`indexmap`.** <https://docs.rs/indexmap/>. The deterministic ordered-map that makes node and edge iteration order reproducible.
- **RaptorQ (RFC 6330).** <https://www.rfc-editor.org/rfc/rfc6330>. The erasure code used in `fnx-durability` for self-healing artifact sidecars.
- **VF2++.** Jüttner, A., & Madarasi, P. (2018). *VF2++: An improved subgraph isomorphism algorithm*. Discrete Applied Mathematics, 242. The basis of the native isomorphism path.
- **Edmonds' algorithm.** Edmonds, J. (1967). *Optimum branchings*. Used in the maximum branching / arborescence path.
- **Stoer-Wagner minimum cut.** Stoer, M., & Wagner, F. (1997). *A simple min-cut algorithm*. JACM 44(4). Used by `stoer_wagner`.
- **Boyer-Myrvold planarity.** Boyer, J., & Myrvold, W. (2004). *On the cutting edge: Simplified O(n) planarity by edge addition*. JGAA 8(3). The basis of the native planarity certificates.
- **Janssens-Sörensen spanning-tree enumeration.** Used in the `SpanningTreeIterator` and `ArborescenceIterator` rewrite.
- **Kleinberg navigable small world.** Kleinberg, J. (2000). *The small-world phenomenon: an algorithmic perspective*. Backing the `navigable_small_world_graph` generator.

---

## Project Layout

```
franken_networkx/
├── Cargo.toml                 # workspace root (12 crates)
├── pyproject.toml             # maturin + NetworkX backend entry points
├── rust-toolchain.toml        # pinned Rust nightly
├── crates/                    # the 12 Rust crates
│   ├── fnx-classes/           # Graph, DiGraph, MultiGraph, MultiDiGraph
│   ├── fnx-views/             # live and cached views
│   ├── fnx-dispatch/          # backend dispatch routing
│   ├── fnx-convert/           # type conversions + NumPy/SciPy/pandas
│   ├── fnx-algorithms/        # algorithm implementations
│   ├── fnx-generators/        # graph generators
│   ├── fnx-readwrite/         # I/O for 12+ formats
│   ├── fnx-cgse/              # Canonical Graph Semantics Engine
│   ├── fnx-runtime/           # Strict/Hardened modes + policy engine
│   ├── fnx-conformance/       # differential conformance harness
│   ├── fnx-durability/        # RaptorQ sidecars + scrub
│   └── fnx-python/            # PyO3 bindings (cdylib)
├── python/franken_networkx/   # Python package surface
│   ├── __init__.py            # 839 FNX root exports; not the NetworkX coverage denominator
│   ├── backend.py             # 313 algorithms wired into nx dispatch
│   ├── backend_info.py        # backend metadata for nx registration
│   └── _fnx.pyi               # type stubs
├── tests/python/              # ~1,100 parity / conformance / metamorphic / fuzz / hypothesis / golden test files
├── fuzz/fuzz_targets/         # 33 cargo-fuzz binaries (parsers + algorithm harnesses)
├── examples/                  # 4 runnable examples
├── docs/                      # docs + 5 auto-generated audit ledgers
├── artifacts/                 # CI-generated conformance / perf / RaptorQ artifacts
├── legacy_networkx_code/      # NetworkX Python reference (behavioral oracle)
├── reference_specs/           # reference specifications
├── scripts/                   # audit generators + CI helpers
└── .github/workflows/ci.yml   # G0–G8 gate topology
```

---

## About Contributions

> *Please don't take this the wrong way, but I do not accept outside contributions for any of my projects. I simply don't have the mental bandwidth to review anything, and it's my name on the thing, so I'm responsible for any problems it causes; thus, the risk-reward is highly asymmetric from my perspective. I'd also have to worry about other "stakeholders," which seems unwise for tools I mostly make for myself for free. Feel free to submit issues, and even PRs if you want to illustrate a proposed fix, but know I won't merge them directly. Instead, I'll have Claude or Codex review submissions via `gh` and independently decide whether and how to address them. Bug reports in particular are welcome. Sorry if this offends, but I want to avoid wasted time and hurt feelings. I understand this isn't in sync with the prevailing open-source ethos that seeks community contributions, but it's the only way I can move at this velocity and keep my sanity.*

---

## License

MIT. See [`LICENSE`](LICENSE).

The upstream NetworkX project is BSD-3-Clause licensed. A reference copy of the NetworkX source ships in [`legacy_networkx_code/`](legacy_networkx_code/) as a behavioral oracle for the conformance harness.

