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>
34 /// \brief Christofides algorithm for symmetric TSP.
36 /// ChristofidesTsp implements Christofides' heuristic for solving
37 /// symmetric \ref tsp "TSP".
39 /// This a well-known approximation method for the TSP problem with
40 /// \ref checkMetricCost() "metric cost function".
41 /// It yields a tour whose total cost is at most 3/2 of the optimum,
42 /// but it is usually much better.
43 /// This implementation runs in O(n<sup>3</sup>log(n)) time.
45 /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and
46 /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching"
47 /// in the subgraph induced by the nodes that have odd degree in the
49 /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal"
50 /// of the union of the spanning tree and the matching.
51 /// During this last step, the algorithm simply skips the visited nodes
52 /// (i.e. creates shortcuts) assuming that the triangle inequality holds
53 /// for the cost function.
55 /// \tparam CM Type of the cost map.
57 /// \warning \& CM::Value must be signed type.
58 template <typename CM>
63 /// Type of the cost map
65 /// Type of the edge costs
66 typedef typename CM::Value Cost;
70 GRAPH_TYPEDEFS(FullGraph);
74 std::vector<Node> _path;
79 /// \brief Constructor
82 /// \param gr The \ref FullGraph "full graph" the algorithm runs on.
83 /// \param cost The cost map.
84 ChristofidesTsp(const FullGraph &gr, const CostMap &cost)
85 : _gr(gr), _cost(cost) {}
87 /// \name Execution Control
90 /// \brief Runs the algorithm.
92 /// This function runs the algorithm.
94 /// \return The total cost of the found tour.
98 if (_gr.nodeNum() == 0) return _sum = 0;
99 else if (_gr.nodeNum() == 1) {
100 _path.push_back(_gr(0));
103 else if (_gr.nodeNum() == 2) {
104 _path.push_back(_gr(0));
105 _path.push_back(_gr(1));
106 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))];
109 // Compute min. cost spanning tree
110 std::vector<Edge> tree;
111 kruskal(_gr, _cost, std::back_inserter(tree));
113 FullGraph::NodeMap<int> deg(_gr, 0);
114 for (int i = 0; i != int(tree.size()); ++i) {
120 // Copy the induced subgraph of odd nodes
121 std::vector<Node> odd_nodes;
122 for (NodeIt u(_gr); u != INVALID; ++u) {
123 if (deg[u] % 2 == 1) odd_nodes.push_back(u);
127 SmartGraph::EdgeMap<Cost> scost(sgr);
128 for (int i = 0; i != int(odd_nodes.size()); ++i) {
131 for (int i = 0; i != int(odd_nodes.size()); ++i) {
132 for (int j = 0; j != int(odd_nodes.size()); ++j) {
133 if (j == i) continue;
135 sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j));
136 scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])];
140 // Compute min. cost perfect matching
141 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> >
145 for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) {
146 if (mwpm.matching(e)) {
147 tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))],
148 odd_nodes[sgr.id(sgr.v(e))]) );
152 // Join the spanning tree and the matching
154 for (int i = 0; i != _gr.nodeNum(); ++i) {
157 for (int i = 0; i != int(tree.size()); ++i) {
158 int ui = _gr.id(_gr.u(tree[i])),
159 vi = _gr.id(_gr.v(tree[i]));
160 sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi));
163 // Compute the tour from the Euler traversal
164 SmartGraph::NodeMap<bool> visited(sgr, false);
165 for (EulerIt<SmartGraph> e(sgr); e != INVALID; ++e) {
166 SmartGraph::Node n = sgr.target(e);
168 _path.push_back(_gr(sgr.id(n)));
173 _sum = _cost[_gr.edge(_path.back(), _path.front())];
174 for (int i = 0; i < int(_path.size())-1; ++i) {
175 _sum += _cost[_gr.edge(_path[i], _path[i+1])];
183 /// \name Query Functions
186 /// \brief The total cost of the found tour.
188 /// This function returns the total cost of the found tour.
190 /// \pre run() must be called before using this function.
191 Cost tourCost() const {
195 /// \brief Returns a const reference to the node sequence of the
198 /// This function returns a const reference to the internal structure
199 /// that stores the node sequence of the found tour.
201 /// \pre run() must be called before using this function.
202 const std::vector<Node>& tourNodes() const {
206 /// \brief Gives back the node sequence of the found tour.
208 /// This function copies the node sequence of the found tour into
209 /// the given standard container.
211 /// \pre run() must be called before using this function.
212 template <typename Container>
213 void tourNodes(Container &container) const {
214 container.assign(_path.begin(), _path.end());
217 /// \brief Gives back the found tour as a path.
219 /// This function copies the found tour as a list of arcs/edges into
220 /// the given \ref concept::Path "path structure".
222 /// \pre run() must be called before using this function.
223 template <typename Path>
224 void tour(Path &path) const {
226 for (int i = 0; i < int(_path.size()) - 1; ++i) {
227 path.addBack(_gr.arc(_path[i], _path[i+1]));
229 if (int(_path.size()) >= 2) {
230 path.addBack(_gr.arc(_path.back(), _path.front()));
238 }; // namespace lemon