Crate concorde_rs
source ·Expand description
A Rust binding to Concorde TSP Solver that allows for directly calling the solver instead of communicating the problem via TSP.lib file. At the moment, this package only supports the call to two routines of the Concorde TSP Solver:
solver::tsp_hk
: Held-Karp dynamic programming algorithmsolver::tsp_lk
: Lin-Kernighan heuristic
Examples
If values for lower distance matrix are provided:
use concorde_rs::{solver, LowerDistanceMatrix};
let dist_mat =
LowerDistanceMatrix::new(5, vec![0, 3, 0, 4, 4, 0, 2, 6, 5, 0, 7, 3, 8, 6, 0]);
assert_eq!(solver::tsp_hk(&dist_mat).unwrap().length, 19);
If values for lower distance matrix are not provided:
use concorde_rs::{solver, Distance, LowerDistanceMatrix};
struct Node(i32, i32);
impl Distance for Node {
fn calc_shortest_dist(&self, other: &Self) -> u32 {
self.0.abs_diff(other.0) + self.1.abs_diff(other.1)
}
}
let nodes: Vec<Node> = vec![Node(0, 0), Node(0, 3), Node(5, 6), Node(9, 1)];
let dist_mat = LowerDistanceMatrix::from(nodes.as_ref());
let solution = solver::tsp_hk(&dist_mat).unwrap();
assert_eq!(solution.length, 30);
Re-exports
pub use distance::Distance;
pub use distance::LowerDistanceMatrix;
pub use solver::Solution;
Modules
- The interface for all available solvers.