Metadata-Version: 2.4
Name: franken-networkx
Version: 0.2.1
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.0
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.0 ; 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">

[![CI](https://github.com/Dicklesworthstone/franken_networkx/actions/workflows/ci.yml/badge.svg)](https://github.com/Dicklesworthstone/franken_networkx/actions/workflows/ci.yml)
[![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 enforced by a 1,085-file Python parity test suite, by a curated Rust differential conformance harness, and by five auto-generated audit ledgers (coverage matrix, raw-vs-public, delegation, upstream divergence, API ergonomics) that fail CI if a measured public symbol drifts. The current structural surface result is not 100%: the pinned NetworkX 3.6.1 FeatureUniverse has 3,823 strictly present paths out of 4,129 applicable paths (92.6%), with 306 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 | **3,823 / 4,129 strictly present (92.6%)**; 306 partial, 0 missing |
| 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 |
| CI gates | tests | **G0–G8**: docs freshness → fmt → clippy → rust tests → python parity → e2e → docs → examples → conformance → performance SLO → UBS → fuzz smoke → RaptorQ scrub |

---

## 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 gate (`pytest tests/python/`, 1,085 files) compares fnx-vs-nx call by call across thousands of fixtures, including iteration order, exception class, and error wording.
- The auto-generated audit ledgers under `docs/` fail CI if `__all__` drifts or if a wrapper acquires a NetworkX delegation route that isn't documented.
- 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 | **partial**; 92.6% strict import/signature coverage, with fallback on many unsupported paths | scoped; explicit CGSE `TieBreakPolicy` on owned paths | 3,823 present / 306 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. CGSE pins the tie-break for every algorithm at the type level, records it in the `ComplexityWitness`, and Merkle-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.

None of these are aspirational. They are load-bearing in the CI gate topology, and skipping any one of them breaks the build.

---

## 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 │  │ 550+ 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` | ~96 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

Every algorithm declares, at the type level, which policy governs its choices when multiple equally-correct answers exist:

```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-02 there are 22 `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
    fnx_algorithms::pagerank(&graph, 0.85, 100, 1e-6)
});

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. The gate runs inside G3's `cargo test` sweep.

### 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 NumPy / SciPy extras
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::pagerank(...) with a CGSE         │
 │       PolicyContext that pins the tie-break policy.                │
 └─────────────────────┬──────────────────────────────────────────────┘
                       │  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 793 `franken_networkx.__all__` implementation routes. Drift fails CI. |
| [`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) | Every `_call_networkx_*_for_parity(...)` call site enumerated and AST-classified: 61 mixed-route / 71 nx-fallback / 1,113 py-wrapper / 92 rust-native / 338 rust-reexport routes. Tracks which algorithms intentionally delegate edge cases to upstream NetworkX. |
| [`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 a CI gate (`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

- Implementation routes across `franken_networkx.__all__` (one name may carry several routes), per the ledger's AST classification: **1,113** py-wrapper, **338** rust-reexport, **92** rust-native, **71** nx-fallback, **61** mixed-route.
- The **71** nx-fallback + **61** mixed-route exports retain a NetworkX path for specific argument shapes or edge cases (typically: complex callable arguments, drawing/matplotlib, exotic format variants). The native fast path runs for the common case.
- 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.
- **0** "DIRECT_NETWORKX" public exports at the Python wrapper layer. Dispatch is always through the `_call_networkx_*_for_parity` helper layer tracked in the delegation ledger.

---

## 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.** Strict mode fails closed on adversarial inputs (NaN edge weights, ±∞ weights on algorithms that can't handle them, malformed directed flags, namespace-prefix abuse). Hardened mode applies bounded defensive recovery.
- **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. The G8 CI gate runs the full scrub + decode-drill against the latest conformance bundle on every push.

---

## 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 = "franken_networkx.backend_info:get_backend_info"
```

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. Mutation-preserving dispatchables (`relabel_nodes`, `contracted_nodes`, `set_node_attributes`, `double_edge_swap`, ...) write the mutation back to the original graph rather than a throwaway copy.

### 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 not documentation. They are *machine-checked invariants*. Each is generated by a script under `scripts/`, run on every CI push, and a drift between the generated file and what's checked in fails the build.

### 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 793 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 CI breaks.

### 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?*

Combined, these turn "byte-for-byte compatibility" from an aspiration into a property the CI enforces on every commit.

---

## Quality Gates (CI)

CI is structured as a strict, sequential gate topology in [`.github/workflows/ci.yml`](.github/workflows/ci.yml). A break at gate N short-circuits everything after it.

| Gate | Job | Purpose |
|---|---|---|
| **G0** | docs freshness | `README.md`, `docs/planning/FEATURE_PARITY.md`, `CHANGELOG.md` may not lag HEAD by more than 150 code commits (raised from 50 in 2026-09; integrity split: `artifacts/g0-threshold-split-2026-09.md`). |
| **G1** | fmt | `cargo fmt --all -- --check` on nightly. |
| **G2** | clippy | `cargo clippy --workspace --all-targets -- -D warnings` on Ubuntu + macOS + Windows. |
| **G3** | rust tests | `cargo test --workspace` on Ubuntu + macOS + Windows. |
| **G4** | python parity | `pytest tests/python/`, the canonical conformance gate (1,085 test files). |
| **G4b** | e2e | `scripts/e2e_integration_test.py` with NumPy + SciPy. |
| **G4c** | docs verifier | `scripts/verify_docs.py`; every code example in `docs/*.md` is import-checked and executed. |
| **G4d** | examples | All four `examples/*.py` scripts must run cleanly. |
| **G5** | conformance | `fnx-conformance` harness replay + dashboard generation into `artifacts/conformance/latest/`. |
| **G6** | performance SLO | `scripts/run_benchmark_gate.sh` (isomorphism, regression, conformal and SLO gates; the SLO step is `scripts/run_perf_slo_gate.py`); p50/p95/p99 thresholds per algorithm family. |
| **G7** | UBS | Ultimate Bug Scanner static analysis on the workspace. |
| **G7b** | fuzz smoke | 15 cargo-fuzz targets: 8 parser harnesses × 60 s + 7 algorithm harnesses × 30 s. |
| **G8** | RaptorQ | Generate / scrub / decode-drill RaptorQ sidecars for conformance + perf bundles. |

---

## 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.

To run the suite:

```bash
maturin develop --release --features pyo3/abi3-py310
pytest tests/python/ -v --tb=long
```

Skip slow tests for a fast loop:

```bash
pytest tests/python/ -v -m "not slow"
```

Cross-validate a specific algorithm family against NetworkX:

```bash
pytest tests/python/ -v -k "shortest_path or dijkstra"
```

### Conformance Testing Methodology

The 1,085 Python test files 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 CI 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 run together as a single `pytest tests/python/` invocation: Gate G4 in CI.

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/` that the CI dashboard generator turns into per-family parity reports, and those reports are RaptorQ-encoded by Gate G8 for self-healing replay.

---

## 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. The dated incumbent comparison below ranges from 1.6085× to 36.1146× on the listed winning rows. |
| 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 power iteration; 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. |
| `Graph` incremental `add_edge` | **0.46–0.50×** | Still a decisive loss, and improving. Two admitted 2026-08-08 measurements vs live nx 3.6.1 in the same invocation (was `0.4387×` on 2026-08-04, `0.26×` before that): `0.4974×` CI `0.4833–0.5129×` and `0.4616×` CI `0.4563–0.4658×`. **The range is the honest figure — the cross-run spread exceeds either CI**, and the mover is the incumbent arm, which timed `677.1` vs `574.8 ns/edge` between the two invocations while fnx moved only `1296 → 1245`. Both runs pass their dual A/A nulls, which is the point: a null certifies stationarity WITHIN a run and says nothing about comparability across runs. 21 interleaved rounds, 8,000 calls on a fresh graph per timed unit, 40 warm-up builds per arm — mutation arms are non-stationary and an under-warmed run here has produced a wrong SIGN before (`br-r37-c1-jc9e4`). Moved by `br-r37-c1-wa1b9` (2026-08-08), which stopped internal endpoint autocreation from filing its own ledger record: `Graph::add_edge_with_attrs` went `816 → 507–540 ns/edge`, and the native path `1113.2 → 928.2 ns/edge` (`0.5525× → 0.6274×`). The Python `None`/hashability shim costs `332.6 ns/edge`, `26.5%` of end-to-end — measured against the raw native path in the SAME invocation (`0.7351×` CI `0.7298–0.7382×`), still under the `40%` bar that rejected attacking it. Batch constructors remain ~3× 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.0159× → 0.0037×** (n=1,600 → 25,600) | Super-linear on all four classes where nx is O(degree): the index-keyed edge store rekeys on every removal. Measured by `br-r37-c1-remove-node-is-quadratic-tv8wd` (2026-08-27, fresh graph per repetition, min-of-5, 0.0015× on `Graph` at 25.6k nodes) and reproduced in shape on 2026-09-02 with a same-process interleaved sanity probe that carried no A/A null (`harness=ad-hoc scaling probe`, `same_host=thinkstation1`, `rch_worker=none`). The scaling class, not the constant, is the finding. Open. |
| `MultiDiGraph.get_edge_data(u, v)` (unkeyed) | **0.2482× → 0.0274×** (1 → 16 parallel edges) | Builds a fresh outer dict per call, linear in the parallel-edge count, where nx returns the live keydict (`br-r37-c1-f3i50`, 2026-08-16, ELF `00a3b11ef4da3fc8`, `same_host=thinkstation1`). The parity defect (new-key insertion does not reach the graph) and the loss share one fix, a live keydict mirror, blocked on `br-r37-c1-himzq`. Open. |
| `G[u][v]` | **0.36×** | The inner subscript is the loss; `G[u]` alone wins 1.16× (`br-r37-c1-ey6ob`, 2026-09-01, `same_host=thinkstation1`). A 2026-09-02 sanity probe with no null read 0.96× on a different shape (repeated lookups of one edge on n=2,000), so the ratio is shape-dependent; the bead's figure stands as the measured row. Open. |

The `add_edge` row was re-measured on 2026-08-04 (`br-r37-c1-8n3j3`, `br-r37-c1-eo88t`): 4,000
`G.add_edge(u, v)` calls building a path graph from empty, genuine unpatched NetworkX 3.6.1 in the
same invocation, 21 interleaved rounds, `PYTHONHASHSEED=0`, pinned with `taskset`, A/A null
0.9944–1.0042×. It moved from 0.26× after the CGSE decision ledger stopped writing two unbounded
records per edge — that ledger was 46.7% of `Graph::add_edge_with_attrs`.

**Updated 2026-08-08** (`br-r37-c1-wa1b9`): the row is now `0.4974×`, measured with 8,000 calls on a
fresh graph per timed unit rather than 4,000 on one growing graph. The ledger's SHARE has since gone
UP, not down — `15.9%` was `270.7 ns` of a `1703.3 ns` total, and it is now `34.9%` because the
absolute cost fell to `176.8 ns` while the total fell further, to `507 ns`. The remaining lever on it
is `br-r37-c1-g2nev`. Reproduce the decomposition with
`env -u CARGO_TARGET_DIR taskset -c 40-47 cargo test -p fnx-classes --release ledger_record_cost_ab -- --ignored --nocapture`;
its `A1` arm is the shipped one-record-per-`add_edge` path and `A2` is the pre-`wa1b9` counterfactual.

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.** A native Rust port of Edmonds' blossom-shrinking algorithm exists (`_fnx.max_weight_matching`, sign-parameterised for min/max with the `maxcardinality` flag), but the public `max_weight_matching` delegates to NetworkX: on graphs with several equally optimal matchings the native kernel picked a different valid matching, and returned some pairs in the opposite `(u, v)` direction, than nx's DFS augmenting-path traversal (`br-r37-c1-kpnc8`). Drop-in code compares matchings against reference pair sets, so the wrapper mirrors nx exactly, including its `NetworkXNotImplemented` on directed and multigraph input. `min_weight_matching` is a Python wrapper over the same route. Both appear as `nx-fallback` / `py-wrapper` in `docs/delegation_ledger.md`.
- **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`).** Currently routes through NetworkX against a converted graph. The former native CNM public route was retired after an insertion-order-sensitive partition divergence (`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 `LexMin` tie-break for the no-predecessor frontier; matches nx's `_topological_sort` exactly including order 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 one also accepts `personalization`, `nstart`, `dangling` and forwards them to the native kernel):

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

The Rust kernel:

1. Calls `cgse_begin(CgseReferenceAlgorithm::PageRank)` to create a `WitnessSink`.
2. Builds dense `Vec<u32>` node-index working data from the `IndexMap`-keyed adjacency.
3. Runs the algorithm body using indices for inner loops.
4. Calls `cgse_record_decision(...)` at every tie-break point.
5. Calls `cgse_publish(...)` at the end to finalize the witness and push it into the thread-local `WitnessLedger`.
6. Returns the result as `HashMap<String, f64>` (or whatever the algorithm's natural return type is).

### 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:

```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).
- **`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 family into `artifacts/conformance/latest/`. Each report carries `{schema_version, fixture_id, fnx_commit, nx_version, status, mismatches[], duration_ms, witness_hash}` and a RaptorQ sidecar (`*.raptorq.json`) plus a decode-proof receipt (`*.recovered.json`). The witness ledger itself is in `structured_logs.jsonl`, one line per algorithm call, drainable as JSON.

### 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);
}
```

The threading of `RuntimePolicy` through parser and high-risk algorithm entry points is in progress (roadmap beads D2–D4). At the Python layer today, the default `Strict` mode is in effect; an explicit Python toggle is part of the same D2–D4 milestone.

### 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
pytest tests/python/ -v --tb=long

# 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

ABI3 wheels published to PyPI are built in CI on three runners (Ubuntu, macOS, Windows). 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__)        # should print "0.2.0" or later

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 |
|---|---|
| `RUST_LOG=fnx=info` | Enables `tracing` output from the workspace. `debug` for verbose; `trace` for everything including per-call diagnostics. Applied at process start; honored by anyone subscribing via `tracing-subscriber`. |
| `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. |

FrankenNetworkX itself does not introduce custom `FNX_*` environment variables today. Runtime behavior is configured per call (via the `RuntimePolicy` builder shown earlier) rather than via process-wide flags. This is intentional: per-call construction means behavior is reproducible from the decision log alone.

---

## 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)
```

The default CGSE `WeightThenLex` tie-break + `IndexMap` adjacency means: on the same input + same fnx version + same seed for any randomized stage, you get byte-identical PageRank values across machines. There is no "but on my Mac it returns 0.299 instead of 0.300"; that doesn't happen in CGSE-pinned algorithms.

### 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.0"
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 ships pre-built ABI3 wheels for:

- Linux x86_64 (manylinux_2_28)
- Linux aarch64
- macOS x86_64 (10.12+)
- macOS arm64 (11.0+)
- Windows x86_64

If you're on a non-standard platform (musl libc, FreeBSD, embedded Linux variants), you'll need to build from source. The build is cargo-driven so it works anywhere Rust nightly works.

### Memory considerations

The IndexMap-backed adjacency is denser than NetworkX's `dict-of-dicts` per node (typical ratio: 60–70% of nx's memory for the same graph). The `node_key_map` + `node_py_attrs` + `edge_py_attrs` caches add overhead proportional to the number of Python-side attribute accesses you make. For pipelines that never touch attributes, those caches stay nearly empty.

Rough rules of thumb for a graph with `n` nodes + `m` edges + average `a` attributes per node/edge:

- Pure adjacency (no attributes): ~80 bytes per node + ~24 bytes per edge.
- With attributes: + ~120 bytes per attribute (CgseValue tagged union + Python dict bridge).

A 1M-node graph with 4M edges and 2 attributes per edge is roughly 80MB pure adjacency + ~1GB with attribute storage on both sides.

### 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)
# The Python wrapper layer logs at INFO when an algorithm is dispatched via the backend.
logging.getLogger("franken_networkx.backend").setLevel(logging.INFO)
```

For Rust-side `tracing` output, set `RUST_LOG=fnx=info` in the process environment before importing fnx.

### 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 NumPy / SciPy extras
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 33 cargo-fuzz binaries have collectively run for thousands of CPU-hours in CI without finding a panic. That's the security contract you want before feeding `nx.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)
logging.getLogger("franken_networkx.backend").setLevel(logging.DEBUG)

