[Boost-commit] svn:boost r83410 - in trunk: boost/graph libs/graph/doc libs/graph/test

Subject: [Boost-commit] svn:boost r83410 - in trunk: boost/graph libs/graph/doc libs/graph/test
From: jewillco_at_[hidden]
Date: 2013-03-11 20:35:49

Author: jewillco
Date: 2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
New Revision: 83410
URL: http://svn.boost.org/trac/boost/changeset/83410

Log:
Added maximum adjacency search from Fernando Vilas; fixes #6780
Added:
   trunk/boost/graph/maximum_adjacency_search.hpp   (contents, props changed)
   trunk/libs/graph/doc/maximum_adjacency_search.html   (contents, props changed)
   trunk/libs/graph/test/mas_test.cpp   (contents, props changed)
Text files modified: 
   trunk/boost/graph/stoer_wagner_min_cut.hpp  |   339 ++++++++++++++++++++------------------- 
   trunk/libs/graph/doc/table_of_contents.html |     1                                         
   trunk/libs/graph/test/Jamfile.v2            |     1                                         
   3 files changed, 177 insertions(+), 164 deletions(-)

Added: trunk/boost/graph/maximum_adjacency_search.hpp
==============================================================================
--- (empty file)
+++ trunk/boost/graph/maximum_adjacency_search.hpp	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -0,0 +1,321 @@
+//
+//=======================================================================
+// 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::graph_traits<Graph>::vertices_size_type vertices_size_type;
+      typedef typename boost::graph_traits<Graph>::edge_descriptor edge_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

Modified: trunk/boost/graph/stoer_wagner_min_cut.hpp
==============================================================================
--- trunk/boost/graph/stoer_wagner_min_cut.hpp	(original)
+++ trunk/boost/graph/stoer_wagner_min_cut.hpp	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -15,104 +15,96 @@
 #include <boost/graph/buffer_concepts.hpp>
 #include <boost/graph/exception.hpp>
 #include <boost/graph/graph_traits.hpp>
-#include <boost/graph/iteration_macros.hpp>
+#include <boost/graph/maximum_adjacency_search.hpp>
 #include <boost/graph/named_function_params.hpp>
+#include <boost/graph/one_bit_color_map.hpp>
 #include <boost/graph/detail/d_ary_heap.hpp>
 #include <boost/property_map/property_map.hpp>
 #include <boost/tuple/tuple.hpp>
 #include <boost/utility/result_of.hpp>
