Struct Graph 

pub struct Graph { /* private fields */ }

Implementations

impl Graph

pub fn new(mode: CompatibilityMode) -> Self

pub fn with_runtime_policy(runtime_policy: RuntimePolicy) -> Self

pub fn clear_edges(&mut self)

br-r37-c1-clearedgesinplace (cc): drop all edges in place, keeping nodes (and their index/order/attrs). O(E) teardown + O(V) row clears – the binding’s prior path rebuilt a fresh Graph with a per-node add_node loop (ledger record_decision tax + node-attr clone + old-inner drop), ~20x slower than nx. Sibling of MultiGraph::clear_edges. adj_indices keeps its N rows (one per node), emptied; the revision bump invalidates all_int_cache.

pub fn strict() -> Self

pub fn complete_graph(mode: CompatibilityMode, n: usize) -> Self

pub fn grid_2d(mode: CompatibilityMode, m: usize, n: usize) -> Self

Build a non-periodic 2-D grid with NetworkX’s node and edge insertion sequence. Canonical node keys are row-major all-int tuple strings like “(i, j)”.

pub fn grid_nd( mode: CompatibilityMode, dimensions: &[usize], periodic: &[bool], ) -> Result<Self, GraphError>

Build NetworkX’s n-dimensional integer grid graph in one bulk pass.

NetworkX constructs this as repeated cartesian products of path/cycle graphs, then flattens the nested tuple labels. The product order matters: periodic axes use cycle edge-view order, not a simple coordinate loop.

pub fn kneser(mode: CompatibilityMode, n: usize, k: usize) -> Self

br-r37-c1-z2eaa: Kneser graph K(n, k) replicating NetworkX’s exact construction sequence. Nodes are k-subsets of 0..n as all-int-tuple canonicals “(a, b, …)” (br-r37-c1-y7m24). nx builds via add_edges_from((s, t) for s in subsets for t in combinations(universe - set(s), k)) — node order is edge-DISCOVERY order (u then v per new edge) and each unordered edge is offered twice (the second add is a structural no-op). The complement universe - set(s) iterates ASCENDING whenever every value fits its exact CPython set slot — the Python wrapper gates this kernel on that condition, so lexicographic combinations over the sorted complement reproduce nx byte-for-byte. For 2k > n nodes are pre-added in subset order and no edges exist.

pub fn hardened() -> Self

pub fn mode(&self) -> CompatibilityMode

pub fn node_count(&self) -> usize

pub fn edge_count(&self) -> usize

pub fn revision(&self) -> u64

pub fn has_node(&self, node: &str) -> bool

pub fn induced_subgraph_ordered( &self, order: &[usize], runtime_policy: RuntimePolicy, ) -> Self

br-r37-c1-indsub: build the induced subgraph over order (parent node indices, already in the caller’s output order) without hashing a single node name.

The per-edge add_edge_with_attrs path costs two String allocations, four name hashes and a record_decision ledger entry (which itself allocates two Strings and a Vec) — ~2.5us/edge, so materializing the 158k-edge k=10 core of ca-AstroPh took 393ms. Everything that loop re-derives is already known here: the surviving rows come straight out of adj_indices, and the new index of a kept node is its slot in order. All the invariants add_edge_with_attrs maintains are reproduced directly:

• edges is keyed by the INDEX-canonical pair of the NEW indices;
• edge_index_endpoints keeps the STRING-canonical orientation (left <= right on names), matching the per-edge path;
• a row records its neighbor when the pair is first emitted, so adjacency order is the walk order — which is exactly what nx’s add_edges_from over the induced walk produces;
• a self-loop appears once in its row.

A pair is emitted from whichever endpoint comes FIRST in order, so each undirected edge is visited once. order must contain distinct, in-range parent indices.

pub fn has_edge(&self, left: &str, right: &str) -> bool

pub fn node_index_matches_int(&self, idx: usize) -> bool

cc-hasedgeintidx: true iff the node stored at idx IS the integer idx (its canonical string parses back to idx). Lets a caller VERIFY, per call and with no allocation, that an exact-int node lands at its own index before probing an edge by index — so any removal / re-add / remap that shifted indices simply returns false and the caller falls back to the string path. O(1) index access + a no-alloc str::parse.

pub fn has_edge_by_indices(&self, l: usize, r: usize) -> bool

cc-hasedgeintidx: undirected edge existence by node INDEX (canonical min/max pair). Caller must have validated both indices (e.g. via node_index_matches_int).