# Now every backend dispatch decision is logged at DEBUG.
```

For Rust-side `tracing` output, point `RUST_LOG=fnx=info` at any process that loads the cdylib; the spans annotate algorithm entry/exit, GIL-release boundaries, and witness-ledger drains.

---

## 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.
- **71 nx-fallback + 61 mixed-route exports** retain a NetworkX path. These are not bugs; they are the documented set in `delegation_ledger.md` where unusual argument shapes (callable arguments, exotic format variants, deprecated API forms) defer to NetworkX. The native fast path runs for the common case.
- **Release status.** `v0.2.1` is published on PyPI with pre-built ABI3 wheels across Linux (`x86_64`, `aarch64`, `musllinux`), macOS (`x86_64`, `aarch64`), and Windows (`x86_64`) supporting Python 3.10 through 3.14+.
- **No Windows/macOS performance SLO yet.** The performance gate (G6) currently runs only on Linux. Correctness gates (G1–G3) cover all three platforms.
- **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?**
Not across all of NetworkX today. Against the pinned 3.6.1 declared import-and-signature FeatureUniverse, 3,823 of 4,129 applicable paths are strictly present (92.6%), while 306 are partial and 0 are 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. Every algorithm declares (at the type level) which of the 13 `TieBreakPolicy` variants governs its 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?**
Mutation-preserving dispatchables (`relabel_nodes`, `contracted_nodes`, `contracted_edge`, `identified_nodes`, `set_node_attributes`, `set_edge_attributes`, `double_edge_swap`, `connected_double_edge_swap`) write the mutation back to the original graph rather than a throwaway copy. This was a coordinated late-cycle effort tracked under beads `br-r37-c1-{pq52x, frbgb, tq78w, l2j31}`.

**How are NaN edge weights handled?**
The Dijkstra / A* / PageRank +∞ gate uses a native Rust nonfinite-weight scan as a fast pre-check. Strict mode fails closed on `NaN` weights with a typed error. Hardened mode applies the documented recovery (e.g. coerce `NaN → +∞` for the affected algorithm only) and records the recovery in the decision log.

**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. The dependency on `networkx>=3.0` is part of the parity-helper architecture (the `_call_networkx_*_for_parity` routes need nx available). A "pure fnx" mode would require porting the remaining NetworkX-bound routes — 71 nx-fallback plus 61 mixed-route in the current ledger classification — to native Rust.

---

## 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.

### "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.

### "My CI is failing G0 (docs freshness)"

This gate fires if `README.md`, `docs/planning/FEATURE_PARITY.md`, or `CHANGELOG.md` hasn't been touched in 150+ code commits (raised from 50 in 2026-09; integrity split: `artifacts/g0-threshold-split-2026-09.md`). Touch the file in the same PR that introduces a substantive change, or batch a `chore(docs):` commit before merging.

---

## 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 target of the planned native planarity port.
- **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 mutation
    nodes:       FxIndexMap<String, AttrMap>,         // node → its attrs, insertion-ordered
    adj_indices: Vec<Vec<usize>>,                     // node index → neighbor indices, insertion-ordered
    edges:       FxIndexMap<(usize, usize), AttrMap>, // index-canonical (min, max) → edge attrs
    edge_index_endpoints: Vec<(usize, usize)>,        // edge slot → string-canonical orientation
    runtime_policy: RuntimePolicy,
}

pub struct DiGraph {
    mode:         CompatibilityMode,
    revision:     u64,
    nodes:        FxIndexMap<String, AttrMap>,
    succ_indices: Vec<Vec<usize>>,
    pred_indices: Vec<Vec<usize>>,
    edges:        FxIndexMap<(usize, usize), AttrMap>,
    runtime_policy: RuntimePolicy,
    // 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 price is paid on node removal: the index-keyed edge map is rekeyed, which is the super-linear `remove_node` cost tracked in `br-r37-c1-remove-node-is-quadratic-tv8wd`.
- **`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

