kpeter@1033: /* -*- mode: C++; indent-tabs-mode: nil; -*- kpeter@1033: * kpeter@1033: * This file is a part of LEMON, a generic C++ optimization library. kpeter@1033: * kpeter@1033: * Copyright (C) 2003-2010 kpeter@1033: * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport kpeter@1033: * (Egervary Research Group on Combinatorial Optimization, EGRES). kpeter@1033: * kpeter@1033: * Permission to use, modify and distribute this software is granted kpeter@1033: * provided that this copyright notice appears in all copies. For kpeter@1033: * precise terms see the accompanying LICENSE file. kpeter@1033: * kpeter@1033: * This software is provided "AS IS" with no warranty of any kind, kpeter@1033: * express or implied, and with no claim as to its suitability for any kpeter@1033: * purpose. kpeter@1033: * kpeter@1033: */ kpeter@1033: f4c3@1031: #ifndef LEMON_CHRISTOFIDES_TSP_H f4c3@1031: #define LEMON_CHRISTOFIDES_TSP_H f4c3@1031: kpeter@1033: /// \ingroup tsp kpeter@1033: /// \file kpeter@1033: /// \brief Christofides algorithm for symmetric TSP kpeter@1033: f4c3@1031: #include f4c3@1031: #include f4c3@1031: #include f4c3@1031: #include f4c3@1031: #include f4c3@1031: f4c3@1031: namespace lemon { f4c3@1031: kpeter@1034: /// \ingroup tsp kpeter@1034: /// kpeter@1033: /// \brief Christofides algorithm for symmetric TSP. kpeter@1033: /// kpeter@1033: /// ChristofidesTsp implements Christofides' heuristic for solving kpeter@1033: /// symmetric \ref tsp "TSP". kpeter@1033: /// kpeter@1033: /// This a well-known approximation method for the TSP problem with kpeter@1034: /// metric cost function. kpeter@1036: /// It has a guaranteed approximation factor of 3/2 (i.e. it finds a tour kpeter@1036: /// whose total cost is at most 3/2 of the optimum), but it usually kpeter@1036: /// provides better solutions in practice. kpeter@1033: /// This implementation runs in O(n3log(n)) time. kpeter@1033: /// kpeter@1033: /// The algorithm starts with a \ref spantree "minimum cost spanning tree" and kpeter@1033: /// finds a \ref MaxWeightedPerfectMatching "minimum cost perfect matching" kpeter@1033: /// in the subgraph induced by the nodes that have odd degree in the kpeter@1033: /// spanning tree. kpeter@1033: /// Finally, it constructs the tour from the \ref EulerIt "Euler traversal" kpeter@1033: /// of the union of the spanning tree and the matching. kpeter@1033: /// During this last step, the algorithm simply skips the visited nodes kpeter@1033: /// (i.e. creates shortcuts) assuming that the triangle inequality holds kpeter@1033: /// for the cost function. kpeter@1033: /// kpeter@1033: /// \tparam CM Type of the cost map. kpeter@1033: /// kpeter@1034: /// \warning CM::Value must be a signed number type. f4c3@1031: template kpeter@1033: class ChristofidesTsp kpeter@1033: { kpeter@1033: public: kpeter@1033: kpeter@1033: /// Type of the cost map kpeter@1033: typedef CM CostMap; kpeter@1033: /// Type of the edge costs kpeter@1033: typedef typename CM::Value Cost; kpeter@1033: f4c3@1031: private: kpeter@1033: kpeter@1033: GRAPH_TYPEDEFS(FullGraph); kpeter@1033: kpeter@1033: const FullGraph &_gr; kpeter@1033: const CostMap &_cost; kpeter@1033: std::vector _path; kpeter@1033: Cost _sum; f4c3@1031: f4c3@1031: public: f4c3@1031: kpeter@1033: /// \brief Constructor kpeter@1033: /// kpeter@1033: /// Constructor. kpeter@1033: /// \param gr The \ref FullGraph "full graph" the algorithm runs on. kpeter@1033: /// \param cost The cost map. kpeter@1033: ChristofidesTsp(const FullGraph &gr, const CostMap &cost) kpeter@1033: : _gr(gr), _cost(cost) {} kpeter@1033: kpeter@1033: /// \name Execution Control kpeter@1033: /// @{ kpeter@1033: kpeter@1033: /// \brief Runs the algorithm. kpeter@1033: /// kpeter@1033: /// This function runs the algorithm. kpeter@1033: /// kpeter@1033: /// \return The total cost of the found tour. f4c3@1031: Cost run() { f4c3@1031: _path.clear(); kpeter@1033: kpeter@1033: if (_gr.nodeNum() == 0) return _sum = 0; kpeter@1033: else if (_gr.nodeNum() == 1) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: return _sum = 0; kpeter@1033: } kpeter@1033: else if (_gr.nodeNum() == 2) { kpeter@1033: _path.push_back(_gr(0)); kpeter@1033: _path.push_back(_gr(1)); kpeter@1033: return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; kpeter@1033: } f4c3@1031: kpeter@1033: // Compute min. cost spanning tree kpeter@1033: std::vector tree; kpeter@1033: kruskal(_gr, _cost, std::back_inserter(tree)); f4c3@1031: kpeter@1033: FullGraph::NodeMap deg(_gr, 0); kpeter@1033: for (int i = 0; i != int(tree.size()); ++i) { kpeter@1033: Edge e = tree[i]; kpeter@1033: ++deg[_gr.u(e)]; kpeter@1033: ++deg[_gr.v(e)]; kpeter@1033: } kpeter@1033: kpeter@1033: // Copy the induced subgraph of odd nodes kpeter@1033: std::vector odd_nodes; kpeter@1033: for (NodeIt u(_gr); u != INVALID; ++u) { kpeter@1033: if (deg[u] % 2 == 1) odd_nodes.push_back(u); kpeter@1033: } kpeter@1033: kpeter@1033: SmartGraph sgr; kpeter@1033: SmartGraph::EdgeMap scost(sgr); kpeter@1033: for (int i = 0; i != int(odd_nodes.size()); ++i) { kpeter@1033: sgr.addNode(); kpeter@1033: } kpeter@1033: for (int i = 0; i != int(odd_nodes.size()); ++i) { kpeter@1033: for (int j = 0; j != int(odd_nodes.size()); ++j) { kpeter@1033: if (j == i) continue; kpeter@1033: SmartGraph::Edge e = kpeter@1033: sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j)); kpeter@1033: scost[e] = -_cost[_gr.edge(odd_nodes[i], odd_nodes[j])]; f4c3@1031: } f4c3@1031: } f4c3@1031: kpeter@1033: // Compute min. cost perfect matching kpeter@1033: MaxWeightedPerfectMatching > kpeter@1033: mwpm(sgr, scost); kpeter@1033: mwpm.run(); f4c3@1031: kpeter@1033: for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) { kpeter@1033: if (mwpm.matching(e)) { kpeter@1033: tree.push_back( _gr.edge(odd_nodes[sgr.id(sgr.u(e))], kpeter@1033: odd_nodes[sgr.id(sgr.v(e))]) ); f4c3@1031: } f4c3@1031: } f4c3@1031: kpeter@1033: // Join the spanning tree and the matching kpeter@1033: sgr.clear(); kpeter@1033: for (int i = 0; i != _gr.nodeNum(); ++i) { kpeter@1033: sgr.addNode(); kpeter@1033: } kpeter@1033: for (int i = 0; i != int(tree.size()); ++i) { kpeter@1033: int ui = _gr.id(_gr.u(tree[i])), kpeter@1033: vi = _gr.id(_gr.v(tree[i])); kpeter@1033: sgr.addEdge(sgr.nodeFromId(ui), sgr.nodeFromId(vi)); kpeter@1033: } kpeter@1033: kpeter@1033: // Compute the tour from the Euler traversal kpeter@1033: SmartGraph::NodeMap visited(sgr, false); kpeter@1033: for (EulerIt e(sgr); e != INVALID; ++e) { kpeter@1033: SmartGraph::Node n = sgr.target(e); kpeter@1033: if (!visited[n]) { kpeter@1033: _path.push_back(_gr(sgr.id(n))); kpeter@1033: visited[n] = true; f4c3@1031: } f4c3@1031: } f4c3@1031: kpeter@1033: _sum = _cost[_gr.edge(_path.back(), _path.front())]; kpeter@1033: for (int i = 0; i < int(_path.size())-1; ++i) { kpeter@1033: _sum += _cost[_gr.edge(_path[i], _path[i+1])]; kpeter@1033: } f4c3@1031: f4c3@1031: return _sum; f4c3@1031: } f4c3@1031: kpeter@1033: /// @} f4c3@1031: kpeter@1033: /// \name Query Functions kpeter@1033: /// @{ f4c3@1031: kpeter@1033: /// \brief The total cost of the found tour. kpeter@1033: /// kpeter@1033: /// This function returns the total cost of the found tour. kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: Cost tourCost() const { f4c3@1031: return _sum; f4c3@1031: } f4c3@1031: kpeter@1033: /// \brief Returns a const reference to the node sequence of the kpeter@1033: /// found tour. kpeter@1033: /// kpeter@1034: /// This function returns a const reference to a vector kpeter@1033: /// that stores the node sequence of the found tour. kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: const std::vector& tourNodes() const { kpeter@1033: return _path; kpeter@1033: } f4c3@1031: kpeter@1033: /// \brief Gives back the node sequence of the found tour. kpeter@1033: /// kpeter@1033: /// This function copies the node sequence of the found tour into kpeter@1037: /// an STL container through the given output iterator. The kpeter@1037: /// value_type of the container must be FullGraph::Node. kpeter@1037: /// For example, kpeter@1037: /// \code kpeter@1037: /// std::vector nodes(countNodes(graph)); kpeter@1037: /// tsp.tourNodes(nodes.begin()); kpeter@1037: /// \endcode kpeter@1037: /// or kpeter@1037: /// \code kpeter@1037: /// std::list nodes; kpeter@1037: /// tsp.tourNodes(std::back_inserter(nodes)); kpeter@1037: /// \endcode kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1037: template kpeter@1037: void tourNodes(Iterator out) const { kpeter@1037: std::copy(_path.begin(), _path.end(), out); kpeter@1033: } kpeter@1033: kpeter@1033: /// \brief Gives back the found tour as a path. kpeter@1033: /// kpeter@1033: /// This function copies the found tour as a list of arcs/edges into kpeter@1033: /// the given \ref concept::Path "path structure". kpeter@1033: /// kpeter@1033: /// \pre run() must be called before using this function. kpeter@1033: template kpeter@1033: void tour(Path &path) const { kpeter@1033: path.clear(); kpeter@1033: for (int i = 0; i < int(_path.size()) - 1; ++i) { kpeter@1033: path.addBack(_gr.arc(_path[i], _path[i+1])); kpeter@1033: } kpeter@1033: if (int(_path.size()) >= 2) { kpeter@1033: path.addBack(_gr.arc(_path.back(), _path.front())); kpeter@1033: } kpeter@1033: } kpeter@1033: kpeter@1033: /// @} kpeter@1033: f4c3@1031: }; f4c3@1031: f4c3@1031: }; // namespace lemon f4c3@1031: f4c3@1031: #endif