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
40namespace 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

source code of boost/boost/graph/metric_tsp_approx.hpp