text: //            Copyright Daniel Trebbien 2010.
  // 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)
  
  #ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
  #define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
  
  #include <boost/assert.hpp>
  #include <set>
  #include <vector>
  #include <boost/concept_check.hpp>
  #include <boost/concept/assert.hpp>
  #include <boost/graph/adjacency_list.hpp>
  #include <boost/graph/buffer_concepts.hpp>
  #include <boost/graph/exception.hpp>
  #include <boost/graph/graph_traits.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 {
      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;
      public:
        template < typename Graph >
        mas_min_cut_visitor(const Graph& g,
                            ParityMap parity,
                            weight_type& cutweight,
                            const 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)();
        }
  
        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;
          }
        }
  
        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));
            }
          }
        }
  
        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
       *
       * Computes a min-cut of the input graph using the Stoer-Wagner algorithm.
       *
       * \pre \p g is a connected, undirected graph
       * \pre <code>pq.empty()</code>
       * \param[in] g the input graph
       * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
       * \param[out] parities a writable property map from each vertex to a bool type object for
       *     distinguishing the two vertex sets of the min-cut
       * \param[out] assignments a read/write property map from each vertex to a \c vertex_descriptor object. This
       *     map serves as work space, and no particular meaning should be derived from property values
       *     after completion of the algorithm.
       * \param[out] pq a keyed, updatable max-priority queue
       * \returns the cut weight of the min-cut
       * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
       * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
       *
       * \author Daniel Trebbien
       * \date 2010-09-11
       */
      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) {
        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 = boost::graph_traits<UndirectedGraph>::null_vertex();
  
        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;
        typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
        typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
        BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<UndirectedGraph>::directed_category, boost::undirected_tag>));
        BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
        typedef typename boost::property_traits<WeightMap>::value_type weight_type;
        BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<ParityMap, vertex_descriptor>));
        typedef typename boost::property_traits<ParityMap>::value_type parity_type;
        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.");
  
        return detail::stoer_wagner_min_cut(g, weights,
                                            parities, assignments, pq, index_map);
      }
  
  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 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>
  
  #endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
  