Chris@16: 
Chris@16: //=======================================================================
Chris@16: // Copyright 2008
Chris@16: // Author: Matyas W Egyhazy
Chris@16: //
Chris@16: // Distributed under the Boost Software License, Version 1.0. (See
Chris@16: // accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //=======================================================================
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_METRIC_TSP_APPROX_HPP
Chris@16: #define BOOST_GRAPH_METRIC_TSP_APPROX_HPP
Chris@16: 
Chris@16: // metric_tsp_approx
Chris@16: // Generates an approximate tour solution for the traveling salesperson
Chris@16: // problem in polynomial time. The current algorithm guarantees a tour with a
Chris@16: // length at most as long as 2x optimal solution. The graph should have
Chris@16: // 'natural' (metric) weights such that the triangle inequality is maintained.
Chris@16: // Graphs must be fully interconnected.
Chris@16: 
Chris@16: // TODO:
Chris@16: // There are a couple of improvements that could be made.
Chris@16: // 1) Change implementation to lower uppper bound Christofides heuristic
Chris@16: // 2) Implement a less restrictive TSP heuristic (one that does not rely on
Chris@16: //    triangle inequality).
Chris@16: // 3) Determine if the algorithm can be implemented without creating a new
Chris@16: //    graph.
Chris@16: 
Chris@16: #include <vector>
Chris@16: 
Chris@16: #include <boost/shared_ptr.hpp>
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/graph_as_tree.hpp>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/prim_minimum_spanning_tree.hpp>
Chris@16: #include <boost/graph/lookup_edge.hpp>
Chris@16: #include <boost/throw_exception.hpp>
Chris@16: 
Chris@16: namespace boost
Chris@16: {
Chris@16:     // Define a concept for the concept-checking library.
Chris@16:     template <typename Visitor, typename Graph>
Chris@16:     struct TSPVertexVisitorConcept
Chris@16:     {
Chris@16:     private:
Chris@16:         Visitor vis_;
Chris@16:     public:
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16: 
Chris@16:         BOOST_CONCEPT_USAGE(TSPVertexVisitorConcept)
Chris@16:         {
Chris@16:             Visitor vis(vis_);  // require copy construction
Chris@16:             Graph g(1);
Chris@16:             Vertex v(*vertices(g).first);
Chris@16:             vis_.visit_vertex(v, g); // require visit_vertex
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     // Tree visitor that keeps track of a preorder traversal of a tree
Chris@16:     // TODO: Consider migrating this to the graph_as_tree header.
Chris@16:     // TODO: Parameterize the underlying stores o it doesn't have to be a vector.
Chris@16:     template<typename Node, typename Tree> class PreorderTraverser
Chris@16:     {
Chris@16:     private:
Chris@16:         std::vector<Node>& path_;
Chris@16:     public:
Chris@16:         typedef typename std::vector<Node>::const_iterator const_iterator;
Chris@16: 
Chris@16:         PreorderTraverser(std::vector<Node>& p) : path_(p) {}
Chris@16: 
Chris@16:         void preorder(Node n, const Tree&)
Chris@16:         { path_.push_back(n); }
Chris@16: 
Chris@16:         void inorder(Node, const Tree&) const {}
Chris@16:         void postorder(Node, const Tree&) const {}
Chris@16: 
Chris@16:         const_iterator begin() const { return path_.begin(); }
Chris@16:         const_iterator end() const { return path_.end(); }
Chris@16:     };
Chris@16: 
Chris@16:     // Forward declarations
Chris@16:     template <typename> class tsp_tour_visitor;
Chris@16:     template <typename, typename, typename, typename> class tsp_tour_len_visitor;
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename OutputIterator>
Chris@16:     void metric_tsp_approx_tour(VertexListGraph& g, OutputIterator o)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, *vertices(g).first,
Chris@16:             get(edge_weight, g), get(vertex_index, g),
Chris@16:             tsp_tour_visitor<OutputIterator>(o));
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename WeightMap, typename OutputIterator>
Chris@16:     void metric_tsp_approx_tour(VertexListGraph& g, WeightMap w, OutputIterator o)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, *vertices(g).first,
Chris@16:             w, tsp_tour_visitor<OutputIterator>(o));
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename OutputIterator>
Chris@16:     void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
Chris@16:         typename graph_traits<VertexListGraph>::vertex_descriptor start,
Chris@16:         OutputIterator o)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, start, get(edge_weight, g),
Chris@16:             get(vertex_index, g), tsp_tour_visitor<OutputIterator>(o));
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename WeightMap,
Chris@16:         typename OutputIterator>
Chris@16:     void metric_tsp_approx_tour_from_vertex(VertexListGraph& g,
Chris@16:     typename graph_traits<VertexListGraph>::vertex_descriptor start,
Chris@16:         WeightMap w, OutputIterator o)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g),
Chris@16:             tsp_tour_visitor<OutputIterator>(o));
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename TSPVertexVisitor>
Chris@16:     void metric_tsp_approx(VertexListGraph& g, TSPVertexVisitor vis)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, *vertices(g).first,
Chris@16:             get(edge_weight, g), get(vertex_index, g), vis);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename Weightmap,
Chris@16:         typename VertexIndexMap, typename TSPVertexVisitor>
Chris@16:     void metric_tsp_approx(VertexListGraph& g, Weightmap w,
Chris@16:         TSPVertexVisitor vis)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, *vertices(g).first, w,
Chris@16:             get(vertex_index, g), vis);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename WeightMap,
Chris@16:         typename VertexIndexMap, typename TSPVertexVisitor>
Chris@16:     void metric_tsp_approx(VertexListGraph& g, WeightMap w, VertexIndexMap id,
Chris@16:         TSPVertexVisitor vis)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, *vertices(g).first, w, id, vis);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename VertexListGraph, typename WeightMap,
Chris@16:         typename TSPVertexVisitor>
Chris@16:     void metric_tsp_approx_from_vertex(VertexListGraph& g,
Chris@16:     typename graph_traits<VertexListGraph>::vertex_descriptor start,
Chris@16:         WeightMap w, TSPVertexVisitor vis)
Chris@16:     {
Chris@16:         metric_tsp_approx_from_vertex(g, start, w, get(vertex_index, g), vis);
Chris@16:     }
Chris@16: 
Chris@16:     template <
Chris@16:         typename VertexListGraph,
Chris@16:         typename WeightMap,
Chris@16:         typename VertexIndexMap,
Chris@16:         typename TSPVertexVisitor>
Chris@16:     void metric_tsp_approx_from_vertex(const VertexListGraph& g,
Chris@16:                                        typename graph_traits<VertexListGraph>::vertex_descriptor start,
Chris@16:                                        WeightMap weightmap,
Chris@16:                                        VertexIndexMap indexmap,
Chris@16:                                        TSPVertexVisitor vis)
Chris@16:     {
Chris@16:         using namespace boost;
Chris@16:         using namespace std;
Chris@16: 
Chris@16:         BOOST_CONCEPT_ASSERT((VertexListGraphConcept<VertexListGraph>));
Chris@16:         BOOST_CONCEPT_ASSERT((TSPVertexVisitorConcept<TSPVertexVisitor, VertexListGraph>));
Chris@16: 
Chris@16:         // Types related to the input graph (GVertex is a template parameter).
Chris@16:         typedef typename graph_traits<VertexListGraph>::vertex_descriptor GVertex;
Chris@16:         typedef typename graph_traits<VertexListGraph>::vertex_iterator GVItr;
Chris@16: 
Chris@16:         // We build a custom graph in this algorithm.
Chris@16:         typedef adjacency_list <vecS, vecS, directedS, no_property, no_property > MSTImpl;
Chris@16:         typedef graph_traits<MSTImpl>::vertex_descriptor Vertex;
Chris@16:         typedef graph_traits<MSTImpl>::vertex_iterator VItr;
Chris@16: 
Chris@16:         // And then re-cast it as a tree.
Chris@16:         typedef iterator_property_map<vector<Vertex>::iterator, property_map<MSTImpl, vertex_index_t>::type> ParentMap;
Chris@16:         typedef graph_as_tree<MSTImpl, ParentMap> Tree;
Chris@16:         typedef tree_traits<Tree>::node_descriptor Node;
Chris@16: 
Chris@16:         // A predecessor map.
Chris@16:         typedef vector<GVertex> PredMap;
Chris@16:         typedef iterator_property_map<typename PredMap::iterator, VertexIndexMap> PredPMap;
Chris@16: 
Chris@16:         PredMap preds(num_vertices(g));
Chris@16:         PredPMap pred_pmap(preds.begin(), indexmap);
Chris@16: 
Chris@16:         // Compute a spanning tree over the in put g.
Chris@16:         prim_minimum_spanning_tree(g, pred_pmap,
Chris@16:              root_vertex(start)
Chris@16:             .vertex_index_map(indexmap)
Chris@16:             .weight_map(weightmap));
Chris@16: 
Chris@16:         // Build a MST using the predecessor map from prim mst
Chris@16:         MSTImpl mst(num_vertices(g));
Chris@16:         std::size_t cnt = 0;
Chris@16:         pair<VItr, VItr> mst_verts(vertices(mst));
Chris@16:         for(typename PredMap::iterator vi(preds.begin()); vi != preds.end(); ++vi, ++cnt)
Chris@16:         {
Chris@16:             if(indexmap[*vi] != cnt) {
Chris@16:                 add_edge(*next(mst_verts.first, indexmap[*vi]),
Chris@16:                          *next(mst_verts.first, cnt), mst);
Chris@16:             }
Chris@16:         }
Chris@16: 
Chris@16:         // Build a tree abstraction over the MST.
Chris@16:         vector<Vertex> parent(num_vertices(mst));
Chris@16:         Tree t(mst, *vertices(mst).first,
Chris@16:             make_iterator_property_map(parent.begin(),
Chris@16:             get(vertex_index, mst)));
Chris@16: 
Chris@16:         // Create tour using a preorder traversal of the mst
Chris@16:         vector<Node> tour;
Chris@16:         PreorderTraverser<Node, Tree> tvis(tour);
Chris@16:         traverse_tree(indexmap[start], t, tvis);
Chris@16: 
Chris@16:         pair<GVItr, GVItr> g_verts(vertices(g));
Chris@16:         for(PreorderTraverser<Node, Tree>::const_iterator curr(tvis.begin());
Chris@16:             curr != tvis.end(); ++curr)
Chris@16:         {
Chris@16:             // TODO: This is will be O(n^2) if vertex storage of g != vecS.
Chris@16:             GVertex v = *next(g_verts.first, get(vertex_index, mst)[*curr]);
Chris@16:             vis.visit_vertex(v, g);
Chris@16:         }
Chris@16: 
Chris@16:         // Connect back to the start of the tour
Chris@16:         vis.visit_vertex(start, g);
Chris@16:     }
Chris@16: 
Chris@16:     // Default tsp tour visitor that puts the tour in an OutputIterator
Chris@16:     template <typename OutItr>
Chris@16:     class tsp_tour_visitor
Chris@16:     {
Chris@16:         OutItr itr_;
Chris@16:     public:
Chris@16:         tsp_tour_visitor(OutItr itr)
Chris@16:             : itr_(itr)
Chris@16:         { }
Chris@16: 
Chris@16:         template <typename Vertex, typename Graph>
Chris@16:         void visit_vertex(Vertex v, const Graph&)
Chris@16:         {
Chris@16:             BOOST_CONCEPT_ASSERT((OutputIterator<OutItr, Vertex>));
Chris@16:             *itr_++ = v;
Chris@16:         }
Chris@16: 
Chris@16:     };
Chris@16: 
Chris@16:     // Tsp tour visitor that adds the total tour length.
Chris@16:     template<typename Graph, typename WeightMap, typename OutIter, typename Length>
Chris@16:     class tsp_tour_len_visitor
Chris@16:     {
Chris@16:         typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
Chris@16:         BOOST_CONCEPT_ASSERT((OutputIterator<OutIter, Vertex>));
Chris@16: 
Chris@16:         OutIter iter_;
Chris@16:         Length& tourlen_;
Chris@16:         WeightMap& wmap_;
Chris@16:         Vertex previous_;
Chris@16: 
Chris@16:         // Helper function for getting the null vertex.
Chris@16:         Vertex null()
Chris@16:         { return graph_traits<Graph>::null_vertex(); }
Chris@16: 
Chris@16:     public:
Chris@16:         tsp_tour_len_visitor(Graph const&, OutIter iter, Length& l, WeightMap map)
Chris@16:             : iter_(iter), tourlen_(l), wmap_(map), previous_(null())
Chris@16:         { }
Chris@16: 
Chris@16:         void visit_vertex(Vertex v, const Graph& g)
Chris@16:         {
Chris@16:             typedef typename graph_traits<Graph>::edge_descriptor Edge;
Chris@16: 
Chris@16:             // If it is not the start, then there is a
Chris@16:             // previous vertex
Chris@16:             if(previous_ != null())
Chris@16:             {
Chris@16:                 // NOTE: For non-adjacency matrix graphs g, this bit of code
Chris@16:                 // will be linear in the degree of previous_ or v. A better
Chris@16:                 // solution would be to visit edges of the graph, but that
Chris@16:                 // would require revisiting the core algorithm.
Chris@16:                 Edge e;
Chris@16:                 bool found;
Chris@16:                 boost::tie(e, found) = lookup_edge(previous_, v, g);
Chris@16:                 if(!found) {
Chris@16:                     BOOST_THROW_EXCEPTION(not_complete());
Chris@16:                 }
Chris@16: 
Chris@16:                 tourlen_ += wmap_[e];
Chris@16:             }
Chris@16: 
Chris@16:             previous_ = v;
Chris@16:             *iter_++ = v;
Chris@16:         }
Chris@16:     };
Chris@16: 
Chris@16:     // Object generator(s)
Chris@16:     template <typename OutIter>
Chris@16:     inline tsp_tour_visitor<OutIter>
Chris@16:     make_tsp_tour_visitor(OutIter iter)
Chris@16:     { return tsp_tour_visitor<OutIter>(iter); }
Chris@16: 
Chris@16:     template <typename Graph, typename WeightMap, typename OutIter, typename Length>
Chris@16:     inline tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length>
Chris@16:     make_tsp_tour_len_visitor(Graph const& g, OutIter iter, Length& l, WeightMap map)
Chris@16:     { return tsp_tour_len_visitor<Graph, WeightMap, OutIter, Length>(g, iter, l, map); }
Chris@16: 
Chris@16: } //boost
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_METRIC_TSP_APPROX_HPP