Changeset 83410


Ignore:
Timestamp:
Mar 12, 2013, 12:35:48 AM (5 years ago)
Author:
Jeremiah Willcock
Message:

Added maximum adjacency search from Fernando Vilas; fixes #6780

Location:
trunk
Files:
3 added
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/boost/graph/stoer_wagner_min_cut.hpp

    r78329 r83410  
    1616#include <boost/graph/exception.hpp>
    1717#include <boost/graph/graph_traits.hpp>
    18 #include <boost/graph/iteration_macros.hpp>
     18#include <boost/graph/maximum_adjacency_search.hpp>
    1919#include <boost/graph/named_function_params.hpp>
     20#include <boost/graph/one_bit_color_map.hpp>
    2021#include <boost/graph/detail/d_ary_heap.hpp>
    2122#include <boost/property_map/property_map.hpp>
    2223#include <boost/tuple/tuple.hpp>
    2324#include <boost/utility/result_of.hpp>
     25#include <boost/graph/iteration_macros.hpp>
    2426
    2527namespace boost {
    26  
     28
    2729  namespace detail {
    28    
    29     /**
    30      * \brief Performs a phase of the Stoer-Wagner min-cut algorithm
    31      *
    32      * Performs a phase of the Stoer-Wagner min-cut algorithm.
    33      *
    34      * As described by Stoer & Wagner (1997), a phase is simply a maximum adjacency search
    35      * (also called a maximum cardinality search), which results in the selection of two vertices
    36      * \em s and \em t, and, as a side product, a minimum <em>s</em>-<em>t</em> cut of
    37      * the input graph. Here, the input graph is basically \p g, but some vertices are virtually
    38      * assigned to others as a way of viewing \p g as a graph with some sets of
    39      * vertices merged together.
    40      *
    41      * This implementation is a translation of pseudocode by Professor Uri Zwick,
    42      * School of Computer Science, Tel Aviv University.
    43      *
    44      * \pre \p g is a connected, undirected graph
    45      * \param[in] g the input graph
    46      * \param[in] assignments a read/write property map from each vertex to the vertex that it is assigned to
    47      * \param[in] assignedVertices a list of vertices that are assigned to others
    48      * \param[in] weights a readable property map from each edge to its weight (a non-negative value)
    49      * \param[out] pq a keyed, updatable max-priority queue
    50      * \returns a tuple (\em s, \em t, \em w) of the "<em>s</em>" and "<em>t</em>"
    51      *     of the minimum <em>s</em>-<em>t</em> cut and the cut weight \em w
    52      *     of the minimum <em>s</em>-<em>t</em> cut.
    53      * \see http://www.cs.tau.ac.il/~zwick/grad-algo-08/gmc.pdf
    54      *
    55      * \author Daniel Trebbien
    56      * \date 2010-09-11
    57      */
    58     template <class UndirectedGraph, class VertexAssignmentMap, class WeightMap, class KeyedUpdatablePriorityQueue>
    59     boost::tuple<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::graph_traits<UndirectedGraph>::vertex_descriptor, typename boost::property_traits<WeightMap>::value_type>
    60     stoer_wagner_phase(const UndirectedGraph& g, VertexAssignmentMap assignments, const std::set<typename boost::graph_traits<UndirectedGraph>::vertex_descriptor>& assignedVertices, WeightMap weights, KeyedUpdatablePriorityQueue& pq) {
    61       typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
     30    template < typename ParityMap, typename WeightMap, typename IndexMap >
     31    class mas_min_cut_visitor : public boost::default_mas_visitor {
     32      typedef one_bit_color_map <IndexMap> InternalParityMap;
    6233      typedef typename boost::property_traits<WeightMap>::value_type weight_type;
    63      
    64       BOOST_ASSERT(pq.empty());
    65       typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
    66      
    67       BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
    68         if (v == get(assignments, v)) { // foreach u \in V do
    69           put(keys, v, weight_type(0));
    70          
    71           pq.push(v);
     34    public:
     35      template < typename Graph >
     36      mas_min_cut_visitor(const Graph& g,
     37                          ParityMap parity,
     38                          weight_type& cutweight,
     39                          WeightMap weight_map,
     40                          IndexMap index_map)
     41        : m_bestParity(parity),
     42          m_parity(make_one_bit_color_map(num_vertices(g), index_map)),
     43          m_bestWeight(cutweight),
     44          m_cutweight(0),
     45          m_visited(0),
     46          m_weightMap(weight_map)
     47      {
     48        // set here since the init list sets the reference
     49        m_bestWeight = (std::numeric_limits<weight_type>::max)();
     50      }
     51
     52      template < typename Vertex, typename Graph >
     53      void initialize_vertex(Vertex u, const Graph & g)
     54      {
     55        typedef typename boost::property_traits<ParityMap>::value_type parity_type;
     56        typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
     57
     58        put(m_parity, u, internal_parity_type(0));
     59        put(m_bestParity, u, parity_type(0));
     60      }
     61
     62      template < typename Edge, typename Graph >
     63      void examine_edge(Edge e, const Graph & g)
     64      {
     65        weight_type w = get(m_weightMap, e);
     66
     67        // if the target of e is already marked then decrease cutweight
     68        // otherwise, increase it
     69        if (get(m_parity, boost::target(e, g))) {
     70          m_cutweight -= w;
     71        } else {
     72          m_cutweight += w;
    7273        }
    7374      }
    74      
    75       BOOST_ASSERT(pq.size() >= 2);
    76      
    77       vertex_descriptor s = boost::graph_traits<UndirectedGraph>::null_vertex();
    78       vertex_descriptor t = boost::graph_traits<UndirectedGraph>::null_vertex();
    79       weight_type w;
    80       while (!pq.empty()) { // while PQ \neq {} do
    81         const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
    82         w = get(keys, u);
    83         pq.pop();
    84        
    85         s = t; t = u;
    86        
    87         BGL_FORALL_OUTEDGES_T(u, e, g, UndirectedGraph) { // foreach (u, v) \in E do
    88           const vertex_descriptor v = get(assignments, target(e, g));
    89          
    90           if (pq.contains(v)) { // if v \in PQ then
    91             put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
    92             pq.update(v);
     75
     76      template < typename Vertex, typename Graph >
     77      void finish_vertex(Vertex u, const Graph & g)
     78      {
     79        typedef typename boost::property_traits<ParityMap>::value_type parity_type;
     80        typedef typename boost::property_traits<InternalParityMap>::value_type internal_parity_type;
     81
     82        ++m_visited;
     83        put(m_parity, u, internal_parity_type(1));
     84
     85        if (m_cutweight < m_bestWeight && m_visited < num_vertices(g)) {
     86          m_bestWeight = m_cutweight;
     87          BGL_FORALL_VERTICES_T(i, g, Graph) {
     88            put(m_bestParity,i, get(m_parity,i));
    9389          }
    9490        }
    95        
    96         typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
    97         for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
    98           const vertex_descriptor uPrime = *assignedVertexIt;
    99          
    100           if (get(assignments, uPrime) == u) {
    101             BGL_FORALL_OUTEDGES_T(uPrime, e, g, UndirectedGraph) { // foreach (u, v) \in E do
    102               const vertex_descriptor v = get(assignments, target(e, g));
    103              
    104               if (pq.contains(v)) { // if v \in PQ then
    105                 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
    106                 pq.update(v);
    107               }
    108             }
    109           }
    110         }
    111       }
    112      
    113       return boost::make_tuple(s, t, w);
    114     }
    115    
     91      }
     92
     93      inline void clear() {
     94        m_bestWeight = (std::numeric_limits<weight_type>::max)();
     95        m_visited = 0;
     96        m_cutweight = 0;
     97      }
     98
     99    private:
     100      ParityMap m_bestParity;
     101      InternalParityMap m_parity;
     102      weight_type& m_bestWeight;
     103      weight_type m_cutweight;
     104      unsigned m_visited;
     105      const WeightMap& m_weightMap;
     106    };
     107
    116108    /**
    117109     * \brief Computes a min-cut of the input graph
     
    136128     * \date 2010-09-11
    137129     */
    138     template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
     130    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
    139131    typename boost::property_traits<WeightMap>::value_type
    140     stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
     132    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
     133      typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
     134      typedef typename boost::graph_traits<UndirectedGraph>::vertices_size_type vertices_size_type;
     135      typedef typename boost::graph_traits<UndirectedGraph>::edge_descriptor edge_descriptor;
     136      typedef typename boost::property_traits<WeightMap>::value_type weight_type;
     137      typedef typename boost::property_traits<ParityMap>::value_type parity_type;
     138
     139      typename graph_traits<UndirectedGraph>::vertex_iterator u_iter, u_end;
     140
     141      weight_type bestW = (std::numeric_limits<weight_type>::max)();
     142      weight_type bestThisTime = (std::numeric_limits<weight_type>::max)();
     143      vertex_descriptor bestStart;
     144
     145      detail::mas_min_cut_visitor<ParityMap, WeightMap, IndexMap>
     146        vis(g, parities, bestThisTime, weights, index_map);
     147
     148      // for each node in the graph,
     149      for (boost::tie(u_iter, u_end) = vertices(g); u_iter != u_end; ++u_iter) {
     150        // run the MAS and find the min cut
     151        vis.clear();
     152        boost::maximum_adjacency_search(g,
     153            boost::weight_map(weights).
     154            visitor(vis).
     155            root_vertex(*u_iter).
     156            vertex_assignment_map(assignments).
     157            max_priority_queue(pq));
     158        if (bestThisTime < bestW) {
     159          bestW = bestThisTime;
     160          bestStart = *u_iter;
     161        }
     162      }
     163
     164      // Run one more time, starting from the best start location, to
     165      // ensure the visitor has the best values.
     166      vis.clear();
     167      boost::maximum_adjacency_search(g,
     168        boost::vertex_assignment_map(assignments).
     169        weight_map(weights).
     170        visitor(vis).
     171        root_vertex(bestStart).
     172        max_priority_queue(pq));
     173
     174      return bestW;
     175    }
     176  } // end `namespace detail` within `namespace boost`
     177
     178    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue, class IndexMap>
     179    typename boost::property_traits<WeightMap>::value_type
     180    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq, IndexMap index_map) {
    141181      BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<UndirectedGraph>));
    142182      BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<UndirectedGraph>));
     
    152192      BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
    153193      BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
    154      
     194
    155195      vertices_size_type n = num_vertices(g);
    156196      if (n < 2)
     
    158198      else if (!pq.empty())
    159199        throw std::invalid_argument("the max-priority queue must be empty initially.");
    160      
    161       std::set<vertex_descriptor> assignedVertices;
    162      
    163       // initialize `assignments` (all vertices are initially assigned to themselves)
    164       BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
    165         put(assignments, v, v);
    166       }
    167      
    168       vertex_descriptor s, t;
    169       weight_type bestW;
    170      
    171       boost::tie(s, t, bestW) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
    172       BOOST_ASSERT(s != t);
    173       BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
    174         put(parities, v, parity_type(v == t ? 1 : 0));
    175       }
    176       put(assignments, t, s);
    177       assignedVertices.insert(t);
    178       --n;
    179      
    180       for (; n >= 2; --n) {
    181         weight_type w;
    182         boost::tie(s, t, w) = boost::detail::stoer_wagner_phase(g, assignments, assignedVertices, weights, pq);
    183         BOOST_ASSERT(s != t);
    184        
    185         if (w < bestW) {
    186           BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
    187             put(parities, v, parity_type(get(assignments, v) == t ? 1 : 0));
    188            
    189             if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
    190               put(assignments, v, s);
    191           }
    192          
    193           bestW = w;
    194         } else {
    195           BGL_FORALL_VERTICES_T(v, g, UndirectedGraph) {
    196             if (get(assignments, v) == t) // all vertices that were assigned to t are now assigned to s
    197               put(assignments, v, s);
    198           }
    199         }
    200         put(assignments, t, s);
    201         assignedVertices.insert(t);
    202       }
    203      
    204       BOOST_ASSERT(pq.empty());
    205      
    206       return bestW;
     200
     201      return detail::stoer_wagner_min_cut(g, weights,
     202                                          parities, assignments, pq, index_map);
    207203    }
    208    
    209   } // end `namespace detail` within `namespace boost`
    210  
    211   template <class UndirectedGraph, class WeightMap, class P, class T, class R>
    212   inline typename boost::property_traits<WeightMap>::value_type
    213   stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, const boost::bgl_named_params<P, T, R>& params) {
    214     typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
    215     typedef typename std::vector<vertex_descriptor>::size_type heap_container_size_type;
    216     typedef typename boost::property_traits<WeightMap>::value_type weight_type;
    217    
    218     typedef boost::bgl_named_params<P, T, R> params_type;
    219     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
    220    
    221     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;
    222     gen_type gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
    223     typename boost::result_of<gen_type(const UndirectedGraph&, const arg_pack_type&)>::type pq = gen(g, arg_pack);
    224    
    225     return boost::detail::stoer_wagner_min_cut(g,
    226         weights,
    227         choose_param(get_param(params, boost::parity_map_t()), boost::dummy_property_map()),
    228         boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
    229         pq
    230       );
     204
     205namespace graph {
     206  namespace detail {
     207    template <class UndirectedGraph, class WeightMap>
     208    struct stoer_wagner_min_cut_impl {
     209      typedef typename boost::property_traits<WeightMap>::value_type result_type;
     210      template <typename ArgPack>
     211      result_type operator() (const UndirectedGraph& g, WeightMap weights, const ArgPack& arg_pack) const {
     212        using namespace boost::graph::keywords;
     213        typedef typename boost::graph_traits<UndirectedGraph>::vertex_descriptor vertex_descriptor;
     214        typedef typename boost::property_traits<WeightMap>::value_type weight_type;
     215
     216        typedef typename 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;
     217
     218        gen_type gen(choose_param(get_param(arg_pack, boost::distance_zero_t()), weight_type(0)));
     219
     220        typename boost::result_of<gen_type(const UndirectedGraph&, const ArgPack&)>::type pq = gen(g, arg_pack);
     221
     222        return boost::stoer_wagner_min_cut(g,
     223          weights,
     224          arg_pack [_parity_map | boost::dummy_property_map()],
     225          boost::detail::make_property_map_from_arg_pack_gen<tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, arg_pack),
     226          pq,
     227          boost::detail::override_const_property(arg_pack, _vertex_index_map, g, vertex_index)
     228        );
     229      }
     230    };
    231231  }
    232  
    233   template <class UndirectedGraph, class WeightMap>
    234   inline typename boost::property_traits<WeightMap>::value_type
    235   stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights) {
    236     return boost::stoer_wagner_min_cut(g, weights, boost::vertex_index_map(get(boost::vertex_index, g)));
    237   }
    238  
     232  BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(stoer_wagner_min_cut,2,4)
     233}
     234
     235  // Named parameter interface
     236  BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(stoer_wagner_min_cut, 2)
     237namespace graph {
     238    // version without IndexMap kept for backwards compatibility
     239    // (but requires vertex_index_t to be defined in the graph)
     240    // Place after the macro to avoid compilation errors
     241    template <class UndirectedGraph, class WeightMap, class ParityMap, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
     242    typename boost::property_traits<WeightMap>::value_type
     243    stoer_wagner_min_cut(const UndirectedGraph& g, WeightMap weights, ParityMap parities, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue& pq) {
     244
     245      return stoer_wagner_min_cut(g, weights,
     246                                  parities, assignments, pq,
     247                                  get(vertex_index, g));
     248    }
     249} // end `namespace graph`
    239250} // end `namespace boost`
    240251
  • trunk/libs/graph/doc/table_of_contents.html

    r81725 r83410  
    288288                      <LI><A href="is_bipartite.html"><tt>is_bipartite</tt></A> (including two-coloring of bipartite graphs)
    289289                      <LI><A href="find_odd_cycle.html"><tt>find_odd_cycle</tt></A>
     290                      <LI><A href="maximum_adjacency_search.html"><tt>maximum_adjacency_search</tt></A>
    290291                  </ol>
    291292              </li>
  • trunk/libs/graph/test/Jamfile.v2

    r82007 r83410  
    124124    [ run random_spanning_tree_test.cpp ../build//boost_graph ]
    125125    [ run graphml_test.cpp ../build//boost_graph : : "graphml_test.xml" ]
     126    [ run mas_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
    126127    [ run stoer_wagner_test.cpp ../../test/build//boost_unit_test_framework/<link>static : $(TEST_DIR) ]
    127128    [ compile filtered_graph_properties_dijkstra.cpp ]
Note: See TracChangeset for help on using the changeset viewer.