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
165
166
167
168
169
170
171
172
173
174
175
176
177
178

use super::*;

pub struct Hill<'a, I, N, E, Ty, Ix, F> {
    goal: Option<NodeIndex<Ix>>,
    graph: &'a Graph<I, N, E, Ty, Ix>,
    direction: Direction,
    neighbors: Vec<NodeIndex<Ix>>,
    border: VecDeque<Step<f32, Ix>>,
    compare: F,
}

impl<'a, I, N, E, Ty: EdgeType, Ix: IndexType, F> Hill<'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>>),
        compare: F,
        direction: Direction,
    ) -> Self {
        Self {
            graph,
            goal: journey.1,
            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 Hill<'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
            {
                self.neighbors.clear();
                self.neighbors.extend(
                    self.graph
                        .inner
                        .neighbors_directed(parent.idx, self.direction),
                );

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

                self.neighbors.iter().copied().rev().for_each(|child_idx| {
                    self.border.push_front(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
        }
    }
}

pub struct StochasticHill<'a, I, N, E, Ty, Ix, F> {
    goal: Option<NodeIndex<Ix>>,
    graph: &'a Graph<I, N, E, Ty, Ix>,
    direction: Direction,
    neighbors: Vec<NodeIndex<Ix>>,
    border: VecDeque<Step<f32, Ix>>,
    compare: F,
}

impl<'a, I, N, E, Ty: EdgeType, Ix: IndexType, F> StochasticHill<'a, I, N, E, Ty, Ix, F>
where
    F: FnMut(&NodeIndex<Ix>) -> f32,
{
    #[allow(dead_code)]
    pub fn new(
        graph: &'a Graph<I, N, E, Ty, Ix>,
        journey: (NodeIndex<Ix>, Option<NodeIndex<Ix>>),
        compare: F,
        direction: Direction,
    ) -> Self {
        Self {
            graph,
            goal: journey.1,
            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 StochasticHill<'a, I, N, E, Ty, Ix, F>
where
    F: FnMut(&NodeIndex<Ix>) -> f32,
{
    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
            {
                self.neighbors.clear();
                self.neighbors.extend(
                    self.graph
                        .inner
                        .neighbors_directed(parent.idx, self.direction),
                );

                self.neighbors.sort_by(|a, b| {
                    (self.compare)(a)
                        .partial_cmp(&(self.compare)(b))
                        .unwrap_or(Ordering::Equal)
                });

                let len = self.neighbors.len();
                self.neighbors
                    .partial_shuffle(&mut rrand::get_rng(), len / 3);

                self.neighbors.iter().copied().rev().for_each(|child_idx| {
                    self.border.push_front(Step {
                        caller: Some(parent.clone()),
                        idx: child_idx,
                        rel: Some(self.graph.edge_between_unchecked(parent.idx, child_idx)),
                        state: 0.,
                    });
                });
            }

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