Loading...
Searching...
No Matches
ChristofidesTsp< CM > Class Template Reference
Algorithms » Traveling Salesman Problem

## Detailed Description

template<typename CM>
class lemon::ChristofidesTsp< CM >

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.

Template Parameters

  CM | Type of the cost map.

Warning
  CM::Value must be a signed number type.

`#include <lemon/christofides_tsp.h>`

## Public Types

typedef CM | CostMap
| Type of the cost map.
typedef CM::Value | Cost
| Type of the edge costs.

## Public Member Functions

| ChristofidesTsp (const FullGraph &gr, const CostMap &cost)
| Constructor.
Execution Control
Cost | run ()
| Runs the algorithm.
Query Functions
Cost | tourCost () const
| The total cost of the found tour.
const std::vector< Node > & | tourNodes () const
| Returns a const reference to the node sequence of the found tour.
template<typename Iterator>
void | tourNodes (Iterator out) const
| Gives back the node sequence of the found tour.
template<typename Path>
void | tour (Path &path) const
| Gives back the found tour as a path.

## Constructor & Destructor Documentation

## ChristofidesTsp()

template<typename CM>

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

inline

Constructor.

Parameters

  gr | The full graph the algorithm runs on.
  cost | The cost map.

## Member Function Documentation

## run()

template<typename CM>

Cost run | ( |  | ) |

inline

This function runs the algorithm.

Returns
  The total cost of the found tour.

## tourCost()

template<typename CM>

Cost tourCost | ( |  | ) | const

inline

This function returns the total cost of the found tour.

Precondition
  run() must be called before using this function.

## tourNodes() [1/2]

template<typename CM>

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

inline

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

Precondition
  run() must be called before using this function.

## tourNodes() [2/2]

template<typename CM>
template<typename Iterator>

void tourNodes | ( | Iterator | out | ) | const

inline

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());
lemon::countNodes
int countNodes(const Graph &g)
Function to count the nodes in the graph.
Definition core.h:252

or

std::list<FullGraph::Node> nodes;
tsp.tourNodes(std::back_inserter(nodes));

Precondition
  run() must be called before using this function.

## tour()

template<typename CM>
template<typename Path>

void tour | ( | Path & | path | ) | const

inline

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

Precondition
  run() must be called before using this function.