boost/boost/graph/maximum_adjacency_search.hpp - nest-cam/4320010/boost - Git at Google

 //
 //=======================================================================
 // Copyright 2012 Fernando Vilas
 //           2010 Daniel Trebbien
 //
 // 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)
 //=======================================================================
 //

 // The maximum adjacency search algorithm was originally part of the
 // Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
 // broken out into its own file to be a public search algorithm, with
 // visitor concepts.
 #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
 #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H

 /**
  * This is an implementation of the maximum adjacency search on an
  * undirected graph. It allows a visitor object to perform some
  * operation on each vertex as that vertex is visited.
  *
  * The algorithm runs as follows:
  *
  * Initialize all nodes to be unvisited (reach count = 0)
  *   and call vis.initialize_vertex
  * For i = number of nodes in graph downto 1
  *   Select the unvisited node with the highest reach count
  *     The user provides the starting node to break the first tie,
  *     but future ties are broken arbitrarily
  *   Visit the node by calling vis.start_vertex
  *   Increment the reach count for all unvisited neighbors
  *     and call vis.examine_edge for each of these edges
  *   Mark the node as visited and call vis.finish_vertex
  *
  */

 #include <boost/concept_check.hpp>
 #include <boost/concept/assert.hpp>
 #include <boost/graph/buffer_concepts.hpp>
 #include <boost/graph/exception.hpp>
 #include <boost/graph/graph_concepts.hpp>
 #include <boost/graph/iteration_macros.hpp>
 #include <boost/graph/named_function_params.hpp>
 #include <boost/graph/visitors.hpp>
 #include <boost/tuple/tuple.hpp>

 #include <set>

 namespace boost {
   template <class Visitor, class Graph>
   struct MASVisitorConcept {
     void constraints() {
       boost::function_requires< boost::CopyConstructibleConcept<Visitor> >();
       vis.initialize_vertex(u, g);
       vis.start_vertex(u, g);
       vis.examine_edge(e, g);
       vis.finish_vertex(u, g);
     }
     Visitor vis;
     Graph g;
     typename boost::graph_traits<Graph>::vertex_descriptor u;
     typename boost::graph_traits<Graph>::edge_descriptor e;
   };

   template <class Visitors = null_visitor>
   class mas_visitor {
   public:
     mas_visitor() { }
     mas_visitor(Visitors vis) : m_vis(vis) { }

     template <class Vertex, class Graph>
     void
     initialize_vertex(Vertex u, Graph& g)
     {
       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
     }

     template <class Vertex, class Graph>
     void
     start_vertex(Vertex u, Graph& g)
     {
       invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
     }

     template <class Edge, class Graph>
     void
     examine_edge(Edge e, Graph& g)
     {
       invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
     }

     template <class Vertex, class Graph>
     void
     finish_vertex(Vertex u, Graph& g)
     {
       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
     }

     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas)
     BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas)
     BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas)
     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas)

   protected:
     Visitors m_vis;
   };
   template <class Visitors>
   mas_visitor<Visitors>
   make_mas_visitor(Visitors vis) {
     return mas_visitor<Visitors>(vis);
   }
   typedef mas_visitor<> default_mas_visitor;

   namespace detail {
     template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
       void
       maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
       typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
       typedef typename boost::property_traits<WeightMap>::value_type weight_type;

      std::set<vertex_descriptor> assignedVertices;

      // initialize `assignments` (all vertices are initially
      // assigned to themselves)
      BGL_FORALL_VERTICES_T(v, g, Graph) {
        put(assignments, v, v);
      }

       typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();

       // set number of visited neighbors for all vertices to 0
       BGL_FORALL_VERTICES_T(v, g, Graph) {
         if (v == get(assignments, v)) { // foreach u \in V do
           put(keys, v, weight_type(0));          vis.initialize_vertex(v, g);

           pq.push(v);
         }
       }
       BOOST_ASSERT(pq.size() >= 2);

       // Give the starting vertex high priority
       put(keys, start, get(keys, start) + num_vertices(g) + 1);
       pq.update(start);

       // start traversing the graph
       //vertex_descriptor s, t;
       weight_type w;
       while (!pq.empty()) { // while PQ \neq {} do
         const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
         w = get(keys, u);                        vis.start_vertex(u, g);
         pq.pop();                  //            vis.start_vertex(u, g);

         BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
                                                  vis.examine_edge(e, g);

           const vertex_descriptor v = get(assignments, target(e, g));

           if (pq.contains(v)) { // if v \in PQ then
             put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
             pq.update(v);
           }
         }

         typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
         for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
           const vertex_descriptor uPrime = *assignedVertexIt;

           if (get(assignments, uPrime) == u) {
             BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do
                                                  vis.examine_edge(e, g);

               const vertex_descriptor v = get(assignments, target(e, g));

               if (pq.contains(v)) { // if v \in PQ then
                 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
                 pq.update(v);
               }
             }
           }
         }
                                                  vis.finish_vertex(u, g);
       }
     }
   } // end namespace detail

   template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
     void
 maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
     BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>));
     BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
     typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
     typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
     BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
     BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
     // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
     boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
     BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
     BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
     BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));

     vertices_size_type n = num_vertices(g);
     if (n < 2)
       throw boost::bad_graph("the input graph must have at least two vertices.");
     else if (!pq.empty())
       throw std::invalid_argument("the max-priority queue must be empty initially.");

     detail::maximum_adjacency_search(g, weights,
                                             vis, start,
                                             assignments, pq);
   }

   namespace graph {
     namespace detail {
       template <typename WeightMap>
       struct mas_dispatch {
         typedef void result_type;
         template <typename Graph, typename ArgPack>
         static result_type apply(const Graph& g,
                           //const bgl_named_params<P,T,R>& params,
                           const ArgPack& params,
                           WeightMap w) {

           using namespace boost::graph::keywords;
           typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
           typedef typename WeightMap::value_type weight_type;

           typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type;

           default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

           typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

           boost::maximum_adjacency_search
                (g,
                 w,
                 params [ _visitor | make_mas_visitor(null_visitor())],
                 params [ _root_vertex | *vertices(g).first],
                 params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
                 pq
                 );
         }
       };

       template <>
       struct mas_dispatch<boost::param_not_found> {
         typedef void result_type;

         template <typename Graph, typename ArgPack>
         static result_type apply(const Graph& g,
                           const ArgPack& params,
                           param_not_found) {

           using namespace boost::graph::keywords;
           typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;

           // get edge_weight_t as the weight type
           typedef typename boost::property_map<Graph, edge_weight_t> WeightMap;
           typedef typename WeightMap::value_type weight_type;

           typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type;

           default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

           typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

           boost::maximum_adjacency_search
                (g,
                 get(edge_weight, g),
                 params [ _visitor | make_mas_visitor(null_visitor())],
                 params [ _root_vertex | *vertices(g).first],
                 params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
                 pq
                 );
         }
       };
     } // end namespace detail
   } // end namespace graph

   // Named parameter interface
   //BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
   template <typename Graph, typename P, typename T, typename R>
   void
   maximum_adjacency_search (const Graph& g,
       const bgl_named_params<P,T,R>& params) {

     typedef bgl_named_params<P, T, R> params_type;
     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)

     // do the dispatch based on WeightMap
     typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W;
     graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight));
   }

   namespace graph {
     namespace detail {
       template <typename Graph>
       struct maximum_adjacency_search_impl {
         typedef void result_type;

         template <typename ArgPack>
         void
         operator() (const Graph& g, const ArgPack& arg_pack) const {
           // call the function that does the dispatching
           typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
           graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
         }
       };
     } // end namespace detail
     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
   } // end namespace graph

 } // end namespace boost

 #include <boost/graph/iteration_macros_undef.hpp>

 #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
	//
	//=======================================================================
	// Copyright 2012 Fernando Vilas
	// 2010 Daniel Trebbien
	//
	// 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)
	//=======================================================================
	//

	// The maximum adjacency search algorithm was originally part of the
	// Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
	// broken out into its own file to be a public search algorithm, with
	// visitor concepts.
	#ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
	#define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H

	/**
	* This is an implementation of the maximum adjacency search on an
	* undirected graph. It allows a visitor object to perform some
	* operation on each vertex as that vertex is visited.
	*
	* The algorithm runs as follows:
	*
	* Initialize all nodes to be unvisited (reach count = 0)
	* and call vis.initialize_vertex
	* For i = number of nodes in graph downto 1
	* Select the unvisited node with the highest reach count
	* The user provides the starting node to break the first tie,
	* but future ties are broken arbitrarily
	* Visit the node by calling vis.start_vertex
	* Increment the reach count for all unvisited neighbors
	* and call vis.examine_edge for each of these edges
	* Mark the node as visited and call vis.finish_vertex
	*
	*/

	#include <boost/concept_check.hpp>
	#include <boost/concept/assert.hpp>
	#include <boost/graph/buffer_concepts.hpp>
	#include <boost/graph/exception.hpp>
	#include <boost/graph/graph_concepts.hpp>
	#include <boost/graph/iteration_macros.hpp>
	#include <boost/graph/named_function_params.hpp>
	#include <boost/graph/visitors.hpp>
	#include <boost/tuple/tuple.hpp>

	#include <set>

	namespace boost {
	template <class Visitor, class Graph>
	struct MASVisitorConcept {
	void constraints() {
	boost::function_requires< boost::CopyConstructibleConcept<Visitor> >();
	vis.initialize_vertex(u, g);
	vis.start_vertex(u, g);
	vis.examine_edge(e, g);
	vis.finish_vertex(u, g);
	}
	Visitor vis;
	Graph g;
	typename boost::graph_traits<Graph>::vertex_descriptor u;
	typename boost::graph_traits<Graph>::edge_descriptor e;
	};

	template <class Visitors = null_visitor>
	class mas_visitor {
	public:
	mas_visitor() { }
	mas_visitor(Visitors vis) : m_vis(vis) { }

	template <class Vertex, class Graph>
	void
	initialize_vertex(Vertex u, Graph& g)
	{
	invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
	}

	template <class Vertex, class Graph>
	void
	start_vertex(Vertex u, Graph& g)
	{
	invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
	}

	template <class Edge, class Graph>
	void
	examine_edge(Edge e, Graph& g)
	{
	invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
	}

	template <class Vertex, class Graph>
	void
	finish_vertex(Vertex u, Graph& g)
	{
	invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
	}

	BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas)
	BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas)
	BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas)
	BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas)

	protected:
	Visitors m_vis;
	};
	template <class Visitors>
	mas_visitor<Visitors>
	make_mas_visitor(Visitors vis) {
	return mas_visitor<Visitors>(vis);
	}
	typedef mas_visitor<> default_mas_visitor;

	namespace detail {
	template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
	void
	maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
	typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
	typedef typename boost::property_traits<WeightMap>::value_type weight_type;

	std::set<vertex_descriptor> assignedVertices;

	// initialize `assignments` (all vertices are initially
	// assigned to themselves)
	BGL_FORALL_VERTICES_T(v, g, Graph) {
	put(assignments, v, v);
	}

	typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();

	// set number of visited neighbors for all vertices to 0
	BGL_FORALL_VERTICES_T(v, g, Graph) {
	if (v == get(assignments, v)) { // foreach u \in V do
	put(keys, v, weight_type(0)); vis.initialize_vertex(v, g);

	pq.push(v);
	}
	}
	BOOST_ASSERT(pq.size() >= 2);

	// Give the starting vertex high priority
	put(keys, start, get(keys, start) + num_vertices(g) + 1);
	pq.update(start);

	// start traversing the graph
	//vertex_descriptor s, t;
	weight_type w;
	while (!pq.empty()) { // while PQ \neq {} do
	const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
	w = get(keys, u); vis.start_vertex(u, g);
	pq.pop(); // vis.start_vertex(u, g);

	BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
	vis.examine_edge(e, g);

	const vertex_descriptor v = get(assignments, target(e, g));

	if (pq.contains(v)) { // if v \in PQ then
	put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
	pq.update(v);
	}
	}

	typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
	for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
	const vertex_descriptor uPrime = *assignedVertexIt;

	if (get(assignments, uPrime) == u) {
	BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do
	vis.examine_edge(e, g);

	const vertex_descriptor v = get(assignments, target(e, g));

	if (pq.contains(v)) { // if v \in PQ then
	put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
	pq.update(v);
	}
	}
	}
	}
	vis.finish_vertex(u, g);
	}
	}
	} // end namespace detail

	template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
	void
	maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
	BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>));
	BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
	typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
	typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
	typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
	BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
	BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
	// typedef typename boost::property_traits<WeightMap>::value_type weight_type;
	boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
	BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
	BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
	BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));

	vertices_size_type n = num_vertices(g);
	if (n < 2)
	throw boost::bad_graph("the input graph must have at least two vertices.");
	else if (!pq.empty())
	throw std::invalid_argument("the max-priority queue must be empty initially.");

	detail::maximum_adjacency_search(g, weights,
	vis, start,
	assignments, pq);
	}

	namespace graph {
	namespace detail {
	template <typename WeightMap>
	struct mas_dispatch {
	typedef void result_type;
	template <typename Graph, typename ArgPack>
	static result_type apply(const Graph& g,
	//const bgl_named_params<P,T,R>& params,
	const ArgPack& params,
	WeightMap w) {

	using namespace boost::graph::keywords;
	typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
	typedef typename WeightMap::value_type weight_type;

	typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type;

	default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

	typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

	boost::maximum_adjacency_search
	(g,
	w,
	params [ _visitor \| make_mas_visitor(null_visitor())],
	params [ _root_vertex \| *vertices(g).first],
	params [ _vertex_assignment_map \| boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
	pq
	);
	}
	};

	template <>
	struct mas_dispatch<boost::param_not_found> {
	typedef void result_type;

	template <typename Graph, typename ArgPack>
	static result_type apply(const Graph& g,
	const ArgPack& params,
	param_not_found) {

	using namespace boost::graph::keywords;
	typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;

	// get edge_weight_t as the weight type
	typedef typename boost::property_map<Graph, edge_weight_t> WeightMap;
	typedef typename WeightMap::value_type weight_type;

	typedef boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > default_pq_gen_type;

	default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

	typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

	boost::maximum_adjacency_search
	(g,
	get(edge_weight, g),
	params [ _visitor \| make_mas_visitor(null_visitor())],
	params [ _root_vertex \| *vertices(g).first],
	params [ _vertex_assignment_map \| boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
	pq
	);
	}
	};
	} // end namespace detail
	} // end namespace graph

	// Named parameter interface
	//BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
	template <typename Graph, typename P, typename T, typename R>
	void
	maximum_adjacency_search (const Graph& g,
	const bgl_named_params<P,T,R>& params) {

	typedef bgl_named_params<P, T, R> params_type;
	BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)

	// do the dispatch based on WeightMap
	typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W;
	graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight));
	}

	namespace graph {
	namespace detail {
	template <typename Graph>
	struct maximum_adjacency_search_impl {
	typedef void result_type;

	template <typename ArgPack>
	void
	operator() (const Graph& g, const ArgPack& arg_pack) const {
	// call the function that does the dispatching
	typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
	graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
	}
	};
	} // end namespace detail
	BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
	} // end namespace graph

	} // end namespace boost

	#include <boost/graph/iteration_macros_undef.hpp>

	#endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H