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
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

//! This module defines basic datastructures for this crate.
mod nalgebra;
mod vecmatrix;

/// Adjacency list based on TSPLIB-XML
pub use crate::parser::{Edge, Graph, Vertex};

#[cfg(feature = "mpi")]
use mpi::traits::*;

/// Defines properties/functions, that an adjacency matrix of a graph has.
pub trait AdjacencyMatrix {
    /// Creates an unconnected graph with `dim` many vertices
    fn from_dim(dim: usize) -> Self;

    /// The dimension of the matrix
    fn dim(&self) -> usize;

    /// Value extraction
    fn get(&self, row: usize, col: usize) -> f64;

    /// Set the cost of an edge `row <-> col`.
    fn set(&mut self, row: usize, col: usize, cost: f64);

    /// Evaluates the accumulative path cost given the current underlying graph
    fn evaluate_path(&self, path: &Path) -> f64 {
        let n = path.len();
        if n <= 1 {
            return 0.0;
        }
        let mut acc = 0.0;
        for from in 0..(n - 1) {
            let to = from + 1;
            let cost = self.get(path[from], path[to]);
            acc += cost;
        }
        acc
    }

    /// Evaluates the accumulative circle path cost given the current underlying graph
    /// This is equivalent to `GraphMatrix.evaluate_path` + returning to the initial vertex
    fn evaluate_circle(&self, path: &Path) -> f64 {
        if path.len() <= 1 {
            return 0.0;
        }
        let last_edge = self.get(*path.last().unwrap(), *path.first().unwrap());
        let path_cost = self.evaluate_path(path);
        path_cost + last_edge
    }

    /// checks, if the triangle inequality holds:
    /// `cost(i,j) <= cost(i,k) + cost(k,j)` for all i,j,k
    fn is_metric(&self) -> bool {
        let dim = self.dim();
        for i in 0..dim {
            for j in i..dim {
                let direct_cost = self.get(i, j);
                for k in 0..dim {
                    let indirect_cost = self.get(i, k) + self.get(k, j);
                    // sometimes due to rounding errors a metric graph would be rejected.
                    // By adding 1e-10 to indirect_costs,
                    // small rounding errors are being ignored
                    if direct_cost > indirect_cost + 1e-10 {
                        return false;
                    }
                }
            }
        }
        true
    }
}

/// Represents a path in a graph.
pub type Path = Vec<usize>;
/// Represents the solution to a TSP instance:
///
/// `Solution(solution_weight, solution_cycle)`
pub type Solution = (f64, Vec<usize>);

/// Naive Matrix implementation with `Vec<Vec<>>`
pub use crate::datastructures::vecmatrix::VecMatrix;

/// nalgebra DMatrix based implementation
pub use crate::datastructures::nalgebra::NAMatrix;

/// helper for MPI calls to send both some accumulated cost and the rank who calculated it
/// See either [`static_mpi_solver_generic`] or [`dynamic_mpi_solver`]
#[derive(Default, Clone, Copy, Equivalence)]
#[cfg(feature = "mpi")]
pub struct MPICostRank(pub f64, pub mpi::topology::Rank);

/// helper for MPI calls to send both the global minimum cost and the next path to compute
/// See [`dynamic_mpi_solver_generic`]
#[derive(Default, Clone, Copy, Equivalence)]
#[cfg(feature = "mpi")]
pub struct MPICostPath(pub f64, pub [usize; 3]);

#[cfg(test)]
mod test {
    use super::*;
    use ::nalgebra::DMatrix;

    /// 1 -3.- 2
    /// |     /
    /// |    /
    /// 1.  1.
    /// |  /
    /// | /
    /// 3
    ///
    /// violates the triangle inequality: 1 - 3 - 2 is shorter than 1 - 2
    #[test]
    fn test_triangle_inequality_check_fails() {
        let graph = NAMatrix(DMatrix::from_row_slice(
            3,
            3,
            &[0., 3., 1., 3., 0., 1., 1., 1., 0.],
        ));
        assert!(!graph.is_metric());
    }

    /// 1 -0.3- 2
    /// |     /
    /// |    /
    /// 0.1  0.2
    /// |  /
    /// | /
    /// 3
    ///
    /// triangle inequality holds
    #[test]
    fn test_triangle_inequality_check_succedes() {
        let graph = NAMatrix(DMatrix::from_row_slice(
            3,
            3,
            &[0., 0.3, 0.1, 0.3, 0., 0.2, 0.1, 0.2, 0.],
        ));
        assert!(graph.is_metric());
    }
}