boost/graph/metric_tsp_approx.hpp

0001
0002 //=======================================================================
0003 // Copyright 2008
0004 // Author: Matyas W Egyhazy
0005 //
0006 // Distributed under the Boost Software License, Version 1.0. (See
0007 // accompanying file LICENSE_1_0.txt or copy at
0008 // http://www.boost.org/LICENSE_1_0.txt)
0009 //=======================================================================
0010
0011 #ifndef BOOST_GRAPH_METRIC_TSP_APPROX_HPP
0012 #define BOOST_GRAPH_METRIC_TSP_APPROX_HPP
0013
0014 // metric_tsp_approx
0015 // Generates an approximate tour solution for the traveling salesperson
0016 // problem in polynomial time. The current algorithm guarantees a tour with a
0017 // length at most as long as 2x optimal solution. The graph should have
0018 // 'natural' (metric) weights such that the triangle inequality is maintained.
0019 // Graphs must be fully interconnected.
0020
0021 // TODO:
0022 // There are a couple of improvements that could be made.
0023 // 1) Change implementation to lower uppper bound Christofides heuristic
0024 // 2) Implement a less restrictive TSP heuristic (one that does not rely on
0025 //    triangle inequality).
0026 // 3) Determine if the algorithm can be implemented without creating a new
0027 //    graph.
0028
0029 #include <vector>
0030
0031 #include <boost/shared_ptr.hpp>
0032 #include <boost/concept_check.hpp>
0033 #include <boost/graph/graph_traits.hpp>
0034 #include <boost/graph/graph_as_tree.hpp>
0035 #include <boost/graph/adjacency_list.hpp>
0036 #include <boost/graph/prim_minimum_spanning_tree.hpp>
0037 #include <boost/graph/lookup_edge.hpp>
0038 #include <boost/throw_exception.hpp>
0039
0040 namespace boost
0041 {
0042 // Define a concept for the concept-checking library.
0043 template < typename Visitor, typename Graph > struct TSPVertexVisitorConcept
0044 {
0045 private:
0046     Visitor vis_;
0047
0048 public:
0049     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0050
0051     BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept)
0052     {
0053         Visitor vis(vis_); // require copy construction
0054         Graph g(1);
0055         Vertex v(*vertices(g).first);
0056         vis.visit_vertex(v, g); // require visit_vertex
0057     }
0058 };
0059
0060 // Tree visitor that keeps track of a preorder traversal of a tree
0061 // TODO: Consider migrating this to the graph_as_tree header.
0062 // TODO: Parameterize the underlying stores so it doesn't have to be a vector.
0063 template < typename Node, typename Tree > class PreorderTraverser
0064 {
0065 private:
0066     std::vector< Node >& path_;
0067
0068 public:
0069     typedef typename std::vector< Node >::const_iterator const_iterator;
0070
0071     PreorderTraverser(std::vector< Node >& p) : path_(p) {}
0072
0073     void preorder(Node n, const Tree&) { path_.push_back(n); }
0074
0075     void inorder(Node, const Tree&) const {}
0076     void postorder(Node, const Tree&) const {}
0077
0078     const_iterator begin() const { return path_.begin(); }
0079     const_iterator end() const { return path_.end(); }
0080 };
0081
0082 // Forward declarations
0083 template < typename > class tsp_tour_visitor;
0084 template < typename, typename, typename, typename > class tsp_tour_len_visitor;
0085
0086 template < typename VertexListGraph, typename OutputIterator >
0087 void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o)
0088 {
0089     metric_tsp_approx_from_vertex(g, *vertices(g).first, get(edge_weight, g),
0090         get(vertex_index, g), tsp_tour_visitor< OutputIterator >(o));
0091 }
0092
0093 template < typename VertexListGraph, typename WeightMap,
0094     typename OutputIterator >
0095 void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o)
0096 {
0097     metric_tsp_approx_from_vertex(
0098         g, *vertices(g).first, w, tsp_tour_visitor< OutputIterator >(o));
0099 }
0100
0101 template < typename VertexListGraph, typename OutputIterator >
0102 void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
0103     typename graph_traits< VertexListGraph >::vertex_descriptor start,
0104     OutputIterator o)
0105 {
0106     metric_tsp_approx_from_vertex(g, start, get(edge_weight, g),
0107         get(vertex_index, g), tsp_tour_visitor< OutputIterator >(o));
0108 }
0109
0110 template < typename VertexListGraph, typename WeightMap,
0111     typename OutputIterator >
0112 void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
0113     typename graph_traits< VertexListGraph >::vertex_descriptor start,
0114     WeightMap w, OutputIterator o)
0115 {
0116     metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g),
0117         tsp_tour_visitor< OutputIterator >(o));
0118 }
0119
0120 template < typename VertexListGraph, typename TSPVertexVisitor >
0121 void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)
0122 {
0123     metric_tsp_approx_from_vertex(
0124         g, *vertices(g).first, get(edge_weight, g), get(vertex_index, g), vis);
0125 }
0126
0127 template < typename VertexListGraph, typename Weightmap,
0128     typename VertexIndexMap, typename TSPVertexVisitor >
0129 void metric_tsp_approx(VertexListGraph& g, Weightmap w, TSPVertexVisitor vis)
0130 {
0131     metric_tsp_approx_from_vertex(
0132         g, *vertices(g).first, w, get(vertex_index, g), vis);
0133 }
0134
0135 template < typename VertexListGraph, typename WeightMap,
0136     typename VertexIndexMap, typename TSPVertexVisitor >
0137 void metric_tsp_approx(
0138     VertexListGraph& g, WeightMap w, VertexIndexMap id, TSPVertexVisitor vis)
0139 {
0140     metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis);
0141 }
0142
0143 template < typename VertexListGraph, typename WeightMap,
0144     typename TSPVertexVisitor >
0145 void metric_tsp_approx_from_vertex(VertexListGraph& g,
0146     typename graph_traits< VertexListGraph >::vertex_descriptor start,
0147     WeightMap w, TSPVertexVisitor vis)
0148 {
0149     metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), vis);
0150 }
0151
0152 template < typename VertexListGraph, typename WeightMap,
0153     typename VertexIndexMap, typename TSPVertexVisitor >
0154 void metric_tsp_approx_from_vertex(const VertexListGraph& g,
0155     typename graph_traits< VertexListGraph >::vertex_descriptor start,
0156     WeightMap weightmap, VertexIndexMap indexmap, TSPVertexVisitor vis)
0157 {
0158     using namespace boost;
0159     using namespace std;
0160
0161     BOOST_CONCEPT_ASSERT((VertexListGraphConcept< VertexListGraph >));
0162     BOOST_CONCEPT_ASSERT(
0163         (TSPVertexVisitorConcept< TSPVertexVisitor, VertexListGraph >));
0164
0165     // Types related to the input graph (GVertex is a template parameter).
0166     typedef typename graph_traits< VertexListGraph >::vertex_descriptor GVertex;
0167     typedef typename graph_traits< VertexListGraph >::vertex_iterator GVItr;
0168
0169     // We build a custom graph in this algorithm.
0170     typedef adjacency_list< vecS, vecS, directedS, no_property, no_property >
0171         MSTImpl;
0172     typedef graph_traits< MSTImpl >::vertex_descriptor Vertex;
0173     typedef graph_traits< MSTImpl >::vertex_iterator VItr;
0174
0175     // And then re-cast it as a tree.
0176     typedef iterator_property_map< vector< Vertex >::iterator,
0177         property_map< MSTImpl, vertex_index_t >::type >
0178         ParentMap;
0179     typedef graph_as_tree< MSTImpl, ParentMap > Tree;
0180     typedef tree_traits< Tree >::node_descriptor Node;
0181
0182     // A predecessor map.
0183     typedef vector< GVertex > PredMap;
0184     typedef iterator_property_map< typename PredMap::iterator, VertexIndexMap >
0185         PredPMap;
0186
0187     PredMap preds(num_vertices(g));
0188     PredPMap pred_pmap(preds.begin(), indexmap);
0189
0190     // Compute a spanning tree over the in put g.
0191     prim_minimum_spanning_tree(g, pred_pmap,
0192         root_vertex(start).vertex_index_map(indexmap).weight_map(weightmap));
0193
0194     // Build a MST using the predecessor map from prim mst
0195     MSTImpl mst(num_vertices(g));
0196     std::size_t cnt = 0;
0197     pair< VItr, VItr > mst_verts(vertices(mst));
0198     for (typename PredMap::iterator vi(preds.begin()); vi != preds.end();
0199          ++vi, ++cnt)
0200     {
0201         if (indexmap[*vi] != cnt)
0202         {
0203             add_edge(*next(mst_verts.first, indexmap[*vi]),
0204                 *next(mst_verts.first, cnt), mst);
0205         }
0206     }
0207
0208     // Build a tree abstraction over the MST.
0209     vector< Vertex > parent(num_vertices(mst));
0210     Tree t(mst, *vertices(mst).first,
0211         make_iterator_property_map(parent.begin(), get(vertex_index, mst)));
0212
0213     // Create tour using a preorder traversal of the mst
0214     vector< Node > tour;
0215     PreorderTraverser< Node, Tree > tvis(tour);
0216     traverse_tree(indexmap[start], t, tvis);
0217
0218     pair< GVItr, GVItr > g_verts(vertices(g));
0219     for (PreorderTraverser< Node, Tree >::const_iterator curr(tvis.begin());
0220          curr != tvis.end(); ++curr)
0221     {
0222         // TODO: This is will be O(n^2) if vertex storage of g != vecS.
0223         GVertex v = *next(g_verts.first, get(vertex_index, mst)[*curr]);
0224         vis.visit_vertex(v, g);
0225     }
0226
0227     // Connect back to the start of the tour
0228     vis.visit_vertex(start, g);
0229 }
0230
0231 // Default tsp tour visitor that puts the tour in an OutputIterator
0232 template < typename OutItr > class tsp_tour_visitor
0233 {
0234     OutItr itr_;
0235
0236 public:
0237     tsp_tour_visitor(OutItr itr) : itr_(itr) {}
0238
0239     template < typename Vertex, typename Graph >
0240     void visit_vertex(Vertex v, const Graph&)
0241     {
0242         BOOST_CONCEPT_ASSERT((OutputIterator< OutItr, Vertex >));
0243         *itr_++ = v;
0244     }
0245 };
0246
0247 // Tsp tour visitor that adds the total tour length.
0248 template < typename Graph, typename WeightMap, typename OutIter,
0249     typename Length >
0250 class tsp_tour_len_visitor
0251 {
0252     typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
0253     BOOST_CONCEPT_ASSERT((OutputIterator< OutIter, Vertex >));
0254
0255     OutIter iter_;
0256     Length& tourlen_;
0257     WeightMap& wmap_;
0258     Vertex previous_;
0259
0260     // Helper function for getting the null vertex.
0261     Vertex null() { return graph_traits< Graph >::null_vertex(); }
0262
0263 public:
0264     tsp_tour_len_visitor(Graph const&, OutIter iter, Length& l, WeightMap& map)
0265     : iter_(iter), tourlen_(l), wmap_(map), previous_(null())
0266     {
0267     }
0268
0269     void visit_vertex(Vertex v, const Graph& g)
0270     {
0271         typedef typename graph_traits< Graph >::edge_descriptor Edge;
0272
0273         // If it is not the start, then there is a
0274         // previous vertex
0275         if (previous_ != null())
0276         {
0277             // NOTE: For non-adjacency matrix graphs g, this bit of code
0278             // will be linear in the degree of previous_ or v. A better
0279             // solution would be to visit edges of the graph, but that
0280             // would require revisiting the core algorithm.
0281             Edge e;
0282             bool found;
0283             boost::tie(e, found) = lookup_edge(previous_, v, g);
0284             if (!found)
0285             {
0286                 BOOST_THROW_EXCEPTION(not_complete());
0287             }
0288
0289             tourlen_ += wmap_[e];
0290         }
0291
0292         previous_ = v;
0293         *iter_++ = v;
0294     }
0295 };
0296
0297 // Object generator(s)
0298 template < typename OutIter >
0299 inline tsp_tour_visitor< OutIter > make_tsp_tour_visitor(OutIter iter)
0300 {
0301     return tsp_tour_visitor< OutIter >(iter);
0302 }
0303
0304 template < typename Graph, typename WeightMap, typename OutIter,
0305     typename Length >
0306 inline tsp_tour_len_visitor< Graph, WeightMap, OutIter, Length >
0307 make_tsp_tour_len_visitor(
0308     Graph const& g, OutIter iter, Length& l, WeightMap map)
0309 {
0310     return tsp_tour_len_visitor< Graph, WeightMap, OutIter, Length >(
0311         g, iter, l, map);
0312 }
0313
0314 } // boost
0315
0316 #endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP