Crate xgraph 

xgraph

Graph data structures and algorithms: directed and undirected, weighted, with parallel edges and arbitrary data on nodes and edges.

How the crate is arranged

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. tests/architecture.rs enforces this by reading the source, because a rule that is only written down erodes.

  graph::Graph ──┐                    the write models: mutation is cheap,
  hgraph::Het… ──┤                    identifiers are stable
                 │  implement
                 ▼
           core::GraphView  ◄──── core::CsrView       a read model: traversal is cheap,
                 ▲                                    the structure is frozen
                 │  written against
  ┌──────────────┴───────────────┐
  core::algo::*    core::io::*    core::filter::*
  (the algorithms) (DOT export)   (restricted views)

What follows from that arrangement:

• Each algorithm exists once. Before, every one of them existed twice — once per graph type — and the copies had drifted apart in their error handling, their trait bounds and, in several cases, their answers.
• Restriction is a view, not a variant. “Only the rail routes” is EdgeFiltered wrapped around a graph, and every algorithm applies to the result unchanged. The heterogeneous graph used to carry a *_by_types twin of each method, each duplicating its sibling’s traversal.
• New views come free. CsrView and Observed are graphs to every algorithm here without any of them being told about it.

Where to start

graph::Graph for a graph whose nodes all hold the same type; hgraph::HeterogeneousGraph when they do not. The algorithms live in core and apply to both.

use xgraph::core::{Centrality, ShortestPath, Traversal};
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");
let trondheim = graph.add_node("Trondheim");
graph.add_edge(oslo, bergen, 500, "rail").unwrap();
graph.add_edge(bergen, trondheim, 700, "road").unwrap();

let (route, cost) = graph.shortest_path_to(oslo, trondheim).unwrap().unwrap();
assert_eq!(route, vec![oslo, bergen, trondheim]);
assert_eq!(cost, 1200);

assert!(graph.has_path(oslo, trondheim).unwrap());
assert_eq!(graph.degree_centrality()[&bergen], 2);

Re-exports

pub use error::Error;

pub use error::Result;

pub use graph::leiden_clustering;

pub use graph::bridges;

pub use graph::centrality;

pub use graph::connectivity;

pub use graph::search;

pub use graph::shortest_path;

pub use graph::wiedemann_ford;

pub use graph::Edge;

pub use graph::Graph;

pub use graph::Node;

pub use hgraph::h_leiden_clustering;

pub use hgraph::h_bridges;

pub use hgraph::h_centrality;

pub use hgraph::h_connectivity;

pub use hgraph::h_search;

pub use hgraph::h_shortest_path;

pub use hgraph::h_wiedemann_ford;

pub use hgraph::HEdge;

pub use hgraph::HGraphError;

pub use hgraph::HNode;

pub use hgraph::HeterogeneousGraph;

Modules

core

Storage-agnostic core of the library.

error

The crate’s unifying error type.

graph

hgraph

prelude