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

use super::*;

pub struct SimAnnealing<'a, Ix> {
    graph: &'a Graph<&'static str, (f32, f32), f32, Directed, Ix>,
    state: Rc<Step<f32, Ix>>,
    temperature: f32,
}

impl<'a, Ix: IndexType> SimAnnealing<'a, Ix> {
    fn perturb_state(&mut self) -> Rc<Step<f32, Ix>> {
        let mut rng = rrand::get_rng();
        use rand::Rng;
        let mut indices = self.state.collect_nodes();
        let len = indices.len() - 1;
        let idx1 = rng.gen_range(1..(len - 1));
        let idx2 = rng.gen_range(1..(len - 1));

        indices.swap(idx1, idx2);

        // Re-create the step chain
        Rc::new(Step::from_slice(
            &indices,
            self.graph,
            |par, _, curr, step| {
                self.graph
                    .inner
                    .edge_weight(self.graph.edge_between_unchecked(par, curr))
                    .unwrap()
                    + *step
            },
        ))
    }

    pub fn new(
        graph: &'a Graph<&'static str, (f32, f32), f32, Directed, Ix>,
        journey: (NodeIndex<Ix>, Option<NodeIndex<Ix>>),
        temperature: f32,
    ) -> Self {
        let mut graph_nodes = graph.inner.node_indices().collect::<Vec<_>>();
        let mut rng = rrand::get_rng();
        while let Ok(start) = {
            graph_nodes.sort();
            graph_nodes.binary_search(&journey.0)
        } {
            graph_nodes.remove(start);
        }
        graph_nodes.shuffle(&mut rng);

        let mut result_nodes = Vec::with_capacity(graph_nodes.len() + 1);
        result_nodes.push(journey.0);
        result_nodes.extend(graph_nodes);
        result_nodes.push(journey.0);
        let step = Rc::new(Step::from_slice(
            &result_nodes,
            graph,
            |par, _, curr, step| {
                graph
                    .inner
                    .edge_weight(graph.edge_between_unchecked(par, curr))
                    .unwrap()
                    + *step
            },
        ));
        Self {
            graph,
            temperature,
            state: step,
        }
    }
}

impl<'a, Ix: IndexType> Walker<Ix> for SimAnnealing<'a, Ix> {
    fn step(&mut self) -> WalkerState<Ix> {
        self.temperature -= 100. * 0.1 / self.temperature;
        if self.temperature <= 0.1 {
            WalkerState::Done
        } else {
            let new = self.perturb_state();

            if new.state < self.state.state {
                self.state = new;
                WalkerState::NotFound(self.state.clone())
            } else {
                // To try and force recalculations we give non-direct benefiting changes a chance
                use rand::Rng;
                let mut rng = rrand::get_rng();
                let p = rng.gen::<f32>().ln();
                if p > 0.8 {
                    self.state = new;
                    WalkerState::NotFound(self.state.clone())
                } else {
                    WalkerState::Cutoff
                }
            }
        }
    }
}