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