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