File: maximum_adjacency_search.hpp

package info (click to toggle)
boost1.62 1.62.0+dfsg-4
  • links: PTS, VCS
  • area: main
  • in suites: stretch
  • size: 686,420 kB
  • sloc: cpp: 2,609,004; xml: 972,558; ansic: 53,674; python: 32,437; sh: 8,829; asm: 3,071; cs: 2,121; makefile: 964; perl: 859; yacc: 472; php: 132; ruby: 94; f90: 55; sql: 13; csh: 6
file content (319 lines) | stat: -rw-r--r-- 12,956 bytes parent folder | download | duplicates (10)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
//
//=======================================================================
// Copyright 2012 Fernando Vilas
//           2010 Daniel Trebbien
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
//

// The maximum adjacency search algorithm was originally part of the
// Stoer-Wagner min cut implementation by Daniel Trebbien. It has been
// broken out into its own file to be a public search algorithm, with
// visitor concepts.
#ifndef BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H
#define BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H

/**
 * This is an implementation of the maximum adjacency search on an
 * undirected graph. It allows a visitor object to perform some
 * operation on each vertex as that vertex is visited.
 *
 * The algorithm runs as follows:
 *
 * Initialize all nodes to be unvisited (reach count = 0)
 *   and call vis.initialize_vertex
 * For i = number of nodes in graph downto 1
 *   Select the unvisited node with the highest reach count
 *     The user provides the starting node to break the first tie,
 *     but future ties are broken arbitrarily
 *   Visit the node by calling vis.start_vertex
 *   Increment the reach count for all unvisited neighbors
 *     and call vis.examine_edge for each of these edges
 *   Mark the node as visited and call vis.finish_vertex
 *
 */

#include <boost/concept_check.hpp>
#include <boost/concept/assert.hpp>
#include <boost/graph/buffer_concepts.hpp>
#include <boost/graph/exception.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/tuple/tuple.hpp>

#include <set>

namespace boost {
  template <class Visitor, class Graph>
  struct MASVisitorConcept {
    void constraints() {
      boost::function_requires< boost::CopyConstructibleConcept<Visitor> >();
      vis.initialize_vertex(u, g);
      vis.start_vertex(u, g);
      vis.examine_edge(e, g);
      vis.finish_vertex(u, g);
    }
    Visitor vis;
    Graph g;
    typename boost::graph_traits<Graph>::vertex_descriptor u;
    typename boost::graph_traits<Graph>::edge_descriptor e;
  };

  template <class Visitors = null_visitor>
  class mas_visitor {
  public:
    mas_visitor() { }
    mas_visitor(Visitors vis) : m_vis(vis) { }

    template <class Vertex, class Graph>
    void
    initialize_vertex(Vertex u, Graph& g)
    {
      invoke_visitors(m_vis, u, g, ::boost::on_initialize_vertex());
    }

    template <class Vertex, class Graph>
    void
    start_vertex(Vertex u, Graph& g)
    {
      invoke_visitors(m_vis, u, g, ::boost::on_start_vertex());
    }

    template <class Edge, class Graph>
    void
    examine_edge(Edge e, Graph& g)
    {
      invoke_visitors(m_vis, e, g, ::boost::on_examine_edge());
    }

    template <class Vertex, class Graph>
    void
    finish_vertex(Vertex u, Graph& g)
    {
      invoke_visitors(m_vis, u, g, ::boost::on_finish_vertex());
    }

    BOOST_GRAPH_EVENT_STUB(on_initialize_vertex,mas)
    BOOST_GRAPH_EVENT_STUB(on_start_vertex,mas)
    BOOST_GRAPH_EVENT_STUB(on_examine_edge,mas)
    BOOST_GRAPH_EVENT_STUB(on_finish_vertex,mas)

  protected:
    Visitors m_vis;
  };
  template <class Visitors>
  mas_visitor<Visitors>
  make_mas_visitor(Visitors vis) {
    return mas_visitor<Visitors>(vis);
  }
  typedef mas_visitor<> default_mas_visitor;

  namespace detail {
    template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
      void
      maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
      typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
      typedef typename boost::property_traits<WeightMap>::value_type weight_type;

     std::set<vertex_descriptor> assignedVertices;

     // initialize `assignments` (all vertices are initially
     // assigned to themselves)
     BGL_FORALL_VERTICES_T(v, g, Graph) {
       put(assignments, v, v);
     }

      typename KeyedUpdatablePriorityQueue::key_map keys = pq.keys();

      // set number of visited neighbors for all vertices to 0
      BGL_FORALL_VERTICES_T(v, g, Graph) {
        if (v == get(assignments, v)) { // foreach u \in V do
          put(keys, v, weight_type(0));          vis.initialize_vertex(v, g);

          pq.push(v);
        }
      }
      BOOST_ASSERT(pq.size() >= 2);

      // Give the starting vertex high priority
      put(keys, start, get(keys, start) + num_vertices(g) + 1);
      pq.update(start);