Edge and node attributes live in `BTreeMap<String, CgseValue>`. `CgseValue` is a tagged union covering:

- `None` / `Bool` / `Int` (i64) / `Float` (f64) / `String`
- Homogeneous and heterogeneous sequences
- Nested dicts (recursive `CgseValue` map)

Reading and writing attributes uses `serde` end to end. Format writers (`write_gml`, `write_graphml`, `write_gexf`) emit the correct typed values (`bool=0/1`, `long`, `double`) based on the `CgseValue` variant. Read-side, parsers validate type tags and reject malformed inputs in strict mode.

### Node order preservation

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

- **`G.copy()` is shallow per the NetworkX contract.** Node insertion order is preserved on the copy, but node attribute dicts are aliased, not deep-cloned.
- **`G.copy()` does not preserve node insertion order in some legacy code paths.** This is a known quirk recorded in the project memory; rely on the explicit `add_node` / `add_edge` order if order matters for a tie-break-sensitive downstream call.

### 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 pass through `CgseValue`, a tagged-union representation that round-trips between Python objects and Rust's `serde`-serializable values. The supported types and how they survive a round-trip:

| Python type | CgseValue variant | Round-trips through GraphML / GML / JSON? | Notes |
|---|---|---|---|
| `None` | `Null` | yes | GraphML `<data>` element with empty body |
| `bool` | `Bool` | yes | `bool=true/false` for GraphML, `0/1` for GML, JSON boolean |
| `int` (i64 range) | `Int` | yes | GraphML `long`, GML integer, JSON number |
| `float` (finite) | `Float` | yes | GraphML `double`, GML real, JSON number |
| `float` (`NaN`/`±Inf`) | `Float` | partial | GML/GraphML lose precision; JSON preserves via `null` per RFC 7159 |
| `str` | `String` | yes | XML-escaped for GraphML/GEXF, escaped for GML, JSON-escaped |
| `list[T]` (homogeneous) | `Sequence` | yes | type-tagged in GraphML, lossy in GML |
| `dict[str, T]` | `Mapping` | partial | preserved in JSON node-link; GraphML/GML flatten or skip |
| arbitrary Python object | `Repr(String)` | no | falls back to `repr()`, type identity not preserved |

The contract is *NetworkX parity*: anywhere NetworkX accepts an arbitrary Python value as an edge attribute, fnx accepts it too. The difference is that fnx's serialization preserves type tags where the underlying format supports it (GraphML's typed `<data>` elements, GML's typed scalars) so a round-trip `G → write_graphml → read_graphml → G'` preserves the type, not just the string representation.

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 run on every CI push for 60 s each, with persisted corpora. 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 CI signal. 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. Audit ledgers fail CI on drift. |

---

## 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. **First green CI run refreshes `artifacts/conformance/latest/`** — the freshness gate already exists in CI (`.github/workflows/ci.yml`, beads B2–B4 closed); the committed bundles are stale (conformance newest 2026-05-22, perf artifacts 2026-04) purely because no run has gotten past G0/G1 since April.
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** (71 nx-fallback + 61 mixed-route routes in the ledger). Move as many as possible to native fast paths while preserving the parity contract.
6. **Release cadence.** `v0.2.1` is published on PyPI with multi-platform ABI3 wheels across Linux, macOS, and Windows. 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 target of the planned native planarity port.
- **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            # 793 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,085 parity / conformance / metamorphic / fuzz / hypothesis / golden tests
├── 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.

