| |
| //======================================================================= |
| // 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> |
| #include <boost/graph/lookup_edge.hpp> |
| #include <boost/throw_exception.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&) |
| { path_.push_back(n); } |
| |
| void inorder(Node, const Tree&) const {} |
| void postorder(Node, const Tree&) 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&) |
| { |
| 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; |
| boost::tie(e, found) = lookup_edge(previous_, v, g); |
| if(!found) { |
| BOOST_THROW_EXCEPTION(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 |