# Tspf
[](https://crates.io/crates/tspf) [](https://docs.rs/tspf) [](https://github.com/1crcbl/tspf-rs/actions/workflows/main.yml)
Tspf is a library for parsing the TSPLIB file format, a text-based file format often used in the research field of travelling salesman problem (TSP), vehicle routing problem and other related problems. Some well-known TSP solvers (e.g. [Concorde](http://www.math.uwaterloo.ca/tsp/concorde/index.html) or [LKH](http://webhotel4.ruc.dk/~keld/research/LKH/)) work mainly with this file format as inputs.
The parser is implemented based on the [documentation](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/) from the Department of Discrete and Combinatorial Optimization at Ruprecht-Karls-Universität Heidelberg.
The library can fully parse all problem datasets hosted on TSPLIB's [website](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/):
- [X] TSP - symmetric travelling salesman problem
- [X] HCP - Hamiltonian cycle problem
- [X] ATSP - asymmetric travelling salesman problem
- [X] SOP - sequential ordering problem
- [X] CVRP - capacitated vehicle routing problem
- [X] Tour - a collection of tours
Moreover, it also provides common metric functions to calculate edge weights (or cost/distance) between nodes in public interface. Among them are:
- [X] 2D- and 3D-Euclidean distance
- [X] 2D- and 3D-Manhattan distance
- [X] Geographical distance
This is a sister project from [cykl-rs](https://github.com/1crcbl/cykl-rs), a heuristic solver for TSP, which is still under-development.
## Usage
To parse an input string, we use the function ```parse_str``` from the struct ```TspBuilder```:
```rust
use tspf;
match TspBuilder::parse_str("some input string") {
Ok(tsp) => {
// tsp is an instance of struct Tsp.
// From tsp, one can access all data.
}
Err(e) => eprint!("{:?}", e),
}
```
On the other hand, the function ```parse_path``` handles the parsing from files:
```rust
use std::path::Path;
use tspf;
let path = ;
match TspBuilder::parse_path(Path::new("path/to/some_file.tsp")) {
Ok(tsp) => {
// tsp is an instance of struct Tsp.
// From tsp, one can access all data.
}
Err(e) => eprint!("{:?}", e),
}
```
**NOTES**:
- The files ```si175.tsp```, ```si535.tsp```, ```si1032.tsp``` from the TSP dataset require a small change: the type entry in the second line ```TYPE: TSP (M.~Hofmeister)``` is wrong according to the format definition. Instead, that line should simply be ```TYPE: TSP```.
- For the HCP dataset, the file ```alb4000.hcp``` has a wrong entry in line ```8005```. The line should reads ```FIXED_EDGES_SECTION```, instead ```FIXED_EDGES```.
## Datasets
The following list doesn't contain all test instance datasets used in academia. If you have any interesting datasets that are not included in the list, please let me know:
|TSPLIB Travelling salesman problem | [[Website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/tsp/)| Optimal solution: [[website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.html)|
|TSPLIB Asymmetric travelling salesman problem | [[Website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/atsp/)| Optimal solution: [[website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ATSP.html)|
|TSPLIB Hamiltonian cycle problem |[[Website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/hcp/)||
|FHCP Hamiltonian cycle challenge set |[[Website]](https://sites.flinders.edu.au/flinders-hamiltonian-cycle-project/fhcp-challenge-set/)||
|TSPLIB Sequential ordering problem |[[Website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/sop/)| Optimal solution: [[website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/SOP.html)|
|TSPLIB Capacitated vehicle routing problem |[[Website]](http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/vrp/)||
|Shortest tour to nearly every pub in UK| [[Website]](http://www.math.uwaterloo.ca/tsp/uk/index.html) [[Download]](http://www.math.uwaterloo.ca/tsp/uk/files/uk49687_geom.tsp.txt) | Distance function not yet implemented |
|Orienteering problem | [[Github]](https://github.com/bcamath-ds/OPLib/tree/master/instances) | Parser not yet implemented |
## License
Licensed under either of
* Apache License, Version 2.0
([LICENSE-APACHE](LICENSE-APACHE) or http://www.apache.org/licenses/LICENSE-2.0)
* MIT license
([LICENSE-MIT](LICENSE-MIT) or http://opensource.org/licenses/MIT)
at your option.
## Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.