Changeset 1270:dceba191c00d in lemon for lemon/christofides_tsp.h
 Timestamp:
 08/09/13 11:28:17 (6 years ago)
 Branch:
 default
 Children:
 1271:fb1c7da561ce, 1381:e0ccc1f0268f
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/christofides_tsp.h
r1250 r1270 3 3 * This file is a part of LEMON, a generic C++ optimization library. 4 4 * 5 * Copyright (C) 2003201 05 * Copyright (C) 20032013 6 6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport 7 7 * (Egervary Research Group on Combinatorial Optimization, EGRES). … … 31 31 32 32 namespace lemon { 33 33 34 34 /// \ingroup tsp 35 35 /// … … 109 109 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; 110 110 } 111 111 112 112 // Compute min. cost spanning tree 113 113 std::vector<Edge> tree; 114 114 kruskal(_gr, _cost, std::back_inserter(tree)); 115 115 116 116 FullGraph::NodeMap<int> deg(_gr, 0); 117 117 for (int i = 0; i != int(tree.size()); ++i) { … … 126 126 if (deg[u] % 2 == 1) odd_nodes.push_back(u); 127 127 } 128 128 129 129 SmartGraph sgr; 130 130 SmartGraph::EdgeMap<Cost> scost(sgr); … … 140 140 } 141 141 } 142 142 143 143 // Compute min. cost perfect matching 144 144 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> > 145 145 mwpm(sgr, scost); 146 146 mwpm.run(); 147 147 148 148 for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) { 149 149 if (mwpm.matching(e)) { … … 152 152 } 153 153 } 154 155 // Join the spanning tree and the matching 154 155 // Join the spanning tree and the matching 156 156 sgr.clear(); 157 157 for (int i = 0; i != _gr.nodeNum(); ++i) { … … 183 183 184 184 /// @} 185 185 186 186 /// \name Query Functions 187 187 /// @{ 188 188 189 189 /// \brief The total cost of the found tour. 190 190 /// … … 195 195 return _sum; 196 196 } 197 197 198 198 /// \brief Returns a const reference to the node sequence of the 199 199 /// found tour. … … 228 228 std::copy(_path.begin(), _path.end(), out); 229 229 } 230 230 231 231 /// \brief Gives back the found tour as a path. 232 232 /// … … 245 245 } 246 246 } 247 247 248 248 /// @} 249 249 250 250 }; 251 251
Note: See TracChangeset
for help on using the changeset viewer.