|
1 /* -*- mode: C++; indent-tabs-mode: nil; -*- |
|
2 * |
|
3 * This file is a part of LEMON, a generic C++ optimization library. |
|
4 * |
|
5 * Copyright (C) 2003-2010 |
|
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 #ifndef LEMON_CHRISTOFIDES_TSP_H |
19 #ifndef LEMON_CHRISTOFIDES_TSP_H |
2 #define LEMON_CHRISTOFIDES_TSP_H |
20 #define LEMON_CHRISTOFIDES_TSP_H |
3 |
21 |
|
22 /// \ingroup tsp |
|
23 /// \file |
|
24 /// \brief Christofides algorithm for symmetric TSP |
|
25 |
4 #include <lemon/full_graph.h> |
26 #include <lemon/full_graph.h> |
5 #include <lemon/smart_graph.h> |
27 #include <lemon/smart_graph.h> |
6 #include <lemon/path.h> |
|
7 #include <lemon/kruskal.h> |
28 #include <lemon/kruskal.h> |
8 #include <lemon/matching.h> |
29 #include <lemon/matching.h> |
9 #include <lemon/adaptors.h> |
|
10 #include <lemon/maps.h> |
|
11 #include <lemon/euler.h> |
30 #include <lemon/euler.h> |
12 |
31 |
13 namespace lemon { |
32 namespace lemon { |
14 |
33 |
15 namespace christofides_helper { |
34 /// \brief Christofides algorithm for symmetric TSP. |
16 template <class L> |
35 /// |
17 L vectorConvert(const std::vector<FullGraph::Node> &_path) { |
36 /// ChristofidesTsp implements Christofides' heuristic for solving |
18 return L(_path.begin(), _path.end()); |
37 /// symmetric \ref tsp "TSP". |
19 } |
38 /// |
20 |
39 /// This a well-known approximation method for the TSP problem with |
21 template <> |
40 /// \ref checkMetricCost() "metric cost function". |
22 std::vector<FullGraph::Node> vectorConvert(const std::vector<FullGraph::Node> &_path) { |
41 /// It yields a tour whose total cost is at most 3/2 of the optimum, |
23 return _path; |
42 /// but it is usually much better. |
24 } |
43 /// This implementation runs in O(n<sup>3</sup>log(n)) time. |
25 } |
44 /// |
26 |
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 template <typename CM> |
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 private: |
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 public: |
77 public: |
33 typedef typename CM::Value Cost; |
78 |
34 typedef SmartGraph::EdgeMap<Cost> CostMap; |
79 /// \brief Constructor |
35 |
80 /// |
36 ChristofidesTsp(const FullGraph &gr, const CM &cost) : _cost(_gr), fullg(gr), fullcost(cost), nr(_gr) { |
81 /// Constructor. |
37 graphCopy(gr, _gr).nodeCrossRef(nr).edgeMap(cost, _cost).run(); |
82 /// \param gr The \ref FullGraph "full graph" the algorithm runs on. |
38 } |
83 /// \param cost The cost map. |
39 |
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 Cost run() { |
95 Cost run() { |
41 _path.clear(); |
96 _path.clear(); |
42 |
97 |
43 SmartGraph::EdgeMap<bool> tree(_gr); |
98 if (_gr.nodeNum() == 0) return _sum = 0; |
44 kruskal(_gr, _cost, tree); |
99 else if (_gr.nodeNum() == 1) { |
45 |
100 _path.push_back(_gr(0)); |
46 FilterEdges<SmartGraph> treefiltered(_gr, tree); |
101 return _sum = 0; |
47 InDegMap<FilterEdges<SmartGraph> > deg(treefiltered); |
102 } |
48 |
103 else if (_gr.nodeNum() == 2) { |
49 SmartGraph::NodeMap<bool> oddfilter(_gr, false); |
104 _path.push_back(_gr(0)); |
50 FilterNodes<SmartGraph> oddNodes(_gr, oddfilter); |
105 _path.push_back(_gr(1)); |
51 |
106 return _sum = 2 * _cost[_gr.edge(_gr(0), _gr(1))]; |
52 for (NodeIt n(_gr); n!=INVALID; ++n) { |
107 } |
53 if (deg[n]%2 == 1) { |
108 |
54 oddNodes.enable(n); |
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); |
140 // Compute min. cost perfect matching |
59 MaxWeightedPerfectMatching<FilterNodes<SmartGraph>, |
141 MaxWeightedPerfectMatching<SmartGraph, SmartGraph::EdgeMap<Cost> > |
60 NegMap<CostMap> > perfmatch(oddNodes, negmap); |
142 mwpm(sgr, scost); |
61 perfmatch.run(); |
143 mwpm.run(); |
62 |
144 |
63 for (FilterNodes<SmartGraph>::EdgeIt e(oddNodes); e!=INVALID; ++e) { |
145 for (SmartGraph::EdgeIt e(sgr); e != INVALID; ++e) { |
64 if (perfmatch.matching(e)) { |
146 if (mwpm.matching(e)) { |
65 treefiltered.enable(_gr.addEdge(_gr.u(e), _gr.v(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); |
152 // Join the spanning tree and the matching |
70 for (EulerIt<FilterEdges<SmartGraph> > e(treefiltered); e!=INVALID; ++e) { |
153 sgr.clear(); |
71 if (seen[treefiltered.target(e)]==false) { |
154 for (int i = 0; i != _gr.nodeNum(); ++i) { |
72 _path.push_back(nr[treefiltered.target(e)]); |
155 sgr.addNode(); |
73 seen[treefiltered.target(e)] = true; |
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()) ]; |
173 _sum = _cost[_gr.edge(_path.back(), _path.front())]; |
78 for (unsigned int i=0; i<_path.size()-1; ++i) |
174 for (int i = 0; i < int(_path.size())-1; ++i) { |
79 _sum += fullcost[ fullg.edge(_path[i], _path[i+1]) ]; |
175 _sum += _cost[_gr.edge(_path[i], _path[i+1])]; |
|
176 } |
80 |
177 |
81 return _sum; |
178 return _sum; |
82 } |
179 } |
83 |
180 |
84 template <typename L> |
181 /// @} |
85 void tourNodes(L &container) { |
182 |
86 container(christofides_helper::vectorConvert<L>(_path)); |
183 /// \name Query Functions |
87 } |
184 /// @{ |
88 |
185 |
89 template <template <typename> class L> |
186 /// \brief The total cost of the found tour. |
90 L<FullGraph::Node> tourNodes() { |
187 /// |
91 return christofides_helper::vectorConvert<L<FullGraph::Node> >(_path); |
188 /// This function returns the total cost of the found tour. |
92 } |
189 /// |
93 |
190 /// \pre run() must be called before using this function. |
94 const std::vector<Node>& tourNodes() { |
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 return _path; |
203 return _path; |
96 } |
204 } |
97 |
205 |
98 Path<FullGraph> tour() { |
206 /// \brief Gives back the node sequence of the found tour. |
99 Path<FullGraph> p; |
207 /// |
100 if (_path.size()<2) |
208 /// This function copies the node sequence of the found tour into |
101 return p; |
209 /// the given standard container. |
102 |
210 /// |
103 for (unsigned int i=0; i<_path.size()-1; ++i) { |
211 /// \pre run() must be called before using this function. |
104 p.addBack(fullg.arc(_path[i], _path[i+1])); |
212 template <typename Container> |
105 } |
213 void tourNodes(Container &container) const { |
106 p.addBack(fullg.arc(_path.back(), _path.front())); |
214 container.assign(_path.begin(), _path.end()); |
107 |
215 } |
108 return p; |
216 |
109 } |
217 /// \brief Gives back the found tour as a path. |
110 |
218 /// |
111 Cost tourCost() { |
219 /// This function copies the found tour as a list of arcs/edges into |
112 return _sum; |
220 /// the given \ref concept::Path "path structure". |
113 } |
221 /// |
114 |
222 /// \pre run() must be called before using this function. |
115 |
223 template <typename Path> |
116 private: |
224 void tour(Path &path) const { |
117 SmartGraph _gr; |
225 path.clear(); |
118 CostMap _cost; |
226 for (int i = 0; i < int(_path.size()) - 1; ++i) { |
119 Cost _sum; |
227 path.addBack(_gr.arc(_path[i], _path[i+1])); |
120 const FullGraph &fullg; |
228 } |
121 const CM &fullcost; |
229 if (int(_path.size()) >= 2) { |
122 std::vector<FullGraph::Node> _path; |
230 path.addBack(_gr.arc(_path.back(), _path.front())); |
123 SmartGraph::NodeMap<FullGraph::Node> nr; |
231 } |
|
232 } |
|
233 |
|
234 /// @} |
|
235 |
124 }; |
236 }; |
125 |
237 |
126 |
|
127 }; // namespace lemon |
238 }; // namespace lemon |
128 |
239 |
129 #endif |
240 #endif |