# Weavatrix Graph
[](https://github.com/sergii-ziborov/weavatrix-graph/actions/workflows/ci.yml)
[](https://crates.io/crates/weavatrix-graph)
[](https://docs.rs/weavatrix-graph)
[](https://github.com/sergii-ziborov/weavatrix-graph/blob/main/LICENSE)
[](https://github.com/sergii-ziborov/weavatrix-graph/blob/main/Cargo.toml)
**The deterministic graph core behind Weavatrix repository intelligence.**
`weavatrix-graph` is the protocol-independent Rust library that gives
Weavatrix its typed, evidence-carrying repository graph. It is also usable by
repository analyzers, architecture tools, dependency explorers, and other
applications without depending on the Weavatrix engine or MCP product.
The crate owns graph integrity and serialization. It does **not** walk files,
parse programming languages, execute commands, access the network, or provide
an MCP/CLI transport.
## Properties
- typed nodes and edges with custom extension kinds;
- strongly typed, non-empty node identifiers;
- source spans, optional language labels, evidence kind, confidence, and extractor
provenance;
- structured node and edge attributes for parser-specific metadata;
- deterministic node and edge order independent of insertion order;
- compact numeric endpoints with incoming and outgoing CSR indexes;
- an optional direct-neighbor traversal cache with automatic, fast, bit-packed,
and succinct layouts, reusable eager/lazy walks, and no new dependency;
- a mutable insertion-order graph with generation-stable node and edge keys;
- allocation-reusing lazy BFS, DFS, and generic Dijkstra iterators, early
stopping, DFS events, and reusable workspaces;
- generic checked integer and finite floating-point path costs through the
`Measure` trait;
- BFS, DFS, reachability, unweighted shortest paths, Dijkstra, A*, signed
Bellman-Ford, filtered SCC, weak components, condensation DAGs, cycle
discovery, topological sort, MST, and Dinic maximum flow;
- standard `PageRank` with dangling-mass redistribution, control-flow dominators,
dominance frontiers, deterministic DAG longest paths and topological
generations, and DAG transitive reduction plus closure;
- Floyd-Warshall and Johnson all-pairs shortest paths, bounded simple and
K-shortest paths, bounded elementary circuit enumeration, undirected bridges
and articulation points, iterative vertex-biconnected edge blocks, exact
eccentricity/radius/diameter/center/periphery analytics, deterministic
multigraph-safe chain decomposition, checked weighted Stoer-Wagner global
min-cut, and label-aware graph/subgraph isomorphism;
- bidirectional Dijkstra and queue-based SPFA with checked arithmetic and
reachable-negative-cycle reporting;
- bipartite partitioning, Hopcroft-Karp maximum bipartite matching, and bounded
Bron-Kerbosch maximal-clique enumeration;
- exact general-graph maximum matching with Edmonds blossoms and deterministic
DSATUR coloring;
- deterministic Eades feedback-arc approximation and a multi-start
metric-closure Steiner-tree approximation that retains the standard
two-approximation candidate;
- degree, closeness, node/edge betweenness, Katz, eigenvector, and HITS
hub/authority centrality, plus k-core, cycle-basis, and deterministic
label-propagation community analysis;
- Edmonds-Karp, push-relabel, min-cost maximum flow, and Prim spanning forests
alongside Dinic and Kruskal;
- zero-copy reversed, edge-filtered, and induced-subgraph views, plus
complement and union operators;
- edge-kind, evidence, extractor, confidence, and caller-defined traversal
filters;
- automatic Floyd-Warshall/Johnson selection with the selected strategy exposed
to callers;
- deterministic DOT, Graph6, and `GraphML` topology interchange;
- undirected incidence CSR, a generic dense matrix, a bit-packed adjacency
matrix, and deterministic seeded graph generators;
- generic directed and undirected payload graphs alongside the
evidence-carrying model;
- optional Rayon batch traversal, shortest-path queries, Johnson APSP,
closeness, and node/edge betweenness centrality;
- a generic mutable payload graph with compact intrusive adjacency, generation
keys, mapping, compaction, and an acyclic invariant wrapper;
- a GraphMap-style keyed payload index backed by generation-stable handles, plus
a mutable undirected payload graph with O(1) intrusive incidence updates;
- `no_std + alloc` support with the default `std` feature kept for faster
hash-backed rich graph construction;
- idempotent insertion of identical nodes and edges;
- rejection of conflicting nodes, dangling edges, and invalid source spans;
- validated deserialization that cannot bypass graph invariants;
- compatibility conversion from Weavatrix's legacy `{ nodes, links }` graph;
- no unsafe code in the default or featureless `no_std` build; the opt-in
`unsafe-fast` feature is confined to audited bit-matrix and parallel-CSR
primitives;
- the default build has one runtime dependency, `serde`, while the optional
`rayon` feature is isolated from the core.
## Architecture
The crate is a layered graph core, not a monolithic graph type. Dependencies
flow from stable contracts toward specialized behavior:
| Evidence model | `attribute`, `error`, `filter`, `kind`, `model` | Typed identities, kinds, provenance, confidence, spans, attributes, and validation errors |
| Graph views | `topology`, `undirected`, `matrix`, `view`, `operator` | Compact endpoints and the generic directed/undirected view contracts algorithms consume |
| Algorithms | `algo` | Traversal, paths, components, cuts, flow, ranking, matching, and structural analysis over views |
| Storage | `graph`, `working`, `payload`, `traversal_cache` | Canonical evidence snapshots, mutable builders, stable payload graphs, and derived traversal indexes |
| Interchange | `format`, `generator`, `legacy` | Deterministic wire formats, seeded graph construction, and compatibility conversion |
| Public facade | `lib.rs` | Stable crate-root re-exports without owning domain logic |
Module trees use one idiomatic source form: nested modules live under
`foo/mod.rs`, never beside a competing `foo.rs`. The strict
`.weavatrix/architecture.json` contract enforces a 300-line file budget,
100-line function budget, zero runtime dependency cycles, and no exception or
ratchet baseline. `tests/architecture.rs` independently guards file size,
single-form module layout, focused facades, dependency uniqueness, and wire-kind
uniqueness.
The default and `no_std` paths forbid unsafe code. The explicitly enabled
`unsafe-fast` feature remains isolated to audited matrix and CSR primitives;
it does not change the public layering or graph invariants.
## Layered graph contracts
The crate keeps storage contracts separate instead of making one graph type pay
for every feature:
| `Topology` | Immutable directed numeric graph | Preserves edge order, validates compact endpoints, builds outgoing and incoming CSR |
| `TraversalCache` | Optional derived neighbor topology | Keeps both directions and exact adjacency order; selects direct, bit-packed, or succinct storage |
| `WorkingGraph` | Fast rich mutation and incremental extraction | Preserves insertion order, validates local invariants once, uses generation-stable keys |
| `Graph` | Immutable evidence snapshot and wire format | Sorts, deduplicates, validates, and emits canonical output |
| `UndirectedTopology` | General-purpose undirected algorithms | Compact incidence CSR with parallel-edge and self-loop support |
| `DenseMatrix<T>` | Small dense graphs | Fixed-size O(1) edge lookup without sparse-graph overhead |
| `BitMatrix` | Large dense boolean relations | One bit per possible directed edge with safe O(1) lookup |
| `PayloadGraph<N, E>` | Arbitrary application payloads | Validated topology plus separately owned node and edge values |
| `StablePayloadGraph<N, E>` | Generic mutable application graph | Generation-checked stable keys, compact intrusive adjacency, payload mapping, and immutable `freeze()` |
| `KeyedPayloadGraph<K, N, E>` | Domain-key lookup and mutation | Hash-backed under `std`, deterministic tree-backed under `no_std`, stable handles for algorithms |
| `StableUndirectedPayloadGraph<N, E>` | Mutable undirected multigraph | Generation-checked node/edge keys, intrusive double-ended incidence, parallel edges, self-loops, retargeting, and compact `freeze()` |
| `AcyclicPayloadGraph<N, E>` | Mutable DAG workflows | Rejects cycle-creating inserts and edge retargeting |
`WorkingGraph::freeze()` is the explicit boundary between extraction and
publication. It returns the canonical `Graph` plus a stable-to-compact index
map. `Graph::try_from_sorted_nodes` avoids rebuilding the node-id map when an
extractor already emits unique sorted nodes, while
`Graph::try_from_sorted_parts` is the fastest fully canonical input path.
`KeyedPayloadGraph` keeps application keys out of algorithm internals: lookups
resolve to `StableNodeKey`, while its inner `StablePayloadGraph` implements the
shared graph views. `StableUndirectedPayloadGraph` implements
`IndexUndirectedGraphView` directly, so BCC, MST, matching, coloring, and other
undirected algorithms run before or after mutation without an adapter.
## Example
```rust
use weavatrix_graph::{
Confidence, Edge, EdgeKind, EvidenceKind, GraphBuilder, Node, NodeKind,
Provenance,
};
let repository = Node::new("repo:demo", "demo", NodeKind::Repository)?;
let file = Node::new("file:src/lib.rs", "src/lib.rs", NodeKind::File)?;
let mut builder = GraphBuilder::new();
builder.add_node(repository.clone())?;
builder.add_node(file.clone())?;
builder.add_edge(Edge::new(
repository.id,
file.id,
EdgeKind::Contains,
Provenance::new("example", EvidenceKind::Parsed, Confidence::High)?,
))?;
let graph = builder.build()?;
assert_eq!(graph.node_count(), 2);
assert_eq!(graph.edge_count(), 1);
# Ok::<(), weavatrix_graph::GraphError>(())
```
Algorithms use `GraphView`/`IndexGraphView`, so the same call works with a
canonical `Graph`, a numeric `Topology`, or a mutable `WorkingGraph`.
Filtering stays outside the topology and can inspect the evidence payload:
```rust
use weavatrix_graph::{
Confidence, Direction, EdgeFilter, EdgeKind, EvidenceKind, Graph,
bfs_filtered,
};
# fn inspect(graph: &Graph) -> Result<(), weavatrix_graph::GraphError> {
let Some(start) = graph.node_index("repo:demo") else {
return Ok(());
};
let filter = EdgeFilter::new()
.with_kind(EdgeKind::Contains)
.with_evidence(EvidenceKind::Parsed)
.with_minimum_confidence(Confidence::High);
let reachable = bfs_filtered(graph, start, Direction::Outgoing, |index| {
graph.edge_at(index).is_some_and(|edge| filter.matches(edge))
});
assert!(!reachable.is_empty());
# Ok(())
# }
```
Component algorithms accept the same pure edge predicate. Condensation records
the original component membership and produces a compact, deduplicated DAG:
```rust
use weavatrix_graph::{
EdgeEndpoints, NodeIndex, Topology, condensation_filtered,
strongly_connected_components_filtered,
};
let topology = Topology::try_from_edges(
3,
[(0, 1), (1, 0), (1, 2)].map(|(source, target)| {
EdgeEndpoints::new(NodeIndex::new(source), NodeIndex::new(target))
}),
)?;
let components = strongly_connected_components_filtered(
&topology,
without_back_edge,
);
let condensed = condensation_filtered(&topology, without_back_edge)?;
assert_eq!(components.len(), 3);
assert_eq!(condensed.topology().node_count(), 3);
# Ok::<(), weavatrix_graph::GraphError>(())
```
Advanced algorithms retain the same index/view contract. A* accepts an
admissible heuristic, Bellman-Ford reports checked signed overflow and reachable
negative cycles, and `PageRank` returns values in deterministic graph-node order:
```rust
use weavatrix_graph::{
EdgeEndpoints, NodeIndex, Topology, astar, dominators, page_rank,
};
let graph = Topology::try_from_edges(
4,
[(0, 1), (0, 2), (1, 3), (2, 3)].map(|(source, target)| {
EdgeEndpoints::new(NodeIndex::new(source), NodeIndex::new(target))
}),
)?;
let weights = [2_u64, 5, 2, 1];
let Some(path) = astar(
&graph,
NodeIndex::new(0),
NodeIndex::new(3),
|edge| weights[edge.index()],
|_| 0,
) else {
return Ok(());
};
assert_eq!(path.total_cost(), 4);
assert_eq!(page_rank(&graph, 0.85, 20)?.len(), 4);
assert!(dominators(&graph, NodeIndex::new(0)).is_some());
# Ok::<(), weavatrix_graph::GraphError>(())
```
All potentially exponential enumeration APIs require a caller-provided result
limit and report truncation. Isomorphism accepts node and edge predicates, so
architecture tools can match semantic kinds without coupling the graph crate to
one language model:
```rust
use weavatrix_graph::{
EdgeEndpoints, NodeIndex, SubgraphMode, Topology, johnson_all_pairs,
subgraph_isomorphisms,
};
let graph = Topology::try_from_edges(
3,
[(0, 1), (1, 2)].map(|(source, target)| {
EdgeEndpoints::new(NodeIndex::new(source), NodeIndex::new(target))
}),
)?;
&graph,
&graph,
SubgraphMode::Induced,
1,
|left, right| left == right,
|_, _| true,
);
assert_eq!(matches.mappings().len(), 1);
# Ok::<(), weavatrix_graph::GraphError>(())
```
Biconnected and chain analysis are iterative and preserve original edge IDs.
Both treat parallel edges and self-loops explicitly. Exact distance analytics
return `None` for an empty or disconnected accepted-edge graph rather than
inventing finite metrics. HITS ranks topological relationships rather than
evidence multiplicity: equal endpoint pairs are deduplicated after the semantic
edge predicate runs once per edge.
```rust
use weavatrix_graph::{
EdgeEndpoints, NodeIndex, Topology, UndirectedTopology,
biconnected_components, chain_decomposition, distance_analytics, hits,
stoer_wagner_min_cut, undirected_edge_betweenness_centrality,
};
});
let undirected = UndirectedTopology::try_from_edges(4, edges)?;
let blocks = biconnected_components(&undirected);
assert_eq!(blocks.component_count(), 2);
assert_eq!(blocks.articulation_points(), &[NodeIndex::new(1)]);
let Some(distances) = distance_analytics(&undirected) else {
return Ok(());
};
assert_eq!(distances.diameter(), 2);
assert_eq!(distances.center(), &[NodeIndex::new(1)]);
let chains = chain_decomposition(&undirected);
assert_eq!(chains.chain_count(), 1);
let edge_scores = undirected_edge_betweenness_centrality(&undirected, true);
assert_eq!(edge_scores.len(), 4);
let scores = hits(&directed, 100, 1e-10)?;
assert!(scores.hub(NodeIndex::new(1)).is_some());
# Ok::<(), weavatrix_graph::GraphError>(())
```
## P2 storage, interchange, and portability
`all_pairs_auto` snapshots every accepted edge weight once, selects
Floyd-Warshall for small or dense graphs and Johnson for sparse graphs, and
returns the chosen `AllPairsStrategy` with the result. Explicit algorithms
remain available when an application already knows the best strategy.
Interchange intentionally targets deterministic topology rather than pretending
to support every dialect:
- DOT reads and writes a strict numeric directed/undirected subset and ignores
attributes;
- Graph6 supports simple undirected graphs and rejects loops and parallel edges;
- `GraphML` preserves graph direction and node declaration order while rejecting
ports, hyperedges, and per-edge direction overrides.
All decoders validate endpoint references and rebuild the crate's canonical
topology indexes. `PayloadGraph<N, E>` and `UndirectedPayloadGraph<N, E>` attach
arbitrary payloads without weakening those topology invariants.
The crate defaults to `std`. Embedded and WASM consumers can disable default
features for a real `no_std + alloc` build:
```toml
[dependencies]
weavatrix-graph = { version = "0.6", default-features = false }
```
Parallel batches are explicit and optional:
```toml
[dependencies]
weavatrix-graph = { version = "0.6", features = ["rayon"] }
```
Large topology construction can select a measured sequential/Rayon crossover
while preserving stable edge indexes and adjacency order:
```rust
# use weavatrix_graph::{EdgeEndpoints, NodeIndex, Topology};
# let edges = [EdgeEndpoints::new(NodeIndex::new(0), NodeIndex::new(1))];
# #[cfg(feature = "rayon")]
# {
let topology = Topology::try_from_edges_auto(2, edges)?;
# assert_eq!(topology.edge_count(), 1);
# }
# Ok::<(), weavatrix_graph::GraphError>(())
```
`try_from_edges_parallel` always uses the safe stable-order Rayon builder.
`try_from_edges_parallel_unordered` keeps edge identity but leaves node-local
adjacency order unspecified. The automatic builder uses sequential construction
below 1.5 million edges, where scheduling and atomic setup usually cost more
than they save.
Traversal-heavy callers can derive a separate cache without weakening stable
edge identity or evidence storage:
```rust
# use weavatrix_graph::{
# Direction, EdgeEndpoints, NodeIndex, Topology, TraversalCacheWorkspace,
# TraversalStorage,
# };
# let topology = Topology::try_from_edges(
# 2,
# [EdgeEndpoints::new(NodeIndex::new(0), NodeIndex::new(1))],
# )?;
let cache = topology.traversal_cache(); // speed-aware Auto policy
let mut workspace = TraversalCacheWorkspace::new();
let visited = cache.bfs_with_workspace(
NodeIndex::new(0),
Direction::Outgoing,
&mut workspace,
);
assert_eq!(visited.len(), 2);
let compact = topology.traversal_cache_with(TraversalStorage::Compact);
assert_eq!(compact.edge_count(), 1);
# Ok::<(), weavatrix_graph::GraphError>(())
```
`Fast` stores direct `u32` neighbors and offsets. `Balanced` bit-packs neighbor
ids while retaining direct offsets. `Compact` adds Elias-Fano monotone offsets
and automatically uses block-local frame-of-reference neighbor packing only
when its exact encoded size beats global packing. `Auto` chooses `Balanced`
only when it saves at least 12.5%; otherwise it keeps `Fast`. All modes preserve
parallel edges, self-loops, and node-local adjacency order. `Graph` exposes the
same two convenience methods, and `From<&Topology>` / `From<&Graph>` are
available for generic construction.
`bfs_batch_parallel` and `dijkstra_batch_parallel` preserve query order and the
same deterministic result contract as their sequential counterparts. They are
intended for batches large enough to amortize scheduling, not as replacements
for a single small query.
Bit-matrix lookup has an additional, separately auditable performance feature:
```toml
[dependencies]
weavatrix-graph = { version = "0.6", features = ["unsafe-fast"] }
```
The default `BitMatrix::contains` remains fully safe. With `unsafe-fast`,
`contains_fast` keeps a safe API and validates both endpoints before one
unchecked word access. `contains_unchecked` removes endpoint checks too and is
an `unsafe fn`: callers must guarantee that both indexes are inside the matrix.
The same feature exposes `try_from_edges_parallel_fast` and its unordered
variant. Their public API remains safe; an isolated scatter backend writes
validated edge slots directly and reuses atomic cursor storage as final offsets.
Enabling the feature never silently changes the behavior of `contains`.
## Extension Kinds
Known relation and node kinds are enum variants. Ecosystem-specific kinds remain
forward-compatible through `Custom` values. Language taxonomies intentionally
belong to analyzers, not the graph core; nodes carry language as a validated
string label.
```rust
use weavatrix_graph::NodeKind;
let kind = NodeKind::custom("terraform_resource")?;
assert_eq!(kind.as_str(), "terraform_resource");
# Ok::<(), weavatrix_graph::GraphError>(())
```
## Weavatrix compatibility
The core graph format intentionally keeps canonical `nodes` and `edges`, but the
crate can ingest the current JavaScript Weavatrix `{ nodes, links }` shape:
```rust
use weavatrix_graph::{Graph, LegacyGraph};
let legacy: LegacyGraph = serde_json::from_str(r#"{
"nodes": [
{ "id": "src/lib.rs", "label": "lib.rs" },
{ "id": "src/lib.rs#entry@1", "label": "entry()" }
],
"links": [
{
"source": "src/lib.rs",
"target": "src/lib.rs#entry@1",
"relation": "contains",
"confidence": "EXTRACTED"
}
],
"edgeTypesV": 2,
"edgeProvenanceV": 1
}"#)?;
let graph: Graph = legacy.into_graph("weavatrix-js")?;
assert_eq!(graph.edge_count(), 1);
# Ok::<(), Box<dyn std::error::Error>>(())
```
Legacy metadata such as `line`, `compileOnly`, `typeOnly`, `specifier`,
`usage`, `source_range`, and unknown extension fields is preserved as structured
attributes.
## Benchmarks
The repository includes benchmark harnesses for graph construction, indexed
queries, JSON serialization, validated deserialization, and dev-only
comparisons with `petgraph 0.8.3` and `graaf 0.112.0`:
```sh
cargo bench --locked
```
Unless a section states otherwise, each workload runs two warmups and 11
measured iterations. The tables below use the median of five independent
harness medians on Windows 11 with Rust 1.97.1. They compare equal contracts
where possible and label preprocessing explicitly.
### Rich evidence construction
10,000 nodes and 30,000 evidence-carrying edges:
| Unsorted canonical snapshot | weavatrix-graph `Graph` | 40.725 ms |
| Sorted canonical snapshot | weavatrix-graph `Graph` | 23.427 ms |
| Validated mutable append | weavatrix-graph `WorkingGraph` | 35.362 ms |
| Payload append, no canonicalization | petgraph adapter | 18.372 ms |
| Mutable append plus canonical `freeze()` | weavatrix-graph | 47.199 ms |
The petgraph adapter resolves string ids and clones the same payload but does
not validate, sort, or deduplicate it. `WorkingGraph` remains slightly faster
than full canonical construction while validating local invariants.
`freeze()` is reported separately because it adds canonical sorting, evidence
deduplication, and immutable CSR construction. At repository scale the sorted
canonical implementation amortizes those guarantees and moves ahead of the
narrower adapter; see the 200,000 / 1,000,000 table below.
### Compact dual CSR
10,000 numeric nodes and 30,000 edges:
| Arbitrary input, endpoint validation, both CSR directions | weavatrix-graph | 0.365 ms |
| Two CSR builds from caller-provided pre-sorted directions | petgraph | 0.463 ms |
| Sorting/dedup plus both CSR builds | petgraph | 1.699 ms |
The pre-sorted petgraph row deliberately excludes preparing two differently
sorted edge arrays. It is retained because that narrower contract can be useful
when a caller already owns both orders.
### Algorithms
10,000 nodes and 30,000 edges, except maximum flow at 1,000/5,000:
| BFS | 0.107 ms | 0.157 ms |
| Strongly connected components | 0.474 ms | 0.650 ms |
| Dijkstra to one target | 0.913 ms | 0.960 ms |
| Minimum spanning forest | 1.288 ms | 1.856 ms |
| Dinic maximum flow | 0.322 ms | 0.379 ms |
Deterministic randomized differential tests also compare reachability, shortest
path existence and cost, SCC partitions, cycle status, topological feasibility,
MST weight, and maximum-flow value against petgraph.
### Repository scale: 200,000 nodes and 1,000,000 edges
`scale_graph_competitors` models files as nodes and deterministic dependency
relations as directed edges. Each independent process performs one warmup and
five measured iterations; the table is the median of five process medians.
Every process asserts exact node and edge counts, equal reachable counts, equal
SCC partitions, and the same target distance before reporting timings.
| Dual CSR from arbitrary unique endpoints | 14.391 ms | petgraph adapter 78.735 ms | 5.47x faster |
| Narrow baseline: both directions pre-sorted for petgraph | 14.391 ms | petgraph 12.895 ms | petgraph 11.6% faster |
| Mutable append, no reverse CSR or canonicalization | — | petgraph 9.934 ms / graaf 30.969 ms | narrower contract |
| BFS, materialized reachable nodes | 13.026 ms | petgraph 49.606 ms / graaf 34.896 ms | 3.81x / 2.68x faster |
| Strongly connected components | 92.304 ms | petgraph 316.340 ms | 3.43x faster |
| Dijkstra to one target | 69.190 ms | petgraph 102.050 ms | 1.47x faster |
| Rich evidence snapshot from sorted owned payloads | 623.691 ms | petgraph adapter 644.840 ms | 3.4% faster |
The generated workload contains no duplicate endpoint pair. Weavatrix validates
the arbitrary endpoints and builds both directions by linear counting placement
while retaining stable original edge indexes and support for parallel edges.
The equal-input petgraph adapter must produce, sort, and deduplicate two edge
orders for its simple CSR contract. Its pre-sorted row receives both orders
already prepared and therefore measures a deliberately narrower input
contract. Mutable append is shown only as a lower-bound reference because it
does not build an immutable dual-CSR snapshot.
The rich adapter resolves the same string ids and moves the same node/edge
payloads, but does not validate payloads, check canonical ordering, deduplicate
evidence, or build reverse CSR. The 6.2% construction premium is therefore the
remaining scale tradeoff for the stronger snapshot contract, not an
algorithmic correctness gap.
Median peak working set from three fresh processes, including input generation,
temporary construction storage, allocator high-water state, and the live
result:
| Compact dual CSR | 37.9 MiB | petgraph dual CSR 68.5 MiB |
| Mutable adjacency | — | petgraph 44.9 MiB / graaf 47.5 MiB |
| Rich evidence graph, ownership transferred | 377.1 MiB | petgraph adapter 585.8 MiB |
Peak working set is a capacity-planning number, not the retained deep size of
the graph. Reproduce the scale run with:
```sh
cargo bench --locked --all-features --bench scale_graph_competitors
```
### Parallel construction at 1M, 10M, and 100M edges
This follow-up compares parallel with parallel. It ran locally on Windows 11,
Rust 1.97.1, and an Intel Core Ultra 7 255U with 14 Rayon workers. The
deterministic input has five outgoing edges per node. The 1M and 10M rows are
medians of nine and seven measured builds; 100M is a three-build median after
one warmup.
| 200k / 1M, auto stable | 14.165 ms | 15.223 ms | Weavatrix 7.5% faster |
| 2M / 10M, safe stable | 178.705 ms | 115.697 ms | narrower competitor 35.3% faster |
| 2M / 10M, `unsafe-fast` stable | 117.888 ms | 115.697 ms | within 1.9% |
| 20M / 100M, `unsafe-fast` stable | 1.705 s | 1.518 s | narrower competitor 12.3% faster |
| 20M / 100M, `unsafe-fast` unordered | 1.662 s | 1.518 s | narrower competitor 9.5% faster |
Both sides ingest arbitrary endpoint order, validate or infer bounds, and build
incoming plus outgoing CSR. The contracts are not identical:
`weavatrix-graph::Topology` also retains the original endpoint array, stable
`EdgeIndex` identity, parallel-edge identity, and, in stable modes,
deterministic node-local edge order. `graph_builder` stores direct neighbor
targets and uses internal unchecked scatter writes. Its row is a throughput
lower bound, not evidence that the stronger snapshot is incorrect. Every
Weavatrix stable build is asserted equal to the sequential topology before
timing.
The original evidence topology exposes the cost of resolving an `EdgeIndex`
through the endpoint array:
| 200k / 1M | 10.179 ms | 6.902 ms | direct neighbors 1.47x faster |
| 2M / 10M | 102.811 ms | 75.804 ms | direct neighbors 1.36x faster |
Both adapters assert the same reachable count. The derived `TraversalCache`
closes that gap without changing `Topology`. An interleaved, allocation-reusing
BFS comparison on the same five-outgoing-edge workload measured:
| 200k / 1M | Fast | 9.60 MB | 17.131 ms | 17.636 ms | 2.9% faster |
| 200k / 1M | Balanced | 6.10 MB | 28.104 ms | 18.197 ms | 36.5% less memory, slower traversal |
| 200k / 1M | Compact | 4.55 MB | 76.027 ms | 18.592 ms | 52.6% less memory, smallest layout |
| 2M / 10M | Fast | 96.00 MB | 345.978 ms | 394.968 ms | 12.4% faster |
| 2M / 10M | Balanced | 68.50 MB | 464.830 ms | 322.858 ms | 28.6% less memory |
| 2M / 10M | Compact | 48.78 MB | 1,251.840 ms | 415.216 ms | 49.2% less memory |
The times are medians of nine runs at 1M edges and five runs at 10M, with the
measurement order alternated every run. Cache and competitor return the same
reachable count; both reuse traversal marks and queue storage. The compressed
layouts are explicit space/latency choices, not claims that bit decoding is
free. At 20M nodes / 100M edges the measured encoded sizes were 960.00 MB
(`Fast`), 785.00 MB (`Balanced`), and 536.76 MB (`Compact`). On adjacency with
local ids, Compact can reduce this further through block-local frames while
preserving the original order.
On the equal all-pairs output contract, parallel Johnson measured 41.638 ms
here versus petgraph's 64.769 ms, 1.56x faster.
The real-filesystem harness scanned `C:\Windows` with `weavatrix-scan 0.3.0`,
then built a parent-child containment graph. The scan returned 192,575 files,
240,734 nodes, 240,733 edges, and 51 warnings (`complete=false`) in 1.904 s.
Scanning is outside the graph-build interval:
| Weavatrix auto stable | 3.469 ms |
| Weavatrix forced Rayon stable | 6.782 ms |
| `graph_builder` Rayon, narrower contract | 5.653 ms |
The real graph confirms why automatic selection matters: sequential construction
is 38.6% faster than the narrower parallel competitor at this size. Reproduce
the synthetic and filesystem runs with:
```powershell
cargo bench --locked --all-features --bench parallel_scale_competitors
cargo bench --locked --all-features --bench traversal_cache_competitors
$env:WEAVATRIX_GRAPH_NODES=20000000
$env:WEAVATRIX_GRAPH_EDGES=100000000
$env:WEAVATRIX_GRAPH_RUNS=3
$env:WEAVATRIX_GRAPH_MODE="fast"
cargo bench --locked --all-features --bench parallel_scale_competitors
$env:WEAVATRIX_REAL_ROOT="C:\Windows"
cargo bench --locked --all-features --bench filesystem_graph_workload
```
### Advanced algorithms
The A*, dominator, and DAG-intelligence workloads use 10,000 nodes / 30,000
edges. Bellman-Ford uses a 1,000-node / 5,000-edge signed DAG, `PageRank` uses
500 nodes / 2,000 unique edges and 20 iterations, and DAG reduction/closure
uses 512 nodes / 3,000 edges. Values are the median of five independent harness
medians:
| A*, zero heuristic, cost and path | 1.130 ms | 1.495 ms | 1.32x faster |
| Bellman-Ford, distances and predecessors | 0.057 ms | 0.033 ms | 1.73x slower |
| `PageRank`, 20 iterations | 0.071 ms | 12.892 ms | 181.58x faster |
| Immediate dominators | 2.161 ms | 3.163 ms | 1.46x faster |
| Maximum-cost DAG path | 0.496 ms | 0.628 ms adapter | 1.27x faster |
| Topological generations | 0.655 ms | 0.804 ms adapter | 1.23x faster |
| Dominance frontiers | 4.081 ms | 6.151 ms adapter | 1.51x faster |
| DAG transitive reduction and closure | 0.684 ms | 1.051 ms | 1.54x faster |
The DAG row includes `petgraph`'s required conversion to a topologically ordered
adjacency list; `weavatrix-graph` accepts the original graph, validates
acyclicity, and returns deterministic node endpoints. The `PageRank` workload has
no parallel edges; our implementation is O(V + E) per iteration and follows
the standard teleport plus uniform dangling-mass contract. Its correctness is
checked against an independent reference because `petgraph 0.8.3` uses a
different transition formula.
The Bellman-Ford row is intentionally retained as a known tradeoff, not hidden:
our operation snapshots the filtered signed weights once, uses checked `i64`
addition, distinguishes unreachable nodes without an infinity sentinel, and
returns overflow or reachable-negative-cycle errors. `petgraph` uses `f64`
distances and does not provide integer overflow semantics. Randomized
differential tests cover A* costs, Bellman-Ford distances and negative-cycle
status, immediate dominators, longest-path costs, topological generation
invariants, dominance-frontier memberships, and exact transitive
reduction/closure edges. Petgraph does not expose the three DAG-intelligence
operations directly; those rows use equal-output adapters over its graph,
topological-sort, and immediate-dominator APIs.
### P0 all-pairs, cuts, and isomorphism
Local Windows release-mode sample from 2026-07-24, with two warmups and the
median of 11 measured runs over deterministic synthetic graphs:
| Floyd-Warshall APSP | 160 nodes / 1,200 weighted edges | 2.874 ms | 3.319 ms |
| Johnson APSP | 800 nodes / 4,000 weighted edges | 52.636 ms | 67.018 ms |
| Bridges plus articulation points | 5,000 nodes / 15,000 edges | 0.362 ms | 0.302 ms bridges only |
| Exact directed isomorphism | 64 nodes / 300 edges | 0.100 ms | 0.031 ms |
The cuts row is deliberately marked as a different contract rather than a speed
win: our traversal returns both cut-edge and cut-vertex evidence. Isomorphism is
a known optimization gap. Randomized differential tests compare APSP distances,
bridges, articulation points, and exact isomorphism against `petgraph 0.8.3`.
Integer Floyd-Warshall additionally preserves unreachable pairs as `None`
instead of allowing a negative edge to modify an infinity sentinel.
### Biconnected structure and HITS
Biconnected components use 2,000 nodes / 6,000 simple undirected edges. HITS
uses 10,000 nodes / 30,000 unique directed relationships, an iteration cap of
100, and tolerance `1e-10`. Values are the median of five independent harness
medians:
| Biconnected edge blocks plus articulation points | 0.225 ms | equal-output adapter 0.257 ms | 1.14x faster |
| HITS hubs and authorities, L2 normalized | 7.704 ms | petgraph equal-equation adapter 7.950 ms | 1.03x faster |
The direct BCC competitor uses recursive Hopcroft-Tarjan traversal and
overflowed the Windows stack on the 10,000 / 30,000 benchmark input. The
Weavatrix traversal is iterative; its regression suite includes a 200,000-node
chain. Its raw node-block-only lower bound is 0.157 ms, but adding original
edge blocks and articulation points raises it to 0.257 ms. The table compares
that equal output instead of presenting the narrower operation as equivalent.
Petgraph does not expose HITS directly, so that row uses an equal-equation
adapter over its graph storage, including endpoint deduplication, L2
normalization, convergence checks, and the same cap. Seeded dense-matrix
references check both score vectors.
### Keyed and stable undirected mutation
The keyed build uses 10,000 domain keys / 30,000 directed edges. Stable
undirected construction uses the same size; the churn row removes and reinserts
1,000 edges with cloning/setup outside the timed interval:
| Keyed directed build | 0.650 ms | `GraphMap` 3.788 ms | 5.83x faster |
| Stable undirected build | 0.557 ms | `StableUnGraph` 0.230 ms | petgraph 2.42x faster |
| Stable undirected 1,000 remove + 1,000 insert | 0.169 ms | `StableUnGraph` 0.018 ms | petgraph 9.39x faster |
The keyed row is conservative for Weavatrix: it also stores independent node
payloads and returns generation-stable handles. The stable rows document a
deliberate safety cost rather than hiding it: Weavatrix detects stale node and
edge keys after slot reuse, while petgraph stable indexes can alias a reused
slot. Both Weavatrix operations use intrusive incidence and perform no
per-node heap allocation.
### Distance analytics and chain decomposition
Distance analytics use 1,500 nodes / 4,500 connected undirected edges. Chain
decomposition uses 20,000 nodes / 60,000 simple undirected edges. Values are the
median of five independent harness medians; every harness performs two warmups
and 11 measured runs:
| Eccentricity, radius, diameter, center, and periphery | 30.890 ms | petgraph equal-output adapter 61.343 ms | 1.99x faster |
| Chain decomposition | 5.958 ms | `rustworkx-core 0.18.0` 10.797 ms | 1.81x faster |
The distance fast path builds compact neighbor CSR once, then reuses
epoch-stamped BFS storage for every source. The petgraph adapter computes the
same five outputs, reuses its queue and distance vector, and rejects
disconnected graphs under the same contract.
The chain row calls rustworkx-core directly and compares the exact non-bridge
endpoint set and chain count. Weavatrix additionally returns original edge IDs
and has defined behavior for parallel edges and self-loops; rustworkx documents
those inputs as unsupported. Seeded differential tests cover simple graphs, an
independent edge-removal reference checks exact non-bridge coverage, and a
200,000-node chain protects the iterative stack-safety contract.
### Edge betweenness and global min-cut
Edge betweenness uses 1,200 nodes / 4,800 simple undirected edges and returns a
normalized score for every original edge. Stoer-Wagner uses 350 nodes / 1,400
weighted edges. Values are the median of five independent harness medians;
every harness performs two warmups and 11 measured runs:
| Edge betweenness, sequential | 71.367 ms | 262.602 ms | 3.68x faster |
| Edge betweenness, Rayon | 14.985 ms | 294.388 ms | 19.64x faster |
| Stoer-Wagner global min-cut | 22.644 ms | 24.012 ms | 1.06x faster |
Both edge-centrality rows call the rustworkx implementation directly and assert
every edge score before timing. The Weavatrix implementation keeps
source-local score vectors in the Rayon path and reduces them after traversal;
it also preserves parallel-edge identities, gives self-loops a defined zero
score, and evaluates semantic filters once per edge.
The min-cut row asserts the same minimum weight. Weavatrix additionally checks
negative/non-finite weights and arithmetic overflow, aggregates parallel edges,
and returns both sides in deterministic canonical order; rustworkx returns one
partition side and uses unchecked weight addition. Reproduce these rows with:
```sh
cargo bench --locked --all-features --bench edge_cut_analysis
```
### P1 matching, coloring, feedback, and Steiner
The workloads use 400 nodes / 1,400 edges for general matching, 180 / 500 for
maximal cliques, 5,000 / 15,000 for DSATUR, 10,000 / 30,000 directed edges for
feedback arc set, and 1,000 / 4,000 with 32 terminals for Steiner tree:
| Exact maximum matching, materialized pairs | 0.097 ms | 0.124 ms | 1.28x faster; 200 pairs |
| All maximal cliques | 0.164 ms | 0.368 ms | 2.24x faster; 500 cliques |
| DSATUR coloring | 3.299 ms | 3.550 ms | 1.08x faster; 5 colors |
| Eades feedback arc set | 2.375 ms | 3.431 ms | 1.44x faster; 8,216 edges |
| Multi-start metric-closure Steiner tree | 5.596 ms | 965.055 ms | 172.45x faster; cost 340 vs median 344 |
The matching adapter consumes `petgraph::Matching::edges()` into endpoint pairs
instead of timing its lazy result. Feedback returns the same set cardinality on
the benchmark and no more edges across 24 seeded differential cases. DSATUR
uses the same color count across those cases. The deterministic multi-start
Steiner result is no more expensive across 20 seeded comparisons and preserves
the standard metric-closure two-approximation candidate; the brute-force tests
also verify the bound directly on small graphs. Petgraph's Steiner cost varied
from 340 to 344 across the five benchmark processes, while the
weavatrix-graph result remained 340.
### P2 bit matrix and optional parallel batches
The bit-matrix workload performs one million deterministic adjacency lookups
over 10,000 nodes / 30,000 edges. The batch workloads run 128 BFS traversals and
64 weighted Dijkstra queries over the same dual-CSR topology. Values are the
median of five independent harness medians:
| Safe bit-matrix lookup | petgraph `FixedBitSet` 5.284 ms | `BitMatrix::contains` 5.396 ms | within 2.1% |
| Checked opt-in fast lookup | petgraph `FixedBitSet` 5.284 ms | `contains_fast` 4.804 ms | 1.10x faster |
| Caller-validated lookup | petgraph `FixedBitSet` 5.284 ms | `contains_unchecked` 3.382 ms | 1.56x faster |
| 128 BFS traversals | sequential 33.258 ms | Rayon 6.609 ms | 5.03x faster |
| 64 Dijkstra queries | sequential 39.771 ms | Rayon 8.699 ms | 4.57x faster |
| Johnson APSP, 1,200 / 6,000 | sequential 217.512 ms | Rayon 64.038 ms | 3.40x faster |
| Closeness, 1,000 / 4,000 | sequential 21.041 ms | Rayon 4.818 ms | 4.37x faster |
| Betweenness, 1,000 / 4,000 | sequential 139.065 ms | Rayon 25.033 ms | 5.56x faster |
`BitMatrix` uses exactly 12,500,000 payload bytes for the 10,000-square matrix
in every mode. The default path is fully safe and essentially at parity.
The checked opt-in path beats petgraph while retaining a safe public contract;
the caller-validated path is fastest. Unsafe code is feature-gated, isolated,
and rejected everywhere else by an architecture test. Rayon is not enabled by
default and has no effect on single-query algorithms or `no_std` builds.
### Lazy traversal, generic costs, and stable mutation
The traversal graph has 50,000 nodes and 150,000 weighted edges. Lazy BFS stops
after 128 settlements, generic Dijkstra uses `f64`, and the mutation workload
builds the same graph before removing and replacing 100 nodes. Values are the
median of five independent harness medians:
| Lazy BFS, first 128 nodes | 0.002 ms | 0.003 ms | 1.50x faster |
| Generic `f64` Dijkstra to target | 8.342 ms | 11.936 ms | 1.43x faster |
| Stable build/remove/reinsert | 2.247 ms | 2.227 ms | within 0.9% |
The mutable row is conservative: `StablePayloadGraph` also detects stale keys
after slot reuse through a generation counter. Its adjacency is an intrusive
slot list, so construction performs no per-node adjacency allocations. Filtered
views are genuinely lazy: creating an adjacency iterator does not evaluate its
predicate, and early stopping evaluates only the consumed prefix.
### Filtered components and condensation
10,000 nodes and 30,000 edges. Each measured sample batches 64 operations; the
table is the median of five independent harness medians:
| Filtered SCC memberships | 0.899 ms | 1.353 ms |
| Filtered topological order | 0.080 ms | 0.427 ms |
| Weak component memberships | 0.206 ms | 0.208 ms |
| Condensation DAG and memberships | 0.821 ms | 2.385 ms |
The petgraph filtered rows use `EdgeFiltered` rather than rebuilding a graph.
Both weak-component rows return complete deterministic memberships, not only a
component count. Condensation consumes the petgraph input, so input clones are
prepared outside the timed interval. Randomized differential tests compare
exact SCC and weak-component partitions plus canonical condensation edges.
Incoming and outgoing indexes are rebuilt during graph construction and
deserialization. They are intentionally excluded from JSON, so the canonical
wire format remains only `nodes` and `edges`. Resolve a stable string id once
with `node_index`, then use `node_at`, `outgoing_at`, `incoming_at`,
`out_degree`, and `in_degree` in repeated graph algorithms.
Extractors that already emit sorted nodes can use
`Graph::try_from_sorted_nodes`; fully canonical input can use
`Graph::try_from_sorted_parts`. Both keep validation, endpoint checks,
deduplication, and both indexes. Unordered input safely falls back to the
canonicalizing constructor.
`petgraph`, `graaf`, `graph_builder`, `rustworkx-core`, and `weavatrix-scan` are
dev-dependencies only. The default runtime dependency budget remains `serde`;
Rayon and its transitive dependencies appear only when the `rayon` feature is
explicitly selected.
Timing varies by allocator, CPU, and build toolchain. Run the included harnesses
on the deployment target before using these figures for capacity planning.
## Quality Gates
Local checks:
```sh
cargo fmt --check
cargo test --all-features --locked
cargo clippy --locked --all-targets --all-features -- -D warnings
cargo check --no-default-features --target thumbv7em-none-eabihf --lib --locked
cargo check --no-default-features --features unsafe-fast --target thumbv7em-none-eabihf --lib --locked
cargo doc --locked --no-deps --all-features
cargo llvm-cov --workspace --all-features --fail-under-lines 85
cargo bench --all-features --locked
```
The release gates combine the test suite with strict architecture verification:
every Rust source stays at or below 300 lines, every function stays at or below
100 lines, module source forms cannot collide, domain facades remain focused,
runtime dependencies remain limited, and canonical kind strings cannot
collide. Production source contains no `.unwrap()` or `.expect()` calls:
internal graph invariants use checked conversions, fallible propagation, or
total control flow instead of process-terminating shortcuts.
CI also runs measured Rust coverage with `cargo-llvm-cov`, emits `lcov.info`
for analyzer import, and fails below 85% line coverage. It additionally runs
Linux `proptest` contracts, Miri over traversal/view/analytics/mutable storage,
and bounded libFuzzer smoke targets for topology, matrices, mutation, and
interchange formats. Weavatrix architecture verification is backed by the
strict `.weavatrix/architecture.json` contract. The current local
MSVC LLVM report measures 92.28% of lines and 88.81% of functions.
## License
MIT