]>
Commit | Line | Data |
---|---|---|
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 | { | |
42 | // Define a concept for the concept-checking library. | |
43 | template <typename Visitor, typename Graph> | |
44 | struct TSPVertexVisitorConcept | |
45 | { | |
46 | private: | |
47 | Visitor vis_; | |
48 | public: | |
49 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
50 | ||
51 | BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept) | |
52 | { | |
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 | }; | |
59 | ||
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_; | |
67 | public: | |
68 | typedef typename std::vector<Node>::const_iterator const_iterator; | |
69 | ||
70 | PreorderTraverser(std::vector<Node>& p) : path_(p) {} | |
71 | ||
72 | void preorder(Node n, const Tree&) | |
73 | { path_.push_back(n); } | |
74 | ||
75 | void inorder(Node, const Tree&) const {} | |
76 | void postorder(Node, const Tree&) const {} | |
77 | ||
78 | const_iterator begin() const { return path_.begin(); } | |
79 | const_iterator end() const { return path_.end(); } | |
80 | }; | |
81 | ||
82 | // Forward declarations | |
83 | template <typename> class tsp_tour_visitor; | |
84 | template <typename, typename, typename, typename> class tsp_tour_len_visitor; | |
85 | ||
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, | |
90 | get(edge_weight, g), get(vertex_index, g), | |
91 | tsp_tour_visitor<OutputIterator>(o)); | |
92 | } | |
93 | ||
94 | template<typename VertexListGraph, typename WeightMap, typename OutputIterator> | |
95 | void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o) | |
96 | { | |
97 | metric_tsp_approx_from_vertex(g, *vertices(g).first, | |
98 | 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 | } | |
119 | ||
120 | template<typename VertexListGraph, typename TSPVertexVisitor> | |
121 | void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis) | |
122 | { | |
123 | metric_tsp_approx_from_vertex(g, *vertices(g).first, | |
124 | get(edge_weight, g), get(vertex_index, g), vis); | |
125 | } | |
126 | ||
127 | template<typename VertexListGraph, typename Weightmap, | |
128 | typename VertexIndexMap, typename TSPVertexVisitor> | |
129 | void metric_tsp_approx(VertexListGraph& g, Weightmap w, | |
130 | TSPVertexVisitor vis) | |
131 | { | |
132 | metric_tsp_approx_from_vertex(g, *vertices(g).first, w, | |
133 | get(vertex_index, g), vis); | |
134 | } | |
135 | ||
136 | template<typename VertexListGraph, typename WeightMap, | |
137 | typename VertexIndexMap, typename TSPVertexVisitor> | |
138 | void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id, | |
139 | TSPVertexVisitor vis) | |
140 | { | |
141 | metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis); | |
142 | } | |
143 | ||
144 | template<typename VertexListGraph, typename WeightMap, | |
145 | typename TSPVertexVisitor> | |
146 | void metric_tsp_approx_from_vertex(VertexListGraph& g, | |
147 | typename graph_traits<VertexListGraph>::vertex_descriptor start, | |
148 | WeightMap w, TSPVertexVisitor vis) | |
149 | { | |
150 | metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), vis); | |
151 | } | |
152 | ||
153 | template < | |
154 | typename VertexListGraph, | |
155 | typename WeightMap, | |
156 | typename VertexIndexMap, | |
157 | typename TSPVertexVisitor> | |
158 | void metric_tsp_approx_from_vertex(const VertexListGraph& g, | |
159 | typename graph_traits<VertexListGraph>::vertex_descriptor start, | |
160 | WeightMap weightmap, | |
161 | VertexIndexMap indexmap, | |
162 | TSPVertexVisitor vis) | |
163 | { | |
164 | using namespace boost; | |
165 | using namespace std; | |
166 | ||
167 | BOOST_CONCEPT_ASSERT((VertexListGraphConcept<VertexListGraph>)); | |
168 | BOOST_CONCEPT_ASSERT((TSPVertexVisitorConcept<TSPVertexVisitor, VertexListGraph>)); | |
169 | ||
170 | // Types related to the input graph (GVertex is a template parameter). | |
171 | typedef typename graph_traits<VertexListGraph>::vertex_descriptor GVertex; | |
172 | typedef typename graph_traits<VertexListGraph>::vertex_iterator GVItr; | |
173 | ||
174 | // We build a custom graph in this algorithm. | |
175 | typedef adjacency_list <vecS, vecS, directedS, no_property, no_property > MSTImpl; | |
176 | typedef graph_traits<MSTImpl>::vertex_descriptor Vertex; | |
177 | typedef graph_traits<MSTImpl>::vertex_iterator VItr; | |
178 | ||
179 | // And then re-cast it as a tree. | |
180 | typedef iterator_property_map<vector<Vertex>::iterator, property_map<MSTImpl, vertex_index_t>::type> ParentMap; | |
181 | typedef graph_as_tree<MSTImpl, ParentMap> Tree; | |
182 | typedef tree_traits<Tree>::node_descriptor Node; | |
183 | ||
184 | // A predecessor map. | |
185 | typedef vector<GVertex> PredMap; | |
186 | typedef iterator_property_map<typename PredMap::iterator, VertexIndexMap> PredPMap; | |
187 | ||
188 | PredMap preds(num_vertices(g)); | |
189 | PredPMap pred_pmap(preds.begin(), indexmap); | |
190 | ||
191 | // Compute a spanning tree over the in put g. | |
192 | prim_minimum_spanning_tree(g, pred_pmap, | |
193 | root_vertex(start) | |
194 | .vertex_index_map(indexmap) | |
195 | .weight_map(weightmap)); | |
196 | ||
197 | // Build a MST using the predecessor map from prim mst | |
198 | MSTImpl mst(num_vertices(g)); | |
199 | std::size_t cnt = 0; | |
200 | pair<VItr, VItr> mst_verts(vertices(mst)); | |
201 | for(typename PredMap::iterator vi(preds.begin()); vi != preds.end(); ++vi, ++cnt) | |
202 | { | |
203 | if(indexmap[*vi] != cnt) { | |
204 | add_edge(*next(mst_verts.first, indexmap[*vi]), | |
205 | *next(mst_verts.first, cnt), mst); | |
206 | } | |
207 | } | |
208 | ||
209 | // Build a tree abstraction over the MST. | |
210 | vector<Vertex> parent(num_vertices(mst)); | |
211 | Tree t(mst, *vertices(mst).first, | |
212 | make_iterator_property_map(parent.begin(), | |
213 | get(vertex_index, mst))); | |
214 | ||
215 | // Create tour using a preorder traversal of the mst | |
216 | vector<Node> tour; | |
217 | PreorderTraverser<Node, Tree> tvis(tour); | |
218 | traverse_tree(indexmap[start], t, tvis); | |
219 | ||
220 | pair<GVItr, GVItr> g_verts(vertices(g)); | |
221 | for(PreorderTraverser<Node, Tree>::const_iterator curr(tvis.begin()); | |
222 | curr != tvis.end(); ++curr) | |
223 | { | |
224 | // TODO: This is will be O(n^2) if vertex storage of g != vecS. | |
225 | GVertex v = *next(g_verts.first, get(vertex_index, mst)[*curr]); | |
226 | vis.visit_vertex(v, g); | |
227 | } | |
228 | ||
229 | // Connect back to the start of the tour | |
230 | vis.visit_vertex(start, g); | |
231 | } | |
232 | ||
233 | // Default tsp tour visitor that puts the tour in an OutputIterator | |
234 | template <typename OutItr> | |
235 | class tsp_tour_visitor | |
236 | { | |
237 | OutItr itr_; | |
238 | public: | |
239 | tsp_tour_visitor(OutItr itr) | |
240 | : itr_(itr) | |
241 | { } | |
242 | ||
243 | template <typename Vertex, typename Graph> | |
244 | void visit_vertex(Vertex v, const Graph&) | |
245 | { | |
246 | BOOST_CONCEPT_ASSERT((OutputIterator<OutItr, Vertex>)); | |
247 | *itr_++ = v; | |
248 | } | |
249 | ||
250 | }; | |
251 | ||
252 | // Tsp tour visitor that adds the total tour length. | |
253 | template<typename Graph, typename WeightMap, typename OutIter, typename Length> | |
254 | class tsp_tour_len_visitor | |
255 | { | |
256 | typedef typename graph_traits<Graph>::vertex_descriptor Vertex; | |
257 | BOOST_CONCEPT_ASSERT((OutputIterator<OutIter, Vertex>)); | |
258 | ||
259 | OutIter iter_; | |
260 | Length& tourlen_; | |
261 | WeightMap& wmap_; | |
262 | Vertex previous_; | |
263 | ||
264 | // Helper function for getting the null vertex. | |
265 | Vertex null() | |
266 | { return graph_traits<Graph>::null_vertex(); } | |
267 | ||
268 | public: | |
269 | tsp_tour_len_visitor(Graph const&, OutIter iter, Length& l, WeightMap& map) | |
270 | : iter_(iter), tourlen_(l), wmap_(map), previous_(null()) | |
271 | { } | |
272 | ||
273 | void visit_vertex(Vertex v, const Graph& g) | |
274 | { | |
275 | typedef typename graph_traits<Graph>::edge_descriptor Edge; | |
276 | ||
277 | // If it is not the start, then there is a | |
278 | // previous vertex | |
279 | if(previous_ != null()) | |
280 | { | |
281 | // NOTE: For non-adjacency matrix graphs g, this bit of code | |
282 | // will be linear in the degree of previous_ or v. A better | |
283 | // solution would be to visit edges of the graph, but that | |
284 | // would require revisiting the core algorithm. | |
285 | Edge e; | |
286 | bool found; | |
287 | boost::tie(e, found) = lookup_edge(previous_, v, g); | |
288 | if(!found) { | |
289 | BOOST_THROW_EXCEPTION(not_complete()); | |
290 | } | |
291 | ||
292 | tourlen_ += wmap_[e]; | |
293 | } | |
294 | ||
295 | previous_ = v; | |
296 | *iter_++ = v; | |
297 | } | |
298 | }; | |
299 | ||
300 | // Object generator(s) | |
301 | template <typename OutIter> | |
302 | inline tsp_tour_visitor<OutIter> | |
303 | make_tsp_tour_visitor(OutIter iter) | |
304 | { return tsp_tour_visitor<OutIter>(iter); } | |
305 | ||
306 | template <typename Graph, typename WeightMap, typename OutIter, typename Length> | |
307 | inline tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length> | |
308 | make_tsp_tour_len_visitor(Graph const& g, OutIter iter, Length& l, WeightMap map) | |
309 | { return tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length>(g, iter, l, map); } | |
310 | ||
311 | } //boost | |
312 | ||
313 | #endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP |