metric_tsp_approx

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)

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

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

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

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)

// visitor versions
template<typename VertexListGraph, typename TSPVertexVisitor>
void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)

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

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

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)

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.

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)

Where Defined

boost/graph/metric_tsp_approx.hpp

Parameters

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

The vertex that will be the start (and end) of the tour.
Default: *vertices(g).first

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.
Default: get(edge_weight, g)

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.
Default: get(vertex_index, g) Note: if you use this default, make sure your graph has an internal vertex_index property. For example, adjacenty_list with VertexList=listS does not have an internal vertex_index property.

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

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

Complexity

The time complexity is O(E log V).

Example

The file test/metric_tsp_approx.cpp contains an example of using this TSP approximation algorithm.

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.