Struct tspf::Tsp

pub struct Tsp { /* fields omitted */ }

Represents a parsed TSP dataset.

An instance of this struct can only be created through the use of TspBuilder.

TSP format has two parts:

• Specification part: contains metadata and general information about the dataset.
• Data part: contains all data stored according to the formats given in the specification part.

Format

The specification part has the following entries:

• NAME (required): the name of a dataset.
• TYPE (required): the type specifier of a dataset. Represented by the enum TspKind.
• COMMENT (optional): comments of a dataset.
• DIM (required): the dimension of a dataset.
• CAPACITY (required if TYPE is TspKind::Cvrp): the truck capacity in Capacitated Vehicle Routing Problem (CVRP).
• EDGE_WEIGHT_TYPE (required): indicates how the edge weights (or distances) are calculated. Represented by the enum WeightKind.
• EDGE_WEIGHT_FORMAT (required if EDGE_WEIGHT_TYPE is WeightKind::Explicit): specifies how the edge weights are given in the file. Represented by the enum WeightFormat.
• EDGE_DATA_FORMAT (optional): specifies how the edges of a graph are given in the file, if the graph is not complete. Represented by the enum EdgeFormat.
• NODE_COORD_TYPE (required if EDGE_WEIGHT_TYPE is not WeightKind::Explicit): specifies how the coordinate for each node is given in the file. Represented by the enum CoordKind.
• DISPLAY_DATA_TYPE (optional): spcifies how the coordinate for each node for display purpose is given in the file. Represented by the enum DisplayKind.

The data part has the following entries:

• NODE_COORD_SECTION (required if NODE_COORD_TYPE is not CoordKind::NoCoord): a list of node coordinates.
• DEPOT_SECTION (relevant for TspKind::Cvrp): a list of possible alternate nodes.
• DEMAND_SECTION (relevant for TspKind::Cvrp): a list of demands for all nodes. Each entry is a tuple (usize, usize), in which the first number is a node’s id and the second number represents the demand for that node. All depot nodes must be also included in this section and their demands are always 0.
• EDGE_DATA_SECTION: a list of edges.
• FIXED_EDGES_SECTION (optional): a list of edges that must be included in solutions to the problem.
• DISPLAY_DATA_SECTION (required if DISPLAY_DATA_TYPE is DisplayKind::Disp2d): a list of 2D node coordinates for display purpose.
• TOUR_SECTION: a collection of tours. Each tour is a sequence of node ids.
• EDGE_WEIGHT_SECTION(optional if EDGE_WEIGHT_FORMAT is WeightFormat::Function): node coordinates in a matrix form as dictated in EDGE_WEIGHT_FORMAT.

Example

The following example shows how to parse a TSP data from string with TspBuilder::parse_str:

let s = "
NAME: test
TYPE: TSP
COMMENT: Test
DIMENSION: 3
EDGE_WEIGHT_TYPE: GEO
DISPLAY_DATA_TYPE: COORD_DISPLAY
NODE_COORD_SECTION
1 38.24 20.42
2 39.57 26.15
3 40.56 25.32
EOF
";
let result = TspBuilder::parse_str(s);
assert!(result.is_ok());
let _ = result.unwrap();

We can also parse a file by calling the function TspBuilder::parse_path:

let path = Path::new("./test.tsp");
let result = TspBuilder::parse_path(path);
assert!(result.is_ok());

Implementations

impl Tsp

pub fn kind(&self) -> TspKind

Type specifier of the dataset.

Maps to the entry TYPE in the TSP format.

pub fn dim(&self) -> usize

The dimension of a dataset.

Maps to the entry DIMENSION in the TSP format.

pub fn capacity(&self) -> usize

The truck capacity for CVRP.

Maps to the entry CAPACITY in the TSP format.

pub fn weight_kind(&self) -> WeightKind

Specifier for how the edge weights are calculated.

Maps to the entry EDGE_WEIGHT_TYPE in the TSP format.

pub fn weight_format(&self) -> WeightFormat

Specifier for how the edge weights are stored in a file.

Maps to the entry EDGE_WEIGHT_FORMAT in the TSP format.

pub fn coord_kind(&self) -> CoordKind

Specifier for how the node coordinates are stored in a file.

Maps to the entry NODE_COORD_TYPE in the TSP format.

pub fn disp_kind(&self) -> DisplayKind

Specifier for how node coordinates for display purpose are stored in a file.

Maps to the entry DISPLAY_DATA_TYPE in the TSP format.

impl Tsp

pub fn name(&self) -> &String

Name of the dataset.

Maps to the entry NAME in the TSP format.

pub fn comment(&self) -> &String

Additional comments.

Maps to the entry COMMENT in the TSP format.

pub fn edge_format(&self) -> &EdgeFormat

Specifier for how the edges are stored in a file.

Maps to the entry EDGE_DATA_FORMAT in the TSP format.

pub fn node_coords(&self) -> &Vec<Point>

Vector of node coordinates, if available.

Maps to the entry NODE_COORD_SECTION in the TSP format.

pub fn depots(&self) -> &Vec<usize>

Vector of depot nodes’ id, if available.

Maps to the entry DEPOT_SECTION in the TSP format.

pub fn demands(&self) -> &Vec<(usize, usize)>

Vector of node demands, if available.

Maps to the entry DEMAND_SECTION in the TSP format.

pub fn fixed_edges(&self) -> &Vec<(usize, usize)>

Vector of edges that must appear in solutions to the problem.

Maps to the entry FIXED_EDGES_SECTION in the TSP format.

pub fn disp_coords(&self) -> &Vec<Point>

A vector of 2D node coordinates for display purpose, if available.

Maps to the entry DISPLAY_DATA_SECTION in the TSP format.

pub fn edge_weights(&self) -> &Vec<Vec<f64>>

Edge weights in a matrix form as stated in EDGE_WEIGHT_FORMAT, if available.

Maps to the entry EDGE_WEIGHT_SECTION in the TSP format.

pub fn tours(&self) -> &Vec<Vec<usize>>

A collection of tours (a sequence of nodes).

Maps to the entry TOUR_SECTION in the TSP format.

impl Tsp

pub fn weight(&self, a: usize, b: usize) -> f64

Returns the edge weight between two nodes.

Arguments

• a - index of the first node.
• b - index of the second node.

Trait Implementations

impl Debug for Tsp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Display for Tsp

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.