+#include <boost/graph/iteration_macros.hpp>
 
 namespace boost {
-  
+
   namespace detail {
-    
-    /**
-     * \brief Performs a phase of the Stoer-Wagner min-cut algorithm
-     *
-     * Performs a phase of the Stoer-Wagner min-cut algorithm.
-     *
-     * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search
-     * (also called a maximum cardinality search), which results in the selection of two vertices
-     * \em s and \em t, and, as a side product, a minimum <em>s</em>-<em>t</em> cut of
-     * the input graph. Here, the input graph is basically \p g, but some vertices are virtually
-     * assigned to others as a way of viewing \p g as a graph with some sets of
-     * vertices merged together.
-     *
-     * This implementation is a translation of pseudocode by Professor Uri Zwick,
-     * School of Computer Science, Tel Aviv University.
-     *
-     * \pre \p g is a connected, undirected graph
-     * \param[in] g the input graph
-     * \param[in] assignments a read/write property map from each vertex to the vertex that it is assigned to
-     * \param[in] assignedVertices a list of vertices that are assigned to others
-     * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
-     * \param[out] pq a keyed, updatable max-priority queue
-     * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>"
-     *     of the minimum <em>s</em>-<em>t</em> cut and the cut weight \em w
-     *     of the minimum <em>s</em>-<em>t</em> cut.
-     * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
-     *
-     * \author Daniel Trebbien
-     * \date 2010-09-11
-     */
-    template <class UndirectedGraph, class VertexAssignmentMap, class WeightMap, class KeyedUpdatablePriorityQueue>
-    boost::tuple<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::property_traits<WeightMap>::value_type>
-    stoer_wagner_phase(const UndirectedGraph& g, VertexAssignmentMap assignments, const std::set<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor>& assignedVertices, WeightMap weights, KeyedUpdatablePriorityQueue& pq) {
-      typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+    template < typename ParityMap, typename WeightMap, typename IndexMap >
+    class mas_min_cut_visitor : public boost::default_mas_visitor {
+      typedef one_bit_color_map <IndexMap> InternalParityMap;
       typedef typename boost::property_traits<WeightMap>::value_type weight_type;
-      
-      BOOST_ASSERT(pq.empty());
-      typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
-      
-      BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
-        if (v == get(assignments, v)) { // foreach u \in V do
-          put(keys, v, weight_type(0));
-          
-          pq.push(v);
-        }
+    public:
+      template < typename Graph >
+      mas_min_cut_visitor(const Graph& g,
+                          ParityMap parity,
+                          weight_type& cutweight,
+                          WeightMap weight_map, 
+                          IndexMap index_map)
+        : m_bestParity(parity),
+          m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
+          m_bestWeight(cutweight),
+          m_cutweight(0),
+          m_visited(0),
+          m_weightMap(weight_map)
+      {
+        // set here since the init list sets the reference
+        m_bestWeight = (std::numeric_limits<weight_type>::max)();
       }
-      
-      BOOST_ASSERT(pq.size() >= 2);
-      
-      vertex_descriptor s = boost::graph_traits<UndirectedGraph>::null_vertex();
-      vertex_descriptor t = boost::graph_traits<UndirectedGraph>::null_vertex();
-      weight_type w;
-      while (!pq.empty()) { // while PQ \neq {} do
-        const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
-        w = get(keys, u);
-        pq.pop();
-        
-        s = t; t = u;
-        
-        BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) { // foreach (u, v) \in E do
-          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);
-          }
+
+      template < typename Vertex, typename Graph >
+      void initialize_vertex(Vertex u, const Graph & g)
+      {
+        typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+        typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
+
+        put(m_parity, u, internal_parity_type(0));
+        put(m_bestParity, u, parity_type(0));
+      }
+
+      template < typename Edge, typename Graph >
+      void examine_edge(Edge e, const Graph & g)
+      {
+        weight_type w = get(m_weightMap, e);
+
+        // if the target of e is already marked then decrease cutweight
+        // otherwise, increase it
+        if (get(m_parity, boost::target(e, g))) {
+          m_cutweight -= w;
+        } else {
+          m_cutweight += w;
         }
-        
-        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, UndirectedGraph) { // foreach (u, v) \in E do
-              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);
-              }
-            }
+      }
+
+      template < typename Vertex, typename Graph >
+      void finish_vertex(Vertex u, const Graph & g)
+      {
+        typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+        typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
+
+        ++m_visited;
+        put(m_parity, u, internal_parity_type(1));
+
+        if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) {
+          m_bestWeight = m_cutweight;
+          BGL_FORALL_VERTICES_T(i, g, Graph) {
+            put(m_bestParity,i, get(m_parity,i));
           }
         }
       }
-      
-      return boost::make_tuple(s, t, w);
-    }
-    
+
+      inline void clear() {
+        m_bestWeight = (std::numeric_limits<weight_type>::max)();
+        m_visited = 0;
+        m_cutweight = 0;
+      }
+
+    private:
+      ParityMap m_bestParity;
+      InternalParityMap m_parity;
+      weight_type& m_bestWeight;
+      weight_type m_cutweight;
+      unsigned m_visited;
+      const WeightMap& m_weightMap;
+    };
+
     /**
      * \brief Computes a min-cut of the input graph
      *
@@ -135,9 +127,57 @@
      * \author Daniel Trebbien
      * \date 2010-09-11
      */
-    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
+    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
     typename boost::property_traits<WeightMap>::value_type
-    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
+    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
+      typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+      typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
+      typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
+      typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+      typedef typename boost::property_traits<ParityMap>::value_type parity_type;
+
+      typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
+
+      weight_type bestW = (std::numeric_limits<weight_type>::max)();
+      weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
+      vertex_descriptor bestStart;
+
+      detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
+        vis(g, parities, bestThisTime, weights, index_map);
+
+      // for each node in the graph,
+      for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
+        // run the MAS and find the min cut
+        vis.clear();
+        boost::maximum_adjacency_search(g,
+            boost::weight_map(weights).
+            visitor(vis).
+            root_vertex(*u_iter).
+            vertex_assignment_map(assignments).
+            max_priority_queue(pq));
+        if (bestThisTime < bestW) {
+          bestW = bestThisTime;
+          bestStart = *u_iter;
+        }
+      }
+
+      // Run one more time, starting from the best start location, to
+      // ensure the visitor has the best values.
+      vis.clear();
+      boost::maximum_adjacency_search(g,
+        boost::vertex_assignment_map(assignments).
+        weight_map(weights).
+        visitor(vis).
+        root_vertex(bestStart).
+        max_priority_queue(pq));
+
+      return bestW;
+    }
+  } // end `namespace detail` within `namespace boost`
+
+    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
+    typename boost::property_traits<WeightMap>::value_type
+    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
       BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
       BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
       typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
