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

#![deny(missing_docs)]

//! This crate implements several pathfinding, flow, and graph algorithms.

extern crate fixedbitset;
extern crate indexmap;
#[macro_use]
extern crate itertools;
pub extern crate num_traits;

pub mod astar;
pub mod bfs;
pub mod connected_components;
pub mod dfs;
pub mod dijkstra;
pub mod edmonds_karp;
pub mod fringe;
pub mod grid;
pub mod idastar;
pub mod kuhn_munkres;
pub mod matrix;
pub mod topological_sort;

/// Export all public functions and structures for an easy access.
pub mod prelude {
    pub use astar::*;
    pub use bfs::*;
    pub use connected_components::*;
    pub use dfs::*;
    pub use dijkstra::*;
    pub use edmonds_karp::*;
    pub use fringe::*;
    pub use grid::*;
    pub use idastar::*;
    pub use kuhn_munkres::*;
    pub use matrix::*;
    pub use topological_sort::*;
}

use indexmap::IndexMap;
use std::hash::Hash;

fn reverse_path<N, V, F>(parents: &IndexMap<N, V>, mut parent: F, start: usize) -> Vec<N>
where
    N: Eq + Hash + Clone,
    F: FnMut(&V) -> usize,
{
    let path = itertools::unfold(start, |i| {
        parents.get_index(*i).map(|(node, value)| {
            *i = parent(value);
            node
        })
    }).collect::<Vec<&N>>();

    path.into_iter().rev().cloned().collect()
}