pathfinding 4.15.0

Pathfinding, flow, and graph algorithms
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

#![forbid(missing_docs)]
//! # pathfinding
//!
//! [![Current Version](https://img.shields.io/crates/v/pathfinding.svg)](https://crates.io/crates/pathfinding)
//! [![Documentation](https://docs.rs/pathfinding/badge.svg)](https://docs.rs/pathfinding)
//! [![License: Apache-2.0/MIT](https://img.shields.io/crates/l/pathfinding.svg)](#license)
//!
//! This crate implements several pathfinding, flow, and graph algorithms in [Rust][Rust].
//!
//! ## Algorithms
//!
//! The algorithms are generic over their arguments.
//!
//! ### Directed graphs
//!
//! - [A*](directed/astar/index.html): find the shortest path in a weighted graph using an heuristic to guide the process ([⇒ Wikipedia][A*])
//! - [BFS](directed/bfs/index.html): explore nearest successors first, then widen the search ([⇒ Wikipedia][BFS])
//! - [Bidirectional search](directed/bfs/fn.bfs_bidirectional.html): simultaneously explore paths forwards from the start and backwards from the goal ([=> Wikipedia][Bidirectional search])
//! - [Brent](directed/cycle_detection/index.html): find a cycle in an infinite sequence ([⇒ Wikipedia][Brent])
//! - [DFS](directed/dfs/index.html): explore a graph by going as far as possible, then backtrack ([⇒ Wikipedia][DFS])
//! - [Dijkstra](directed/dijkstra/index.html): find the shortest path in a weighted graph ([⇒ Wikipedia][Dijkstra])
//! - [Edmonds Karp](directed/edmonds_karp/index.html): find the maximum flow in a weighted graph ([⇒ Wikipedia][Edmonds Karp])
//! - [Floyd](directed/cycle_detection/index.html): find a cycle in an infinite sequence ([⇒ Wikipedia][Floyd])
//! - [Fringe](directed/fringe/index.html): find the shortest path in a weighted graph using an heuristic to guide the process ([⇒ Wikipedia][Fringe])
//! - [IDA*](directed/idastar/index.html): explore longer and longer paths in a weighted graph at the cost of multiple similar examinations ([⇒ Wikipedia][IDA*])
//! - [IDDFS](directed/iddfs/index.html): explore longer and longer paths in an unweighted graph at the cost of multiple similar examinations ([⇒ Wikipedia][IDDFS])
//! - [paths counting](directed/count_paths/index.html): count the paths to the destination in an acyclic graph
//! - [strongly connected components](directed/strongly_connected_components/index.html): find strongly connected components in a directed graph ([⇒ Wikipedia][Strongly connected components])
//! - [topological sorting](directed/topological_sort/index.html): find an acceptable topological order in a directed graph ([⇒ Wikipedia][Topological sorting])
//! - [Yen](directed/yen/index.html): find k-shortest paths using Dijkstra ([⇒ Wikipedia][Yen])
//!
//! ### Undirected graphs
//!
//! - [connected components](undirected/connected_components/index.html): find disjoint connected sets of vertices ([⇒ Wikipedia][Connected components])
//! - [Kruskal](undirected/kruskal/index.html): find a minimum-spanning-tree ([⇒ Wikipedia][Kruskal])
//! - [Prim](undirected/prim/index.html): find a minimum-spanning-tree ([⇒ Wikipedia][Prim])
//! - [cliques](undirected/cliques/index.html): find maximum cliques in a graph ([= Wikipedia][BronKerbosch])
//!
//! ### Matching
//!
//! - [Kuhn-Munkres](kuhn_munkres/index.html) (Hungarian algorithm): find the maximum (or minimum) matching in a weighted bipartite graph ([⇒ Wikipedia][Kuhn-Munkres])
//!
//! ### Miscellaneous structures
//!
//! - A [`Grid`](grid/index.html) type representing a rectangular grid in which vertices can be added or removed, with automatic creation of edges between adjacent vertices.
//! - A [`Matrix`](matrix/index.html) type to store data of arbitrary types, with neighbour-aware methods.
//!
//! ## Working with Graphs
//!
//! This library does not provide a fixed graph data structure. Instead, the algorithms accept
//! a **successor function** that defines how to navigate from one node to its neighbors.
//!
//! For comprehensive examples showing how to represent graphs (adjacency lists, adjacency matrices,
//! edge lists, etc.) and use them with various algorithms, see the
//! [Graph Guide](https://github.com/evenfurther/pathfinding/blob/main/GRAPH_GUIDE.md).
//!
//! ## Example
//!
//! We will search the shortest path on a chess board to go from (1, 1) to (4, 6) doing only knight
//! moves.
//!
//! ``` rust
//! use pathfinding::prelude::bfs;
//!
//! #[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
//! struct Pos(i32, i32);
//!
//! impl Pos {
//!   fn successors(&self) -> Vec<Pos> {
//!     let &Pos(x, y) = self;
//!     vec![Pos(x+1,y+2), Pos(x+1,y-2), Pos(x-1,y+2), Pos(x-1,y-2),
//!          Pos(x+2,y+1), Pos(x+2,y-1), Pos(x-2,y+1), Pos(x-2,y-1)]
//!   }
//! }
//!
//! static GOAL: Pos = Pos(4, 6);
//! let result = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
//! assert_eq!(result.expect("no path found").len(), 5);
//! ```
//!
//! ## Note on floating-point types
//!
//! Several algorithms require that the numerical types used to describe
//! edge weights implement `Ord`. If you wish to use Rust built-in
//! floating-point types (such as `f32`) that implement `PartialOrd`
//! in this context, you can wrap them into compliant types using the
//! [ordered-float](https://crates.io/crates/ordered-float) crate.
//!
//! The minimum supported Rust version (MSRV) is Rust 1.87.0.
//!
//! [A*]: https://en.wikipedia.org/wiki/A*_search_algorithm
//! [BFS]: https://en.wikipedia.org/wiki/Breadth-first_search
//! [Bidirectional search]: https://en.wikipedia.org/wiki/Bidirectional_search
//! [Brent]: https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algorithm
//! [BronKerbosch]: https://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm
//! [Connected components]: https://en.wikipedia.org/wiki/Connected_component_(graph_theory)
//! [DFS]: https://en.wikipedia.org/wiki/Depth-first_search
//! [Dijkstra]: https://en.wikipedia.org/wiki/Dijkstra's_algorithm
//! [Edmonds Karp]: https://en.wikipedia.org/wiki/Edmonds–Karp_algorithm
//! [Floyd]: https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare
//! [Fringe]: https://en.wikipedia.org/wiki/Fringe_search
//! [IDA*]: https://en.wikipedia.org/wiki/Iterative_deepening_A*
//! [IDDFS]: https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search
//! [Kruskal]: https://en.wikipedia.org/wiki/Kruskal's_algorithm
//! [Kuhn-Munkres]: https://en.wikipedia.org/wiki/Hungarian_algorithm
//! [Prim]: https://en.wikipedia.org/wiki/Prim's_algorithm
//! [Rust]: https://rust-lang.org/
//! [Strongly connected components]: https://en.wikipedia.org/wiki/Strongly_connected_component
//! [Topological sorting]: https://en.wikipedia.org/wiki/Topological_sorting
//! [Yen]: https://en.wikipedia.org/wiki/Yen's_algorithm

