Metric Traveling Salesperson Approximation

A traveling salesperson heuristic for generating a tour of vertices for a fully connected undirected graph with weighted edges that obey the triangle inequality.

Complexity: O(E log V)
Defined in: <boost/graph/metric_tsp_approx.hpp>

Example

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/metric_tsp_approx.hpp>
#include <iostream>
#include <vector>

struct Edge { double weight; };

using namespace boost;
using Graph = adjacency_list<vecS, vecS, undirectedS, no_property, Edge>;
using Vertex = graph_traits<Graph>::vertex_descriptor;

int main() {
    const int N = 4;
    Graph g(N);
    double w[][4] = {{0,10,15,20},{10,0,35,25},{15,35,0,30},{20,25,30,0}};
    for (int i = 0; i < N; ++i)
        for (int j = i + 1; j < N; ++j)
            add_edge(i, j, Edge{w[i][j]}, g);

    // Bundled weight via member pointer — the 3-arg overload of
    // metric_tsp_approx_tour takes an explicit WeightMap.
    std::vector<Vertex> tour;
    metric_tsp_approx_tour(g, get(&Edge::weight, g), std::back_inserter(tour));

    std::cout << "TSP tour:";
    for (auto v : tour) { std::cout << " " << v; }
    std::cout << "\n";
}

TSP tour: 0 1 2 3 0

(1) metric_tsp_approx_from_vertex (full)

template <typename VertexListGraph,
          typename WeightMap,
          typename VertexIndexMap,
          typename TSPVertexVisitor>
void metric_tsp_approx_from_vertex(
    const VertexListGraph& g,
    typename graph_traits<VertexListGraph>::vertex_descriptor start,
    WeightMap weightmap,
    VertexIndexMap indexmap,
    TSPVertexVisitor vis);

Direction Parameter Description

Direction	Parameter	Description
IN	`const VertexListGraph& g`	An undirected graph. The type `VertexListGraph` must be a model of Vertex List Graph and Incidence Graph [2].
IN	`vertex_descriptor start`	The vertex that will be the start (and end) of the tour.
IN	`WeightMap weightmap`	The weight of each edge in the graph. The type `WeightMap` must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map.
IN	`VertexIndexMap indexmap`	This maps each vertex to an integer in the range `[0, num_vertices(g))`. This is necessary for efficient updates of the heap data structure when an edge is relaxed. The type `VertexIndexMap` must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.
OUT	`TSPVertexVisitor vis`	Use this to specify actions that you would like to happen when the algorithm visits a vertex of the tour. The type `TSPVertexVisitor` must be a model of the TSP Tour Visitor concept. The visitor object is passed by value [1].

const VertexListGraph& g

An undirected graph. The type VertexListGraph must be a model of Vertex List Graph and Incidence Graph [2].

vertex_descriptor start

The vertex that will be the start (and end) of the tour.

WeightMap weightmap

The weight of each edge in the graph. The type WeightMap must be a model of Readable Property Map. The edge descriptor type of the graph needs to be usable as the key type for the weight map.

VertexIndexMap indexmap

This maps each vertex to an integer in the range [0, num_vertices(g)). This is necessary for efficient updates of the heap data structure when an edge is relaxed. The type VertexIndexMap must be a model of Readable Property Map. The value type of the map must be an integer type. The vertex descriptor type of the graph needs to be usable as the key type of the map.

OUT

TSPVertexVisitor vis

Use this to specify actions that you would like to happen when the algorithm visits a vertex of the tour. The type TSPVertexVisitor must be a model of the TSP Tour Visitor concept. The visitor object is passed by value [1].

(2) metric_tsp_approx_tour (2 args)

template <typename VertexListGraph,
          typename OutputIterator>
void metric_tsp_approx_tour(
    VertexListGraph& g,
    OutputIterator o);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
OUT	`OutputIterator o`	The OutputIterator holds the vertices of the tour. The type `OutputIterator` must be a model of the OutputIterator concept.

VertexListGraph& g

An undirected graph (see (1)).

OUT

OutputIterator o

The OutputIterator holds the vertices of the tour. The type OutputIterator must be a model of the OutputIterator concept.

(3) metric_tsp_approx_tour (3 args)

template <typename VertexListGraph,
          typename WeightMap,
          typename OutputIterator>
void metric_tsp_approx_tour(
    VertexListGraph& g,
    WeightMap w,
    OutputIterator o);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`WeightMap w`	Edge weight map (see (1) `WeightMap weightmap`).
OUT	`OutputIterator o`	Output iterator for the tour vertices (see (2)).

VertexListGraph& g

An undirected graph (see (1)).

WeightMap w

Edge weight map (see (1) WeightMap weightmap).

OUT

OutputIterator o

Output iterator for the tour vertices (see (2)).

(4) metric_tsp_approx_tour_from_vertex (3 args)

template <typename VertexListGraph,
          typename OutputIterator>
void metric_tsp_approx_tour_from_vertex(
    VertexListGraph& g,
    typename graph_traits<VertexListGraph>::vertex_descriptor start,
    OutputIterator o);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`vertex_descriptor start`	The vertex that will be the start (and end) of the tour.
OUT	`OutputIterator o`	Output iterator for the tour vertices (see (2)).

VertexListGraph& g

An undirected graph (see (1)).

vertex_descriptor start

The vertex that will be the start (and end) of the tour.

OUT

OutputIterator o

Output iterator for the tour vertices (see (2)).

(5) metric_tsp_approx_tour_from_vertex (4 args)

template <typename VertexListGraph,
          typename WeightMap,
          typename OutputIterator>
