genetic_algorithm_tsp/
distance_mat.rs

1use crate::routes;
2/// A representation of a f64 based distance matrix.
3#[derive(Debug)]
4pub struct DistanceMat {
5    distances: Vec<Vec<f64>>,
6}
7
8impl DistanceMat {
9    /// Create a new distance mat based on exising
10    /// distances.
11    ///
12    /// # Arguments
13    ///
14    /// * `distances` - The distances between all indexes 0..n. The matrix
15    /// is assumed to be symmetrical and the distance between an object and itself
16    /// (the diagonal) should be only 0.
17    ///
18    /// # Examples
19    ///
20    /// ```
21    /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
22    ///
23    /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
24    /// ```
25    pub fn new(distances: Vec<Vec<f64>>) -> Self {
26        DistanceMat { distances }
27    }
28    /// Get the number of nodes in the distance matrix, e.g. one of its dimensions.
29    ///
30    /// # Examples
31    ///
32    /// ```
33    /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
34    ///
35    /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
36    /// println!("{}", distance_matrix.n_units());
37    /// ```
38    pub fn n_units(&self) -> usize {
39        self.distances.len()
40    }
41    /// Given a sequence of nodes (in a `Route`-object) compute the distance for the round-
42    /// trip between node 0..0
43    ///
44    /// # Arguments
45    ///
46    /// * `route` - The sequence of nodes that is visited and for which the round-trip-lenght
47    /// should be computed.
48    ///
49    /// # Examples
50    ///
51    /// ```
52    /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
53    /// use genetic_algorithm_tsp::route::Route;
54    ///
55    /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
56    /// println!("{}", distance_matrix.get_distance(&vec![1,0,2]));
57    /// ```
58    pub fn get_distance(&self, route: &[usize]) -> f64 {
59        route
60            .iter()
61            .fold(
62                // By folding the indexes we get the distances between 1-2, 2-3, ... , (n-1)-n.
63                // Then we are missing n-0, therefore that's the initial value we choose in the `fold`-
64                // operator.
65                (self.distances[route[route.len() - 1]][route[0]], None),
66                |(mut loss, last_point): (f64, Option<usize>), current_point| {
67                    if let Some(last_point) = last_point {
68                        loss += &self.distances[last_point][*current_point];
69                    }
70                    (loss, Some(*current_point))
71                },
72            )
73            .0
74    }
75
76    /// Generate a random population suiting your distance mat.  
77    ///
78    /// # Arguments
79    ///
80    /// * `n_routes` - How many routes should be generated?
81    ///
82    /// # Examples
83    ///
84    /// ```
85    /// use genetic_algorithm_tsp::distance_mat::DistanceMat;
86    ///
87    /// let distance_matrix = DistanceMat::new(vec![vec![0.0,1.0,2.0], vec![1.0,0.0,3.0], vec![2.0,3.0,0.0]]);
88    /// println!("{}", distance_matrix.get_random_population(5));
89    /// ```
90    pub fn get_random_population(&self, n_routes: usize) -> routes::Routes {
91        routes::Routes::random(n_routes, self.n_units())
92    }
93}
94
95#[cfg(test)]
96mod test_distance_mat {
97    use super::*;
98    use crate::test_utils::test_dist_mat;
99    #[test]
100    fn test_constructor() {
101        let dist_mat = DistanceMat::new(vec![vec![0.0, 1.0], vec![1.0, 0.0]]);
102        assert_eq!(dist_mat.distances, vec![vec![0.0, 1.0], vec![1.0, 0.0]]);
103    }
104    #[test]
105    fn test_dist_same_node() {
106        assert_eq!(test_dist_mat().get_distance(&vec![0, 0]), 0.0);
107    }
108    #[test]
109    fn test_dist_two_nodes() {
110        assert_eq!(test_dist_mat().get_distance(&vec![0, 1]), 2.0);
111        assert_eq!(test_dist_mat().get_distance(&vec![0, 2]), 4.0);
112        assert_eq!(test_dist_mat().get_distance(&vec![1, 2]), 6.0);
113    }
114    #[test]
115    fn test_dist_three_nodes() {
116        assert_eq!(test_dist_mat().get_distance(&vec![0, 1, 2]), 6.0);
117        assert_eq!(test_dist_mat().get_distance(&vec![0, 2, 1]), 6.0);
118    }
119    #[test]
120    fn test_dist_repeat_visit() {
121        assert_eq!(test_dist_mat().get_distance(&[0, 2, 1, 2]), 10.0);
122    }
123    #[test]
124    fn test_get_random_population() {
125        let distance_matrix = DistanceMat::new(vec![
126            vec![0.0, 1.0, 2.0],
127            vec![1.0, 0.0, 3.0],
128            vec![2.0, 3.0, 0.0],
129        ]);
130        distance_matrix.get_random_population(5);
131    }
132}
genetic_algorithm_tsp/distance_mat.rs

genetic_algorithm_tsp/
distance_mat.rs