      // start traversing the graph
      //vertex_descriptor s, t;
      weight_type w;
      while (!pq.empty()) { // while PQ \neq {} do
        const vertex_descriptor u = pq.top(); // u = extractmax(PQ)
        w = get(keys, u);                        vis.start_vertex(u, g);
        pq.pop();                  //            vis.start_vertex(u, g);

        BGL_FORALL_OUTEDGES_T(u, e, g, Graph) { // foreach (u, v) \in E do
                                                 vis.examine_edge(e, g);

          const vertex_descriptor v = get(assignments, target(e, g));

          if (pq.contains(v)) { // if v \in PQ then
            put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
            pq.update(v);
          }
        }

        typename std::set<vertex_descriptor>::const_iterator assignedVertexIt, assignedVertexEnd = assignedVertices.end();
        for (assignedVertexIt = assignedVertices.begin(); assignedVertexIt != assignedVertexEnd; ++assignedVertexIt) {
          const vertex_descriptor uPrime = *assignedVertexIt;

          if (get(assignments, uPrime) == u) {
            BGL_FORALL_OUTEDGES_T(uPrime, e, g, Graph) { // foreach (u, v) \in E do
                                                 vis.examine_edge(e, g);

              const vertex_descriptor v = get(assignments, target(e, g));

              if (pq.contains(v)) { // if v \in PQ then
                put(keys, v, get(keys, v) + get(weights, e)); // increasekey(PQ, v, wA(v) + w(u, v))
                pq.update(v);
              }
            }
          }
        }
                                                 vis.finish_vertex(u, g);
      }
    }
  } // end namespace detail

  template <class Graph, class WeightMap, class MASVisitor, class VertexAssignmentMap, class KeyedUpdatablePriorityQueue>
    void
maximum_adjacency_search(const Graph& g, WeightMap weights, MASVisitor vis, const typename boost::graph_traits<Graph>::vertex_descriptor start, VertexAssignmentMap assignments, KeyedUpdatablePriorityQueue pq) {
    BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<Graph>));
    BOOST_CONCEPT_ASSERT((boost::VertexListGraphConcept<Graph>));
    typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
    typedef typename boost::graph_traits<Graph>::vertices_size_type vertices_size_type;
    typedef typename boost::graph_traits<Graph>::edge_descriptor edge_descriptor;
    BOOST_CONCEPT_ASSERT((boost::Convertible<typename boost::graph_traits<Graph>::directed_category, boost::undirected_tag>));
    BOOST_CONCEPT_ASSERT((boost::ReadablePropertyMapConcept<WeightMap, edge_descriptor>));
    // typedef typename boost::property_traits<WeightMap>::value_type weight_type;
    boost::function_requires< MASVisitorConcept<MASVisitor, Graph> >();
    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.");

    detail::maximum_adjacency_search(g, weights,
                                            vis, start,
                                            assignments, pq);
  }

  namespace graph {
    namespace detail {
      template <typename WeightMap>
      struct mas_dispatch {
        typedef void result_type;
        template <typename Graph, typename ArgPack>
        static result_type apply(const Graph& g, 
                          //const bgl_named_params<P,T,R>& params, 
                          const ArgPack& params, 
                          WeightMap w) {

          using namespace boost::graph::keywords;
          typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
          typedef typename 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> > default_pq_gen_type;

          default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

          typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

          boost::maximum_adjacency_search
               (g,
                w,
                params [ _visitor | make_mas_visitor(null_visitor())],
                params [ _root_vertex | *vertices(g).first],
                params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
                pq
                );
        }
      };

      template <>
      struct mas_dispatch<boost::param_not_found> {
        typedef void result_type;

        template <typename Graph, typename ArgPack>
        static result_type apply(const Graph& g, 
                          const ArgPack& params, 
                          param_not_found) {

          using namespace boost::graph::keywords;
          typedef typename boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;

          // get edge_weight_t as the weight type
          typedef typename boost::property_map<Graph, edge_weight_t> WeightMap;
          typedef typename 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> > default_pq_gen_type;

          default_pq_gen_type pq_gen(choose_param(get_param(params, boost::distance_zero_t()), weight_type(0)));

          typename boost::result_of<default_pq_gen_type(const Graph&, const ArgPack&)>::type pq = pq_gen(g, params);

          boost::maximum_adjacency_search
               (g,
                get(edge_weight, g),
                params [ _visitor | make_mas_visitor(null_visitor())],
                params [ _root_vertex | *vertices(g).first],
                params [ _vertex_assignment_map | boost::detail::make_property_map_from_arg_pack_gen<boost::graph::keywords::tag::vertex_assignment_map, vertex_descriptor>(vertex_descriptor())(g, params)],
                pq
                );
        }
      };
    } // end namespace detail
  } // end namespace graph

  // Named parameter interface
  //BOOST_GRAPH_MAKE_OLD_STYLE_PARAMETER_FUNCTION(maximum_adjacency_search, 1)
  template <typename Graph, typename P, typename T, typename R>
  void
  maximum_adjacency_search (const Graph& g,
      const bgl_named_params<P,T,R>& params) {

    typedef bgl_named_params<P, T, R> params_type;
    BOOST_GRAPH_DECLARE_CONVERTED_PARAMETERS(params_type, params)

    // do the dispatch based on WeightMap
    typedef typename get_param_type<edge_weight_t, bgl_named_params<P,T,R> >::type W;
    graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(params, edge_weight));
  }

  namespace graph {
    namespace detail {
      template <typename Graph>
      struct maximum_adjacency_search_impl {
        typedef void result_type;

        template <typename ArgPack>
        void
        operator() (const Graph& g, const ArgPack& arg_pack) const {
          // call the function that does the dispatching
          typedef typename get_param_type<edge_weight_t, ArgPack >::type W;
          graph::detail::mas_dispatch<W>::apply(g, arg_pack, get_param(arg_pack, edge_weight));
        }
      };
    } // end namespace detail
    BOOST_GRAPH_MAKE_FORWARDING_FUNCTION(maximum_adjacency_search,1,5)
  } // end namespace graph

} // end namespace boost

#include <boost/graph/iteration_macros_undef.hpp>

#endif // BOOST_GRAPH_MAXIMUM_ADJACENCY_SEARCH_H