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