@@ -151,91 +191,62 @@
       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.");
-      
-      std::set<vertex_descriptor> assignedVertices;
-      
-      // initialize `assignments` (all vertices are initially assigned to themselves)
-      BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
-        put(assignments, v, v);
-      }
-      
-      vertex_descriptor s, t;
-      weight_type bestW;
-      
-      boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
-      BOOST_ASSERT(s != t);
-      BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
-        put(parities, v, parity_type(v == t ? 1 : 0));
-      }
-      put(assignments, t, s);
-      assignedVertices.insert(t);
-      --n;
-      
-      for (; n >= 2; --n) {
-        weight_type w;
-        boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
-        BOOST_ASSERT(s != t);
-        
-        if (w < bestW) {
-          BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
-            put(parities, v, parity_type(get(assignments, v) == t ? 1 : 0));
-            
-            if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
-              put(assignments, v, s);
-          }
-          
-          bestW = w;
-        } else {
-          BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
-            if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
-              put(assignments, v, s);
-          }
-        }
-        put(assignments, t, s);
-        assignedVertices.insert(t);
-      }
-      
-      BOOST_ASSERT(pq.empty());
-      
-      return bestW;
+
+      return detail::stoer_wagner_min_cut(g, weights,
+                                          parities, assignments, pq, index_map);
     }
-    
-  } // end `namespace detail` within `namespace boost`
-  
-  template <class UndirectedGraph, class WeightMap, class P, class T, class R>
-  inline typename boost::property_traits<WeightMap>::value_type
-  stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, const boost::bgl_named_params<P, T, R>& params) {
-    typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
-    typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type;
-    typedef typename boost::property_traits<WeightMap>::value_type weight_type;
-    
-    typedef boost::bgl_named_params<P, T, R> params_type;
-    BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
-    
-    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> > gen_type;
-    gen_type gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
-    typename boost::result_of<gen_type(const UndirectedGraph&, const arg_pack_type&)>::type pq = gen(g, arg_pack);
-    
-    return boost::detail::stoer_wagner_min_cut(g,
-        weights,
-        choose_param(get_param(params, boost::parity_map_t()), boost::dummy_property_map()),
-        boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
-        pq
-      );
-  }
-  
-  template <class UndirectedGraph, class WeightMap>
-  inline typename boost::property_traits<WeightMap>::value_type
-  stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights) {
-    return boost::stoer_wagner_min_cut(g, weights, boost::vertex_index_map(get(boost::vertex_index, g)));
+
+namespace graph {
+  namespace detail {
+    template <class UndirectedGraph, class WeightMap>
+    struct stoer_wagner_min_cut_impl {
+      typedef typename boost::property_traits<WeightMap>::value_type result_type;
+      template <typename ArgPack>
+      result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const {
+        using namespace boost::graph::keywords;
+        typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
+        typedef typename boost::property_traits<WeightMap>::value_type weight_type;
+
+        typedef typename boost::detail::make_priority_queue_from_arg_pack_gen<boost::graph::keywords::tag::max_priority_queue, weight_type, vertex_descriptor, std::greater<weight_type> > gen_type;
+
+        gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
+
+        typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack);
+
+        return boost::stoer_wagner_min_cut(g,
+          weights,
+          arg_pack [_parity_map | boost::dummy_property_map()],
+          boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
+          pq,
+          boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index)
+        );
+      }
+    };
   }
-  
+  BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4)
+}
+
+  // Named parameter interface
+  BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
+namespace graph {
+    // version without IndexMap kept for backwards compatibility
+    // (but requires vertex_index_t to be defined in the graph)
+    // Place after the macro to avoid compilation errors
+    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
+    typename boost::property_traits<WeightMap>::value_type
+    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
+
+      return stoer_wagner_min_cut(g, weights,
+                                  parities, assignments, pq,
+                                  get(vertex_index, g));
+    }
+} // end `namespace graph`
 } // end `namespace boost`
 
 #include <boost/graph/iteration_macros_undef.hpp>