pub fn nodes_ordered(&self) -> Vec<&str>

pub fn get_node_index(&self, node: &str) -> Option<usize>

pub fn get_node_name(&self, index: usize) -> Option<&str>

pub fn neighbors(&self, node: &str) -> Option<Vec<&str>>

pub fn neighbors_iter( &self, node: &str, ) -> Option<impl Iterator<Item = &str> + '_>

pub fn neighbors_indices(&self, node_idx: usize) -> Option<&[usize]>

Return neighbor indices for O(1) traversal. Avoids string hashing during BFS/DFS. Returns None if node index is out of bounds.

pub fn clone_with_fresh_policy(&self) -> Self

br-r37-c1-7dpyg: structural clone with a FRESH RuntimePolicy — Clone deep-copies the unbounded decision ledger (copy() measured 2.3-2.8x slower on per-edge-ctor sources with identical structure); result graphs carry the MODE, not the history.

pub fn apply_row_orders(&mut self, orders: &[(String, Vec<String>)])

br-r37-c1-u3qyn: restore explicit adjacency row orders (pickle round-trip). Each entry is (node, neighbor order); rows are rebuilt in the given order with any unlisted survivors appended in their current order (robust to stale state). The integer adj_indices mirror is rebuilt to match.

pub fn reorder_rows_for_nx_copy_walk(&mut self)

br-r37-c1-0ek49: reorder every adjacency row into NetworkX’s Graph.copy() walk order. nx copy rebuilds via add_edges_from((u, v, d) for u in _adj for v in _adj[u]), so an unordered pair enters BOTH endpoint rows at its first touch — during the earlier endpoint’s row scan. Row u therefore lists neighbors at a smaller node position first (ordered by that neighbor’s scan time: (pos(v), index of u within row v)), followed by its remaining neighbors — self-loops included — in row u’s original order. Call on a fresh clone inside copy-shaped constructors; graph content is unchanged, only row order moves.

pub fn edges_storage_order_index_iter( &self, ) -> impl Iterator<Item = (usize, usize, &AttrMap)> + '_

pub fn neighbor_count(&self, node: &str) -> usize

pub fn degree(&self, node: &str) -> usize

Return the degree of a node. Self-loops contribute 2 to the degree (NetworkX convention).

pub fn degree_by_index(&self, idx: usize) -> usize

br-r37-c1-degidx: degree by node INDEX — O(1), zero String hashing (the &str path costs 2 hashes/node: neighbor_count’s get_index_of + the self-loop has_edge). Used by the DegreeView iterator which already walks nodes in index order.

pub fn node_attrs(&self, node: &str) -> Option<&AttrMap>

pub fn edge_attrs(&self, left: &str, right: &str) -> Option<&AttrMap>

pub fn edge_attrs_by_indices( &self, left_idx: usize, right_idx: usize, ) -> Option<&AttrMap>

br-r37-c1-d58s8: index-keyed attr access — a DIRECT map get for callers that already hold node indices (kernels, CSR weight builders, compose walks). Zero node-map probes.

pub fn edge_attrs_by_slot(&self, edge_slot: usize) -> Option<&AttrMap>

Read an edge’s attributes by a storage slot supplied by the row-order-preserving edge-slot cache.

pub fn with_edge_slots_by_neighbor<T>( &self, f: impl FnOnce(&[Vec<usize>]) -> T, ) -> T

Give a reader the edge-storage slot for every entry in every adjacency row. The first reader after a structural revision resolves pairs once; steady-state readers avoid pair hashing entirely.

pub fn any_edge_has_attr(&self, key: &str) -> bool

br-r37-c1-hasattrlazyfix: does ANY edge carry the attribute key in the authoritative Rust storage? Unlike the edge_py_attrs Python mirror (which is LAZILY materialized — a batch-built graph leaves it empty), this scans the inner edges AttrMaps directly (no node-name resolution, no allocation), so a freshly-constructed weighted graph reports True. ~O(E) BTreeMap key checks.

pub fn all_edge_attr_values_scalar(&self) -> bool

True if EVERY inner edge attr value is a faithful scalar (Int/Float/Bool) — a String/Map value is a coerced non-scalar (repr/JSON) or genuine str, ambiguous for lossless cloning. Direct no-alloc scan over the edge store values (contrast edges_ordered_borrowed, which builds an O(E) dedup HashMap). Used by the compose store-read gate.

pub fn any_node_has_attrs(&self) -> bool

