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

#![deny(missing_docs)]

//! This crate implements functions to search in a graph.
//!
//! It supports the following Cargo features:
//!
//! - `edmonds_karp`: include the Edmonds-Karp algorithm variants
//!   (default: true)
//! - `kuhn_munkres`: include the Kuhn-Munkres algorithm (default: true)

#[cfg(feature = "kuhn_munkres")]
extern crate fixedbitset;
#[cfg(any(feature = "edmonds_karp", feature = "kuhn_munkres"))]
pub extern crate ndarray;
pub extern crate num_traits;

mod astar;
mod bfs;
mod dfs;
mod dijkstra;
#[cfg(feature = "edmonds_karp")]
mod edmonds_karp;
mod fringe;
mod idastar;
#[cfg(feature = "kuhn_munkres")]
mod kuhn_munkres;

pub use astar::*;
pub use bfs::*;
pub use dfs::*;
pub use dijkstra::*;
#[cfg(feature = "edmonds_karp")]
pub use edmonds_karp::*;
pub use fringe::*;
pub use idastar::*;
#[cfg(feature = "kuhn_munkres")]
pub use kuhn_munkres::*;

use std::collections::HashMap;
use std::hash::Hash;

fn reverse_path<N: Eq + Hash + Clone>(parents: &HashMap<N, N>, start: N) -> Vec<N> {
    let mut path = vec![start];
    while let Some(parent) = parents.get(path.last().unwrap()).cloned() {
        path.push(parent);
    }
    path.into_iter().rev().collect()
}