Added: trunk/libs/graph/doc/maximum_adjacency_search.html
==============================================================================
--- (empty file)
+++ trunk/libs/graph/doc/maximum_adjacency_search.html	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -0,0 +1,284 @@
+<html>
+<!--
+    Copyright (c) Fernando Vilas 2013
+
+
+    Some content from the Stoer-Wagner Min Cut documentation,
+    Copyright (c) Daniel Trebbien 2010
+
+     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)
+  -->
+<head>
+<title>Boost Graph Library: Maximum Adjacency Search</Title>
+<body>
+<img src="../../../boost.png" alt="C++ Boost" width="277" height="86">
+
+<h1><a name="sec:maximum-adjacency-search"></a>
+<tt>maximum_adjacency_search</tt>
+</h1>
+
+<p>
+<pre>
+<em>// named parameter versions</em>
+template &lt;class Graph, class class P, class T, class R&gt;
+void
+maximum_adjacency_search(const Graph&amp; g,
+       const bgl_named_params&lt;P, T, R&gt;&amp; params);
+
+<i>// non-named parameter versions</i>
+template &lt;class Graph, class WeightMap, class MASVisitor&gt;
+void
+maximum_adjacency_search(const Graph&amp; g, WeightMap weights, MASVisitor vis,
+       const typename graph_traits&lt;Graph&gt;::vertex_descriptor start);
+
+</pre>
+
+<p>
+The <tt>maximum_adjacency_search()</tt> function performs a traversal
+of the vertices in an undirected graph. The next vertex visited is the
+vertex that has the most visited neighbors at any time. In the case of
+an unweighted, undirected graph, the number of visited neighbors of the
+very last vertex visited in the graph is also the number of edge-disjoint
+paths between that vertex and the next-to-last vertex visited. These can be
+retrieved from a visitor, an example of which is in the test harness
+mas_test.cpp.
+</p>
+
+<p>
+The <tt>maximum_adjacency_search()</tt> function invokes user-defined
+actions at certain event-points within the algorithm. This provides a
+mechanism for adapting the generic MAS algorithm to the many situations
+in which it can be used. In the pseudo-code below, the event points
+for MAS are the labels on the right. The user-defined actions must be
+provided in the form of a visitor object, that is, an object whose type
+meets the requirements for a MAS Visitor.
+</p>
+
+<table>
+<tr>
+<td valign="top">
+<pre>
+MAS(<i>G</i>)
+  <b>for</b> each vertex <i>u in V</i> 
+    <i>reach_count[u] := 0</i>
+  <b>end for</b>
+  // for the starting vertex s
+  <i>reach_count[s] := 1</i>
+  <b>for</b> each unvisited vertex <i>u in V</i>
+    <b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
+    remove u from the list on unvisited vertices
+    <b>for</b> each out edge from <i>u</i> to <i>t</i>
+       <b>if</b> <i>t</i> has not yet been visited
+         increment <i>reach_count[t]</i>
+       <b>end if</b>
+    <b>end for</b> each out edge
+    <b>call</b> MAS-VISIT(<i>G</i>, <i>u</i>)
+  <b>end for</b> each unvisited vertex
+<pre>
+</td>
+<td valign="top">
+<pre>
+-
+-
+initialize vertex <i>u</i>
+-
+-
+-
+-
+examine vertex <i>u</i>
+-
+examine edge <i>(u,t)</i>
+-
+-
+-
+-
+finish vertex <i>u</i>
+-
+</pre>
+</td>
+</tr>
+</table>
+
+<h3>Where Defined</h3>
+
+<p>
+boost/graph/maximum_adjacency_search.hpp</p>
+
+<h3>Parameters</h3>
+
+IN: <tt>const UndirectedGraph&amp; g</tt></p>
+<blockquote>
+  A connected, directed graph. The graph type must
+  be a model of Incidence Graph
+  and Vertex List Graph.<br>
+</blockquote>
+
+<h3>Named Parameters</h3>
+
+<p>IN: <tt>WeightMap weights</tt></p>
+<blockquote>
+  The weight or length of each edge in the graph. The
+  <tt>WeightMap</tt> type must be a model of
+  <a href="../../property_map/doc/ReadablePropertyMap.html">Readable
+  Property Map</a> and its value type must be <a class="external"
+  href="http://www.sgi.com/tech/stl/LessThanComparable.html">
+  Less Than Comparable</a> and summable. The key type of this map
+  needs to be the graph's edge descriptor type.
+  <b>Default:</b> <tt>get(edge_weight, g)</tt><br>
+</blockquote>
+
+IN: <tt>visitor(MASVisitor vis)</tt></p>
+<blockquote>
+  A visitor object that is invoked inside the algorithm at the
+  event-points specified by the MAS Visitor concept. The visitor
+  object is passed by value [1]. <br>
+  <b>Default:</b> <tt>mas_visitor&lt;null_visitor&gt;</tt><br>
+</blockquote>
+
+IN: <tt>root_vertex(typename
+graph_traits&lt;VertexListGraph&gt;::vertex_descriptor start)</tt></p>
+<blockquote>
+  This specifies the vertex that the depth-first search should
+  originate from. The type is the type of a vertex descriptor for the
+  given graph.<br>
+  <b>Default:</b> <tt>*vertices(g).first</tt><br>
+</blockquote>
+
+<h4>Expert Parameters</h4>
+
+<p>IN: <tt>vertex_index_map(VertexIndexMap vertexIndices)</tt> </p>
+<blockquote>
+  This maps each vertex to an integer in the range
+  [0, <tt>num_vertices(g)</tt>). This is only necessary if the default is
+  used for the assignment, index-in-heap, or distance maps.
+  <tt>VertexIndexMap</tt> must be a model of <a
+  href="../../property_map/doc/ReadablePropertyMap.html">Readable Property
+  Map</a>. The value type of the map must be an integer type. The
+  key type must be the graph's vertex descriptor type.<br>
+  <b>Default:</b> <tt>get(boost::vertex_index, g)</tt>
+    Note: if you use this default, make sure your graph has
+    an internal <tt>vertex_index</tt> property. For example,
+    <tt>adjacency_list</tt> with <tt>VertexList=listS</tt> does
+    not have an internal <tt>vertex_index</tt> property.
+</blockquote>
+
+<p>UTIL: <tt>vertex_assignment_map(AssignmentMap assignments)</tt></p>
+<blockquote>
+  <tt>AssignmentMap</tt> must be a model of <a
+  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+  Map</a>. The key and value types must be the graph's vertex descriptor
+  type.<br>
+  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
+  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> vertex descriptors and
+  <tt>vertexIndices</tt> for the index map.
+</blockquote>
+
+<p>UTIL: <tt>max_priority_queue(MaxPriorityQueue&amp; pq)</tt></p>
+<blockquote>
+  <tt>MaxPriorityQueue</tt> must be a model of <a
+  href="./KeyedUpdatableQueue.html">Keyed Updatable Queue</a> and a
+  max-<a href="./UpdatableQueue.html#concept%3AUpdatablePriorityQueue">
+  Updatable Priority Queue</a>. The value type must be the graph's vertex
+  descriptor and the key type must be the weight type.
+  <b>Default:</b> A <tt>boost::d_ary_heap_indirect</tt> using a default
+  index-in-heap and distance map.
+</blockquote>
+
+<p>UTIL: <tt>index_in_heap_map(IndexInHeapMap indicesInHeap)</tt></p>
+<blockquote>
+  This parameter only has an effect when the default max-priority queue is used.<br>
+  <tt>IndexInHeapMap</tt> must be a model of <a
+  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+  Map</a>. The key type must be the graph's vertex descriptor type. The
+  value type must be a size type
+  (<tt>typename&nbsp;std::vector&lt;vertex_descriptor&gt;::size_type</tt>).<br>
+  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
+  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> size type objects and
+  <tt>vertexIndices</tt> for the index map.
+</blockquote>
+
+<p>UTIL: <tt>distance_map(DistanceMap wAs)</tt></p>
+<blockquote>
+  This parameter only has an effect when the default max-priority queue is used.<br>
+  <tt>DistanceMap</tt> must be a model of <a
+  href="../../property_map/doc/ReadWritePropertyMap.html">Read/Write Property
+  Map</a>. The key type must be the graph's vertex descriptor type. The
+  value type must be the weight type
+  (<tt>typename&nbsp;boost::property_traits&lt;WeightMap&gt;::value_type</tt>).
+  <br>
+  <b>Default:</b> A <tt>boost::iterator_property_map</tt> using a
+  <tt>std::vector</tt> of <tt>num_vertices(g)</tt> weight type objects
+  and <tt>vertexIndices</tt> for the index map.
+</blockquote>
+
+<h3>Returns</h3>
+<p>void</p>
+
+<h3>Throws</h3>
+
+<p><tt>bad_graph</tt>
+<blockquote>
+  If <tt>num_vertices(g)</tt> is less than 2
+</blockquote></p>
+
+<p><tt>std::invalid_argument</tt>
+<blockquote>
+  If a max-priority queue is given as an argument and it is not empty
+</blockquote>.
+
+<h3><a name="SECTION001340300000000000000">
+Complexity</a>
+</h3>
+
+<p>
+The time complexity is <i>O(E + V)</i>.
+</p>
+
+<h3>References</h3>
+<ul>
+<li>David Matula (1993). <q>A linear time 2 + epsilon approximation algorightm for edge connectivity</q>
+</li>
+<li>Cai, Weiqing and Matula, David W. 
+Partitioning by maximum adjacency search of graphs. 
+Partitioning Data Sets: Dimacs Workshop, April 19-21, 1993. 
+Vol 19. Page 55. 1995. Amer Mathematical Society</li>
+}
+</ul>
+
+<h3>Visitor Event Points</h3>
+
+<ul>
+<li><b><tt>vis.initialize_vertex(s, g)</tt></b> is invoked on every
+  vertex of the graph before the start of the graph search.</li>
+
+<li><b><tt>vis.start_vertex(s, g)</tt></b> is invoked on the source
+  vertex once before processing its out edges.</li>
+
+<li><b><tt>vis.examine_edge(e, g)</tt></b> is invoked on every out-edge
+  of each vertex after it is started.</li>
+
+<li><b><tt>vis.finish_vertex(u, g)</tt></b> is invoked on a vertex after
+  all of its out edges have been examined and the reach counts of the
+  unvisited targets have been updated.</li>
+</ul>
+
+<h3>Notes</h3>
+
+<p><a name="1">[1]</a> 
+  Since the visitor parameter is passed by value, if your visitor
+  contains state then any changes to the state during the algorithm
+  will be made to a copy of the visitor object, not the visitor object
+  passed in. Therefore you may want the visitor to hold this state by
+  pointer or reference.</p>
+
+<hr>
+<table>
+<tr valign=top>
+<td nowrap>Copyright &copy; 2012</td><td>
+Fernando Vilas
+</td></tr></table>
+
+</body>
+</html> 

