boost/graph/stoer_wagner_min_cut.hpp

0001 //            Copyright Daniel Trebbien 2010.
0002 // Distributed under the Boost Software License, Version 1.0.
0003 //   (See accompanying file LICENSE_1_0.txt or the copy at
0004 //         http://www.boost.org/LICENSE_1_0.txt)
0005
0006 #ifndef BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP
0007 #define BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP 1
0008
0009 #include <boost/assert.hpp>
0010 #include <set>
0011 #include <vector>
0012 #include <boost/concept_check.hpp>
0013 #include <boost/concept/assert.hpp>
0014 #include <boost/graph/adjacency_list.hpp>
0015 #include <boost/graph/buffer_concepts.hpp>
0016 #include <boost/graph/exception.hpp>
0017 #include <boost/graph/graph_traits.hpp>
0018 #include <boost/graph/maximum_adjacency_search.hpp>
0019 #include <boost/graph/named_function_params.hpp>
0020 #include <boost/graph/one_bit_color_map.hpp>
0021 #include <boost/graph/detail/d_ary_heap.hpp>
0022 #include <boost/property_map/property_map.hpp>
0023 #include <boost/tuple/tuple.hpp>
0024 #include <boost/utility/result_of.hpp>
0025 #include <boost/graph/iteration_macros.hpp>
0026
0027 namespace boost
0028 {
0029
0030 namespace detail
0031 {
0032     /**
0033      * \brief Performs a phase of the Stoer-Wagner min-cut algorithm
0034      *
0035      * Performs a phase of the Stoer-Wagner min-cut algorithm.
0036      *
0037      * As described by Stoer & Wagner (1997), a phase is simply a maximum
0038      * adjacency search (also called a maximum cardinality search), which
0039      * results in the selection of two vertices \em s and \em t, and, as a side
0040      * product, a minimum <em>s</em>-<em>t</em> cut of the input graph. Here,
0041      * the input graph is basically \p g, but some vertices are virtually
0042      * assigned to others as a way of viewing \p g as a graph with some sets of
0043      * vertices merged together.
0044      *
0045      * This implementation is a translation of pseudocode by Professor Uri
0046      * Zwick, School of Computer Science, Tel Aviv University.
0047      *
0048      * \pre \p g is a connected, undirected graph
0049      * \param[in] g the input graph
0050      * \param[in] assignments a read/write property map from each vertex to the
0051      *                        vertex that it is assigned to
0052      * \param[in] assignedVertices a list of vertices that are assigned to
0053      *                             others
0054      * \param[in] weights a readable property map from each edge to its
0055      *                    weight (a non-negative value)
0056      * \param[out] pq a keyed, updatable max-priority queue
0057      * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and
0058      *          "<em>t</em>" of the minimum <em>s</em>-<em>t</em> cut and the
0059      *          cut weight \em w of the minimum <em>s</em>-<em>t</em> cut.
0060      * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
0061      *
0062      * \author Daniel Trebbien
0063      * \date 2010-09-11
0064      */
0065     template < class UndirectedGraph, class VertexAssignmentMap,
0066         class WeightMap, class KeyedUpdatablePriorityQueue >
0067     boost::tuple<
0068         typename boost::graph_traits< UndirectedGraph >::vertex_descriptor,
0069         typename boost::graph_traits< UndirectedGraph >::vertex_descriptor,
0070         typename boost::property_traits< WeightMap >::value_type >
0071     stoer_wagner_phase(const UndirectedGraph& g,
0072         VertexAssignmentMap assignments,
0073         const std::set< typename boost::graph_traits<
0074             UndirectedGraph >::vertex_descriptor >& assignedVertices,
0075         WeightMap weights, KeyedUpdatablePriorityQueue& pq)
0076     {
0077         typedef
0078             typename boost::graph_traits< UndirectedGraph >::vertex_descriptor
0079                 vertex_descriptor;
0080         typedef typename boost::property_traits< WeightMap >::value_type
0081             weight_type;
0082
0083         BOOST_ASSERT(pq.empty());
0084         typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
0085
0086         BGL_FORALL_VERTICES_T(v, g, UndirectedGraph)
0087         {
0088             if (v == get(assignments, v))
0089             { // foreach u \in V do
0090                 put(keys, v, weight_type(0));
0091
0092                 pq.push(v);
0093             }
0094         }
0095
0096         BOOST_ASSERT(pq.size() >= 2);
0097
0098         vertex_descriptor s
0099             = boost::graph_traits< UndirectedGraph >::null_vertex();
0100         vertex_descriptor t
0101             = boost::graph_traits< UndirectedGraph >::null_vertex();
0102         weight_type w;
0103         while (!pq.empty())
0104         { // while PQ \neq {} do
0105             const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
0106             w = get(keys, u);
0107             pq.pop();
0108
0109             s = t;
0110             t = u;
0111
0112             BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph)
0113             { // foreach (u, v) \in E do
0114                 const vertex_descriptor v = get(assignments, target(e, g));
0115
0116                 if (pq.contains(v))
0117                 { // if v \in PQ then
0118                     put(keys, v,
0119                         get(keys, v)
0120                             + get(weights,
0121                                 e)); // increasekey(PQ, v, wA(v) + w(u, v))
0122                     pq.update(v);
0123                 }
0124             }
0125
0126             typename std::set< vertex_descriptor >::const_iterator
0127                 assignedVertexIt,
0128                 assignedVertexEnd = assignedVertices.end();
0129             for (assignedVertexIt = assignedVertices.begin();
0130                  assignedVertexIt != assignedVertexEnd; ++assignedVertexIt)
0131             {
0132                 const vertex_descriptor uPrime = *assignedVertexIt;
0133
0134                 if (get(assignments, uPrime) == u)
0135                 {
0136                     BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph)
0137                     { // foreach (u, v) \in E do
0138                         const vertex_descriptor v
0139                             = get(assignments, target(e, g));
0140
0141                         if (pq.contains(v))
0142                         { // if v \in PQ then
0143                             put(keys, v,
0144                                 get(keys, v)
0145                                     + get(weights, e)); // increasekey(PQ, v,
0146                                                         // wA(v) + w(u, v))
0147                             pq.update(v);
0148                         }
0149                     }
0150                 }
0151             }
0152         }
0153
0154         return boost::make_tuple(s, t, w);
0155     }
0156
0157     /**
0158      * \brief Computes a min-cut of the input graph
0159      *
0160      * Computes a min-cut of the input graph using the Stoer-Wagner algorithm.
0161      *
0162      * \pre \p g is a connected, undirected graph
0163      * \pre <code>pq.empty()</code>
0164      * \param[in] g the input graph
0165      * \param[in] weights a readable property map from each edge to its weight
0166      * (a non-negative value) \param[out] parities a writable property map from
0167      * each vertex to a bool type object for distinguishing the two vertex sets
0168      * of the min-cut \param[out] assignments a read/write property map from
0169      * each vertex to a \c vertex_descriptor object. This map serves as work
0170      * space, and no particular meaning should be derived from property values
0171      *     after completion of the algorithm.
0172      * \param[out] pq a keyed, updatable max-priority queue
0173      * \returns the cut weight of the min-cut
0174      * \see
0175      * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.114.6687&rep=rep1&type=pdf
0176      * \see
0177      * http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.31.614&rep=rep1&type=pdf
0178      *
0179      * \author Daniel Trebbien
0180      * \date 2010-09-11
0181      */
0182     template < class UndirectedGraph, class WeightMap, class ParityMap,
0183         class VertexAssignmentMap, class KeyedUpdatablePriorityQueue,
0184         class IndexMap >
0185     typename boost::property_traits< WeightMap >::value_type
0186     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights,
0187         ParityMap parities, VertexAssignmentMap assignments,
0188         KeyedUpdatablePriorityQueue& pq, IndexMap index_map)
0189     {
0190         typedef
0191             typename boost::graph_traits< UndirectedGraph >::vertex_descriptor
0192                 vertex_descriptor;
0193         typedef typename boost::property_traits< WeightMap >::value_type
0194             weight_type;
0195         typedef
0196             typename boost::graph_traits< UndirectedGraph >::vertices_size_type
0197                 vertices_size_type;
0198         typedef typename boost::property_traits< ParityMap >::value_type
0199             parity_type;
0200
0201         vertices_size_type n = num_vertices(g);
0202
0203         std::set< vertex_descriptor > assignedVertices;
0204
0205         // initialize `assignments` (all vertices are initially assigned to
0206         // themselves)
0207         BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) { put(assignments, v, v); }
0208
0209         vertex_descriptor s, t;
0210         weight_type bestW;
0211
0212         boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(
0213             g, assignments, assignedVertices, weights, pq);
0214         BOOST_ASSERT(s != t);
0215         BGL_FORALL_VERTICES_T(v, g, UndirectedGraph)
0216         {
0217             put(parities, v, parity_type(v == t ? 1 : 0));
0218         }
0219         put(assignments, t, s);
0220         assignedVertices.insert(t);
0221         --n;
0222
0223         for (; n >= 2; --n)
0224         {
0225             weight_type w;
0226             boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(
0227                 g, assignments, assignedVertices, weights, pq);
0228             BOOST_ASSERT(s != t);
0229
0230             if (w < bestW)
0231             {
0232                 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph)
0233                 {
0234                     put(parities, v,
0235                         parity_type(get(assignments, v) == t ? 1 : 0));
0236
0237                     if (get(assignments, v)
0238                         == t) // all vertices that were assigned to t are now
0239                               // assigned to s
0240                         put(assignments, v, s);
0241                 }
0242
0243                 bestW = w;
0244             }
0245             else
0246             {
0247                 BGL_FORALL_VERTICES_T(v, g, UndirectedGraph)
0248                 {
0249                     if (get(assignments, v)
0250                         == t) // all vertices that were assigned to t are now
0251                               // assigned to s
0252                         put(assignments, v, s);
0253                 }
0254             }
0255             put(assignments, t, s);
0256             assignedVertices.insert(t);
0257         }
0258
0259         BOOST_ASSERT(pq.empty());
0260
0261         return bestW;
0262     }
0263 } // end `namespace detail` within `namespace boost`
0264
0265 template < class UndirectedGraph, class WeightMap, class ParityMap,
0266     class VertexAssignmentMap, class KeyedUpdatablePriorityQueue,
0267     class IndexMap >
0268 typename boost::property_traits< WeightMap >::value_type stoer_wagner_min_cut(
0269     const UndirectedGraph& g, WeightMap weights, ParityMap parities,
0270     VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq,
0271     IndexMap index_map)
0272 {
0273     BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept< UndirectedGraph >));
0274     BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept< UndirectedGraph >));
0275     typedef typename boost::graph_traits< UndirectedGraph >::vertex_descriptor
0276         vertex_descriptor;
0277     typedef typename boost::graph_traits< UndirectedGraph >::vertices_size_type
0278         vertices_size_type;
0279     typedef typename boost::graph_traits< UndirectedGraph >::edge_descriptor
0280         edge_descriptor;
0281     BOOST_CONCEPT_ASSERT((boost::Convertible<
0282         typename boost::graph_traits< UndirectedGraph >::directed_category,
0283         boost::undirected_tag >));
0284     BOOST_CONCEPT_ASSERT(
0285         (boost::ReadablePropertyMapConcept< WeightMap, edge_descriptor >));
0286     // typedef typename boost::property_traits<WeightMap>::value_type
0287     // weight_type;
0288     BOOST_CONCEPT_ASSERT(
0289         (boost::WritablePropertyMapConcept< ParityMap, vertex_descriptor >));
0290     // typedef typename boost::property_traits<ParityMap>::value_type
0291     // parity_type;
0292     BOOST_CONCEPT_ASSERT(
0293         (boost::ReadWritePropertyMapConcept< VertexAssignmentMap,
0294             vertex_descriptor >));
0295     BOOST_CONCEPT_ASSERT((boost::Convertible< vertex_descriptor,
0296         typename boost::property_traits< VertexAssignmentMap >::value_type >));
0297     BOOST_CONCEPT_ASSERT(
0298         (boost::KeyedUpdatableQueueConcept< KeyedUpdatablePriorityQueue >));
0299
0300     vertices_size_type n = num_vertices(g);
0301     if (n < 2)
0302         throw boost::bad_graph(
0303             "the input graph must have at least two vertices.");
0304     else if (!pq.empty())
0305         throw std::invalid_argument(
0306             "the max-priority queue must be empty initially.");
0307
0308     return detail::stoer_wagner_min_cut(
0309         g, weights, parities, assignments, pq, index_map);
0310 }
0311
0312 namespace graph
0313 {
0314     namespace detail
0315     {
0316         template < class UndirectedGraph, class WeightMap >
0317         struct stoer_wagner_min_cut_impl
0318         {
0319             typedef typename boost::property_traits< WeightMap >::value_type
0320                 result_type;
0321             template < typename ArgPack >
0322             result_type operator()(const UndirectedGraph& g, WeightMap weights,
0323                 const ArgPack& arg_pack) const
0324             {
0325                 using namespace boost::graph::keywords;
0326                 typedef typename boost::graph_traits<
0327                     UndirectedGraph >::vertex_descriptor vertex_descriptor;
0328                 typedef typename boost::property_traits< WeightMap >::value_type
0329                     weight_type;
0330
0331                 typedef boost::detail::make_priority_queue_from_arg_pack_gen<
0332                     boost::graph::keywords::tag::max_priority_queue,
0333                     weight_type, vertex_descriptor,
0334                     std::greater< weight_type > >
0335                     gen_type;
0336
0337                 gen_type gen(
0338                     choose_param(get_param(arg_pack, boost::distance_zero_t()),
0339                         weight_type(0)));
0340
0341                 typename boost::result_of< gen_type(
0342                     const UndirectedGraph&, const ArgPack&) >::type pq
0343                     = gen(g, arg_pack);
0344
0345                 boost::dummy_property_map dummy_prop;
0346                 return boost::stoer_wagner_min_cut(g, weights,
0347                     arg_pack[_parity_map | dummy_prop],
0348                     boost::detail::make_property_map_from_arg_pack_gen<
0349                         tag::vertex_assignment_map, vertex_descriptor >(
0350                         vertex_descriptor())(g, arg_pack),
0351                     pq,
0352                     boost::detail::override_const_property(
0353                         arg_pack, _vertex_index_map, g, vertex_index));
0354             }
0355         };
0356     }
0357     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut, 2, 4)
0358 }
0359
0360 // Named parameter interface
0361 BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
0362 namespace graph
0363 {
0364     // version without IndexMap kept for backwards compatibility
0365     // (but requires vertex_index_t to be defined in the graph)
0366     // Place after the macro to avoid compilation errors
0367     template < class UndirectedGraph, class WeightMap, class ParityMap,
0368         class VertexAssignmentMap, class KeyedUpdatablePriorityQueue >
0369     typename boost::property_traits< WeightMap >::value_type
0370     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights,
0371         ParityMap parities, VertexAssignmentMap assignments,
0372         KeyedUpdatablePriorityQueue& pq)
0373     {
0374
0375         return stoer_wagner_min_cut(
0376             g, weights, parities, assignments, pq, get(vertex_index, g));
0377     }
0378 } // end `namespace graph`
0379 } // end `namespace boost`
0380
0381 #include <boost/graph/iteration_macros_undef.hpp>
0382
0383 #endif // !BOOST_GRAPH_STOER_WAGNER_MIN_CUT_HPP