Chris@16: //            Copyright Daniel Trebbien 2010.
Chris@16: // Distributed under the Boost Software License, Version 1.0.
Chris@16: //   (See accompanying file LICENSE_1_0.txt or the copy at
Chris@16: //         http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
Chris@16: #define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <set>
Chris@16: #include <vector>
Chris@16: #include <boost/concept_check.hpp>
Chris@16: #include <boost/concept/assert.hpp>
Chris@16: #include <boost/graph/adjacency_list.hpp>
Chris@16: #include <boost/graph/buffer_concepts.hpp>
Chris@16: #include <boost/graph/exception.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/maximum_adjacency_search.hpp>
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: #include <boost/graph/one_bit_color_map.hpp>
Chris@16: #include <boost/graph/detail/d_ary_heap.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/tuple/tuple.hpp>
Chris@16: #include <boost/utility/result_of.hpp>
Chris@16: #include <boost/graph/iteration_macros.hpp>
Chris@16: 
Chris@16: namespace boost {
Chris@16: 
Chris@16:   namespace detail {
Chris@16:     template < typename ParityMap, typename WeightMap, typename IndexMap >
Chris@16:     class mas_min_cut_visitor : public boost::default_mas_visitor {
Chris@16:       typedef one_bit_color_map <IndexMap> InternalParityMap;
Chris@16:       typedef typename boost::property_traits<WeightMap>::value_type weight_type;
Chris@16:     public:
Chris@16:       template < typename Graph >
Chris@16:       mas_min_cut_visitor(const Graph& g,
Chris@16:                           ParityMap parity,
Chris@16:                           weight_type& cutweight,
Chris@16:                           const WeightMap& weight_map, 
Chris@16:                           IndexMap index_map)
Chris@16:         : m_bestParity(parity),
Chris@16:           m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
Chris@16:           m_bestWeight(cutweight),
Chris@16:           m_cutweight(0),
Chris@16:           m_visited(0),
Chris@16:           m_weightMap(weight_map)
Chris@16:       {
Chris@16:         // set here since the init list sets the reference
Chris@16:         m_bestWeight = (std::numeric_limits<weight_type>::max)();
Chris@16:       }
Chris@16: 
Chris@16:       template < typename Vertex, typename Graph >
Chris@16:       void initialize_vertex(Vertex u, const Graph & g)
Chris@16:       {
Chris@16:         typedef typename boost::property_traits<ParityMap>::value_type parity_type;
Chris@16:         typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
Chris@16: 
Chris@16:         put(m_parity, u, internal_parity_type(0));
Chris@16:         put(m_bestParity, u, parity_type(0));
Chris@16:       }
Chris@16: 
Chris@16:       template < typename Edge, typename Graph >
Chris@16:       void examine_edge(Edge e, const Graph & g)
Chris@16:       {
Chris@16:         weight_type w = get(m_weightMap, e);
Chris@16: 
Chris@16:         // if the target of e is already marked then decrease cutweight
Chris@16:         // otherwise, increase it
Chris@16:         if (get(m_parity, boost::target(e, g))) {
Chris@16:           m_cutweight -= w;
Chris@16:         } else {
Chris@16:           m_cutweight += w;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       template < typename Vertex, typename Graph >
Chris@16:       void finish_vertex(Vertex u, const Graph & g)
Chris@16:       {
Chris@16:         typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
Chris@16: 
Chris@16:         ++m_visited;
Chris@16:         put(m_parity, u, internal_parity_type(1));
Chris@16: 
Chris@16:         if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) {
Chris@16:           m_bestWeight = m_cutweight;
Chris@16:           BGL_FORALL_VERTICES_T(i, g, Graph) {
Chris@16:             put(m_bestParity,i, get(m_parity,i));
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       inline void clear() {
Chris@16:         m_bestWeight = (std::numeric_limits<weight_type>::max)();
Chris@16:         m_visited = 0;
Chris@16:         m_cutweight = 0;
Chris@16:       }
Chris@16: 
Chris@16:     private:
Chris@16:       ParityMap m_bestParity;
Chris@16:       InternalParityMap m_parity;
Chris@16:       weight_type& m_bestWeight;
Chris@16:       weight_type m_cutweight;
Chris@16:       unsigned m_visited;
Chris@16:       const WeightMap& m_weightMap;
Chris@16:     };
Chris@16: 
Chris@16:     /**
Chris@16:      * \brief Computes a min-cut of the input graph
Chris@16:      *
Chris@16:      * Computes a min-cut of the input graph using the Stoer-Wagner algorithm.
Chris@16:      *
Chris@16:      * \pre \p g is a connected, undirected graph
Chris@16:      * \pre <code>pq.empty()</code>
Chris@16:      * \param[in] g the input graph
Chris@16:      * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
Chris@16:      * \param[out] parities a writable property map from each vertex to a bool type object for
Chris@16:      *     distinguishing the two vertex sets of the min-cut
Chris@16:      * \param[out] assignments a read/write property map from each vertex to a \c vertex_descriptor object. This
Chris@16:      *     map serves as work space, and no particular meaning should be derived from property values
Chris@16:      *     after completion of the algorithm.
Chris@16:      * \param[out] pq a keyed, updatable max-priority queue
Chris@16:      * \returns the cut weight of the min-cut
Chris@16:      * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
Chris@16:      * \see http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
Chris@16:      *
Chris@16:      * \author Daniel Trebbien
Chris@16:      * \date 2010-09-11
Chris@16:      */
Chris@16:     template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
Chris@16:     typename boost::property_traits<WeightMap>::value_type
Chris@16:     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
Chris@16:       typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename boost::property_traits<WeightMap>::value_type weight_type;
Chris@16: 
Chris@16:       typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
Chris@16: 
Chris@16:       weight_type bestW = (std::numeric_limits<weight_type>::max)();
Chris@16:       weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
Chris@16:       vertex_descriptor bestStart = boost::graph_traits<UndirectedGraph>::null_vertex();
Chris@16: 
Chris@16:       detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
Chris@16:         vis(g, parities, bestThisTime, weights, index_map);
Chris@16: 
Chris@16:       // for each node in the graph,
Chris@16:       for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
Chris@16:         // run the MAS and find the min cut
Chris@16:         vis.clear();
Chris@16:         boost::maximum_adjacency_search(g,
Chris@16:             boost::weight_map(weights).
Chris@16:             visitor(vis).
Chris@16:             root_vertex(*u_iter).
Chris@16:             vertex_assignment_map(assignments).
Chris@16:             max_priority_queue(pq));
Chris@16:         if (bestThisTime < bestW) {
Chris@16:           bestW = bestThisTime;
Chris@16:           bestStart = *u_iter;
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       // Run one more time, starting from the best start location, to
Chris@16:       // ensure the visitor has the best values.
Chris@16:       vis.clear();
Chris@16:       boost::maximum_adjacency_search(g,
Chris@16:         boost::vertex_assignment_map(assignments).
Chris@16:         weight_map(weights).
Chris@16:         visitor(vis).
Chris@16:         root_vertex(bestStart).
Chris@16:         max_priority_queue(pq));
Chris@16: 
Chris@16:       return bestW;
Chris@16:     }
Chris@16:   } // end `namespace detail` within `namespace boost`
Chris@16: 
Chris@16:     template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
Chris@16:     typename boost::property_traits<WeightMap>::value_type
Chris@16:     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
Chris@16:       BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
Chris@16:       BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
Chris@16:       typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
Chris@16:       typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
Chris@16:       BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<UndirectedGraph>::directed_category, boost::undirected_tag>));
Chris@16:       BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
Chris@16:       // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
Chris@16:       BOOST_CONCEPT_ASSERT((boost::WritablePropertyMapConcept<ParityMap, vertex_descriptor>));
Chris@16:       // typedef typename boost::property_traits<ParityMap>::value_type parity_type;
Chris@16:       BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
Chris@16:       BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
Chris@16:       BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
Chris@16: 
Chris@16:       vertices_size_type n = num_vertices(g);
Chris@16:       if (n < 2)
Chris@16:         throw boost::bad_graph("the input graph must have at least two vertices.");
Chris@16:       else if (!pq.empty())
Chris@16:         throw std::invalid_argument("the max-priority queue must be empty initially.");
Chris@16: 
Chris@16:       return detail::stoer_wagner_min_cut(g, weights,
Chris@16:                                           parities, assignments, pq, index_map);
Chris@16:     }
Chris@16: 
Chris@16: namespace graph {
Chris@16:   namespace detail {
Chris@16:     template <class UndirectedGraph, class WeightMap>
Chris@16:     struct stoer_wagner_min_cut_impl {
Chris@16:       typedef typename boost::property_traits<WeightMap>::value_type result_type;
Chris@16:       template <typename ArgPack>
Chris@16:       result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const {
Chris@16:         using namespace boost::graph::keywords;
Chris@16:         typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
Chris@16:         typedef typename boost::property_traits<WeightMap>::value_type weight_type;
Chris@16: 
Chris@16:         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;
Chris@16: 
Chris@16:         gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
Chris@16: 
Chris@16:         typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack);
Chris@16: 
Chris@16:         return boost::stoer_wagner_min_cut(g,
Chris@16:           weights,
Chris@16:           arg_pack [_parity_map | boost::dummy_property_map()],
Chris@16:           boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
Chris@16:           pq,
Chris@16:           boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index)
Chris@16:         );
Chris@16:       }
Chris@16:     };
Chris@16:   }
Chris@16:   BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4)
Chris@16: }
Chris@16: 
Chris@16:   // Named parameter interface
Chris@16:   BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
Chris@16: namespace graph {
Chris@16:     // version without IndexMap kept for backwards compatibility
Chris@16:     // (but requires vertex_index_t to be defined in the graph)
Chris@16:     // Place after the macro to avoid compilation errors
Chris@16:     template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
Chris@16:     typename boost::property_traits<WeightMap>::value_type
Chris@16:     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
Chris@16: 
Chris@16:       return stoer_wagner_min_cut(g, weights,
Chris@16:                                   parities, assignments, pq,
Chris@16:                                   get(vertex_index, g));
Chris@16:     }
Chris@16: } // end `namespace graph`
Chris@16: } // end `namespace boost`
Chris@16: 
Chris@16: #include <boost/graph/iteration_macros_undef.hpp>
Chris@16: 
Chris@16: #endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP