boost/graph/metric_tsp_approx.hpp - platform/external/boost - Git at Google


 //=======================================================================
 // 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

	//=======================================================================
	// 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