ceph/src/boost/boost/graph/maximum_adjacency_search.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 2012 Fernando Vilas
   4 //           2010 Daniel Trebbien
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11
  12 // The maximum adjacency search algorithm was originally part of the
  13 // Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
  14 // broken out into its own file to be a public search algorithm, with
  15 // visitor concepts.
  16 #ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
  17 #define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
  18
  19 /**
  20  * This is an implementation of the maximum adjacency search on an
  21  * undirected graph. It allows a visitor object to perform some
  22  * operation on each vertex as that vertex is visited.
  23  *
  24  * The algorithm runs as follows:
  25  *
  26  * Initialize all nodes to be unvisited (reach count = 0)
  27  *   and call vis.initialize_vertex
  28  * For i = number of nodes in graph downto 1
  29  *   Select the unvisited node with the highest reach count
  30  *     The user provides the starting node to break the first tie,
  31  *     but future ties are broken arbitrarily
  32  *   Visit the node by calling vis.start_vertex
  33  *   Increment the reach count for all unvisited neighbors
  34  *     and call vis.examine_edge for each of these edges
  35  *   Mark the node as visited and call vis.finish_vertex
  36  *
  37  */
  38
  39 #include <boost/concept_check.hpp>
  40 #include <boost/concept/assert.hpp>
  41 #include <boost/graph/buffer_concepts.hpp>
  42 #include <boost/graph/exception.hpp>
  43 #include <boost/graph/graph_concepts.hpp>
  44 #include <boost/graph/iteration_macros.hpp>
  45 #include <boost/graph/named_function_params.hpp>
  46 #include <boost/graph/visitors.hpp>
  47 #include <boost/tuple/tuple.hpp>
  48
  49 #include <set>
  50
  51 namespace boost {
  52   template <class Visitor, class Graph>
  53   struct MASVisitorConcept {
  54     void constraints() {
  55       boost::function_requires< boost::CopyConstructibleConcept<Visitor> >();
  56       vis.initialize_vertex(u, g);
  57       vis.start_vertex(u, g);
  58       vis.examine_edge(e, g);
  59       vis.finish_vertex(u, g);
  60     }
  61     Visitor vis;
  62     Graph g;
  63     typename boost::graph_traits<Graph>::vertex_descriptor u;
  64     typename boost::graph_traits<Graph>::edge_descriptor e;
  65   };
  66
  67   template <class Visitors = null_visitor>
  68   class mas_visitor {
  69   public:
  70     mas_visitor() { }
  71     mas_visitor(Visitors vis) : m_vis(vis) { }
  72
  73     template <class Vertex, class Graph>
  74     void
  75     initialize_vertex(Vertex u, Graph& g)
  76     {
  77       invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
  78     }
  79
  80     template <class Vertex, class Graph>
  81     void
  82     start_vertex(Vertex u, Graph& g)
  83     {
  84       invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
  85     }
  86
  87     template <class Edge, class Graph>
  88     void
  89     examine_edge(Edge e, Graph& g)
  90     {
  91       invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
  92     }
  93
  94     template <class Vertex, class Graph>
  95     void
  96     finish_vertex(Vertex u, Graph& g)
  97     {
  98       invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
  99     }
 100
 101     BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas)
 102     BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas)
 103     BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas)
 104     BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas)
 105
 106   protected:
 107     Visitors m_vis;
 108   };
 109   template <class Visitors>
 110   mas_visitor<Visitors>
 111   make_mas_visitor(Visitors vis) {
 112     return mas_visitor<Visitors>(vis);
 113   }
 114   typedef mas_visitor<> default_mas_visitor;
 115
 116   namespace detail {
 117     template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
 118       void
 119       maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
 120       typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 121       typedef typename boost::property_traits<WeightMap>::value_type weight_type;
 122
 123      std::set<vertex_descriptor> assignedVertices;
 124
 125      // initialize `assignments` (all vertices are initially
 126      // assigned to themselves)
 127      BGL_FORALL_VERTICES_T(v, g, Graph) {
 128        put(assignments, v, v);
 129      }
 130
 131       typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();
 132
 133       // set number of visited neighbors for all vertices to 0
 134       BGL_FORALL_VERTICES_T(v, g, Graph) {
 135         if (v == get(assignments, v)) { // foreach u \in V do
 136           put(keys, v, weight_type(0));          vis.initialize_vertex(v, g);
 137
 138           pq.push(v);
 139         }
 140       }
 141       BOOST_ASSERT(pq.size() >= 2);
 142
 143       // Give the starting vertex high priority
 144       put(keys, start, get(keys, start) + num_vertices(g) + 1);
 145       pq.update(start);
 146
 147       // start traversing the graph
 148       //vertex_descriptor s, t;
 149       //weight_type w;
 150       while (!pq.empty()) { // while PQ \neq {} do
 151         const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
 152         /* weight_type w = */ get(keys, u);      vis.start_vertex(u, g);
 153         pq.pop();                  //            vis.start_vertex(u, g);
 154
 155         BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
 156                                                  vis.examine_edge(e, g);
 157
 158           const vertex_descriptor v = get(assignments, target(e, g));
 159
 160           if (pq.contains(v)) { // if v \in PQ then
 161             put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
 162             pq.update(v);
 163           }
 164         }
 165
 166         typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
 167         for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
 168           const vertex_descriptor uPrime = *assignedVertexIt;
 169
 170           if (get(assignments, uPrime) == u) {
 171             BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do
 172                                                  vis.examine_edge(e, g);
 173
 174               const vertex_descriptor v = get(assignments, target(e, g));
 175
 176               if (pq.contains(v)) { // if v \in PQ then
 177                 put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
 178                 pq.update(v);
 179               }
 180             }
 181           }
 182         }
 183                                                  vis.finish_vertex(u, g);
 184       }
 185     }
 186   } // end namespace detail
 187
 188   template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
 189     void
 190 maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
 191     BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>));
 192     BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
 193     typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 194     typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
 195     typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
 196     BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
 197     BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
 198     // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
 199     boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
 200     BOOST_CONCEPT_ASSERT((boost::ReadWritePropertyMapConcept<VertexAssignmentMap, vertex_descriptor>));
 201     BOOST_CONCEPT_ASSERT((boost::Convertible<vertex_descriptor, typename boost::property_traits<VertexAssignmentMap>::value_type>));
 202     BOOST_CONCEPT_ASSERT((boost::KeyedUpdatableQueueConcept<KeyedUpdatablePriorityQueue>));
 203
 204     vertices_size_type n = num_vertices(g);
 205     if (n < 2)
 206       throw boost::bad_graph("the input graph must have at least two vertices.");
 207     else if (!pq.empty())
 208       throw std::invalid_argument("the max-priority queue must be empty initially.");
 209
 210     detail::maximum_adjacency_search(g, weights,
 211                                             vis, start,
 212                                             assignments, pq);
 213   }
 214
 215   namespace graph {
 216     namespace detail {
 217       template <typename WeightMap>
 218       struct mas_dispatch {
 219         typedef void result_type;
 220         template <typename Graph, typename ArgPack>
 221         static result_type apply(const Graph& g,
 222                           //const bgl_named_params<P,T,R>& params,
 223                           const ArgPack& params,
 224                           WeightMap w) {
 225
 226           using namespace boost::graph::keywords;
 227           typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 228           typedef typename WeightMap::value_type weight_type;
 229
 230           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> > default_pq_gen_type;
 231
 232           default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
 233
 234           typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
 235
 236           boost::null_visitor null_vis;
 237           boost::mas_visitor<boost::null_visitor> default_visitor(null_vis);
 238           vertex_descriptor v = vertex_descriptor();
 239           boost::detail::make_property_map_from_arg_pack_gen<
 240               boost::graph::keywords::tag::vertex_assignment_map,
 241               vertex_descriptor
 242           > map_gen(v);
 243           typename boost::detail::map_maker<
 244               Graph,
 245               ArgPack,
 246               boost::graph::keywords::tag::vertex_assignment_map,
 247               vertex_descriptor
 248           >::map_type default_map = map_gen(g, params);
 249           boost::maximum_adjacency_search
 250                (g,
 251                 w,
 252                 params [ _visitor | default_visitor],
 253                 params [ _root_vertex | *vertices(g).first],
 254                 params [ _vertex_assignment_map | default_map],
 255                 pq
 256                 );
 257         }
 258       };
 259
 260       template <>
 261       struct mas_dispatch<boost::param_not_found> {
 262         typedef void result_type;
 263
 264         template <typename Graph, typename ArgPack>
 265         static result_type apply(const Graph& g,
 266                           const ArgPack& params,
 267                           param_not_found) {
 268
 269           using namespace boost::graph::keywords;
 270           typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
 271
 272           // get edge_weight_t as the weight type
 273           typedef typename boost::property_map<Graph, edge_weight_t> WeightMap;
 274           typedef typename WeightMap::value_type weight_type;
 275
 276           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> > default_pq_gen_type;
 277
 278           default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));
 279
 280           typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);
 281
 282           boost::null_visitor null_vis;
 283           boost::mas_visitor<boost::null_visitor> default_visitor(null_vis);
 284           vertex_descriptor v = vertex_descriptor();
 285           boost::detail::make_property_map_from_arg_pack_gen<
 286               boost::graph::keywords::tag::vertex_assignment_map,
 287               vertex_descriptor
 288           > map_gen(v);
 289           typename boost::detail::map_maker<
 290               Graph,
 291               ArgPack,
 292               boost::graph::keywords::tag::vertex_assignment_map,
 293               vertex_descriptor
 294           >::map_type default_map = map_gen(g, params);
 295           boost::maximum_adjacency_search
 296                (g,
 297                 get(edge_weight, g),
 298                 params [ _visitor | default_visitor],
 299                 params [ _root_vertex | *vertices(g).first],
 300                 params [ _vertex_assignment_map | default_map],
 301                 pq
 302                 );
 303         }
 304       };
 305     } // end namespace detail
 306   } // end namespace graph
 307
 308   // Named parameter interface
 309   //BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
 310   template <typename Graph, typename P, typename T, typename R>
 311   void
 312   maximum_adjacency_search (const Graph& g,
 313       const bgl_named_params<P,T,R>& params) {
 314
 315     typedef bgl_named_params<P, T, R> params_type;
 316     BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)
 317
 318     // do the dispatch based on WeightMap
 319     typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W;
 320     graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight));
 321   }
 322
 323   namespace graph {
 324     namespace detail {
 325       template <typename Graph>
 326       struct maximum_adjacency_search_impl {
 327         typedef void result_type;
 328
 329         template <typename ArgPack>
 330         void
 331         operator() (const Graph& g, const ArgPack& arg_pack) const {
 332           // call the function that does the dispatching
 333           typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
 334           graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
 335         }
 336       };
 337     } // end namespace detail
 338     BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
 339   } // end namespace graph
 340
 341 } // end namespace boost
 342
 343 #include <boost/graph/iteration_macros_undef.hpp>
 344
 345 #endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H