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 o 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(g_: 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(x: mst_verts.first, n: cnt), mst); |
206 | } |
207 | } |
208 | |
209 | // Build a tree abstraction over the MST. |
210 | vector<Vertex> parent(num_vertices(g_: mst)); |
211 | Tree t(mst, *vertices(g_: mst).first, |
212 | make_iterator_property_map(iter: parent.begin(), |
213 | id: get(p: vertex_index, g&: 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(p: vertex_index, g&: 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 |
314 | |