Crate pathfinding_indexed 

pathfinding-indexed

Index-only pathfinding, flow, and graph algorithms with dense usize indices.

The primary API is IndexedGraph for directed graphs and IndexedUndirectedGraph for undirected graphs. Algorithms are exposed as methods on these types.

This crate builds on the original pathfinding crate and credits Samuel Tardieu and its contributors for the original library this indexed-only variant descends from.

Example

use pathfinding_indexed::IndexedGraph;

let graph = IndexedGraph::from_adjacency(vec![
    vec![(1, 2), (2, 4)],
    vec![(2, 1), (3, 7)],
    vec![(3, 3)],
    vec![],
]);

let result = graph.dijkstra(0, |node| node == 3);
assert_eq!(result, Some((vec![0, 1, 2, 3], 6)));

More Examples

Build a graph from external node values:

use pathfinding_indexed::IndexedGraphMap;
use std::collections::HashMap;

let raw: HashMap<&str, Vec<(&str, u32)>> = [
    ("A", vec![("B", 4), ("C", 2)]),
    ("B", vec![("C", 1), ("D", 5)]),
    ("C", vec![("D", 8)]),
    ("D", vec![]),
]
.into_iter()
.collect();

let mapped = IndexedGraphMap::from_nodes_and_successors(["A"], |node| {
    raw.get(node).cloned().unwrap_or_default()
});

let start = mapped.index_of(&"A").unwrap();
let goal = mapped.index_of(&"D").unwrap();
let result = mapped.graph().dijkstra(start, |node| node == goal);
assert_eq!(result.map(|(_, cost)| cost), Some(9));

Use the undirected graph API for MST algorithms:

use pathfinding_indexed::IndexedUndirectedGraph;

let graph = IndexedUndirectedGraph::from_edges(
    4,
    vec![(0, 1, 7), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 6)],
);

let mst = graph.kruskal();
assert_eq!(mst.len(), 3);

The minimum supported Rust version (MSRV) is Rust 1.87.0.

Re-exports

pub use indexed_graph::IndexedGraph;

pub use indexed_graph::IndexedGraphMap;

pub use indexed_graph::IndexedInputError;

pub use indexed_graph::IndexedUndirectedGraph;

Modules

indexed_graph

Indexed graph storage and algorithms.

prelude

Convenience re-exports for indexed graph types.