```text
____ ____._____ .______ .______ ._______ .___.__
\ \_/ /:_ ___\ : __ \ : \ : ____ |: | \
\___ ___/ | |___| \____|| . || : || : |
/ _ \ | / || : \ | : || |___|| . |
/___/ \___\|. __ || |___\|___| ||___| |___| |
:/ |. ||___| |___| |___|
: :/
:
```
[](https://crates.io/crates/xgraph)
[](https://docs.rs/xgraph)
[](https://github.com/xvi-xv-xii-ix-xxii-ix-xiv/xgraph/actions/workflows/ci.yml)
[](LICENSE)
# xgraph
A graph library for Rust: directed and undirected graphs, weighted edges, parallel edges,
and arbitrary data on nodes and edges — with a full complement of algorithms that work the
same way on every one of them.
```rust
use xgraph::core::{Centrality, ShortestPath, Traversal};
use xgraph::graph::Graph;
let mut network = Graph::<u32, &str, &str>::new(false);
let oslo = network.add_node("Oslo");
let bergen = network.add_node("Bergen");
let trondheim = network.add_node("Trondheim");
network.add_edge(oslo, bergen, 500, "rail").unwrap();
network.add_edge(bergen, trondheim, 700, "road").unwrap();
let (route, cost) = network.shortest_path_to(oslo, trondheim).unwrap().unwrap();
assert_eq!(route, vec![oslo, bergen, trondheim]);
assert_eq!(cost, 1200);
assert!(network.has_path(oslo, trondheim).unwrap());
assert_eq!(network.degree_centrality()[&bergen], 2);
```
---
## Contents
- [What makes it different](#what-makes-it-different)
- [Installation](#installation)
- [The two graph types](#the-two-graph-types)
- [Algorithms](#algorithms)
- [Views: restricting, freezing and observing a graph](#views-restricting-freezing-and-observing-a-graph)
- [Input and output](#input-and-output)
- [Design](#design)
- [Performance](#performance)
- [Correctness](#correctness)
- [Cargo features](#cargo-features)
- [Compatibility and versioning](#compatibility-and-versioning)
- [Development](#development)
---
## What makes it different
**One implementation per algorithm.** Everything is written against a single `GraphView`
abstraction. The same Dijkstra serves the homogeneous graph, the heterogeneous multigraph,
a graph restricted to a subset of its edges, a read-optimised projection, and a graph with
an observer attached. Adding a new algorithm makes it available on all of them; adding a
new kind of graph makes every algorithm available to it.
**Restriction is a view, not a variant of every method.** "Shortest path using only rail
routes" is the ordinary shortest-path call applied to a filtered view:
```rust
# use xgraph::core::{ShortestPath, Traversal};
# use xgraph::hgraph::h_edge::EdgeType;
# use xgraph::hgraph::h_node::NodeType;
# use xgraph::hgraph::HeterogeneousGraph;
# #[derive(Clone, Eq, PartialEq, Hash, Debug)]
# struct City(String);
# impl NodeType for City { fn as_string(&self) -> String { self.0.clone() } }
# #[derive(Clone, Debug, Default, PartialEq)]
# struct Route(String);
# impl EdgeType for Route { fn as_string(&self) -> String { self.0.clone() } }
# let mut network = HeterogeneousGraph::<f64, City, Route>::new(false);
# let oslo = network.add_node(City("Oslo".into()));
# let bergen = network.add_node(City("Bergen".into()));
# let tromso = network.add_node(City("Tromsø".into()));
# network.add_edge(oslo, bergen, 500.0, Route("rail".into())).unwrap();
# network.add_edge(bergen, tromso, 1600.0, Route("sea".into())).unwrap();
// The whole network connects Oslo to Tromsø…
assert!(network.has_path(oslo, tromso).unwrap());
// …but the rail network alone does not.
let rail = network.of_edge_kinds(&["rail"]);
assert!(!rail.has_path(oslo, tromso).unwrap());
assert!(rail.has_path(oslo, bergen).unwrap());
```
Filters compose, and every algorithm — not a chosen subset — applies to the result.
**Identifiers that cannot be misused.** Node and edge identifiers are distinct types, so
one cannot be passed where the other is expected. Each carries a generation counter, so an
identifier held across a removal fails to resolve rather than silently naming whatever took
its place:
```rust
use xgraph::graph::Graph;
let mut graph = Graph::<u32, &str, ()>::new(false);
let first = graph.add_node("first");
graph.remove_node(first).unwrap();
let second = graph.add_node("second");
// Both occupy the same storage slot, and they are still not the same node.
assert_eq!(first.index(), second.index());
assert!(!graph.contains_node(first));
assert_eq!(graph.node(second).unwrap().data, "second");
```
**Preconditions are checked, not assumed.** Dijkstra rejects negative and incomparable
weights instead of returning a plausible-looking wrong answer. Topological sort names the
nodes it could not order. Parameters such as PageRank's damping factor are validated. Every
fallible operation returns a typed error.
**Traversals are iterative.** No algorithm here recurses over graph structure, so depth is
bounded by memory rather than by the call stack. A path graph of 200,000 nodes is a
regression test.
---
## Installation
```toml
[dependencies]
xgraph = "3.0"
```
The default build gives you both graph types and every algorithm. To take only what you
need — for example the homogeneous graph, leaving out the one algorithm that has a
dependency of its own:
```toml
[dependencies]
xgraph = { version = "3.0", default-features = false, features = ["graph"] }
```
That build depends on `slab` and `thiserror`, and nothing else.
---
## The two graph types
Both support directed and undirected edges, weights of any type you choose, parallel edges,
and string attributes on nodes and edges.
### `Graph<W, N, E>` — one node type, one edge type
`W` is the weight, `N` the data on each node, `E` the data on each edge.
```rust
use xgraph::graph::Graph;
let mut graph = Graph::<f64, String, &str>::new(true); // directed
let a = graph.add_node("Warehouse".to_string());
let b = graph.add_node("Depot".to_string());
let road = graph.add_edge(a, b, 34.5, "road").unwrap();
graph.set_edge_attribute_by_id(road, "surface".into(), "gravel".into()).unwrap();
assert_eq!(graph.edge(road).unwrap().weight, 34.5);
```
### `HeterogeneousGraph<W, N, E>` — many node and edge kinds in one graph
Node and edge types describe themselves through the `NodeType` and `EdgeType` traits, which
lets a single graph hold genuinely different entities and relationships — users and items,
roads and rail lines and ferries.
```rust
use xgraph::hgraph::h_edge::EdgeType;
use xgraph::hgraph::h_node::NodeType;
use xgraph::hgraph::HeterogeneousGraph;
#[derive(Clone, Eq, PartialEq, Hash, Debug)]
struct City(String);
impl NodeType for City {
fn as_string(&self) -> String { self.0.clone() }
}
#[derive(Clone, Debug, Default, PartialEq)]
struct Route(String);
impl EdgeType for Route {
fn as_string(&self) -> String { self.0.clone() }
}
let mut network = HeterogeneousGraph::<f64, City, Route>::new(false);
let oslo = network.add_node(City("Oslo".into()));
let bergen = network.add_node(City("Bergen".into()));
// Several routes between the same pair, each with its own kind and weight.
network.add_edge(oslo, bergen, 500.0, Route("rail".into())).unwrap();
network.add_edge(oslo, bergen, 460.0, Route("road".into())).unwrap();
assert_eq!(network.get_edges_between(oslo, bergen).len(), 2);
```
---
## Algorithms
Every algorithm lives in `xgraph::core` and applies to both graph types and to any view of
one. Complexities are given for a graph of `V` nodes and `E` edges.
### Shortest paths — `ShortestPath`
| `dijkstra` | distance from one source to every reachable node | O((V + E) log V) |
| `dijkstra_with_predecessors` | the same, plus the predecessor tree | O((V + E) log V) |
| `shortest_path_to` | one route, with its cost | O((V + E) log V) |
| `astar_path_to` | one route, guided by a heuristic | O((V + E) log V), typically far less |
Weights need only be partially ordered, so `f64` works. Negative weights and weights that do
not compare with themselves (`NaN`) are reported as errors rather than silently producing an
incorrect result. Parallel edges are relaxed individually, so the cheapest one wins without a
separate step. `astar_path_to` takes any admissible heuristic; a heuristic that returns zero
reduces it exactly to Dijkstra.
### Traversal — `Traversal`
| `has_path` | whether one node reaches another | O(V + E) |
| `reachable_from` | every node reachable from a source | O(V + E) |
| `bfs_path` | a path with the fewest edges | O(V + E) |
| `dfs_preorder_into` / `dfs_postorder_into` | depth-first orderings | O(V + E) |
| `has_cycle` / `has_cycle_from` | cycle detection, directed or undirected | O(V + E) |
Undirected cycle detection excludes the specific edge it arrived on rather than every edge
back to the previous node, so a pair of parallel edges is correctly recognised as a cycle.
### Connectivity — `Connectivity`
| `weakly_connected_components` | components with direction ignored | O(V + E) |
| `strongly_connected_components` | Kosaraju's components | O(V + E) |
| `connected_components` | whichever suits the graph's directionality | O(V + E) |
| `is_weakly_connected` / `is_strongly_connected` / `is_connected` | connectivity predicates | O(V + E) |
| `predecessors` | reverse adjacency | O(V + E) |
Components are sorted, and so is the list of them, so results are reproducible run to run.
### Critical structure — `Bridges`
| `bridge_edges` | edges whose removal disconnects a component, by edge | O(V + E) |
| `bridges` | the same, by node pair | O(V + E) |
| `articulation_points` | nodes whose removal disconnects a component | O(V + E) |
Both come from one Tarjan sweep. Reporting bridges by edge is the precise answer on a
multigraph, where a node pair does not identify an edge.
### Spanning trees — `SpanningTree`
| `minimum_spanning_forest` | Kruskal's forest, edges in the order accepted | O(E log E) |
| `minimum_spanning_weight` | its total weight | O(E log E) |
A forest rather than a tree, because a disconnected graph has one tree per component. Backed
by a `DisjointSets` union-find with union-by-size and path compression, which is public and
usable on its own.
### Ordering — `TopologicalSort`
| `topological_order` | Kahn's ordering | O(V + E) |
| `is_dag` | whether the graph is acyclic | O(V + E) |
A cyclic graph reports *which* nodes could not be placed, so a caller can name the circular
dependencies. Ties go to the lowest identifier, so the ordering is reproducible.
### Centrality — `Centrality`
| `degree_centrality` / `in_degree_centrality` | connection count | O(V + E) |
| `betweenness_centrality` | how often a node lies on a shortest path | O(V · E) |
| `closeness_centrality` | nearness to everything reachable | O(V · E) |
| `eigenvector_centrality` | importance derived from neighbours' importance | O(k · (V + E)) |
| `pagerank` | stationary distribution of a teleporting random walk | O(k · (V + E)) |
| `katz_centrality` | influence decaying with distance | O(k · (V + E)) |
Betweenness uses Brandes' algorithm. `par_betweenness_centrality` and
`par_closeness_centrality` spread the per-source work across cores under the `parallel`
feature, and produce identical results.
### Community detection — `CommunityDetection`
| `detect_communities` | Leiden communities at a given resolution |
| `detect_communities_with_config` | the same, with full control over the algorithm |
Leiden guarantees that the communities it reports are internally connected — a property this
implementation is tested against directly, across unseeded runs, because the failure mode
depends on iteration order as much as on the random seed.
### Dominating sets — `DominatingSet`
| `dominating_set` | a greedy dominating set | O(V log V + E) |
| `is_dominating_set` | whether a candidate set dominates | O(V + E) |
Ties in the greedy ordering break by identifier, so the result does not depend on hash
iteration order.
---
## Views: restricting, freezing and observing a graph
A view is a graph. Everything above applies to each of these without modification.
### `EdgeFiltered` and `NodeFiltered` — restrict without copying
```rust
use xgraph::core::{Connectivity, EdgeFiltered};
use xgraph::graph::Graph;
let mut graph = Graph::<u32, &str, &str>::new(false);
let a = graph.add_node("A");
let b = graph.add_node("B");
let c = graph.add_node("C");
let rail = graph.add_edge(a, b, 1, "rail").unwrap();
graph.add_edge(b, c, 1, "road").unwrap();
assert!(graph.is_connected().unwrap());
// Dropping the road splits the graph in two.
let rail_only = EdgeFiltered::new(&graph, move |edge| edge == rail);
assert_eq!(rail_only.weakly_connected_components().unwrap().len(), 2);
```
The heterogeneous graph offers `of_edge_kinds`, `of_edge_data` and `filter_edges` as
shorthands for the common restrictions.
### `CsrView` — a read-optimised projection
The graph types are built for mutation. `CsrView` is the same graph in compressed sparse row
form: immutable, with every neighbour laid out contiguously. Build it once, query it many
times.
```rust
use xgraph::core::{CsrView, GraphView, ShortestPath};
use xgraph::graph::Graph;
let mut graph = Graph::<u32, &str, &str>::new(false);
let a = graph.add_node("A");
let b = graph.add_node("B");
graph.add_edge(a, b, 5, "rail").unwrap();
let frozen = CsrView::from_view(&graph);
assert_eq!(frozen.node_count(), 2);
assert_eq!(frozen.dijkstra(a).unwrap()[&b], 5);
```
Identifiers are preserved, so a route found in the projection names nodes the original graph
still recognises. See [Performance](#performance) for what it is worth in practice.
### `Observed` — react to changes instead of recomputing
Pairs a graph with something watching it change. Useful when a derived structure is
expensive to rebuild and cheap to maintain.
```rust
use xgraph::core::{IncrementalComponents, Observed};
use xgraph::graph::Graph;
let mut network = Observed::new(
Graph::<u32, &str, &str>::new(false),
IncrementalComponents::new(),
);
let a = network.add_node("A");
let b = network.add_node("B");
let c = network.add_node("C");
network.add_edge(a, b, 1, "rail").unwrap();
// Connectivity stays current for the cost of a union-find operation,
// rather than an O(V + E) sweep after every edit.
assert!(network.observer_mut().connected(a, b));
assert!(!network.observer_mut().connected(a, c));
```
There is no event bus and no dynamic dispatch. The default observer is `()`, whose
notification the compiler removes entirely. `IncrementalComponents` is explicit about its
limit: a removal can split a component in a way union-find cannot undo, so it marks itself
stale rather than answering wrongly.
---
## Input and output
### CSV
```rust
use xgraph::graph::io::csv_io::CsvIO;
use xgraph::graph::Graph;
# let dir = std::env::temp_dir().join("xgraph-readme-csv");
# std::fs::create_dir_all(&dir).unwrap();
# let nodes_path = dir.join("nodes.csv").to_string_lossy().into_owned();
# let edges_path = dir.join("edges.csv").to_string_lossy().into_owned();
let mut graph = Graph::<u32, String, String>::new(false);
let a = graph.add_node("Oslo".to_string());
let b = graph.add_node("Bergen".to_string());
graph.add_edge(a, b, 500, "rail".to_string()).unwrap();
graph.save_to_csv(&nodes_path, &edges_path).unwrap();
let restored = Graph::<u32, String, String>::load_from_csv(&nodes_path, &edges_path, false)
.unwrap();
assert_eq!(restored.get_all_edges().len(), 1);
```
Node and edge attributes become columns. Fields containing separators, quotes or line breaks
round-trip exactly. Node identifiers in the file are remapped on load, so a graph saved after
removals restores correctly.
### Graphviz DOT
Any graph, and any view of one, renders to DOT. Node and edge attributes pass straight
through, so colours and shapes set on the data appear in the drawing.
```rust
use xgraph::core::ToDot;
use xgraph::graph::Graph;
let mut graph = Graph::<u32, &str, &str>::new(false);
let oslo = graph.add_node("Oslo");
let bergen = graph.add_node("Bergen");
graph.add_edge(oslo, bergen, 500, "rail").unwrap();
let dot = graph.to_dot("routes");
assert!(dot.starts_with("graph \"routes\" {"));
// std::fs::write("routes.dot", dot)?;
// dot -Tpng routes.dot -o routes.png
```
### serde
With the `serde` feature, both graph types and their identifiers serialise to any format
serde supports. Generation counters are preserved, so an identifier that no longer resolves
does not start resolving again after a round trip.
### Adjacency matrices
`from_adjacency_matrix` and `to_adjacency_matrix` convert in both directions.
`to_adjacency_matrix_with_nodes` also returns the row-to-identifier mapping, which matters
once identifiers are no longer contiguous.
---
## Design
One rule holds the structure together: **`core` knows nothing about the concrete graph
types.** Everything there is written against the `GraphView` abstraction, and the concrete
graphs depend on `core` by implementing it — never the other way round.
```text
graph::Graph ──────┐ write models: mutation is cheap,
hgraph::Hetero… ───┤ identifiers are stable
│ implement
▼
core::GraphView ◄────── core::CsrView read model: traversal is cheap,
▲ the structure is frozen
│ written against
┌─────────────────┼──────────────────┬────────────────────┐
core::algo::* core::filter::* core::io::* core::observer::*
(the algorithms) (restricted views) (DOT export) (change notification)
```
`tests/architecture.rs` reads the source and fails if that rule is broken, or if the two
graph modules start depending on each other. A rule that is only written down erodes.
What follows from the arrangement:
- Each algorithm exists once, so a correction is made once.
- A new view — filtered, frozen, observed — gets every algorithm without any of them being
told it exists.
- A build with only one graph type genuinely excludes the other; the layering is what makes
the feature flags real rather than cosmetic.
`GraphView` uses generic associated types for its iterators, so traversing through the
abstraction allocates nothing and compiles to the same code as traversing the concrete type.
---
## Performance
Measured on a 200 × 200 grid — 40,000 nodes, roughly 80,000 edges — on an Apple M-series
laptop. Reproduce with `cargo bench`.
| Dijkstra from one source | 9.2 ms | 7.4 ms |
| Reachability (breadth-first) | 2.35 ms | 2.36 ms |
| Connected components | 3.6 ms | 3.4 ms |
| Building the projection | — | 1.35 ms |
The projection takes about a fifth off Dijkstra and nothing off a single linear sweep: the
mutable graph already stores each node's neighbours contiguously, so the layout was never as
scattered as compressed-row storage usually improves on. Reach for `CsrView` when the same
graph is queried repeatedly and shortest paths dominate; a single traversal does not repay
the build.
These numbers are in the repository rather than in a claim, and the module documentation
repeats them at the point of use, including the case where the projection does not help.
---
## Correctness
`cargo test --all-features` runs 366 tests: unit tests, integration tests, and every example
in this file and in the API documentation.
Beyond example-based tests:
- **Property tests** drive random sequences of edits and assert the invariants that must
hold afterwards — that the structure stays self-consistent through arbitrary
insertion and removal, that components partition the nodes, that the edges reported as
bridges are exactly those whose removal disconnects something, that Dijkstra's distances
cannot be improved along any edge, that a graph has a cycle exactly when it has more edges
than a spanning forest. They found two defects on their first run.
- **An architecture test** enforces the layering rule by reading the source.
- **A fuzz target** covers the CSV loader, the one place the library consumes input it did
not produce: `cargo +nightly fuzz run csv_loader`.
- **CI** builds and tests on stable and on the declared MSRV, across every meaningful
combination of features, and requires `clippy` to pass with warnings denied, `rustfmt` to
be clean, and the documentation to build without warnings.
Version 3.0 fixed nine defects that produced wrong answers rather than crashes — including
community detection that did not produce connected communities, parallel edges misreported
as bridges, and a centrality routine that silently dropped nodes. [CHANGELOG.md](CHANGELOG.md)
records each of them and what was actually wrong.
---
## Cargo features
| `graph` | yes | `Graph`, the homogeneous graph type |
| `hgraph` | yes | `HeterogeneousGraph`, the multigraph type |
| `community` | yes | Leiden community detection; the only algorithm with a dependency of its own (`rand`) |
| `serde` | no | `Serialize` / `Deserialize` for both graph types and their identifiers |
| `parallel` | no | `par_betweenness_centrality` and `par_closeness_centrality`, backed by `rayon` |
The parallel measures are offered as separate methods rather than as a switch on the existing
ones. Cargo unifies features across a dependency graph, so a feature that changed an existing
method's bounds could break an unrelated crate that happens to share the build.
---
## Compatibility and versioning
- **Minimum supported Rust version: 1.75**, verified by CI. Raising it is a breaking change.
- **Semantic versioning.** Enabling a feature never removes or changes an existing API.
- **Upgrading from 2.x:** see [CHANGELOG.md](CHANGELOG.md). The per-graph algorithm traits
from 2.x remain as deprecated shims that delegate to the shared implementations, so
existing code compiles and the compiler points at the replacement for each item.
---
## Development
```bash
cargo test --all-features # tests, doctests, property tests
cargo clippy --all-targets --all-features -- -D warnings
cargo fmt --all --check
cargo bench # criterion benchmarks
cargo doc --all-features --open
cargo run --example basic_usage # homogeneous graph, end to end
cargo run --example h_basic_usage # heterogeneous multigraph: Viking trade routes
```
---
## License
MIT — see [LICENSE](LICENSE).