void metric_tsp_approx_tour_from_vertex(
    VertexListGraph& g,
    typename graph_traits<VertexListGraph>::vertex_descriptor start,
    WeightMap w,
    OutputIterator o);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`vertex_descriptor start`	The vertex that will be the start (and end) of the tour.
IN	`WeightMap w`	Edge weight map (see (1) `WeightMap weightmap`).
OUT	`OutputIterator o`	Output iterator for the tour vertices (see (2)).

VertexListGraph& g

An undirected graph (see (1)).

vertex_descriptor start

The vertex that will be the start (and end) of the tour.

WeightMap w

Edge weight map (see (1) WeightMap weightmap).

OUT

OutputIterator o

Output iterator for the tour vertices (see (2)).

(6) metric_tsp_approx (visitor, 2 args)

template <typename VertexListGraph,
          typename TSPVertexVisitor>
void metric_tsp_approx(
    VertexListGraph& g,
    TSPVertexVisitor vis);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
OUT	`TSPVertexVisitor vis`	Visitor invoked at each tour vertex (see (1) `TSPVertexVisitor vis`).

VertexListGraph& g

An undirected graph (see (1)).

OUT

TSPVertexVisitor vis

Visitor invoked at each tour vertex (see (1) TSPVertexVisitor vis).

(7) metric_tsp_approx (visitor, 3 args)

template <typename VertexListGraph,
          typename Weightmap,
          typename VertexIndexMap,
          typename TSPVertexVisitor>
void metric_tsp_approx(
    VertexListGraph& g,
    Weightmap w,
    TSPVertexVisitor vis);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`Weightmap w`	Edge weight map (see (1) `WeightMap weightmap`).
OUT	`TSPVertexVisitor vis`	Visitor invoked at each tour vertex (see (1) `TSPVertexVisitor vis`).

VertexListGraph& g

An undirected graph (see (1)).

Weightmap w

Edge weight map (see (1) WeightMap weightmap).

OUT

TSPVertexVisitor vis

Visitor invoked at each tour vertex (see (1) TSPVertexVisitor vis).

(8) metric_tsp_approx (visitor, 4 args)

template <typename VertexListGraph,
          typename WeightMap,
          typename VertexIndexMap,
          typename TSPVertexVisitor>
void metric_tsp_approx(
    VertexListGraph& g,
    WeightMap w,
    VertexIndexMap id,
    TSPVertexVisitor vis);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`WeightMap w`	Edge weight map (see (1) `WeightMap weightmap`).
IN	`VertexIndexMap id`	Vertex index map (see (1) `VertexIndexMap indexmap`).
OUT	`TSPVertexVisitor vis`	Visitor invoked at each tour vertex (see (1) `TSPVertexVisitor vis`).

VertexListGraph& g

An undirected graph (see (1)).

WeightMap w

Edge weight map (see (1) WeightMap weightmap).

VertexIndexMap id

Vertex index map (see (1) VertexIndexMap indexmap).

OUT

TSPVertexVisitor vis

Visitor invoked at each tour vertex (see (1) TSPVertexVisitor vis).

(9) metric_tsp_approx_from_vertex (visitor, 4 args)

template <typename VertexListGraph,
          typename WeightMap,
          typename TSPVertexVisitor>
void metric_tsp_approx_from_vertex(
    VertexListGraph& g,
    typename graph_traits<VertexListGraph>::vertex_descriptor start,
    WeightMap w,
    TSPVertexVisitor vis);

Direction Parameter Description

Direction	Parameter	Description
IN	`VertexListGraph& g`	An undirected graph (see (1)).
IN	`vertex_descriptor start`	The vertex that will be the start (and end) of the tour.
IN	`WeightMap w`	Edge weight map (see (1) `WeightMap weightmap`).
OUT	`TSPVertexVisitor vis`	Visitor invoked at each tour vertex (see (1) `TSPVertexVisitor vis`).

VertexListGraph& g

An undirected graph (see (1)).

vertex_descriptor start

The vertex that will be the start (and end) of the tour.

WeightMap w

Edge weight map (see (1) WeightMap weightmap).

OUT

TSPVertexVisitor vis

Visitor invoked at each tour vertex (see (1) TSPVertexVisitor vis).

Description

This is a traveling salesperson heuristic for generating a tour of vertices for a fully connected undirected graph with weighted edges that obey the triangle inequality. The current implementation is based off of the algorithm presented in Introduction to Algorithms on page 1029. This implementation generates solutions that are twice as long as the optimal tour in the worst case. The pseudo-code is listed below.

Pseudo-Code

TSP-APPROX(G, w)
  select a vertex r in V[G]
  compute a minimum spanning tree T for G from root r
    using PRIM-MST(G, r, w)
  let L be the list of vertices visited in a preorder traversal of T
  return (the Hamiltonian cycle H that visites the vertices in the order L)

The overloads that do not accept a start vertex use *vertices(g).first as the default starting vertex. The overloads that do not accept a WeightMap use get(edge_weight, g) as the default. The overloads that do not accept a VertexIndexMap use get(vertex_index, g) as the default — if you use this default, make sure your graph has an internal vertex_index property (for example, adjacency_list with VertexList=listS does not have an internal vertex_index property).

Notes

[1] Since the visitor parameter is passed by value, if your visitor contains state then any changes to the state during the algorithm will be made to a copy of the visitor object, not the visitor object passed in. Therefore you may want the visitor to hold this state by pointer or reference.

[2] Passing an adjacency_list with a vertex not set selected by vecS will result in O(n²) performance.

Edit this Page