boost/graph/metric_tsp_approx.hpp

   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
  38
  39 namespace boost
  40 {
  41     // Define a concept for the concept-checking library.
  42     template <typename Visitor, typename Graph>
  43     struct TSPVertexVisitorConcept
  44     {
  45     private:
  46         Visitor vis_;
  47     public:
  48         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
  49
  50         BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept)
  51         {
  52             Visitor vis(vis_);  // require copy construction
  53             Graph g(1);
  54             Vertex v(*vertices(g).first);
  55             vis_.visit_vertex(v, g); // require visit_vertex
  56         }
  57     };
  58
  59     // Tree visitor that keeps track of a preorder traversal of a tree
  60     // TODO: Consider migrating this to the graph_as_tree header.
  61     // TODO: Parameterize the underlying stores o it doesn't have to be a vector.
  62     template<typename Node, typename Tree> class PreorderTraverser
  63     {
  64     private:
  65         std::vector<Node>& path_;
  66     public:
  67         typedef typename std::vector<Node>::const_iterator const_iterator;
  68
  69         PreorderTraverser(std::vector<Node>& p) : path_(p) {}
  70
  71         void preorder(Node n, const Tree& t)
  72         { path_.push_back(n); }
  73
  74         void inorder(Node n, const Tree& t) const {}
  75         void postorder(Node, const Tree& t) const {}
  76
  77         const_iterator begin() const { return path_.begin(); }
  78         const_iterator end() const { return path_.end(); }
  79     };
  80
  81     // Forward declarations
  82     template <typename> class tsp_tour_visitor;
  83     template <typename, typename, typename, typename> class tsp_tour_len_visitor;
  84
  85     template<typename VertexListGraph, typename OutputIterator>
  86     void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o)
  87     {
  88         metric_tsp_approx_from_vertex(g, *vertices(g).first,
  89             get(edge_weight, g), get(vertex_index, g),
  90             tsp_tour_visitor<OutputIterator>(o));
  91     }
  92
  93     template<typename VertexListGraph, typename WeightMap, typename OutputIterator>
  94     void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o)
  95     {
  96         metric_tsp_approx_from_vertex(g, *vertices(g).first,
  97             w, tsp_tour_visitor<OutputIterator>(o));
  98     }
  99
 100     template<typename VertexListGraph, typename OutputIterator>
 101     void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
 102         typename graph_traits<VertexListGraph>::vertex_descriptor start,
 103         OutputIterator o)
 104     {
 105         metric_tsp_approx_from_vertex(g, start, get(edge_weight, g),
 106             get(vertex_index, g), tsp_tour_visitor<OutputIterator>(o));
 107     }
 108
 109     template<typename VertexListGraph, typename WeightMap,
 110         typename OutputIterator>
 111     void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
 112     typename graph_traits<VertexListGraph>::vertex_descriptor start,
 113         WeightMap w, OutputIterator o)
 114     {
 115         metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g),
 116             tsp_tour_visitor<OutputIterator>(o));
 117     }
 118
 119     template<typename VertexListGraph, typename TSPVertexVisitor>
 120     void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)
 121     {
 122         metric_tsp_approx_from_vertex(g, *vertices(g).first,
 123             get(edge_weight, g), get(vertex_index, g), vis);
 124     }
 125
 126     template<typename VertexListGraph, typename Weightmap,
 127         typename VertexIndexMap, typename TSPVertexVisitor>
 128     void metric_tsp_approx(VertexListGraph& g, Weightmap w,
 129         TSPVertexVisitor vis)
 130     {
 131         metric_tsp_approx_from_vertex(g, *vertices(g).first, w,
 132             get(vertex_index, g), vis);
 133     }
 134
 135     template<typename VertexListGraph, typename WeightMap,
 136         typename VertexIndexMap, typename TSPVertexVisitor>
 137     void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id,
 138         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 <
 153         typename VertexListGraph,
 154         typename WeightMap,
 155         typename VertexIndexMap,
 156         typename TSPVertexVisitor>
 157     void metric_tsp_approx_from_vertex(const VertexListGraph& g,
 158                                        typename graph_traits<VertexListGraph>::vertex_descriptor start,
 159                                        WeightMap weightmap,
 160                                        VertexIndexMap indexmap,
 161                                        TSPVertexVisitor vis)
 162     {
 163         using namespace boost;
 164         using namespace std;
 165
 166         BOOST_CONCEPT_ASSERT((VertexListGraphConcept<VertexListGraph>));
 167         BOOST_CONCEPT_ASSERT((TSPVertexVisitorConcept<TSPVertexVisitor, VertexListGraph>));
 168
 169         // Types related to the input graph (GVertex is a template parameter).
 170         typedef typename graph_traits<VertexListGraph>::vertex_descriptor GVertex;
 171         typedef typename graph_traits<VertexListGraph>::vertex_iterator GVItr;
 172
 173         // We build a custom graph in this algorithm.
 174         typedef adjacency_list <vecS, vecS, directedS, no_property, no_property > MSTImpl;
 175         typedef graph_traits<MSTImpl>::edge_descriptor Edge;
 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(0, 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(*g_verts.first, 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& g)
 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                 tie(e, found) = edge(previous_, v, g);
 288                 if(!found) {
 289                     throw 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