xgraph 3.0.0

Graph algorithms for Rust: shortest paths, centrality, connectivity, spanning trees and community detection, over directed, undirected and heterogeneous multigraphs
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

//! # 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`](core::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.
//!
//! ```text
//!   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`](core::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`](core::CsrView) and
//!   [`Observed`](core::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.
//!
//! ```rust
//! # #[cfg(all(feature = "graph", feature = "community"))] {
//! 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);
//! # }
//! ```

/// The README's code samples, compiled and run as doctests.
///
/// They had gone stale — referring to traits that no longer existed — precisely because
/// nothing checked them. Now they cannot.
#[doc = include_str!("../README.md")]
#[cfg(doctest)]
pub struct ReadmeSamples;

pub mod core;
pub mod error;

#[cfg(feature = "graph")]
pub mod graph;
#[cfg(feature = "hgraph")]
pub mod hgraph;

pub mod prelude;

pub use error::{Error, Result};

#[cfg(all(feature = "graph", feature = "community"))]
pub use graph::leiden_clustering;
#[cfg(feature = "graph")]
pub use graph::{
    bridges, centrality, connectivity, search, shortest_path, wiedemann_ford, Edge, Graph, Node,
};

#[cfg(all(feature = "hgraph", feature = "community"))]
pub use hgraph::h_leiden_clustering;
#[cfg(feature = "hgraph")]
pub use hgraph::{
    h_bridges, h_centrality, h_connectivity, h_search, h_shortest_path, h_wiedemann_ford, HEdge,
    HGraphError, HNode, HeterogeneousGraph,
};