____   ____._____  .______  .______  ._______ .___.__  
 \   \_/   /:_ ___\ : __   \ :      \ : ____  |:   |  \ 
  \___ ___/ |   |___|  \____||   .   ||    :  ||   :   |
  /   _   \ |   /  ||   :  \ |   :   ||   |___||   .   |
 /___/ \___\|. __  ||   |___\|___|   ||___|    |___|   |
             :/ |. ||___|        |___|             |___|
             :   :/                                     
                 :                                      

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.

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
• Installation
• The two graph types
• Algorithms
• Views: restricting, freezing and observing a graph
• Input and output
• Design
• Performance
• Correctness
• Cargo features
• Compatibility and versioning
• 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:

# 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:

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

[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:

[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.

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.

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

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

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

Components are sorted, and so is the list of them, so results are reproducible run to run.

Critical structure — Bridges

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

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

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

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

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

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

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.

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 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.

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

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.

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.

  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.

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 records each of them and what was actually wrong.

Cargo features

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. 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

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.