elkai_rs/
lib.rs

1//! elkai-rs is a rust library for solving travelling salesman problems (TSP) based on elkai (LKH 3)   
2//!
3//!  ----
4//!  
5//!  * **based on [elkai](https://github.com/fikisipi/elkai) by fikisipi** **([LKH](http://akira.ruc.dk/~keld/research/LKH/) by Keld Helsgaun)**: with proven optimal solutions up to N=315 and more accurate results than [Google's OR tools](https://developers.google.com/optimization/routing/tsp)
6//!  * **asymmetric and symmetric** [travelling salesman problems](https://en.wikipedia.org/wiki/Travelling_salesman_problem) support
7//!  * **clean and simple API**: get results with one line calls
8//!  
9//!  ## Example usage
10//!  
11//!  ```rust
12//!  use std::collections::HashMap;
13//!  use elkai_rs::Coordinates2D;
14//!  
15//!  fn main() {
16//!      let cities = Coordinates2D::new(HashMap::from_iter([
17//!          ("city1", (0.0, 0.0)),
18//!          ("city2", (0.0, 4.0)),
19//!          ("city3", (5.0, 0.0))
20//!      ]));
21//!      println!("{:?}", cities.solve(10));
22//!  }
23//!  ```
24//!  
25//!  ```rust
26//!  use elkai_rs::DistanceMatrix;
27//!  
28//!  fn main() {
29//!      let cities = DistanceMatrix::new(vec![
30//!          vec![0, 4, 0],
31//!          vec![0, 0, 5],
32//!          vec![0, 0, 0]
33//!      ]);
34//!      println!("{:?}", cities.solve(10));
35//!  }
36//!  ```
37//!  
38//!  ## License
39//!  
40//!  The LKH native code by Helsgaun is released for non-commercial use only. Therefore the same restriction applies to elkai-rs, which is explained in the `LICENSE` file. 
41//!  
42//!  ## How it works internally
43//!  
44//!  * We link the C api of elkai to Rust with [cc-rs](https://github.com/rust-lang/cc-rs).
45//!  
46//!  ⚠️ elkai-rs takes a **global mutex** (just like what elkai did) during the solving phase which means two threads cannot solve problems at the same time. If you want to run other workloads at the same time, you have to run another process.
47
48#![allow(private_bounds)]
49use libc::{c_uchar, size_t, c_int};
50use std::{collections::HashMap, sync::Mutex};
51
52extern "C" {
53    fn _solve_problem(paramsStr: *const c_uchar, problemStr: *const c_uchar, toursize: *mut size_t, msg_buf: *mut u8) -> *mut c_int;
54}
55
56static ELKAI_MUTEX: Mutex<[u8; 1024]> = Mutex::new([0; 1024]);
57
58fn elkai_solve_problem(param: &str, problem: &str) -> Vec<usize> {
59    assert!(param.ends_with('\0') && problem.ends_with('\0'), "input string must end with '\\0'");
60
61    let mut toursize: usize = 0;
62
63    let mut msg_buf = ELKAI_MUTEX.lock().unwrap();
64    
65    let raw_pointer = unsafe {
66        _solve_problem(
67            param.as_ptr(),
68            problem.as_ptr(),
69            &mut toursize as *mut size_t,
70            msg_buf.as_mut_ptr()
71        )
72    };
73    if raw_pointer == std::ptr::null_mut() {
74        panic!("{}", String::from_iter(msg_buf.iter().map(|x| *x as char).take_while(|c| *c != '\0')))
75    }
76    let res = unsafe {
77        &*std::ptr::slice_from_raw_parts(raw_pointer, toursize)
78    }.iter().map(|e| (*e - 1) as usize).collect();
79    
80    drop(msg_buf);
81    
82    res
83}
84
85fn is_2d_matrix<T>(m: &Vec<Vec<T>>) -> bool {
86    let dim = m.len();
87    m.iter().map(|e| e.len()).all(|l| l == dim)
88}
89
90fn is_symmetric_matrix<T: PartialEq>(m: &Vec<Vec<T>>) -> bool {
91    let n = m.len();
92    for i in 0..n {
93        for j in 0..n {
94            if m[i][j] != m[j][i] {
95                return false;
96            }
97        }
98    }
99    return true;
100}
101
102trait Num: num_traits::Num + std::fmt::Display {}
103macro_rules! num_trait_impl { ($name:ident for $($t:ty)*) => ($(impl $name for $t {})*) }
104num_trait_impl!(Num for usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64);
105impl<T: num_traits::Num + std::fmt::Display> Num for std::num::Wrapping<T>
106where std::num::Wrapping<T>: num_traits::NumOps {}
107
108/// solve problem with original LKH input as strings
109/// `param`: content of *.par file
110/// `param`: content of *.[a]tsp file
111/// note to set `PROBLEM_FILE = :stdin:` if use arg `problem`.
112pub fn lkh_solve(mut param: String, mut problem: String) -> Vec<usize> {
113    if !param.ends_with('\0') { param.push('\0'); }
114    if !problem.ends_with('\0') { problem.push('\0'); }
115    elkai_solve_problem(&param, &problem)
116}
117
118/// A structure representing a matrix of float/int weights/distances.
119/// ## Example usage
120/// 
121/// ```rust
122/// use elkai_rs::DistanceMatrix;
123/// 
124/// fn main() {
125///     let cities = DistanceMatrix::new(vec![
126///         vec![0, 4, 0],
127///         vec![0, 0, 5],
128///         vec![0, 0, 0]
129///     ]);
130///     println!("{:?}", cities.solve(10));
131/// }
132/// ```
133pub struct DistanceMatrix<T: Num> {
134    distances: Vec<Vec<T>>
135}
136
137impl<T: Num> DistanceMatrix<T> {
138    /// Creates the matrix structure representing a list of lists (2D matrix) of floats/ints.
139    pub fn new(distances: Vec<Vec<T>>) -> Self {
140        assert!(is_2d_matrix(&distances), "distances must be a 2D matrix");
141        DistanceMatrix {
142            distances
143        }
144    }
145
146    /// Returns a list of indices that represent the TSP tour. You can adjust solver iterations with the runs parameter.
147    pub fn solve(&self, runs: usize) -> Vec<usize> {
148        assert!(runs >= 1, "runs must be a positive integer");
149        let dimension = self.distances.len();
150        assert!(dimension >= 3, "dimension must be at least 3");
151        let param = format!("RUNS = {runs}\nPROBLEM_FILE = :stdin:\n\0");
152        let problem_type = if is_symmetric_matrix(&self.distances) {"TSP"} else {"ATSP"};
153        let mut problem = format!("TYPE : {problem_type}\nDIMENSION : {dimension}\nEDGE_WEIGHT_TYPE : EXPLICIT\nEDGE_WEIGHT_FORMAT : FULL_MATRIX\nEDGE_WEIGHT_SECTION\n");
154        for row in &self.distances {
155            problem.push_str(&row.iter().map(T::to_string).collect::<Vec<_>>().join(" "));
156            problem.push('\n');
157        }
158        problem.push('\0');
159        elkai_solve_problem(&param, &problem)
160    }
161}
162
163/// A structure representing coordinates of type {'city name': (x, y), ...}
164/// ## Example usage
165///  
166///  ```rust
167///  use std::collections::HashMap;
168///  use elkai_rs::Coordinates2D;
169///  
170///  fn main() {
171///      let cities = Coordinates2D::new(HashMap::from_iter([
172///          ("city1", (0.0, 0.0)),
173///          ("city2", (0.0, 4.0)),
174///          ("city3", (5.0, 0.0))
175///      ]));
176///      println!("{:?}", cities.solve(10));
177///  }
178///  ```
179pub struct Coordinates2D<'a, T: Num> {
180    coords: HashMap<&'a str, (T, T)>
181}
182
183impl<'a, T: Num> Coordinates2D<'a, T> {
184    /// Creates the structure representing coordinates of type {'city name': (x, y), ...}
185    pub fn new(coords: HashMap<&'a str, (T, T)>) -> Self {
186        assert!(coords.len() >= 3, "there must be at least 3 cities");
187        Coordinates2D { coords }
188    }
189
190    /// Returns a list of city names in the order of the TSP tour. You can adjust solver iterations with the runs parameter.
191    pub fn solve(&self, runs: usize) -> Vec<&'a str> {
192        assert!(runs >= 1, "runs must be a positive integer");
193        let keys: Vec<&&str> = self.coords.keys().collect();
194        
195        let keys_to_numbers: HashMap<&&&str, usize> = HashMap::from_iter(keys.iter().enumerate()
196            .map(|(i, k)| (k, i + 1)));
197        let numbers_to_keys: HashMap<usize, &&&str> = HashMap::from_iter(keys.iter().enumerate());
198
199        let dimension = keys.len();
200        let param = format!("RUNS = {runs}\nPROBLEM_FILE = :stdin:\n\0");
201        let mut problem = format!("TYPE : TSP\nDIMENSION : {dimension}\nEDGE_WEIGHT_TYPE : EUC_2D\nNODE_COORD_SECTION\n");
202        for (key, num) in keys_to_numbers.iter() {
203            let (x1, x2) = &self.coords[***key];
204            problem.push_str(&format!("{num} {x1} {x2}\n"));
205        }
206        problem.push('\0');
207
208        elkai_solve_problem(&param, &problem).into_iter().map(|num| {
209            **numbers_to_keys[&num]
210        }).collect()
211    }
212}
213
214#[cfg(test)]
215mod test {
216    use std::{collections::HashMap, io::Read};
217    use crate::{elkai_solve_problem, lkh_solve, Coordinates2D, DistanceMatrix, Num};
218
219    #[test]
220    fn elkai_str() {
221        let param = "RUNS = 10\nPROBLEM_FILE = :stdin:\n\0".to_string();
222        let problem = "TYPE : ATSP\nDIMENSION : 3\nEDGE_WEIGHT_TYPE : EXPLICIT\nEDGE_WEIGHT_FORMAT : FULL_MATRIX\nEDGE_WEIGHT_SECTION\n0 4 0\n0 0 5\n0 0 0\n\0".to_string();
223        println!("{:?} ", elkai_solve_problem(&param, &problem));
224    }
225
226    #[test]
227    fn dis_mat() {
228        let s = DistanceMatrix::new(vec![
229            vec![0, 4, 0],
230            vec![0, 0, 5],
231            vec![0, 0, 0]
232        ]);
233        println!("{:?}", s.solve(10));
234    }
235
236    #[test]
237    fn coordinates2d() {
238        let s = Coordinates2D::new(HashMap::from_iter([
239            ("city1", (0.0, 0.0)),
240            ("city2", (0.0, 4.0)),
241            ("city3", (5.0, 0.0))
242        ]));
243        println!("{:?}", s.solve(10));
244    }
245
246    fn coords_result(coords: &HashMap<&str, (f64, f64)>, solution: &Vec<&str>) -> f64 {
247        fn dis(a: (f64, f64), b: (f64, f64)) -> f64 {
248            ((a.0 - b.0).powi(2) + (a.1 - b.1).powi(2)).sqrt()
249        }
250        let mut res = (1..solution.len()).into_iter().map(|i| {
251            dis(coords[solution[i-1]], coords[solution[i]])
252        }).sum::<f64>();
253        res += dis(coords[*solution.last().unwrap()], coords[*solution.first().unwrap()]);
254        res
255    }
256
257    #[test]
258    fn pr2392() {
259        use text_io::scan;
260
261        let mut s = String::new();
262        std::fs::File::open("LKH-3.0.8/pr2392.tsp").unwrap().read_to_string(&mut s).unwrap();
263        let start = s.find("NODE_COORD_SECTION").unwrap() + "NODE_COORD_SECTION".len();
264        let end = s.rfind("EOF").unwrap();
265
266        let (mut k, mut v) = (vec![], vec![]);
267        for line in s[start..end].trim().lines() {
268            let (idx, x, y): (usize, f64, f64);
269            scan!(line.bytes() => "{} {} {}", idx, x, y);
270            k.push(idx.to_string());
271            v.push((x, y));
272        }
273
274        let coords: HashMap<&str, (f64, f64)> = HashMap::from_iter(k.iter().zip(v).map(|(k, v)| (k.as_str(), v)));
275        let s = Coordinates2D::new(coords.clone());
276        let solution = s.solve(10);
277        println!("{:?}", solution);
278        println!("{:?}", coords_result(&coords, &solution))
279    }
280
281    fn distances_result<T: Num + std::iter::Sum + Copy + std::ops::AddAssign>(distances: &Vec<Vec<T>>, solution: &Vec<usize>) -> T {
282        let mut res = (1..solution.len()).into_iter().map(|i| {
283            // distances[solution[i - 1]][solution[i]]
284            match distances.get(solution[i - 1]) {
285                Some(d1) => match d1.get(solution[i]) {
286                    Some(&d) => d,
287                    _ => T::zero()
288                },
289                _ => T::zero()
290            }
291        }).sum::<T>();
292        res += distances[*solution.last().unwrap()][*solution.first().unwrap()];
293        res
294    }
295
296    #[test]
297    fn whizzkids96() {
298        let mut problem = String::new();
299        std::fs::File::open("LKH-3.0.8/whizzkids96.atsp").unwrap().read_to_string(&mut problem).unwrap();
300        let mut param = String::new();
301        std::fs::File::open("LKH-3.0.8/whizzkids96.par").unwrap().read_to_string(&mut param).unwrap();
302        param = param.replace("whizzkids96.atsp", ":stdin:");
303
304        let start = problem.find("EDGE_WEIGHT_SECTION").unwrap() + "EDGE_WEIGHT_SECTION".len();
305        let distances = problem[start..].trim().lines().map(|line| line.split(' ').filter_map(|e| {
306            let e = e.trim();
307            match e.is_empty() {
308                true => None,
309                false => Some(e.parse::<usize>().unwrap()),
310            }
311        }).collect::<Vec<_>>()).collect::<Vec<_>>();
312
313        let solution = lkh_solve(param, problem);
314        println!("{:?}", solution);
315        println!("{:?}", distances_result(&distances, &solution));
316    }
317}
elkai_rs/lib.rs

elkai_rs/
lib.rs