use deprecate_until::deprecate_until;
pub use num_traits;

pub mod directed;
pub mod grid;
pub mod kuhn_munkres;
pub mod matrix;
pub mod undirected;
pub mod utils;

mod noderefs;
pub use noderefs::NodeRefs;

use indexmap::{IndexMap, IndexSet};
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;

type FxIndexMap<K, V> = IndexMap<K, V, BuildHasherDefault<FxHasher>>;
type FxIndexSet<K> = IndexSet<K, BuildHasherDefault<FxHasher>>;

/// Export all public functions and structures for an easy access.
pub mod prelude {
    pub use crate::directed::astar::*;
    pub use crate::directed::bfs::*;
    pub use crate::directed::count_paths::*;
    pub use crate::directed::cycle_detection::*;
    pub use crate::directed::dfs::*;
    pub use crate::directed::dijkstra::*;
    pub use crate::directed::edmonds_karp::*;
    pub use crate::directed::fringe::*;
    pub use crate::directed::idastar::*;
    pub use crate::directed::iddfs::*;
    pub use crate::directed::strongly_connected_components::*;
    pub use crate::directed::topological_sort::*;
    pub use crate::directed::yen::*;
    pub use crate::grid::*;
    pub use crate::kuhn_munkres::*;
    pub use crate::matrix::*;
    pub use crate::undirected::cliques::*;
    pub use crate::undirected::connected_components::*;
    pub use crate::undirected::kruskal::*;
    pub use crate::utils::*;
}

/// Deprecated: moved into the `directed` module.
#[deprecate_until(
    note = "use directed::cycle_detection or the prelude instead",
    since = "4.3.1",
    remove = "> 4.x"
)]
pub mod cycle_detection {
    pub use crate::directed::cycle_detection::*;
}