Changeset 1201:9a51db038228 in lemon for lemon/christofides_tsp.h
 Timestamp:
 01/08/11 22:51:16 (9 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/christofides_tsp.h
r1199 r1201 1 /* * mode: C++; indenttabsmode: nil; * 2 * 3 * This file is a part of LEMON, a generic C++ optimization library. 4 * 5 * Copyright (C) 20032010 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). 8 * 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. 12 * 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 15 * purpose. 16 * 17 */ 18 1 19 #ifndef LEMON_CHRISTOFIDES_TSP_H 2 20 #define LEMON_CHRISTOFIDES_TSP_H 3 21 22 /// \ingroup tsp 23 /// \file 24 /// \brief Christofides algorithm for symmetric TSP 25 4 26 #include <lemon/full_graph.h> 5 27 #include <lemon/smart_graph.h> 6 #include <lemon/path.h>7 28 #include <lemon/kruskal.h> 8 29 #include <lemon/matching.h> 9 #include <lemon/adaptors.h>10 #include <lemon/maps.h>11 30 #include <lemon/euler.h> 12 31 13 32 namespace lemon { 14 33 15 namespace christofides_helper { 16 template <class L> 17 L vectorConvert(const std::vector<FullGraph::Node> &_path) { 18 return L(_path.begin(), _path.end()); 19 } 20 21 template <> 22 std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) { 23 return _path; 24 } 25 } 26 34 /// \brief Christofides algorithm for symmetric TSP. 35 /// 36 /// ChristofidesTsp implements Christofides' heuristic for solving 37 /// symmetric \ref tsp "TSP". 38 /// 39 /// This a wellknown 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. 44 /// 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 48 /// spanning tree. 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. 54 /// 55 /// \tparam CM Type of the cost map. 56 /// 57 /// \warning \& CM::Value must be signed type. 27 58 template <typename CM> 28 class ChristofidesTsp { 59 class ChristofidesTsp 60 { 61 public: 62 63 /// Type of the cost map 64 typedef CM CostMap; 65 /// Type of the edge costs 66 typedef typename CM::Value Cost; 67 29 68 private: 30 GRAPH_TYPEDEFS(SmartGraph); 69 70 GRAPH_TYPEDEFS(FullGraph); 71 72 const FullGraph &_gr; 73 const CostMap &_cost; 74 std::vector<Node> _path; 75 Cost _sum; 31 76 32 77 public: 33 typedef typename CM::Value Cost; 34 typedef SmartGraph::EdgeMap<Cost> CostMap; 35 36 ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) { 37 graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run(); 38 } 39 78 79 /// \brief Constructor 80 /// 81 /// 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) {} 86 87 /// \name Execution Control 88 /// @{ 89 90 /// \brief Runs the algorithm. 91 /// 92 /// This function runs the algorithm. 93 /// 94 /// \return The total cost of the found tour. 40 95 Cost run() { 41 96 _path.clear(); 42 43 SmartGraph::EdgeMap<bool> tree(_gr); 44 kruskal(_gr, _cost, tree); 45 46 FilterEdges<SmartGraph> treefiltered(_gr, tree); 47 InDegMap<FilterEdges<SmartGraph> > deg(treefiltered); 48 49 SmartGraph::NodeMap<bool> oddfilter(_gr, false); 50 FilterNodes<SmartGraph> oddNodes(_gr, oddfilter); 51 52 for (NodeIt n(_gr); n!=INVALID; ++n) { 53 if (deg[n]%2 == 1) { 54 oddNodes.enable(n); 97 98 if (_gr.nodeNum() == 0) return _sum = 0; 99 else if (_gr.nodeNum() == 1) { 100 _path.push_back(_gr(0)); 101 return _sum = 0; 102 } 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))]; 107 } 108 109 // Compute min. cost spanning tree 110 std::vector<Edge> tree; 111 kruskal(_gr, _cost, std::back_inserter(tree)); 112 113 FullGraph::NodeMap<int> deg(_gr, 0); 114 for (int i = 0; i != int(tree.size()); ++i) { 115 Edge e = tree[i]; 116 ++deg[_gr.u(e)]; 117 ++deg[_gr.v(e)]; 118 } 119 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); 124 } 125 126 SmartGraph sgr; 127 SmartGraph::EdgeMap<Cost> scost(sgr); 128 for (int i = 0; i != int(odd_nodes.size()); ++i) { 129 sgr.addNode(); 130 } 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; 134 SmartGraph::Edge e = 135 sgr.addEdge(sgr.nodeFromId(i), sgr.nodeFromId(j)); 136 scost[e] = _cost[_gr.edge(odd_nodes[i], odd_nodes[j])]; 55 137 } 56 138 } 57 139 58 NegMap<CostMap> negmap(_cost); 59 MaxWeightedPerfectMatching<FilterNodes<SmartGraph>, 60 NegMap<CostMap> > perfmatch(oddNodes, negmap); 61 perfmatch.run(); 62 63 for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) { 64 if (perfmatch.matching(e)) { 65 treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(e))); 140 // Compute min. cost perfect matching 141 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> > 142 mwpm(sgr, scost); 143 mwpm.run(); 144 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))]) ); 66 149 } 67 150 } 68 151 69 FilterEdges<SmartGraph>::NodeMap<bool> seen(treefiltered, false); 70 for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) { 71 if (seen[treefiltered.target(e)]==false) { 72 _path.push_back(nr[treefiltered.target(e)]); 73 seen[treefiltered.target(e)] = true; 152 // Join the spanning tree and the matching 153 sgr.clear(); 154 for (int i = 0; i != _gr.nodeNum(); ++i) { 155 sgr.addNode(); 156 } 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)); 161 } 162 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); 167 if (!visited[n]) { 168 _path.push_back(_gr(sgr.id(n))); 169 visited[n] = true; 74 170 } 75 171 } 76 172 77 _sum = fullcost[ fullg.edge(_path.back(), _path.front()) ]; 78 for (unsigned int i=0; i<_path.size()1; ++i) 79 _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ]; 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])]; 176 } 80 177 81 178 return _sum; 82 179 } 83 180 84 template <typename L> 85 void tourNodes(L &container) { 86 container(christofides_helper::vectorConvert<L>(_path)); 87 } 88 89 template <template <typename> class L> 90 L<FullGraph::Node> tourNodes() { 91 return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path); 92 } 93 94 const std::vector<Node>& tourNodes() { 181 /// @} 182 183 /// \name Query Functions 184 /// @{ 185 186 /// \brief The total cost of the found tour. 187 /// 188 /// This function returns the total cost of the found tour. 189 /// 190 /// \pre run() must be called before using this function. 191 Cost tourCost() const { 192 return _sum; 193 } 194 195 /// \brief Returns a const reference to the node sequence of the 196 /// found tour. 197 /// 198 /// This function returns a const reference to the internal structure 199 /// that stores the node sequence of the found tour. 200 /// 201 /// \pre run() must be called before using this function. 202 const std::vector<Node>& tourNodes() const { 95 203 return _path; 96 204 } 97 98 Path<FullGraph> tour() { 99 Path<FullGraph> p; 100 if (_path.size()<2) 101 return p; 102 103 for (unsigned int i=0; i<_path.size()1; ++i) { 104 p.addBack(fullg.arc(_path[i], _path[i+1])); 105 } 106 p.addBack(fullg.arc(_path.back(), _path.front())); 107 108 return p; 109 } 110 111 Cost tourCost() { 112 return _sum; 113 } 114 115 116 private: 117 SmartGraph _gr; 118 CostMap _cost; 119 Cost _sum; 120 const FullGraph &fullg; 121 const CM &fullcost; 122 std::vector<FullGraph::Node> _path; 123 SmartGraph::NodeMap<FullGraph::Node> nr; 205 206 /// \brief Gives back the node sequence of the found tour. 207 /// 208 /// This function copies the node sequence of the found tour into 209 /// the given standard container. 210 /// 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()); 215 } 216 217 /// \brief Gives back the found tour as a path. 218 /// 219 /// This function copies the found tour as a list of arcs/edges into 220 /// the given \ref concept::Path "path structure". 221 /// 222 /// \pre run() must be called before using this function. 223 template <typename Path> 224 void tour(Path &path) const { 225 path.clear(); 226 for (int i = 0; i < int(_path.size())  1; ++i) { 227 path.addBack(_gr.arc(_path[i], _path[i+1])); 228 } 229 if (int(_path.size()) >= 2) { 230 path.addBack(_gr.arc(_path.back(), _path.front())); 231 } 232 } 233 234 /// @} 235 124 236 }; 125 237 126 127 238 }; // namespace lemon 128 239
Note: See TracChangeset
for help on using the changeset viewer.