pathfinding_indexed/lib.rs
1#![forbid(missing_docs)]
2//! # pathfinding-indexed
3//!
4//! Index-only pathfinding, flow, and graph algorithms with dense `usize` indices.
5//!
6//! The primary API is [`IndexedGraph`] for directed graphs and
7//! [`IndexedUndirectedGraph`] for undirected graphs. Algorithms are exposed as
8//! methods on these types.
9//!
10//! This crate builds on the original [`pathfinding`](https://crates.io/crates/pathfinding)
11//! crate and credits Samuel Tardieu and its contributors for the original
12//! library this indexed-only variant descends from.
13//!
14//! ## Example
15//!
16//! ```rust
17//! use pathfinding_indexed::IndexedGraph;
18//!
19//! let graph = IndexedGraph::from_adjacency(vec![
20//! vec![(1, 2), (2, 4)],
21//! vec![(2, 1), (3, 7)],
22//! vec![(3, 3)],
23//! vec![],
24//! ]);
25//!
26//! let result = graph.dijkstra(0, |node| node == 3);
27//! assert_eq!(result, Some((vec![0, 1, 2, 3], 6)));
28//! ```
29//!
30//! ## More Examples
31//!
32//! Build a graph from external node values:
33//!
34//! ```rust
35//! use pathfinding_indexed::IndexedGraphMap;
36//! use std::collections::HashMap;
37//!
38//! let raw: HashMap<&str, Vec<(&str, u32)>> = [
39//! ("A", vec![("B", 4), ("C", 2)]),
40//! ("B", vec![("C", 1), ("D", 5)]),
41//! ("C", vec![("D", 8)]),
42//! ("D", vec![]),
43//! ]
44//! .into_iter()
45//! .collect();
46//!
47//! let mapped = IndexedGraphMap::from_nodes_and_successors(["A"], |node| {
48//! raw.get(node).cloned().unwrap_or_default()
49//! });
50//!
51//! let start = mapped.index_of(&"A").unwrap();
52//! let goal = mapped.index_of(&"D").unwrap();
53//! let result = mapped.graph().dijkstra(start, |node| node == goal);
54//! assert_eq!(result.map(|(_, cost)| cost), Some(9));
55//! ```
56//!
57//! Use the undirected graph API for MST algorithms:
58//!
59//! ```rust
60//! use pathfinding_indexed::IndexedUndirectedGraph;
61//!
62//! let graph = IndexedUndirectedGraph::from_edges(
63//! 4,
64//! vec![(0, 1, 7), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 6)],
65//! );
66//!
67//! let mst = graph.kruskal();
68//! assert_eq!(mst.len(), 3);
69//! ```
70//!
71//! The minimum supported Rust version (MSRV) is Rust 1.87.0.
72
73mod directed;
74mod noderefs;
75mod undirected;
76
77pub mod indexed_graph;
78
79pub use indexed_graph::{IndexedGraph, IndexedGraphMap, IndexedInputError, IndexedUndirectedGraph};
80
81use indexmap::{IndexMap, IndexSet};
82use rustc_hash::FxHasher;
83use std::hash::BuildHasherDefault;
84
85type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
86type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;
87
88/// Convenience re-exports for indexed graph types.
89pub mod prelude {
90 pub use crate::indexed_graph::{
91 IndexedGraph, IndexedGraphMap, IndexedInputError, IndexedUndirectedGraph,
92 };
93}