123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251 |
- // 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<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::property_traits<WeightMap>::value_type weight_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);
- boost::dummy_property_map dummy_prop;
- return boost::stoer_wagner_min_cut(g,
- weights,
- arg_pack [_parity_map | dummy_prop],
- 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
|