br-r37-c1-hasanyattrlazyfix: does ANY node carry a Python-visible attr, per the authoritative inner storage (not the lazy node_py_attrs mirror)?

pub fn any_edge_has_attrs(&self) -> bool

br-r37-c1-hasanyattrlazyfix: does ANY edge carry a Python-visible attr, per the authoritative inner storage (not the lazy edge_py_attrs mirror)?

pub fn nodes_are_contiguous_int_prefix(&self) -> bool

pub fn evidence_ledger(&self) -> &EvidenceLedger

pub fn drain_decision_records(&mut self) -> Vec<DecisionRecord>

pub fn runtime_policy(&self) -> &RuntimePolicy

pub fn set_runtime_policy(&mut self, runtime_policy: RuntimePolicy)

pub fn is_directed(&self) -> bool

Type identity: always false for undirected Graph.

pub fn is_multigraph(&self) -> bool

Type identity: always false for Graph (not a multigraph).

pub fn add_node(&mut self, node: impl AsRef<str> + Into<String>) -> bool

pub fn add_node_with_attrs( &mut self, node: impl AsRef<str> + Into<String>, attrs: AttrMap, ) -> bool

pub fn extend_nodes_unrecorded<I, N>(&mut self, nodes: I) -> usize

where I: IntoIterator<Item = N>, N: Into<String>,

Bulk node insertion for generated/batched construction paths where per-node compatibility evidence would be pure constant-factor overhead.

pub fn extend_nodes_with_attrs_unrecorded<I>(&mut self, nodes: I) -> usize

where I: IntoIterator<Item = (String, AttrMap)>,

br-r37-c1-l5ve7: bulk node insert WITH attrs, one ledger record — mirror of DiGraph::extend_nodes_with_attrs_unrecorded. Existing nodes merge attrs (extend), matching add_node_with_attrs.

pub fn apply_node_defaults(&mut self, defaults: &AttrMap) -> bool

pub fn add_edge( &mut self, left: impl AsRef<str>, right: impl AsRef<str>, ) -> Result<(), GraphError>

pub fn extend_edges_unrecorded<I, L, R>(&mut self, edges: I) -> usize

where I: IntoIterator<Item = (L, R)>, L: Into<String>, R: Into<String>,

Bulk-add a sequence of attribute-free edges. Bypasses the per-edge runtime_policy.record_decision call that [add_edge_with_attrs] makes. Instead, emit one summary record for the whole batch.

Intended for fnx-internal callers that build a fresh graph from a known-good edge list (e.g., complement, transitive_closure, etc.) where the per-edge incompatibility-probability accounting would just add constant-factor overhead and is uninteresting for the policy log.

Nodes referenced by edges are auto-created if absent (matching add_edge semantics). br-r37-c1-4jd8m.

pub fn extend_existing_index_edges_unrecorded<I>(&mut self, edges: I) -> usize

where I: IntoIterator<Item = (usize, usize)>,

Bulk-add attribute-free edges whose endpoints have already been resolved to existing node indices. This is the index-space sibling of [extend_edges_unrecorded]: it preserves duplicate handling, adjacency row order, edge storage order, and string-canonical endpoint orientation without per-edge node-name allocation or map lookup.

pub fn extend_existing_index_edges_with_attrs_unrecorded<I>( &mut self, edges: I, ) -> usize

where I: IntoIterator<Item = (usize, usize, AttrMap)>,

br-r37-c1-dodattrbatch: bulk-add ATTRIBUTED edges by EXISTING node index — the attributed sibling of [extend_existing_index_edges_unrecorded]. All endpoints MUST already exist (callers gate on a contiguous-int node prefix). A new edge takes the given AttrMap; a duplicate edge MERGES (last-writer-wins per key) exactly like add_edge_with_attrs. Replaces the per-edge ledger with one batch summary; no String hashing for the endpoints (they arrive as integer indices).

pub fn extend_edges_with_attrs_unrecorded<I>(&mut self, edges: I) -> usize

where I: IntoIterator<Item = (String, String, AttrMap)>,

br-r37-c1-pr8q6: bulk-add ATTRIBUTED edges without per-edge ledger records — the attributed sibling of [extend_edges_unrecorded].

Semantics match a sequence of add_edge_with_attrs calls exactly: nodes auto-created in first-appearance order, duplicate edges MERGE their attrs into the existing map (extend), adjacency / adj_indices / edge_index_endpoints maintained identically. Only the per-edge record_decision push (timestamp + String allocs per edge, the dominant cost of attributed bulk construction) is replaced by one batch summary record.

