1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
3 * This file is a part of LEMON, a generic C++ optimization library.
5 * Copyright (C) 2003-2010
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
19 #ifndef LEMON_CHRISTOFIDES_TSP_H
20 #define LEMON_CHRISTOFIDES_TSP_H
24 /// \brief Christofides algorithm for symmetric TSP
26 #include <lemon/full_graph.h>
27 #include <lemon/smart_graph.h>
28 #include <lemon/kruskal.h>
29 #include <lemon/matching.h>
30 #include <lemon/euler.h>
36 /// \brief Christofides algorithm for symmetric TSP.
38 /// ChristofidesTsp implements Christofides' heuristic for solving
39 /// symmetric \ref tsp "TSP".
41 /// This a well-known approximation method for the TSP problem with
42 /// metric cost function.
43 /// It yields a tour whose total cost is at most 3/2 of the optimum,
44 /// but it is usually much better.
45 /// This implementation runs in O(n<sup>3</sup>log(n)) time.
47 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
48 /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
49 /// in the subgraph induced by the nodes that have odd degree in the
51 /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
52 /// of the union of the spanning tree and the matching.
53 /// During this last step, the algorithm simply skips the visited nodes
54 /// (i.e. creates shortcuts) assuming that the triangle inequality holds
55 /// for the cost function.
57 /// \tparam CM Type of the cost map.
59 /// \warning CM::Value must be a signed number type.
60 template <typename CM>
65 /// Type of the cost map
67 /// Type of the edge costs
68 typedef typename CM::Value Cost;
72 GRAPH_TYPEDEFS(FullGraph);
76 std::vector<Node> _path;
81 /// \brief Constructor
84 /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
85 /// \param cost The cost map.
86 ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
87 : _gr(gr), _cost(cost) {}
89 /// \name Execution Control
92 /// \brief Runs the algorithm.
94 /// This function runs the algorithm.
96 /// \return The total cost of the found tour.
100 if (_gr.nodeNum() == 0) return _sum = 0;
101 else if (_gr.nodeNum() == 1) {
102 _path.push_back(_gr(0));
105 else if (_gr.nodeNum() == 2) {
106 _path.push_back(_gr(0));
107 _path.push_back(_gr(1));
108 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
111 // Compute min. cost spanning tree
112 std::vector<Edge> tree;
113 kruskal(_gr, _cost, std::back_inserter(tree));
115 FullGraph::NodeMap<int> deg(_gr, 0);
116 for (int i = 0; i != int(tree.size()); ++i) {
122 // Copy the induced subgraph of odd nodes
123 std::vector<Node> odd_nodes;
124 for (NodeIt u(_gr); u != INVALID; ++u) {
125 if (deg[u] % 2 == 1) odd_nodes.push_back(u);
129 SmartGraph::EdgeMap<Cost> scost(sgr);
130 for (int i = 0; i != int(odd_nodes.size()); ++i) {
133 for (int i = 0; i != int(odd_nodes.size()); ++i) {
134 for (int j = 0; j != int(odd_nodes.size()); ++j) {
135 if (j == i) continue;
137 sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
138 scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
142 // Compute min. cost perfect matching
143 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
147 for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
148 if (mwpm.matching(e)) {
149 tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
150 odd_nodes[sgr.id(sgr.v(e))]) );
154 // Join the spanning tree and the matching
156 for (int i = 0; i != _gr.nodeNum(); ++i) {
159 for (int i = 0; i != int(tree.size()); ++i) {
160 int ui = _gr.id(_gr.u(tree[i])),
161 vi = _gr.id(_gr.v(tree[i]));
162 sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
165 // Compute the tour from the Euler traversal
166 SmartGraph::NodeMap<bool> visited(sgr, false);
167 for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
168 SmartGraph::Node n = sgr.target(e);
170 _path.push_back(_gr(sgr.id(n)));
175 _sum = _cost[_gr.edge(_path.back(), _path.front())];
176 for (int i = 0; i < int(_path.size())-1; ++i) {
177 _sum += _cost[_gr.edge(_path[i], _path[i+1])];
185 /// \name Query Functions
188 /// \brief The total cost of the found tour.
190 /// This function returns the total cost of the found tour.
192 /// \pre run() must be called before using this function.
193 Cost tourCost() const {
197 /// \brief Returns a const reference to the node sequence of the
200 /// This function returns a const reference to a vector
201 /// that stores the node sequence of the found tour.
203 /// \pre run() must be called before using this function.
204 const std::vector<Node>& tourNodes() const {
208 /// \brief Gives back the node sequence of the found tour.
210 /// This function copies the node sequence of the found tour into
211 /// the given standard container.
213 /// \pre run() must be called before using this function.
214 template <typename Container>
215 void tourNodes(Container &container) const {
216 container.assign(_path.begin(), _path.end());
219 /// \brief Gives back the found tour as a path.
221 /// This function copies the found tour as a list of arcs/edges into
222 /// the given \ref concept::Path "path structure".
224 /// \pre run() must be called before using this function.
225 template <typename Path>
226 void tour(Path &path) const {
228 for (int i = 0; i < int(_path.size()) - 1; ++i) {
229 path.addBack(_gr.arc(_path[i], _path[i+1]));
231 if (int(_path.size()) >= 2) {
232 path.addBack(_gr.arc(_path.back(), _path.front()));
240 }; // namespace lemon