Modified: trunk/libs/graph/doc/table_of_contents.html
==============================================================================
--- trunk/libs/graph/doc/table_of_contents.html	(original)
+++ trunk/libs/graph/doc/table_of_contents.html	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -287,6 +287,7 @@
                       <LI>sequential_vertex_coloring
                       <LI>is_bipartite (including two-coloring of bipartite graphs)
                       <LI>find_odd_cycle
+                      <LI>maximum_adjacency_search
                   </ol>
               </li>
 

Modified: trunk/libs/graph/test/Jamfile.v2
==============================================================================
--- trunk/libs/graph/test/Jamfile.v2	(original)
+++ trunk/libs/graph/test/Jamfile.v2	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -123,6 +123,7 @@
     [ run two_graphs_common_spanning_trees_test.cpp ]
     [ run random_spanning_tree_test.cpp ../build//boost_graph ]
     [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
+    [ run mas_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
     [ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
     [ compile filtered_graph_properties_dijkstra.cpp ]
     [ run vf2_sub_graph_iso_test.cpp ]

Added: trunk/libs/graph/test/mas_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/graph/test/mas_test.cpp	2013-03-11 20:35:48 EDT (Mon, 11 Mar 2013)
@@ -0,0 +1,227 @@
+//            Copyright Fernando Vilas 2012.
+//     Based on stoer_wagner_test.cpp by Daniel Trebbien.
+// Distributed under the Boost Software License, Version 1.0.
+//   (See accompanying file LICENSE_1_0.txt or the copy at
+//         http://www.boost.org/LICENSE_1_0.txt)
+
+#include <fstream>
+#include <iostream>
+#include <map>
+#include <vector>
+#include <string>
+#include <boost/graph/adjacency_list.hpp>
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/exception.hpp>
+#include <boost/graph/graph_traits.hpp>
+#include <boost/graph/read_dimacs.hpp>
+#include <boost/graph/maximum_adjacency_search.hpp>
+#include <boost/graph/visitors.hpp>
+#include <boost/graph/property_maps/constant_property_map.hpp>
+#include <boost/property_map/property_map.hpp>
+#include <boost/test/unit_test.hpp>
+#include <boost/tuple/tuple.hpp>
+#include <boost/tuple/tuple_comparison.hpp>
+#include <boost/tuple/tuple_io.hpp>
+
+#include <boost/graph/iteration_macros.hpp>
+
+typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, boost::no_property, boost::property<boost::edge_weight_t, int> > undirected_graph;
+typedef boost::property_map<undirected_graph, boost::edge_weight_t>::type weight_map_type;
+typedef boost::property_traits<weight_map_type>::value_type weight_type;
+
+typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> undirected_unweighted_graph;
+
+std::string test_dir;
+
+boost::unit_test::test_suite* init_unit_test_suite( int argc, char* argv[] ) {
+  if (argc != 2) {
+    std::cerr << "Usage: " << argv[0] << " path-to-libs-graph-test" << std::endl;
+    throw boost::unit_test::framework::setup_error("Invalid command line arguments");
+  }
+  test_dir = argv[1];
+  return 0;
+}
+
+struct edge_t
+{
+  unsigned long first;
+  unsigned long second;
+};
+
+template <typename Graph, typename KeyedUpdatablePriorityQueue>
+class mas_edge_connectivity_visitor : public boost::default_mas_visitor {
+  public:
+    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
+    typedef typename KeyedUpdatablePriorityQueue::key_type weight_type;
+#if 0
+    mas_edge_connectivity_visitor(const mas_edge_connectivity_visitor<Graph, KeyedUpdatablePriorityQueue>& r)
+      : m_pq(r.m_pq), m_curr(r.m_curr), m_prev(r.m_prev), 
+        m_reach_weight(r.m_reach_weight) {
+          BOOST_TEST_MESSAGE( "COPY CTOR" );
+        }
+#endif
+    explicit mas_edge_connectivity_visitor(KeyedUpdatablePriorityQueue& pq)
+      : m_pq(pq),
+        m_curr(new vertex_descriptor(0)), m_prev(new vertex_descriptor(0)),
+        m_reach_weight(new weight_type(0)) {
+      //    BOOST_TEST_MESSAGE( "CTOR" );
+        }
+
+  void clear() {
+    *m_curr = 0;
+    *m_prev = 0;
+    *m_reach_weight = 0;
+  }
+
+  //template <typename Vertex> //, typename Graph>
+  //void start_vertex(Vertex u, const Graph& g) {
+  void start_vertex(vertex_descriptor u, const Graph& g) {
+    *m_prev = *m_curr;
+    *m_curr = u;
+    //BOOST_TEST_MESSAGE( "Initializing Vertex(weight): " << u << "(" << *m_reach_weight << ")" );
+    *m_reach_weight = get(m_pq.keys(), u);
+  }
+
+  vertex_descriptor curr() const { return *m_curr; }
+  vertex_descriptor prev() const { return *m_prev; }
+  weight_type reach_weight() const { return *m_reach_weight; }
+
+  private:
+
+    const KeyedUpdatablePriorityQueue& m_pq;
+    boost::shared_ptr<vertex_descriptor> m_curr, m_prev;
+    boost::shared_ptr<weight_type> m_reach_weight;
+};
+
+
+// the example from Stoer & Wagner (1997)
+// Check various implementations of the ArgPack where
+// the weights are provided in it, and one case where
+// they are not.
+BOOST_AUTO_TEST_CASE(test0)
+{
+  typedef boost::graph_traits<undirected_graph>::vertex_descriptor vertex_descriptor;
+  typedef boost::graph_traits<undirected_graph>::edge_descriptor edge_descriptor;
+
+  edge_t edges[] = {{0, 1}, {1, 2}, {2, 3},
+    {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
+  weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
+  undirected_graph g(edges, edges + 12, ws, 8, 12);
+
+  weight_map_type weights = get(boost::edge_weight, g);
+
+  std::map<vertex_descriptor, vertex_descriptor> assignment;
+  boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
+
+  typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
+  distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
+  typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
+  typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
+  indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
+  boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
+
+  mas_edge_connectivity_visitor<undirected_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > >  test_vis(pq);
+
+  boost::maximum_adjacency_search(g,
+        boost::weight_map(weights).
+        visitor(test_vis).
+        root_vertex(*vertices(g).first).
+        vertex_assignment_map(assignments).
+        max_priority_queue(pq));
+
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+  test_vis.clear();
+  boost::maximum_adjacency_search(g,
+        boost::weight_map(weights).
+        visitor(test_vis).
+        root_vertex(*vertices(g).first).
+        max_priority_queue(pq));
+
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+  test_vis.clear();
+  boost::maximum_adjacency_search(g,
+        boost::weight_map(weights).
+        visitor(test_vis).
+        max_priority_queue(pq));
+
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), 5);
+
+  boost::maximum_adjacency_search(g,
+        boost::weight_map(weights).
+        visitor(boost::make_mas_visitor(boost::null_visitor())));
+
+  boost::maximum_adjacency_search(g,
+        boost::weight_map(weights));
+
+  boost::maximum_adjacency_search(g,
+        boost::root_vertex(*vertices(g).first));
+
+  test_vis.clear();
+  boost::maximum_adjacency_search(g,
+      boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).
+      visitor(test_vis).
+      max_priority_queue(pq));
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), 2);
+
+}
+
+// Check the unweighted case
+// with and without providing a weight_map
+BOOST_AUTO_TEST_CASE(test1)
+{
+  typedef boost::graph_traits<undirected_unweighted_graph>::vertex_descriptor vertex_descriptor;
+  typedef boost::graph_traits<undirected_unweighted_graph>::edge_descriptor edge_descriptor;
+
+  edge_t edge_list[] = {{0, 1}, {1, 2}, {2, 3},
+    {0, 4}, {1, 4}, {1, 5}, {2, 6}, {3, 6}, {3, 7}, {4, 5}, {5, 6}, {6, 7}};
+  undirected_unweighted_graph g(edge_list, edge_list + 12, 8);
+
+  std::map<vertex_descriptor, vertex_descriptor> assignment;
+  boost::associative_property_map<std::map<vertex_descriptor, vertex_descriptor> > assignments(assignment);
+
+  typedef unsigned weight_type;
+  typedef boost::shared_array_property_map<weight_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> distances_type;
+  distances_type distances = boost::make_shared_array_property_map(num_vertices(g), weight_type(0), get(boost::vertex_index, g));
+  typedef std::vector<vertex_descriptor>::size_type index_in_heap_type;
+  typedef boost::shared_array_property_map<index_in_heap_type, boost::property_map<undirected_graph, boost::vertex_index_t>::const_type> indicesInHeap_type;
+  indicesInHeap_type indicesInHeap = boost::make_shared_array_property_map(num_vertices(g), index_in_heap_type(-1), get(boost::vertex_index, g));
+  boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > pq(distances, indicesInHeap);
+
+  mas_edge_connectivity_visitor<undirected_unweighted_graph,boost::d_ary_heap_indirect<vertex_descriptor, 22, indicesInHeap_type, distances_type, std::greater<weight_type> > >  test_vis(pq);
+
+  boost::maximum_adjacency_search(g, 
+         boost::weight_map(boost::make_constant_property<edge_descriptor>(weight_type(1))).visitor(test_vis).max_priority_queue(pq));
+
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(3));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(2));
+
+  weight_type ws[] = {2, 3, 4, 3, 2, 2, 2, 2, 2, 3, 1, 3};
+  std::map<edge_descriptor, weight_type> wm;
+
+  weight_type i = 0;
+  BGL_FORALL_EDGES_T(e, g, undirected_unweighted_graph) {
+    wm[e] = ws[i];
+    ++i;
+  }
+  boost::associative_property_map<std::map<edge_descriptor, weight_type> > ws_map(wm);
+
+  boost::maximum_adjacency_search(g, boost::weight_map(ws_map).visitor(test_vis).max_priority_queue(pq));
+  BOOST_CHECK_EQUAL(test_vis.curr(), vertex_descriptor(7));
+  BOOST_CHECK_EQUAL(test_vis.prev(), vertex_descriptor(6));
+  BOOST_CHECK_EQUAL(test_vis.reach_weight(), weight_type(5));
+
+}
+
+#include <boost/graph/iteration_macros_undef.hpp>
+