walky 1.1.0

A TSP solver written in Rust
Documentation 
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

use crate::datastructures::Graph;
use nalgebra::{DMatrix, DVector};
use std::ops::{Deref, DerefMut};

use super::{AdjacencyMatrix, Edge};

/// Wrapper/Smart Pointer around a nalgebra [`DMatrix`]
#[derive(Debug, PartialEq)]
pub struct NAMatrix(pub DMatrix<f64>);

impl Deref for NAMatrix {
    type Target = DMatrix<f64>;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

impl DerefMut for NAMatrix {
    fn deref_mut(&mut self) -> &mut Self::Target {
        &mut self.0
    }
}

impl From<&Graph> for NAMatrix {
    fn from(graph: &Graph) -> Self {
        //let vss: VecMatrix = graph.into();
        let dim = graph.num_vertices();
        let mut res = NAMatrix::from_dim(dim);
        for (i, neighbours) in graph.iter().enumerate() {
            for &Edge { to: j, cost } in neighbours.iter() {
                res[(i, j)] = cost;
            }
        }
        res
    }
}

//impl From<Graph> for NAMatrix {
//    fn from(value: Graph) -> Self {
//        <NAMatrix as From<&Graph>>::from(&value)
//    }
//}

impl AdjacencyMatrix for NAMatrix {
    fn from_dim(dim: usize) -> Self {
        let mut matrix = DMatrix::from_element(dim, dim, f64::INFINITY);
        matrix.set_diagonal(&DVector::repeat(dim, 0.));
        NAMatrix(matrix)
    }
    fn dim(&self) -> usize {
        self.shape().0
    }

    fn get(&self, row: usize, col: usize) -> f64 {
        self[(row, col)]
    }

    fn set(&mut self, row: usize, col: usize, cost: f64) {
        self[(row, col)] = cost;
    }
}

impl<T> From<&T> for NAMatrix
where
    T: AdjacencyMatrix,
{
    fn from(value: &T) -> Self {
        let dim = value.dim();

        let mut adj_matr = NAMatrix::from_dim(dim);
        for i in 0..dim {
            for j in 0..dim {
                adj_matr[(i, j)] = value.get(i, j);
            }
        }
        adj_matr
    }
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_namatrix_from_graph() {
        let graph: Graph = vec![
            vec![Edge { to: 1, cost: 2.5 }],
            vec![Edge { to: 0, cost: 2.5 }],
        ]
        .into();

        let expected: NAMatrix = NAMatrix(DMatrix::from_row_slice(2, 2, &[0., 2.5, 2.5, 0.]));

        assert_eq!(expected, (&graph).into());
    }
}