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).
Returned by katz_centrality_checked when power iteration
fails to converge within [KATZ_DEFAULT_MAX_ITERATIONS]. Mirrors
nx’s PowerIterationFailedConvergence contract — the Rust
scaffolding previously discarded the convergence flag, so callers
got a normalized-but-un-converged vector instead of an error
(br-r37-c1-ua4i8).
networkx’s louvain_partitions(G, ...) one generator resume at a time
(br-r37-c1-81vo1): LouvainLevels::advance runs exactly the code
networkx runs between two yields - a shuffle draw per _one_level - so a
caller stepping it lazily, drawing from the same generator in between,
sees networkx’s stream. The partition is over node positions, in the
order of node_names.
Error returned by pagerank_with_weight_checked when the input
graph carries a negative edge weight. Power iteration over signed
transition matrices is numerically unstable (the per-row weight
shares become signed and the rank vector drifts away from sum=1),
so callers should fall back to a pure-Python NetworkX path that
uses sparse-matrix arithmetic.
Index-space all-pairs Dijkstra rows. Sources are implicit by row index;
targets and predecessors stay as graph indices so bindings can avoid two
temporary String allocations for every reachable pair.
The index-keyed core of all_shortest_paths_weighted_directed: Dijkstra with
multi-predecessor tracking over arcs(u) - (successor, weight) in the order
networkx iterates G[u] - then every shortest path source -> target, in
networkx’s _build_paths_from_predecessors order. Callers holding their own
adjacency (a MultiDiGraph’s min-parallel-weight rows) share it, so they run no
projection graph per call (br-r37-c1-q6rrt).
Byte-exact native reimplementation of
networkx.approximation.average_clustering(G, trials, seed) for an integer
seed (br-r37-c1-approxacc). nx samples trials random nodes, picks two
random neighbours of each, and counts how many are adjacent — all over a
CPython random.Random(seed). The node indices are drawn FIRST (the list
comprehension), then sample(nbrs, 2) interleaves with the loop exactly as
nx does, so the ApproxRandom draw order is identical. Runs over
neighbors_indices (== nx’s list(G[node]) order). Caller gates n >= 1
and trials >= 1.
Return the attracting components of a directed graph.
An attracting component is an SCC with no outgoing edges.
Matches networkx.attracting_components(G).
br-r37-c1-0g2tj: single-source Bellman-Ford in index space for the
bindings - (node, distance, all_int, predecessor) in SPFA first-discovery
order (networkx’s dict order; the source’s predecessor is u32::MAX), or
None for a negative cycle reachable from the source. Emitting from here
drops the owned name per node and the String-keyed maps the public result
needs, and all_int drops the Python pass that re-typed every distance
(the whole-ring single_source_bellman_ford_path_length ran 0.61x
networkx).
Return the shortest path length from source to target using Bellman-Ford.
Matches networkx.bellman_ford_path_length(G, source, target, weight).
Returns Err(true) if a negative cycle is detected, Err(false) if no path, Ok(length) otherwise.
BFS layers from multiple sources on an undirected graph.
Layer 0 = all sources, Layer 1 = neighbors of any source not already visited, etc.
Matches networkx.bfs_layers with an iterable of sources.
br-r37-c1-6hpa9: multi-source BFS layers WITH the discovering parent
(None for sources) — lets bindings reproduce nx’s discovery-object
semantics without a second walk.
Return the biconnected components of the graph.
Each component is a set of edges. Uses edge-stack based DFS.
Matches networkx.biconnected_components(G).
networkx’s EXACT bidirectional Dijkstra for an undirected simple graph with a
string weight key and non-negative, finite, numeric (or absent => 1.0) edge
weights — precisely the cases the Python dispatcher routes here (multigraph,
directed, callable / non-string / negative / non-finite / non-numeric / None
weights are all delegated to nx before this is reached).
br-r37-c1-k4wsy: directed sibling — forward over succ rows, reverse
over pred rows. The old single-pair path used a UNIDIRECTIONAL BFS,
which picks a different (equal-length) path than nx on tie-breaks
(probe: diamond s->{a,b}->t gave fnx [s,a,t] vs nx [s,b,t]).
Bidirectional shortest path (unweighted BFS from both ends).
Matches networkx.bidirectional_shortest_path(G, source, target).
br-r37-c1-k4wsy: nx-faithful bidirectional BFS with discovery
metadata. Mirrors networkx _bidirectional_pred_succ LINE BY LINE:
per-round expansion of the smaller fringe (forward over succ/adj
rows, reverse over pred/adj rows, row order), pred/succ
membership checks in nx’s exact sequence (the meet check runs for
EVERY scanned w, even already-visited ones), early return mid-level.
Returns the nx path as (node, parent_used_for_display, from_reverse)
triples: endpoints have parent None; the meet node records the
RETURNING iteration’s v (which can differ from its stored parent).
Return maximal cliques of a chordal graph.
A graph is chordal if every cycle of length > 3 has a chord.
Uses perfect elimination ordering to find maximal cliques efficiently.
The complement G’ has the same nodes as G but has edges where G does not
(and vice versa). Self-loops are not included.
Matches networkx.complement(G).
Like complement but returns just the list of new (u, v) edge
pairs (in canonical insertion order) without materializing a
fresh Graph. Lets the PyO3 binding skip a duplicate insertion
pass: previously the binding called this fn, walked the result
graph’s edges, and re-inserted each into a PyGraph — twice the
per-edge runtime_policy.record overhead, which dominates for
dense complements (BA500: 130 ms in nx, ~860 ms in fnx).
BFS that returns components as Vec<&str> borrowed from the
input graph — skips the final String::to_owned pass that the
public connected_components API performs to wrap the result in
owned Strings. Useful when the consumer only needs to read the
names (e.g., emit them across the PyO3 boundary) and would
otherwise pay an unnecessary ~|V| allocation pass per call.
br-r37-c1-d7etr: directed degree assortativity for the default (x="out", y="in") contract. nx pairs (out_degree(src), in_degree(tgt)) per DIRECTED
edge (a single pair per edge, NOT both orientations) and runs the same
Pearson over those pairs. Integer successor-CSR walk + precomputed out/in
degree vecs; the five running sums are exact f64 for any realistic graph, so
the result is byte-stable regardless of edge order and matches nx’s
mixing-matrix numeric_ac to f64 tolerance (nx normalises the matrix first,
so the two paths differ only at ULP — same situation as the undirected
kernel). Degenerate inputs (no variance in either column) yield NaN via the
zero denominator, matching nx’s invalid value divide.
networkx’s _directed_triangles_and_degree_iter(G, nodes) for the node
positions nodes, in that order: with ipreds = set(G._pred[v]) - {v}
and isuccs = set(G._succ[v]) - {v}, the total degree
len(ipreds) + len(isuccs), the reciprocal degree len(ipreds & isuccs),
and the directed triangle count - over j in chain(ipreds, isuccs) (a
reciprocal neighbour twice), the four intersections of ipreds / isuccs
with j’s own predecessors and successors less j. All three are exact
integers, so clustering‘s division follows bit for bit, and each node
costs O(its neighbours’ degrees) (br-r37-c1-0g2tj follow-up: the Python
snapshot this replaces ran 0.70-0.85x networkx for a few nodes).
networkx’s edge_betweenness_centrality(G, k=..., normalized=..., weight=...): sources is the sample networkx drew (in its order) or
None for every node; weight_attrNone is the unweighted BFS kernel.
Find edge-disjoint paths between source and target: networkx’s
edge_disjoint_paths with its default flow function, path for path and
in its order (see DisjointPathsError for when there are none).
Enumerate all cliques (not just maximal) in a graph.
Returns all cliques starting from size 1 up.
Index-space core of enumerate_all_cliques (br-r37-c1-eaclidx). Returns the
cliques as node-INDEX vectors. The algorithm was already index-native; this
just stops materializing a String per clique-node (every node appears in
many cliques, so the binding resolves each Python object once and reuses it).
Approximate the Fiedler vector of an unweighted simple graph with a native
safe-Rust Lanczos/Ritz solve on the subspace orthogonal to the all-ones
vector. Returns None when residual checks do not prove a valid Fiedler
vector, letting the Python wrapper fall back to its exact dense path.
Find a cycle in the directed graph. Returns Some(cycle) where cycle is a
list of nodes forming the cycle, or None if the graph is acyclic.
Uses DFS-based cycle detection.
Find a negative cycle in a weighted graph using Bellman-Ford.
Returns Some(cycle) if a negative-weight cycle exists, None otherwise.
Matches networkx.find_negative_cycle(G, source, weight).
br-r37-c1-gdsub (cc): generalized-degree triangle-multiplicity distribution for a
SUBSET of nodes. generalized_degree(G, nodes=<list>) previously ran the Python
_triangles_and_degree_iter_local neighbor-intersection loop (0.76-0.81x vs nx); the
per-node kernel here is lazy (graph.neighbors per node, no whole-graph setup), so
restricting it to targets is O(|S|*deg^2). Byte-identical to the all-node path (same
per-node body) — the caller gates on number_of_selfloops(G) == 0 because this kernel
counts a self-loop as a neighbour (nx excludes them), matching the nodes=None gate.
True iff every present value at weight_attr is an integer variant (missing
keys default to int 1, so they do not break the all-int property). Mirrors
the Python _sp_edge_weights_all_int gate, replacing its O(E) EdgeView scan.
Return true if any edge in graph carries a finite negative
value at weight_attr. Missing or non-finite values are skipped
(treated as the unweighted default).
Return true if any edge in graph carries a value at
weight_attr that is non-numeric (can’t be converted to f64) or
non-finite (NaN / ±∞). Used by the Python pagerank dispatcher
(br-r37-c1-s0tno) to decide whether to delegate to nx — pagerank
power iteration over signed/non-finite transition matrices is
numerically unstable, so the dispatcher needs a fast O(|E|) Rust
scan instead of the previous Python edge iteration.
Greedy modularity communities (Clauset-Newman-Moore), as networkx’s
greedy_modularity_communities(G, weight=weight_attr, resolution=resolution) with the
default cutoff and best_n, over networkx_greedy_modularity_merges: node labels
break ties, and the communities come in networkx’s order (largest first, equal sizes
in node order), each with its members sorted.
Compute immediate dominators for all nodes reachable from start.
Uses the Cooper-Harvey-Kennedy algorithm (iterative).
Returns a map from node -> its immediate dominator.
Check if a directed graph is aperiodic.
A strongly connected digraph is aperiodic if the GCD of all cycle lengths is 1.
A general digraph is aperiodic if every strongly connected component is aperiodic.
Return True if the directed graph is an arborescence (a directed rooted tree
where every node except the root has in-degree 1, and the root has in-degree 0).
Check if a graph is distance-regular.
A connected graph is distance-regular if for any two vertices u, v at distance d,
the numbers of neighbors of v at distances d-1, d, d+1 from u depend only on d.
Return whether the graph has no nodes.
Matches networkx.is_empty(G) — note: NetworkX considers a graph “empty”
if it has no edges, but we follow the function signature which checks edges.
Check if a sequence is multigraphical (can be degree sequence of a multigraph).
A sequence is multigraphical iff its sum is even and max degree <= sum of remaining.
Check if a sequence is pseudographical (can be degree sequence of a pseudograph).
A pseudograph allows self-loops. A sequence is pseudographical iff its sum is even.
Return True if the directed graph is semiconnected.
A digraph is semiconnected if for every pair u,v there is a path u->v or v->u.
Matches networkx.is_semiconnected(G).
load_centrality_normalized with networkx’s tie order: value_rank[v]
is v’s position in sorted(G.nodes()), which Rust alone cannot know.
Without it, nodes at one distance go in BFS order - equal to networkx
only up to the last bit.
Local reaching centrality for a given node.
C_L(v) = (|R(v)| / (n - 1)) where R(v) is the set of nodes reachable from v.
Matches networkx.local_reaching_centrality(G, v).
networkx’s louvain_communities with an int seed (random.Random(seed)),
or none: then the nodes are visited unshuffled, which no networkx call
does - a caller matching networkx passes a seed or uses
louvain_communities_with_rng. sum is the sum() of the CPython
networkx would run on. None where networkx must run instead (see
louvain_run).
louvain_communities shuffling with the caller’s generator - a Python
random.Random’s state, which the caller writes back so later draws
continue where networkx’s would.
louvain_communities(G, ...) as the moves of each level networkx yields
(see LouvainLevels::moves), with the graph’s node names in position
order - what a caller needs to rebuild networkx’s sets, iteration order
included, by replaying networkx’s bookkeeping (br-r37-c1-ygt3z). rng as
for louvain_communities_with_rng; None where LouvainLevels::new
declines.
Find the maximum weight clique.
Uses a branch-and-bound approach. Each node’s weight comes from the given attribute
(default 1.0 if not present).
Returns (clique_nodes, total_weight).
br-r37-c1-m0cj7: networkx’s multi_source_dijkstra in index space - the
sources (positions) all start at distance 0 in the order given, the search
stops once target settles, and a node past cutoff is never relaxed.
(node, distance, all_int, predecessor) in settle order, networkx’s dict
order; a source’s predecessor is u32::MAX. State and rows cost what the
search reaches - the String-named kernel this replaces for the binding
allocated for the whole graph (87 us beside a 32k ring for a cutoff=2 query
networkx answers in 4.5 us).
br-r37-c1-2z0mw (cc): multi-source Dijkstra returning, for each reachable node, the
SOURCE (center) on its shortest path — i.e. path[0] of multi_source_dijkstra —
WITHOUT building any paths. voronoi_cells only needs this mapping; propagating the
source label (source[v] = source[u] on each relaxation, exactly where the path
kernel does path[v] = path[u] + [v]) and skipping the all-paths String construction
is the fix. Emitted in finalize (distance, push-seq) order — identical to the path
kernel’s key order — so {node: source} is byte-identical to {v: paths[v][0]}.
networkx 3.6’s max_weight_matching (van Rantwijk’s blossom algorithm as
networkx adapts it), step for step, over vertices 0..adjacency.len() in
list(G) order; adjacency[v] is (w, weight) in G.neighbors(v) order,
self-loops included (networkx skips them). Returns networkx’s mate dict
items in insertion order, which matching_dict_to_set turns into the
result, so the matching AND each pair’s direction match networkx: every
choice it makes by iteration order is made in the same order here (the
LIFO queue, leaves(), the dict orders of blossomparent,
blossomdual, mate and each new blossom’s best edges, the first
minimum on ties). Weights are f64, which equals networkx’s arithmetic for
floats and for integers f64 represents exactly.
Return the set of nodes on the boundary of nbunch.
The node boundary is the set of nodes outside nbunch that have
a neighbor in nbunch. If nbunch2 is given, only nodes in nbunch2
are considered for the boundary.
Find node-disjoint paths between source and target: networkx’s
node_disjoint_paths with its default flow function, path for path and
in its order. As networkx’s, source == target is a query (for the
cycles through the node), not an error.
Build the planar embedding (per-node clockwise neighbour orders) for a
planar graph, mirroring networkx/algorithms/planarity.py’s embedding
phases exactly: sign(e) resolves each edge’s absolute side through the
ref/side chains, the oriented adjacency lists are re-sorted by the
signed nesting depth, the initial ccw chain is laid down per node, and
dfs_embedding then places tree half-edges first and back edges per the
resolved side (rc-planar-embedding-kernel-07rh8, milestone 1). Returns
None for non-planar graphs.
Return the predecessor dictionary from BFS.
Matches networkx.predecessor(G, source, target=None, cutoff=None).
Each node maps to the list of predecessors on shortest paths from source.
Byte-exact Prim MST edge enumeration matching networkx’s
prim_mst_edges yield order + (parent, child) orientation, returning node
INDEX pairs. nx selects each component’s start node with set(G).pop() — a
CPython set iteration order that cannot be reproduced in safe Rust — so the
caller passes the full pop sequence in start_order (indices); the kernel
starts each unvisited node in that order. Neighbours are pushed in
neighbors_indices (adjacency-insertion) order, identical to nx’s
G.adj[u], so the global seq tie-break reproduces nx exactly. Returns
None when a NaN weight is hit with ignore_nan = false (the caller then
delegates so nx raises its exact ValueError).
Eigenvalues of a real general dense row-major matrix via safe-Rust
Hessenberg reduction plus implicit double-shift QR. This is a private
no-BLAS/no-LAPACK prototype for adjacency_spectrum; callers must still
prove the raw public solver order before routing public APIs to it.
br-r37-c1-svsam: run search and return, beside its result, the position
of every node whose weighted adjacency row it expanded (repeats included),
or None when it wanted more than limit rows - the search is then cut
off at that point and its result is meaningless.
Single-source Dijkstra metadata in index space for direct Python emission:
the finalize order and predecessor chain of single_source_dijkstra_full
without materializing every path as Vec<String> inside the algorithm crate.
weighted sp batch: distances WITH the finalizing predecessor — lets
the binding map nx’s discovery objects (a node displays as its
predecessor’s row object) without a second dijkstra.
Index-space core of single_source_shortest_path_directed (br-r37-c1-ssspdiridx).
Directed mirror of single_source_shortest_path_index: BFS over successors_indices,
each discovered node recording the POSITION of its discovering parent in the discovery
vector, so paths are reconstructed by index arithmetic over a vector sized to the reach
rather than to the graph (br-r37-c1-dkwy7). Returns (target_idx, path_indices) pairs in
BFS discovery order.
Index-space core of single_source_shortest_path (br-r37-c1-ssspidx).
Returns (target_idx, path_indices) pairs in BFS discovery order; the binding
maps the indices to Python node objects, skipping the per-path-node String
materialization (O(|V|·depth) allocations) the String wrapper does for Rust
callers.
br-r37-c1-6hpa9: BFS lengths WITH the discovering parent — lets the
Python bindings reproduce nx’s discovery-object semantics (each
node’s display object is its parent’s adjacency-row object) without
a second walk. Parent is None for the source.
br-r37-c1-sqclsub (cc): square-clustering (squares, potential) pairs for a
SUBSET of node indices, aligned to targets. square_clustering(G, nodes)
with an explicit node list previously ran the Python neighbor-set port
(per-node _raw_neighbors -> set() materialization, 0.5-0.66x vs nx and
growing with N). Byte-identical to the all-node path (same arithmetic, same
order).
Ascending eigenvalues of a real symmetric n×n row-major matrix via a
100% safe-Rust Householder→implicit-shift-QL pipeline (no C BLAS/LAPACK).
The behavioural analogue of numpy.linalg.eigvalsh for symmetric input.
Returns None on a dimension mismatch or non-convergence so callers can
fall back to the reference path.
Kahn’s generations of digraph up to the first boundary with no
zero-in-degree node, and the state networkx’s lazy loop needs to resume
at any boundary. See TopologicalGenerationsTrace.
networkx’s _triangles_and_degree_iter(G, nodes) for the node positions
nodes, in that order: each node’s degree without its self-loop and
sum(len(vs & (set(G[w]) - {w})) for w in vs) - the triangle count
DOUBLED - for vs = set(G[v]) - {v}. Both are exact integers, so
clustering‘s t / (d * (d - 1)) and triangles’ t // 2 follow
bit for bit. Each node costs O(its neighbours’ degrees) - no O(|V|) work,
which is what a small nodes= request needs (br-r37-c1-mub4s).
Weighted Wiener index for directed graphs: sum of shortest-path
distances over all ordered pairs (u, v) with u != v, summed
via Dijkstra. Returns f64::INFINITY if the digraph is not
strongly connected (some pair is unreachable).
One move networkx’s _one_level makes: (node, from, to) - the level
graph’s node position and the community indices it leaves and joins, which
are positions in the level’s node order too (networkx’s node2com starts
each node in its own community).