Callers MUST pre-screen attr keys starting with "__fnx_incompatible" and route those edges through add_edge_with_attrs, which owns the FailClosed contract for them.

pub fn extend_fresh_index_edges_with_attrs_unrecorded<I, N>( &mut self, nodes: N, edges: I, ) -> usize

where I: IntoIterator<Item = (usize, usize, AttrMap)>, N: IntoIterator<Item = String>,

Bulk-add attributed undirected edges into a fresh graph when the caller has already assigned NetworkX-compatible node indices in first-seen order.

This is the fresh/indexed sibling of [extend_edges_with_attrs_unrecorded]. It preserves duplicate insert-or-merge semantics, adjacency row order, self-loop handling, and the public edges() orientation rule used by the string-key path.

pub fn add_edge_with_attrs( &mut self, left: impl AsRef<str>, right: impl AsRef<str>, attrs: AttrMap, ) -> Result<(), GraphError>

br-r37-c1-jc9e4: the endpoint keys are never owned by this function.

This used to open with let left = left.into(); let right = right.into();, then hand left.clone() / right.clone() to autocreation — up to four owned Strings per call, none of which this function keeps. Every use below is a comparison, a map probe, or a forward to add_node_with_attrs_unrecorded, and that callee now owns the key only on the vacant path. So the keys stay borrowed here and the single allocation an insert genuinely needs happens once, inside the callee, exactly when a node is created.

Comparison semantics are unchanged: left == right and left <= right on &str are the same byte-wise comparisons String performed, so the self-loop test and the edge_index_endpoints push order are identical.

pub fn apply_edge_defaults(&mut self, defaults: &AttrMap) -> bool

pub fn replace_edge_attrs( &mut self, left: &str, right: &str, attrs: AttrMap, ) -> bool

br-r37-c1-sjf4t: overwrite the attribute map for an existing edge, matching post-creation Python-side mutations. Unlike add_edge_with_attrs which extends, this replaces. Returns true if the edge existed and was updated, false otherwise.

pub fn replace_node_attrs(&mut self, node: &str, attrs: AttrMap) -> bool

br-r37-c1-sjf4t: overwrite the attribute map for an existing node.

pub fn remove_edge(&mut self, left: &str, right: &str) -> bool

pub fn remove_node(&mut self, node: &str) -> bool

pub fn remove_nodes_from<'a, I>(&mut self, nodes: I) -> (usize, usize)

where I: IntoIterator<Item = &'a str>,

pub fn edge_weights_all_int(&self, attr: &str) -> bool

Rebuild integer adjacency from string adjacency. Called after node removal since indices shift. br-r37-c1-d58s8: revision-keyed memo of “every edge’s attr value is an integer (missing = default 1 = int)”.

pub fn edges_ordered(&self) -> Vec<EdgeSnapshot>

pub fn edges_ordered_borrowed(&self) -> Vec<(&str, &str, &AttrMap)>

pub fn weighted_size_int(&self, weight: &str) -> Option<i128>

br-r37-c1-wsize (cc): integer size(weight) straight from the CgseValue store. size(weight) is sum(degree(weight))/2; the /2 exactly cancels the double-endpoint counting, so the weighted size equals each stored edge’s weight summed ONCE (a self-loop is one stored edge → counted once, matching nx’s degree-counts-it-twice-then-halves). Each edge appears once in self.edges, so a single store walk is the whole answer — no per-node PyObject degree materialization. Returns None (caller falls back to the exact float/PyObject degree path) on ANY non-integer weight value; a missing weight defaults to nx’s int 1. Integer addition is associative, so iteration order is irrelevant.

pub fn edges_ordered_indices(&self) -> Vec<(usize, usize)>

br-r37-c1-2a00r: index-space twin of edges_ordered_borrowed — yields (u, v) node indices in the SAME node-major traversed order/orientation, without resolving endpoints to &str. Lets the EdgeView iterate edges and look up the per-index Python node-key object directly (O(1) incref) instead of hashing the canonical String per endpoint via py_node_key.

pub fn edges_storage_order_borrowed(&self) -> Vec<(&str, &str, &AttrMap)>

pub fn edges_storage_order_iter( &self, ) -> impl Iterator<Item = (&str, &str, &AttrMap)> + '_

pub fn snapshot(&self) -> GraphSnapshot

Trait Implementations

impl Clone for Graph

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Graph

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.