EVOLUTION-MANAGER

Edit File: stoer_wagner_min_cut.hpp

// 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