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

use super::*;

/// The Beam search strategy implementation
///
/// This strategy has a limit of candidate routes at all times.
/// For example, keeps the 3 best routes and all the others get discarded
pub struct Beam<'a, I, N, E, Ty, Ix, F> {
    goal: Option<NodeIndex<Ix>>,
    graph: &'a Graph<I, N, E, Ty, Ix>,
    border: VecDeque<Step<f32, Ix>>,
    successors: usize,
    neighbors: Vec<NodeIndex<Ix>>,
    compare: F,
    pub direction: Direction,
}

impl<'a, I, N, E, Ty: EdgeType, Ix: IndexType, F> Beam<'a, I, N, E, Ty, Ix, F>
where
    F: FnMut(&NodeIndex<Ix>, &NodeIndex<Ix>) -> Ordering,
{
    #[allow(dead_code)]
    pub fn new(
        graph: &'a Graph<I, N, E, Ty, Ix>,
        journey: (NodeIndex<Ix>, Option<NodeIndex<Ix>>),
        successors: usize,
        compare: F,
        direction: Direction,
    ) -> Self {
        Self {
            graph,
            goal: journey.1,
            successors,
            neighbors: Vec::with_capacity(graph.edge_count()),
            border: {
                let mut border = VecDeque::with_capacity(graph.node_count());
                border.push_front(Step {
                    caller: None,
                    idx: journey.0,
                    rel: None,
                    state: 0.,
                });
                border
            },
            compare,
            direction,
        }
    }
}

impl<'a, I, N, E, Ty: EdgeType, Ix: IndexType, F> Walker<Ix> for Beam<'a, I, N, E, Ty, Ix, F>
where
    F: FnMut(&NodeIndex<Ix>, &NodeIndex<Ix>) -> Ordering,
{
    fn step(&mut self) -> WalkerState<Ix> {
        if let Some(parent) = self.border.pop_front() {
            if self.goal.map(|goal| goal == parent.idx).unwrap_or(false) {
                return WalkerState::Found(parent);
            }

            let parent = Rc::new(parent);
            if self
                .graph
                .inner
                .neighbors_directed(parent.idx, self.direction)
                .count()
                != 0
            {
                // Get and sort from the best (smallest value) to worst (biggest value) neighbors
                self.neighbors.clear();
                self.neighbors.extend(
                    self.graph
                        .inner
                        .neighbors_directed(parent.idx, self.direction),
                );

                self.neighbors.sort_by(&mut self.compare);

                // Add the self.successors best neighbors
                self.neighbors
                    .iter()
                    .copied()
                    .enumerate()
                    .take_while(|(i, _)| i < &self.successors)
                    .for_each(|(_, child_idx)| {
                        self.border.push_back(Step {
                            caller: Some(parent.clone()),
                            idx: child_idx,
                            rel: self.graph.edge_between(parent.idx, child_idx),
                            state: 0.,
                        });
                    });
            }

            WalkerState::NotFound(parent)
        } else {
            WalkerState::Done
        }
    }
}