Module network_simplex_int 

Exact-integer primal network-simplex kernel, exposed as a first-class Rust API so sibling crates can use the exact-integer min-cost-flow path without depending on the PyO3 binding crate. The PyO3 network_simplex_int binding in fnx-python delegates here, keeping a single source of truth. Exact-integer primal network-simplex kernel (first-class Rust API).

A faithful transcription of NetworkX’s network_simplex (networkx/algorithms/flow/networksimplex.py, BSD-licensed) pivot logic, specialised to integer demands/capacities/weights — the common, and the only byte-exact-integer, case. All arithmetic here is i64; there is no f64 anywhere on this path, so results are exact and reproducible with no rounding.

This kernel was hoisted out of the PyO3 binding crate (fnx-python) so that sibling Rust consumers (e.g. MTDT’s integer voice-leading optimal transport) can use the exact-integer min-cost-flow path directly, without taking a dependency on fnx-python/PyO3. fnx-python now calls this same code, so there is a single source of truth for the pivot logic and both the Rust API and the Python binding produce identical numeric results.

Determinism: the entering-edge search (block search / Dantzig + Bland), the leaving-edge tie-break (first minimiser in reversed cycle order, matching Python’s min), and every array update below are deterministic functions of the input arrays in the order they are supplied. Given the same (node_demands, src, tgt, cap, wt) the solver always returns the same (status, cost, flows) — see the determinism unit test.

Convention (identical to NetworkX): a node’s demand is positive when the node is a sink (consumes flow) and negative when it is a source (supplies flow); the demands must sum to zero for a feasible problem.

NetworkX uses a dummy root node and encodes “no parent” / the root via Python’s negative-index alias -1 (which addresses the dummy root stored at index n). Here the root is the explicit index n, and a true None parent is NONE = usize::MAX.

Structs

NetworkSimplexIntSolution

Outcome of network_simplex_int.

Enums

NetworkSimplexStatus

Result status of an exact-integer network-simplex solve.

Constants

CAP_INF

Sentinel used inside network_simplex_int to mean “unbounded / +infinity” capacity. Any capacity >= i64::MAX is treated as infinite. Rust callers that want an infinite-capacity edge should pass i64::MAX for that edge’s capacity.

Functions

network_simplex_int

Solve an exact-integer minimum-cost-flow problem via primal network simplex.