]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | |
2 | //======================================================================= | |
3 | // Copyright 2008 | |
4 | // Author: Matyas W Egyhazy | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | //======================================================================= | |
10 | ||
11 | #ifndef BOOST_GRAPH_METRIC_TSP_APPROX_HPP | |
12 | #define BOOST_GRAPH_METRIC_TSP_APPROX_HPP | |
13 | ||
14 | // metric_tsp_approx | |
15 | // Generates an approximate tour solution for the traveling salesperson | |
16 | // problem in polynomial time. The current algorithm guarantees a tour with a | |
17 | // length at most as long as 2x optimal solution. The graph should have | |
18 | // 'natural' (metric) weights such that the triangle inequality is maintained. | |
19 | // Graphs must be fully interconnected. | |
20 | ||
21 | // TODO: | |
22 | // There are a couple of improvements that could be made. | |
23 | // 1) Change implementation to lower uppper bound Christofides heuristic | |
24 | // 2) Implement a less restrictive TSP heuristic (one that does not rely on | |
25 | // triangle inequality). | |
26 | // 3) Determine if the algorithm can be implemented without creating a new | |
27 | // graph. | |
28 | ||
29 | #include <vector> | |
30 | ||
31 | #include <boost/shared_ptr.hpp> | |
32 | #include <boost/concept_check.hpp> | |
33 | #include <boost/graph/graph_traits.hpp> | |
34 | #include <boost/graph/graph_as_tree.hpp> | |
35 | #include <boost/graph/adjacency_list.hpp> | |
36 | #include <boost/graph/prim_minimum_spanning_tree.hpp> | |
37 | #include <boost/graph/lookup_edge.hpp> | |
38 | #include <boost/throw_exception.hpp> | |
39 | ||
40 | namespace boost | |
41 | { | |
f67539c2 TL |
42 | // Define a concept for the concept-checking library. |
43 | template < typename Visitor, typename Graph > struct TSPVertexVisitorConcept | |
44 | { | |
45 | private: | |
46 | Visitor vis_; | |
7c673cae | 47 | |
f67539c2 TL |
48 | public: |
49 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
7c673cae | 50 | |
f67539c2 | 51 | BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept) |
7c673cae | 52 | { |
f67539c2 TL |
53 | Visitor vis(vis_); // require copy construction |
54 | Graph g(1); | |
55 | Vertex v(*vertices(g).first); | |
56 | vis.visit_vertex(v, g); // require visit_vertex | |
57 | } | |
58 | }; | |
7c673cae | 59 | |
f67539c2 TL |
60 | // Tree visitor that keeps track of a preorder traversal of a tree |
61 | // TODO: Consider migrating this to the graph_as_tree header. | |
62 | // TODO: Parameterize the underlying stores so it doesn't have to be a vector. | |
63 | template < typename Node, typename Tree > class PreorderTraverser | |
64 | { | |
65 | private: | |
66 | std::vector< Node >& path_; | |
7c673cae | 67 | |
f67539c2 TL |
68 | public: |
69 | typedef typename std::vector< Node >::const_iterator const_iterator; | |
7c673cae | 70 | |
f67539c2 | 71 | PreorderTraverser(std::vector< Node >& p) : path_(p) {} |
7c673cae | 72 | |
f67539c2 | 73 | void preorder(Node n, const Tree&) { path_.push_back(n); } |
7c673cae | 74 | |
f67539c2 TL |
75 | void inorder(Node, const Tree&) const {} |
76 | void postorder(Node, const Tree&) const {} | |
7c673cae | 77 | |
f67539c2 TL |
78 | const_iterator begin() const { return path_.begin(); } |
79 | const_iterator end() const { return path_.end(); } | |
80 | }; | |
7c673cae | 81 | |
f67539c2 TL |
82 | // Forward declarations |
83 | template < typename > class tsp_tour_visitor; | |
84 | template < typename, typename, typename, typename > class tsp_tour_len_visitor; | |
7c673cae | 85 | |
f67539c2 TL |
86 | template < typename VertexListGraph, typename OutputIterator > |
87 | void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o) | |
88 | { | |
89 | metric_tsp_approx_from_vertex(g, *vertices(g).first, get(edge_weight, g), | |
90 | get(vertex_index, g), tsp_tour_visitor< OutputIterator >(o)); | |
91 | } | |
7c673cae | 92 | |
f67539c2 TL |
93 | template < typename VertexListGraph, typename WeightMap, |
94 | typename OutputIterator > | |
95 | void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o) | |
96 | { | |
97 | metric_tsp_approx_from_vertex( | |
98 | g, *vertices(g).first, w, tsp_tour_visitor< OutputIterator >(o)); | |
99 | } | |
100 | ||
101 | template < typename VertexListGraph, typename OutputIterator > | |
102 | void metric_tsp_approx_tour_from_vertex(VertexListGraph& g, | |
103 | typename graph_traits< VertexListGraph >::vertex_descriptor start, | |
104 | OutputIterator o) | |
105 | { | |
106 | metric_tsp_approx_from_vertex(g, start, get(edge_weight, g), | |
107 | get(vertex_index, g), tsp_tour_visitor< OutputIterator >(o)); | |
108 | } | |
109 | ||
110 | template < typename VertexListGraph, typename WeightMap, | |
111 | typename OutputIterator > | |
112 | void metric_tsp_approx_tour_from_vertex(VertexListGraph& g, | |
113 | typename graph_traits< VertexListGraph >::vertex_descriptor start, | |
114 | WeightMap w, OutputIterator o) | |
115 | { | |
116 | metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), | |
117 | tsp_tour_visitor< OutputIterator >(o)); | |
118 | } | |
7c673cae | 119 | |
f67539c2 TL |
120 | template < typename VertexListGraph, typename TSPVertexVisitor > |
121 | void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis) | |
122 | { | |
123 | metric_tsp_approx_from_vertex( | |
124 | g, *vertices(g).first, get(edge_weight, g), get(vertex_index, g), vis); | |
125 | } | |
7c673cae | 126 | |
f67539c2 TL |
127 | template < typename VertexListGraph, typename Weightmap, |
128 | typename VertexIndexMap, typename TSPVertexVisitor > | |
129 | void metric_tsp_approx(VertexListGraph& g, Weightmap w, TSPVertexVisitor vis) | |
130 | { | |
131 | metric_tsp_approx_from_vertex( | |
132 | g, *vertices(g).first, w, get(vertex_index, g), vis); | |
133 | } | |
134 | ||
135 | template < typename VertexListGraph, typename WeightMap, | |
136 | typename VertexIndexMap, typename TSPVertexVisitor > | |
137 | void metric_tsp_approx( | |
138 | VertexListGraph& g, WeightMap w, VertexIndexMap id, TSPVertexVisitor vis) | |
139 | { | |
140 | metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis); | |
141 | } | |
142 | ||
143 | template < typename VertexListGraph, typename WeightMap, | |
144 | typename TSPVertexVisitor > | |
145 | void metric_tsp_approx_from_vertex(VertexListGraph& g, | |
146 | typename graph_traits< VertexListGraph >::vertex_descriptor start, | |
147 | WeightMap w, TSPVertexVisitor vis) | |
148 | { | |
149 | metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), vis); | |
150 | } | |
151 | ||
152 | template < typename VertexListGraph, typename WeightMap, | |
153 | typename VertexIndexMap, typename TSPVertexVisitor > | |
154 | void metric_tsp_approx_from_vertex(const VertexListGraph& g, | |
155 | typename graph_traits< VertexListGraph >::vertex_descriptor start, | |
156 | WeightMap weightmap, VertexIndexMap indexmap, TSPVertexVisitor vis) | |
157 | { | |
158 | using namespace boost; | |
159 | using namespace std; | |
160 | ||
161 | BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexListGraph >)); | |
162 | BOOST_CONCEPT_ASSERT( | |
163 | (TSPVertexVisitorConcept< TSPVertexVisitor, VertexListGraph >)); | |
164 | ||
165 | // Types related to the input graph (GVertex is a template parameter). | |
166 | typedef typename graph_traits< VertexListGraph >::vertex_descriptor GVertex; | |
167 | typedef typename graph_traits< VertexListGraph >::vertex_iterator GVItr; | |
168 | ||
169 | // We build a custom graph in this algorithm. | |
170 | typedef adjacency_list< vecS, vecS, directedS, no_property, no_property > | |
171 | MSTImpl; | |
172 | typedef graph_traits< MSTImpl >::vertex_descriptor Vertex; | |
173 | typedef graph_traits< MSTImpl >::vertex_iterator VItr; | |
174 | ||
175 | // And then re-cast it as a tree. | |
176 | typedef iterator_property_map< vector< Vertex >::iterator, | |
177 | property_map< MSTImpl, vertex_index_t >::type > | |
178 | ParentMap; | |
179 | typedef graph_as_tree< MSTImpl, ParentMap > Tree; | |
180 | typedef tree_traits< Tree >::node_descriptor Node; | |
181 | ||
182 | // A predecessor map. | |
183 | typedef vector< GVertex > PredMap; | |
184 | typedef iterator_property_map< typename PredMap::iterator, VertexIndexMap > | |
185 | PredPMap; | |
186 | ||
187 | PredMap preds(num_vertices(g)); | |
188 | PredPMap pred_pmap(preds.begin(), indexmap); | |
189 | ||
190 | // Compute a spanning tree over the in put g. | |
191 | prim_minimum_spanning_tree(g, pred_pmap, | |
192 | root_vertex(start).vertex_index_map(indexmap).weight_map(weightmap)); | |
193 | ||
194 | // Build a MST using the predecessor map from prim mst | |
195 | MSTImpl mst(num_vertices(g)); | |
196 | std::size_t cnt = 0; | |
197 | pair< VItr, VItr > mst_verts(vertices(mst)); | |
198 | for (typename PredMap::iterator vi(preds.begin()); vi != preds.end(); | |
199 | ++vi, ++cnt) | |
7c673cae | 200 | { |
f67539c2 TL |
201 | if (indexmap[*vi] != cnt) |
202 | { | |
203 | add_edge(*next(mst_verts.first, indexmap[*vi]), | |
204 | *next(mst_verts.first, cnt), mst); | |
205 | } | |
7c673cae FG |
206 | } |
207 | ||
f67539c2 TL |
208 | // Build a tree abstraction over the MST. |
209 | vector< Vertex > parent(num_vertices(mst)); | |
210 | Tree t(mst, *vertices(mst).first, | |
211 | make_iterator_property_map(parent.begin(), get(vertex_index, mst))); | |
7c673cae | 212 | |
f67539c2 TL |
213 | // Create tour using a preorder traversal of the mst |
214 | vector< Node > tour; | |
215 | PreorderTraverser< Node, Tree > tvis(tour); | |
216 | traverse_tree(indexmap[start], t, tvis); | |
7c673cae | 217 | |
f67539c2 TL |
218 | pair< GVItr, GVItr > g_verts(vertices(g)); |
219 | for (PreorderTraverser< Node, Tree >::const_iterator curr(tvis.begin()); | |
220 | curr != tvis.end(); ++curr) | |
7c673cae | 221 | { |
f67539c2 TL |
222 | // TODO: This is will be O(n^2) if vertex storage of g != vecS. |
223 | GVertex v = *next(g_verts.first, get(vertex_index, mst)[*curr]); | |
224 | vis.visit_vertex(v, g); | |
225 | } | |
7c673cae | 226 | |
f67539c2 TL |
227 | // Connect back to the start of the tour |
228 | vis.visit_vertex(start, g); | |
229 | } | |
7c673cae | 230 | |
f67539c2 TL |
231 | // Default tsp tour visitor that puts the tour in an OutputIterator |
232 | template < typename OutItr > class tsp_tour_visitor | |
233 | { | |
234 | OutItr itr_; | |
7c673cae | 235 | |
f67539c2 TL |
236 | public: |
237 | tsp_tour_visitor(OutItr itr) : itr_(itr) {} | |
7c673cae | 238 | |
f67539c2 TL |
239 | template < typename Vertex, typename Graph > |
240 | void visit_vertex(Vertex v, const Graph&) | |
7c673cae | 241 | { |
f67539c2 TL |
242 | BOOST_CONCEPT_ASSERT((OutputIterator< OutItr, Vertex >)); |
243 | *itr_++ = v; | |
244 | } | |
245 | }; | |
7c673cae | 246 | |
f67539c2 TL |
247 | // Tsp tour visitor that adds the total tour length. |
248 | template < typename Graph, typename WeightMap, typename OutIter, | |
249 | typename Length > | |
250 | class tsp_tour_len_visitor | |
251 | { | |
252 | typedef typename graph_traits< Graph >::vertex_descriptor Vertex; | |
253 | BOOST_CONCEPT_ASSERT((OutputIterator< OutIter, Vertex >)); | |
7c673cae | 254 | |
f67539c2 TL |
255 | OutIter iter_; |
256 | Length& tourlen_; | |
257 | WeightMap& wmap_; | |
258 | Vertex previous_; | |
7c673cae | 259 | |
f67539c2 TL |
260 | // Helper function for getting the null vertex. |
261 | Vertex null() { return graph_traits< Graph >::null_vertex(); } | |
7c673cae | 262 | |
f67539c2 TL |
263 | public: |
264 | tsp_tour_len_visitor(Graph const&, OutIter iter, Length& l, WeightMap& map) | |
265 | : iter_(iter), tourlen_(l), wmap_(map), previous_(null()) | |
266 | { | |
267 | } | |
7c673cae | 268 | |
f67539c2 TL |
269 | void visit_vertex(Vertex v, const Graph& g) |
270 | { | |
271 | typedef typename graph_traits< Graph >::edge_descriptor Edge; | |
7c673cae | 272 | |
f67539c2 TL |
273 | // If it is not the start, then there is a |
274 | // previous vertex | |
275 | if (previous_ != null()) | |
7c673cae | 276 | { |
f67539c2 TL |
277 | // NOTE: For non-adjacency matrix graphs g, this bit of code |
278 | // will be linear in the degree of previous_ or v. A better | |
279 | // solution would be to visit edges of the graph, but that | |
280 | // would require revisiting the core algorithm. | |
281 | Edge e; | |
282 | bool found; | |
283 | boost::tie(e, found) = lookup_edge(previous_, v, g); | |
284 | if (!found) | |
7c673cae | 285 | { |
f67539c2 | 286 | BOOST_THROW_EXCEPTION(not_complete()); |
7c673cae FG |
287 | } |
288 | ||
f67539c2 | 289 | tourlen_ += wmap_[e]; |
7c673cae | 290 | } |
7c673cae | 291 | |
f67539c2 TL |
292 | previous_ = v; |
293 | *iter_++ = v; | |
294 | } | |
295 | }; | |
7c673cae | 296 | |
f67539c2 TL |
297 | // Object generator(s) |
298 | template < typename OutIter > | |
299 | inline tsp_tour_visitor< OutIter > make_tsp_tour_visitor(OutIter iter) | |
300 | { | |
301 | return tsp_tour_visitor< OutIter >(iter); | |
302 | } | |
303 | ||
304 | template < typename Graph, typename WeightMap, typename OutIter, | |
305 | typename Length > | |
306 | inline tsp_tour_len_visitor< Graph, WeightMap, OutIter, Length > | |
307 | make_tsp_tour_len_visitor( | |
308 | Graph const& g, OutIter iter, Length& l, WeightMap map) | |
309 | { | |
310 | return tsp_tour_len_visitor< Graph, WeightMap, OutIter, Length >( | |
311 | g, iter, l, map); | |
312 | } | |
7c673cae | 313 | |
f67539c2 | 314 | } // boost |
7c673cae FG |
315 | |
316 | #endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP |