ChristofidesTsp

Declared in lemon/christofides_tsp.h, in the group Traveling Salesman Problem; the same class on the Doxygen site.

template< typename CM >
class ChristofidesTsp

Christofides algorithm for symmetric TSP.

ChristofidesTsp implements Christofides’ heuristic for solving symmetric TSP.

This a well-known approximation method for the TSP problem with metric cost function. It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour whose total cost is at most 3/2 of the optimum), but it usually provides better solutions in practice. This implementation runs in O(n3log(n)) time.

The algorithm starts with a minimum cost spanning tree and finds a minimum cost perfect matching in the subgraph induced by the nodes that have odd degree in the spanning tree. Finally, it constructs the tour from the Euler traversal of the union of the spanning tree and the matching. During this last step, the algorithm simply skips the visited nodes (i.e. creates shortcuts) assuming that the triangle inequality holds for the cost function.

Warning

CM::Value must be a signed number type.

Template Parameters:

CM – Type of the cost map.

Execution Control

inline Cost run()

Runs the algorithm.

This function runs the algorithm.

Returns:

The total cost of the found tour.

Query Functions

inline Cost tourCost() const

The total cost of the found tour.

This function returns the total cost of the found tour.

Pre:

run() must be called before using this function.

inline const std::vector< Node > & tourNodes() const

Returns a const reference to the node sequence of the found tour.

This function returns a const reference to a vector that stores the node sequence of the found tour.

Pre:

run() must be called before using this function.

template< typename Iterator >
inline void tourNodes( Iterator out ) const

Gives back the node sequence of the found tour.

This function copies the node sequence of the found tour into an STL container through the given output iterator. The value_type of the container must be FullGraph::Node. For example,

std::vector< FullGraph::Node > nodes( countNodes( graph ) );
tsp.tourNodes( nodes.begin() );
or
std::list< FullGraph::Node > nodes;
tsp.tourNodes( std::back_inserter( nodes ) );

Pre:

run() must be called before using this function.

template< typename Path >
inline void tour( Path & path ) const

Gives back the found tour as a path.

This function copies the found tour as a list of arcs/edges into the given path structure.

Pre:

run() must be called before using this function.

Public Types

typedef CM CostMap

Type of the cost map.

typedef CM::Value Cost

Type of the edge costs.

Public Functions

inline ChristofidesTsp( const FullGraph & gr , const CostMap & cost )

Constructor.

Parameters:
  • gr – The full graph the algorithm runs on.

  • cost – The cost map.