Struct Tour

pub struct Tour<T: Metrizable> {
    pub path: Vec<T>,
}

Represents a solution to the tsp for the items T

Fields

path: Vec<T>

Implementations

impl<T: Metrizable + Clone + Borrow<T>> Tour<T>

pub fn new() -> Tour<T>

Returns a new, empty Tour

Example

use tsp_rs::Tour;
use tsp_rs::point::Point;

let tour: Tour<Point> = Tour::new();

pub fn from(nodes: &Vec<T>) -> Tour<T>

where T: Clone,

Returns a tour from nodes: Vec<T> passed in where the tour is nodes[0] -> nodes[1] -> … nodes[nodes.len() - 1] -> nodes[0]

Example

use tsp_rs::Tour;
use tsp_rs::point::Point;

let nodes = vec![
    Point::new(0., 0.),
    Point::new(1., 0.),
    Point::new(1., 1.),
    Point::new(0., 1.),
];

let tour = Tour::from(&nodes);

pub fn tour_len(&self) -> f64

Returns the length of a tour.

Example

let tour = Tour::from(&some_points); let total_cost = tour.tour_len();

pub fn optimize_kopt(&mut self, timeout: Duration)

Improves the tour in place using the 2opt heuristic (with 3opt kicks if it gets stuck)

Examples

use std::time;

use tsp_rs::Tour;
use tsp_rs::point::Point;

let nodes = vec![
    Point::new(0., 0.),
    Point::new(1., 0.),
    Point::new(1., 1.),
    Point::new(0., 1.),
];

let mut tour = Tour::from(&nodes);

tour.optimize_kopt(time::Duration::from_secs(1));

pub fn optimize_nn(&mut self)

where T: Metrizable + Clone,

Constructs a tour inplace using the nearest neighbor heuristic

Examples

use tsp_rs::Tour;
use tsp_rs::point::Point;

let nodes = vec![
    Point::new(0., 0.),
    Point::new(1., 0.),
    Point::new(1., 1.),
    Point::new(0., 1.),
];

let mut tour = Tour::from(&nodes);

tour.optimize_nn();

Trait Implementations

impl<T: Clone + Metrizable> Clone for Tour<T>

fn clone(&self) -> Tour<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug + Metrizable> Debug for Tour<T>

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

Formats the value using the given formatter.

impl<T: PartialEq + Metrizable> PartialEq for Tour<T>

fn eq(&self, other: &Tour<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Metrizable> StructuralPartialEq for Tour<T>