← Back to branch summary

~ubuntu-branches/ubuntu/saucy/deal.ii/saucy

« back to all changes in this revision

Viewing changes to contrib/boost/include/boost/graph/distributed/connected_components.hpp

  • Committer: Package Import Robot
  • Author(s): "Adam C. Powell, IV", Adam C. Powell, IV, Christophe Trophime
  • Date: 2012-02-21 06:57:30 UTC
  • mfrom: (3.1.7 sid)
  • Revision ID: package-import@ubuntu.com-20120221065730-r2iz70lg557wcd2e
Tags: 7.1.0-1
http://bugs.debian.org/652057
http://bugs.debian.org/652058
http://bugs.debian.org/637655
http://bugs.debian.org/659245
[ Adam C. Powell, IV ]
* New upstream (closes: #652057).
* Updated to use PETSc and SLEPc 3.2, and forward-ported all patches.
* Removed NetCDF Build-Depends because it uses serial HDF5.
* Made Sacado cmath patch work with new configure.
* Moved -dev package symlink lines in rules to arch all section.

[ Christophe Trophime ]
* debian/rules:
   - add dh_strip --dbg-package to generate dbg package (closes: #652058)
   - add .install files to simplify rules
* Add support for mumps, arpack (closes: #637655)
* Add patch for slepc 3.2 (closes: #659245)

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/boost/include/boost/graph/distributed/connected_components.hpp
1
 
// Copyright (C) 2004-2006 The Trustees of Indiana University.
2
 
 
3
 
// Use, modification and distribution is subject to the Boost Software
4
 
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
5
 
// http://www.boost.org/LICENSE_1_0.txt)
6
 
 
7
 
//  Authors: Nick Edmonds
8
 
//           Douglas Gregor
9
 
//           Andrew Lumsdaine
10
 
#ifndef BOOST_GRAPH_PARALLEL_CC_HPP
11
 
#define BOOST_GRAPH_PARALLEL_CC_HPP
12
 
 
13
 
#ifndef BOOST_GRAPH_USE_MPI
14
 
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
15
 
#endif
16
 
 
17
 
#include <boost/property_map/property_map.hpp>
18
 
#include <boost/property_map/parallel/caching_property_map.hpp>
19
 
#include <boost/graph/parallel/algorithm.hpp>
20
 
#include <boost/pending/indirect_cmp.hpp>
21
 
#include <boost/graph/graph_traits.hpp>
22
 
#include <boost/graph/overloading.hpp>
23
 
#include <boost/graph/distributed/concepts.hpp>
24
 
#include <boost/graph/parallel/properties.hpp>
25
 
#include <boost/graph/distributed/local_subgraph.hpp>
26
 
#include <boost/graph/connected_components.hpp>
27
 
#include <boost/graph/named_function_params.hpp>
28
 
#include <boost/graph/parallel/process_group.hpp>
29
 
#include <boost/optional.hpp>
30
 
#include <algorithm>
31
 
#include <vector>
32
 
#include <list>
33
 
#include <boost/graph/parallel/container_traits.hpp>
34
 
#include <boost/graph/iteration_macros.hpp>
35
 
 
36
 
#define PBGL_IN_PLACE_MERGE /* In place merge instead of sorting */
37
 
//#define PBGL_SORT_ASSERT    /* Assert sorted for in place merge */
38
 
 
39
 
/* Explicit sychronization in pointer doubling step? */
40
 
#define PBGL_EXPLICIT_SYNCH
41
 
//#define PBGL_CONSTRUCT_METAGRAPH
42
 
#ifdef PBGL_CONSTRUCT_METAGRAPH
43
 
#  define MAX_VERTICES_IN_METAGRAPH 10000
44
 
#endif
45
 
 
46
 
namespace boost { namespace graph { namespace distributed {
47
 
  namespace cc_detail {
48
 
    enum connected_components_message { 
49
 
      edges_msg, req_parents_msg, parents_msg, root_adj_msg
50
 
    };
51
 
 
52
 
    template <typename Vertex>
53
 
    struct metaVertex {
54
 
      metaVertex() {}
55
 
      metaVertex(const Vertex& v) : name(v) {}
56
 
 
57
 
      template<typename Archiver>
58
 
      void serialize(Archiver& ar, const unsigned int /*version*/)
59
 
      {
60
 
        ar & name;
61
 
      }
62
 
 
63
 
      Vertex name;
64
 
    };
65
 
 
66
 
#ifdef PBGL_CONSTRUCT_METAGRAPH
67
 
    // Build meta-graph on result of local connected components
68
 
    template <typename Graph, typename ParentMap, typename RootIterator,
69
 
              typename AdjacencyMap>
70
 
    void
71
 
    build_local_metagraph(const Graph& g, ParentMap p, RootIterator r,
72
 
                          RootIterator r_end, AdjacencyMap& adj)
73
 
    {
74
 
      // TODO: Static assert that AdjacencyMap::value_type is std::vector<vertex_descriptor>
75
 
 
76
 
      typedef typename boost::graph::parallel::process_group_type<Graph>::type
77
 
        process_group_type;
78
 
      typedef typename process_group_type::process_id_type process_id_type;
79
 
 
80
 
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
81
 
 
82
 
      BOOST_STATIC_ASSERT((is_same<typename AdjacencyMap::mapped_type,
83
 
                                     std::vector<vertex_descriptor> >::value));
84
 
 
85
 
      using boost::graph::parallel::process_group;
86
 
 
87
 
      process_group_type pg = process_group(g);
88
 
      process_id_type id = process_id(pg);
89
 
      
90
 
      if (id != 0) {
91
 
 
92
 
        // Send component roots and their associated edges to P0
93
 
        for ( ; r != r_end; ++r ) {
94
 
          std::vector<vertex_descriptor> adjs(1, *r); // Root
95
 
          adjs.reserve(adjs.size() + adj[*r].size());
96
 
          for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
97
 
               iter != adj[*r].end(); ++iter)
98
 
            adjs.push_back(get(p, *iter)); // Adjacencies
99
 
 
100
 
          send(pg, 0, root_adj_msg, adjs); 
101
 
        }
102
 
      }
103
 
      
104
 
      synchronize(pg);
105
 
 
106
 
      if (id == 0) {
107
 
        typedef metaVertex<vertex_descriptor> VertexProperties;
108
 
 
109
 
        typedef boost::adjacency_list<vecS, vecS, undirectedS, 
110
 
          VertexProperties> metaGraph;
111
 
        typedef typename graph_traits<metaGraph>::vertex_descriptor 
112
 
          meta_vertex_descriptor;
113
 
 
114
 
        std::map<vertex_descriptor, meta_vertex_descriptor> vertex_map;
115
 
        std::vector<std::pair<vertex_descriptor, vertex_descriptor> > edges;
116
 
 
117
 
        // Receive remote roots and edges
118
 
        while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
119
 
          assert(m->second == root_adj_msg);
120
 
 
121
 
          std::vector<vertex_descriptor> adjs;
122
 
          receive(pg, m->first, m->second, adjs);
123
 
 
124
 
          vertex_map[adjs[0]] = graph_traits<metaGraph>::null_vertex();
125
 
          for (typename std::vector<vertex_descriptor>::iterator iter 
126
 
                 = ++adjs.begin(); iter != adjs.end(); ++iter)
127
 
            edges.push_back(std::make_pair(adjs[0], *iter));
128
 
        }
129
 
 
130
 
        // Add local roots and edges
131
 
        for ( ; r != r_end; ++r ) {
132
 
          vertex_map[*r] = graph_traits<metaGraph>::null_vertex();
133
 
          edges.reserve(edges.size() + adj[*r].size());
134
 
          for (typename std::vector<vertex_descriptor>::iterator iter = adj[*r].begin();
135
 
               iter != adj[*r].end(); ++iter)
136
 
            edges.push_back(std::make_pair(*r, get(p, *iter)));
137
 
        } 
138
 
 
139
 
        // Build local meta-graph
140
 
        metaGraph mg;
141
 
 
142
 
        // Add vertices with property to map back to distributed graph vertex
143
 
        for (typename std::map<vertex_descriptor, meta_vertex_descriptor>::iterator
144
 
               iter = vertex_map.begin(); iter != vertex_map.end(); ++iter)
145
 
          vertex_map[iter->first] 
146
 
            = add_vertex(metaVertex<vertex_descriptor>(iter->first), mg);
147
 
 
148
 
        // Build meta-vertex map
149
 
        typename property_map<metaGraph, vertex_descriptor VertexProperties::*>::type 
150
 
          metaVertexMap = get(&VertexProperties::name, mg);
151
 
 
152
 
        typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >
153
 
          ::iterator edge_iter = edges.begin();
154
 
        for ( ; edge_iter != edges.end(); ++edge_iter)
155
 
          add_edge(vertex_map[edge_iter->first], vertex_map[edge_iter->second], mg);
156
 
        
157
 
        edges.clear();
158
 
  
159
 
        // Call connected_components on it
160
 
        typedef typename property_map<metaGraph, vertex_index_t>::type 
161
 
          meta_index_map_type;
162
 
        meta_index_map_type meta_index = get(vertex_index, mg);
163
 
 
164
 
        std::vector<std::size_t> mg_component_vec(num_vertices(mg));
165
 
        typedef iterator_property_map<std::vector<std::size_t>::iterator,
166
 
                                      meta_index_map_type>
167
 
        meta_components_map_type;
168
 
        meta_components_map_type mg_component(mg_component_vec.begin(),
169
 
                                              meta_index);
170
 
        std::size_t num_comp = connected_components(mg, mg_component);
171
 
 
172
 
        // Update Parent pointers
173
 
        std::vector<meta_vertex_descriptor> roots(num_comp, graph_traits<metaGraph>::null_vertex());
174
 
 
175
 
        BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
176
 
          size_t component = get(mg_component, v);
177
 
          if (roots[component] == graph_traits<metaGraph>::null_vertex() ||
178
 
              get(meta_index, v) < get(meta_index, roots[component])) 
179
 
            roots[component] = v;
180
 
        }
181
 
 
182
 
        // Set all the local parent pointers
183
 
        BGL_FORALL_VERTICES_T(v, mg, metaGraph) {
184
 
          // Problem in value being put (3rd parameter)
185
 
          put(p, get(metaVertexMap, v), get(metaVertexMap, roots[get(mg_component, v)]));
186
 
        }
187
 
      }
188
 
 
189
 
      synchronize(p);
190
 
    }
191
 
#endif
192
 
 
193
 
    /* Function object used to remove internal vertices and vertices >
194
 
       the current vertex from the adjacent vertex lists at each
195
 
       root */
196
 
    template <typename Vertex, typename ParentMap>
197
 
    class cull_adjacency_list
198
 
    {
199
 
    public:
200
 
      cull_adjacency_list(const Vertex v, const ParentMap p) : v(v), p(p) {}
201
 
      bool operator() (const Vertex x) { return (get(p, x) == v || x == v); }
202
 
 
203
 
    private:
204
 
      const Vertex    v;
205
 
      const ParentMap p;
206
 
    };
207
 
 
208
 
    /* Comparison operator used to choose targets for hooking s.t. vertices 
209
 
       that are hooked to are evenly distributed across processors */
210
 
    template <typename OwnerMap, typename LocalMap>
211
 
    class hashed_vertex_compare
212
 
    {
213
 
    public:
214
 
      hashed_vertex_compare (const OwnerMap& o, const LocalMap& l)
215
 
        : owner(o), local(l) { }
216
 
 
217
 
      template <typename Vertex>
218
 
      bool operator() (const Vertex x, const Vertex y) 
219
 
      { 
220
 
        if (get(local, x) < get(local, y))
221
 
          return true;
222
 
        else if (get(local, x) == get(local, y))
223
 
          return (get(owner, x) < get(owner, y));
224
 
        return false;
225
 
      }
226
 
 
227
 
    private:
228
 
      OwnerMap   owner;
229
 
      LocalMap   local;
230
 
    };
231
 
 
232
 
#ifdef PBGL_EXPLICIT_SYNCH
233
 
    template <typename Graph, typename ParentMap, typename VertexList>
234
 
    void
235
 
    request_parent_map_entries(const Graph& g, ParentMap p,
236
 
                               std::vector<VertexList>& parent_requests)
237
 
    {
238
 
      typedef typename boost::graph::parallel::process_group_type<Graph>
239
 
        ::type process_group_type;
240
 
      typedef typename process_group_type::process_id_type process_id_type;
241
 
 
242
 
      typedef typename graph_traits<Graph>::vertex_descriptor
243
 
        vertex_descriptor;
244
 
 
245
 
      process_group_type pg = process_group(g);
246
 
      
247
 
      /*
248
 
        This should probably be send_oob_with_reply, especially when Dave 
249
 
        finishes prefetch-batching
250
 
      */
251
 
 
252
 
      // Send root requests
253
 
      for (process_id_type i = 0; i < num_processes(pg); ++i) {
254
 
        if (!parent_requests[i].empty()) {
255
 
          std::vector<vertex_descriptor> reqs(parent_requests[i].begin(),
256
 
                                              parent_requests[i].end());
257
 
          send(pg, i, req_parents_msg, reqs);
258
 
        }
259
 
      }
260
 
      
261
 
      synchronize(pg);
262
 
      
263
 
      // Receive root requests and reply to them
264
 
      while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
265
 
        std::vector<vertex_descriptor> requests;
266
 
        receive(pg, m->first, m->second, requests);
267
 
        for (std::size_t i = 0; i < requests.size(); ++i)
268
 
          requests[i] = get(p, requests[i]);
269
 
        send(pg, m->first, parents_msg, requests);
270
 
      }
271
 
      
272
 
      synchronize(pg);
273
 
      
274
 
      // Receive requested parents
275
 
      std::vector<vertex_descriptor> responses;
276
 
      for (process_id_type i = 0; i < num_processes(pg); ++i) {
277
 
        if (!parent_requests[i].empty()) {
278
 
          receive(pg, i, parents_msg, responses);
279
 
          std::size_t parent_idx = 0;
280
 
          for (typename VertexList::iterator v = parent_requests[i].begin();
281
 
               v != parent_requests[i].end(); ++v, ++parent_idx)
282
 
            put(p, *v, responses[parent_idx]);
283
 
        }
284
 
      }
285
 
    }
286
 
#endif
287
 
    
288
 
    template<typename DistributedGraph, typename ParentMap>
289
 
    void
290
 
    parallel_connected_components(DistributedGraph& g, ParentMap p)
291
 
    {
292
 
      using boost::connected_components;
293
 
 
294
 
      typedef typename graph_traits<DistributedGraph>::adjacency_iterator
295
 
        adjacency_iterator;
296
 
      typedef typename graph_traits<DistributedGraph>::out_edge_iterator
297
 
        out_edge_iterator;
298
 
      typedef typename graph_traits<DistributedGraph>::edge_iterator
299
 
        edge_iterator;
300
 
      typedef typename graph_traits<DistributedGraph>::vertex_descriptor
301
 
        vertex_descriptor;
302
 
      typedef typename graph_traits<DistributedGraph>::edge_descriptor
303
 
        edge_descriptor;
304
 
 
305
 
      typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
306
 
        ::type process_group_type;
307
 
      typedef typename process_group_type::process_id_type process_id_type;
308
 
 
309
 
      using boost::graph::parallel::process_group;
310
 
 
311
 
      process_group_type pg = process_group(g);
312
 
      process_id_type id = process_id(pg);
313
 
 
314
 
      // TODO (NGE): Should old_roots, roots, and completed_roots be std::list
315
 
      adjacency_iterator av1, av2;
316
 
      std::vector<vertex_descriptor> old_roots;
317
 
      typename std::vector<vertex_descriptor>::iterator liter;
318
 
      typename std::vector<vertex_descriptor>::iterator aliter;
319
 
      typename std::map<vertex_descriptor,
320
 
                        std::vector<vertex_descriptor> > adj;
321
 
 
322
 
      typedef typename property_map<DistributedGraph, vertex_owner_t>::const_type
323
 
        OwnerMap;
324
 
      OwnerMap owner = get(vertex_owner, g);
325
 
      typedef typename property_map<DistributedGraph, vertex_local_t>::const_type
326
 
        LocalMap;
327
 
      LocalMap local = get(vertex_local, g);
328
 
 
329
 
      // We need to hold on to all of the parent pointers
330
 
      p.set_max_ghost_cells(0);
331
 
 
332
 
      //
333
 
      // STAGE 1 : Compute local components
334
 
      //
335
 
      local_subgraph<const DistributedGraph> ls(g);
336
 
      typedef typename property_map<local_subgraph<const DistributedGraph>,
337
 
                                    vertex_index_t>::type local_index_map_type;
338
 
      local_index_map_type local_index = get(vertex_index, ls);
339
 
 
340
 
      // Compute local connected components
341
 
      std::vector<std::size_t> ls_components_vec(num_vertices(ls));
342
 
      typedef iterator_property_map<std::vector<std::size_t>::iterator,
343
 
                                    local_index_map_type>
344
 
        ls_components_map_type;
345
 
      ls_components_map_type ls_component(ls_components_vec.begin(),
346
 
                                          local_index);
347
 
      std::size_t num_comp = connected_components(ls, ls_component);
348
 
 
349
 
      std::vector<vertex_descriptor> 
350
 
        roots(num_comp, graph_traits<DistributedGraph>::null_vertex());
351
 
 
352
 
      BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
353
 
        size_t component = get(ls_component, v);
354
 
        if (roots[component] == graph_traits<DistributedGraph>::null_vertex() ||
355
 
            get(local_index, v) < get(local_index, roots[component])) 
356
 
          roots[component] = v;
357
 
      }
358
 
 
359
 
      // Set all the local parent pointers
360
 
      BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
361
 
        put(p, v, roots[get(ls_component, v)]);
362
 
      }
363
 
 
364
 
      if (num_processes(pg) == 1) return;
365
 
 
366
 
      // Build adjacency list for all roots
367
 
      BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
368
 
        std::vector<vertex_descriptor>& my_adj = adj[get(p, v)];
369
 
        for (tie(av1, av2) = adjacent_vertices(v, g);
370
 
             av1 != av2; ++av1) {
371
 
          if (get(owner, *av1) != id) my_adj.push_back(*av1);
372
 
        }
373
 
      }
374
 
 
375
 
      // For all vertices adjacent to a local vertex get p(v)
376
 
      for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
377
 
        std::vector<vertex_descriptor>& my_adj = adj[*liter];
378
 
        for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
379
 
          request(p, *aliter);
380
 
      }
381
 
      synchronize(p);
382
 
 
383
 
      // Update adjacency list at root to make sure all adjacent
384
 
      // vertices are roots of remote components
385
 
      for ( liter = roots.begin(); liter != roots.end(); ++liter )
386
 
        {
387
 
          std::vector<vertex_descriptor>& my_adj = adj[*liter];
388
 
          for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
389
 
            *aliter = get(p, *aliter);
390
 
 
391
 
          my_adj.erase
392
 
            (remove_if(my_adj.begin(), my_adj.end(),
393
 
                       cull_adjacency_list<vertex_descriptor, 
394
 
                                           ParentMap>(*liter, p) ),
395
 
             my_adj.end());
396
 
          // This sort needs to be here to make sure the initial
397
 
          // adjacency list is sorted
398
 
          sort(my_adj.begin(), my_adj.end(), std::less<vertex_descriptor>());
399
 
          my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end());
400
 
        }
401
 
 
402
 
      // Get p(v) for the new adjacent roots
403
 
      p.clear();
404
 
      for ( liter = roots.begin(); liter != roots.end(); ++liter ) {
405
 
        std::vector<vertex_descriptor>& my_adj = adj[*liter];
406
 
        for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
407
 
          request(p, *aliter);
408
 
      }
409
 
#ifdef PBGL_EXPLICIT_SYNCH
410
 
      synchronize(p);
411
 
#endif
412
 
 
413
 
      // Lastly, remove roots with no adjacent vertices, this is
414
 
      // unnecessary but will speed up sparse graphs
415
 
      for ( liter = roots.begin(); liter != roots.end(); /*in loop*/)
416
 
        {
417
 
          if ( adj[*liter].empty() )
418
 
            liter = roots.erase(liter);
419
 
          else
420
 
            ++liter;
421
 
        }
422
 
 
423
 
#ifdef PBGL_CONSTRUCT_METAGRAPH
424
 
      /* TODO: If the number of roots is sufficiently small, we can 
425
 
               use a 'problem folding' approach like we do in MST
426
 
               to gather all the roots and their adjacencies on one proc
427
 
               and solve for the connected components of the meta-graph */
428
 
      using boost::parallel::all_reduce;
429
 
      std::size_t num_roots = all_reduce(pg, roots.size(), std::plus<std::size_t>());
430
 
      if (num_roots < MAX_VERTICES_IN_METAGRAPH) {
431
 
        build_local_metagraph(g, p, roots.begin(), roots.end(), adj);
432
 
        
433
 
        // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
434
 
        // vertices from first step to final parent
435
 
        BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
436
 
          put(p, v, get(p, get(p, v)));
437
 
        }
438
 
        
439
 
        synchronize(p);
440
 
        
441
 
        return;
442
 
      }
443
 
#endif
444
 
 
445
 
      //
446
 
      // Parallel Phase
447
 
      //
448
 
 
449
 
      std::vector<vertex_descriptor> completed_roots;
450
 
      hashed_vertex_compare<OwnerMap, LocalMap> v_compare(owner, local);
451
 
      bool any_hooked;
452
 
      vertex_descriptor new_root;
453
 
 
454
 
      std::size_t steps = 0;
455
 
 
456
 
      do {
457
 
        ++steps;
458
 
 
459
 
        // Pull in new parents for hooking phase
460
 
        synchronize(p);
461
 
 
462
 
        //
463
 
        // Hooking
464
 
        //
465
 
        bool hooked = false;
466
 
        completed_roots.clear();
467
 
        for ( liter = roots.begin(); liter != roots.end(); )
468
 
          {
469
 
            new_root = graph_traits<DistributedGraph>::null_vertex();
470
 
            std::vector<vertex_descriptor>& my_adj = adj[*liter];
471
 
            for ( aliter = my_adj.begin(); aliter != my_adj.end(); ++aliter )
472
 
              // try to hook to better adjacent vertex
473
 
              if ( v_compare( get(p, *aliter), *liter ) )
474
 
                new_root = get(p, *aliter);
475
 
 
476
 
            if ( new_root != graph_traits<DistributedGraph>::null_vertex() )
477
 
              {
478
 
                hooked = true;
479
 
                put(p, *liter, new_root);
480
 
                old_roots.push_back(*liter);
481
 
                completed_roots.push_back(*liter);
482
 
                liter = roots.erase(liter);
483
 
              }
484
 
            else
485
 
              ++liter;
486
 
          }
487
 
 
488
 
        //
489
 
        // Pointer jumping, perform until new roots determined
490
 
        //
491
 
 
492
 
        // TODO: Implement cycle reduction rules to reduce this from
493
 
        // O(n) to O(log n) [n = cycle length]
494
 
        bool all_done;
495
 
        std::size_t parent_root_count;
496
 
 
497
 
        std::size_t double_steps = 0;
498
 
 
499
 
        do {
500
 
          ++double_steps;
501
 
#ifndef PBGL_EXPLICIT_SYNCH
502
 
          // Get p(p(v)) for all old roots, and p(v) for all current roots
503
 
          for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
504
 
            request(p, get(p, *liter));
505
 
 
506
 
          synchronize(p);
507
 
#else
508
 
          // Build root requests
509
 
          typedef std::set<vertex_descriptor> VertexSet;
510
 
          std::vector<VertexSet> parent_requests(num_processes(pg));
511
 
          for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
512
 
            {
513
 
              vertex_descriptor p1 = *liter;
514
 
              if (get(owner, p1) != id) parent_requests[get(owner, p1)].insert(p1);
515
 
              vertex_descriptor p2 = get(p, p1);
516
 
              if (get(owner, p2) != id) parent_requests[get(owner, p2)].insert(p2);
517
 
            }
518
 
 
519
 
          request_parent_map_entries(g, p, parent_requests);
520
 
#endif
521
 
          // Perform a pointer jumping step on all old roots
522
 
          for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
523
 
              put(p, *liter, get(p, get(p, *liter)));
524
 
 
525
 
          // make sure the parent of all old roots is itself a root
526
 
          parent_root_count = 0;
527
 
          for ( liter = old_roots.begin(); liter != old_roots.end(); ++liter )
528
 
            if ( get(p, *liter) == get(p, get(p, *liter)) )
529
 
              parent_root_count++;
530
 
 
531
 
          bool done = parent_root_count == old_roots.size();
532
 
 
533
 
          all_reduce(pg, &done, &done+1, &all_done,
534
 
                     std::logical_and<bool>());
535
 
        } while ( !all_done );
536
 
#ifdef PARALLEL_BGL_DEBUG
537
 
        if (id == 0) std::cerr << double_steps << " doubling steps.\n";
538
 
#endif
539
 
        //
540
 
        // Add adjacent vertices of just completed roots to adjacent
541
 
        // vertex list at new parent
542
 
        //
543
 
        typename std::vector<vertex_descriptor> outgoing_edges;
544
 
        for ( liter = completed_roots.begin(); liter != completed_roots.end();
545
 
              ++liter )
546
 
          {
547
 
            vertex_descriptor new_parent = get(p, *liter);
548
 
 
549
 
            if ( get(owner, new_parent) == id )
550
 
              {
551
 
                std::vector<vertex_descriptor>& my_adj = adj[new_parent];
552
 
                my_adj.reserve(my_adj.size() + adj[*liter].size());
553
 
                my_adj.insert( my_adj.end(),
554
 
                               adj[*liter].begin(), adj[*liter].end() );
555
 
#ifdef PBGL_IN_PLACE_MERGE
556
 
#ifdef PBGL_SORT_ASSERT
557
 
                assert(__gnu_cxx::is_sorted(my_adj.begin(),
558
 
                                            my_adj.end() - adj[*liter].size(),
559
 
                                            std::less<vertex_descriptor>()));
560
 
                assert(__gnu_cxx::is_sorted(my_adj.end() - adj[*liter].size(),
561
 
                                            my_adj.end(),
562
 
                                            std::less<vertex_descriptor>()));
563
 
#endif
564
 
                std::inplace_merge(my_adj.begin(),
565
 
                                   my_adj.end() - adj[*liter].size(),
566
 
                                   my_adj.end(),
567
 
                                   std::less<vertex_descriptor>());
568
 
#endif
569
 
 
570
 
 
571
 
              }
572
 
            else if ( adj[*liter].begin() != adj[*liter].end() )
573
 
              {
574
 
                outgoing_edges.clear();
575
 
                outgoing_edges.reserve(adj[*liter].size() + 1);
576
 
                // First element is the destination of the adjacency list
577
 
                outgoing_edges.push_back(new_parent);
578
 
                outgoing_edges.insert(outgoing_edges.end(),
579
 
                                      adj[*liter].begin(), adj[*liter].end() );
580
 
                send(pg, get(owner, new_parent), edges_msg, outgoing_edges);
581
 
                adj[*liter].clear();
582
 
              }
583
 
          }
584
 
        synchronize(pg);
585
 
 
586
 
        // Receive edges sent by remote nodes and add them to the
587
 
        // indicated vertex's adjacency list
588
 
        while (optional<std::pair<process_id_type, int> > m
589
 
               = probe(pg))
590
 
          {
591
 
            std::vector<vertex_descriptor> incoming_edges;
592
 
            receive(pg, m->first, edges_msg, incoming_edges);
593
 
            typename std::vector<vertex_descriptor>::iterator aviter
594
 
              = incoming_edges.begin();
595
 
            ++aviter;
596
 
 
597
 
            std::vector<vertex_descriptor>& my_adj = adj[incoming_edges[0]];
598
 
 
599
 
            my_adj.reserve(my_adj.size() + incoming_edges.size() - 1);
600
 
            my_adj.insert( my_adj.end(), aviter, incoming_edges.end() );
601
 
 
602
 
#ifdef PBGL_IN_PLACE_MERGE
603
 
            std::size_t num_incoming_edges = incoming_edges.size();
604
 
#ifdef PBGL_SORT_ASSERT
605
 
            assert(__gnu_cxx::is_sorted(my_adj.begin(),
606
 
                                        my_adj.end() - (num_incoming_edges-1),
607
 
                                        std::less<vertex_descriptor>()));
608
 
            assert(__gnu_cxx::is_sorted(my_adj.end() - (num_incoming_edges-1),
609
 
                                        my_adj.end(),
610
 
                                        std::less<vertex_descriptor>()));
611
 
#endif
612
 
            std::inplace_merge(my_adj.begin(),
613
 
                               my_adj.end() - (num_incoming_edges - 1),
614
 
                               my_adj.end(),
615
 
                               std::less<vertex_descriptor>());
616
 
#endif
617
 
 
618
 
          }
619
 
 
620
 
 
621
 
        // Remove any adjacent vertices that are in the same component
622
 
        // as a root from that root's list
623
 
        for ( liter = roots.begin(); liter != roots.end(); ++liter )
624
 
          {
625
 
            // We can probably get away without sorting and removing
626
 
            // duplicates Though sorting *may* cause root
627
 
            // determination to occur faster by choosing the root with
628
 
            // the most potential to hook to at each step
629
 
            std::vector<vertex_descriptor>& my_adj = adj[*liter];
630
 
            my_adj.erase
631
 
              (remove_if(my_adj.begin(), my_adj.end(),
632
 
                         cull_adjacency_list<vertex_descriptor,
633
 
                                             ParentMap>(*liter, p) ),
634
 
               my_adj.end());
635
 
#ifndef PBGL_IN_PLACE_MERGE
636
 
            sort(my_adj.begin(), my_adj.end(),
637
 
                 std::less<vertex_descriptor>() );
638
 
#endif
639
 
            my_adj.erase(unique(my_adj.begin(), my_adj.end()), my_adj.end());
640
 
          }
641
 
 
642
 
        // Reduce result of empty root list test
643
 
        all_reduce(pg, &hooked, &hooked+1, &any_hooked,
644
 
                   std::logical_or<bool>());
645
 
      } while ( any_hooked );
646
 
#ifdef PARALLEL_BGL_DEBUG
647
 
      if (id == 0) std::cerr << steps << " iterations.\n";
648
 
#endif
649
 
      //
650
 
      // Finalize
651
 
      //
652
 
 
653
 
      // For each vertex in g, p(v) = p(p(v)), assign parent of leaf
654
 
      // vertices from first step to final parent
655
 
      BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
656
 
        put(p, v, get(p, get(p, v)));
657
 
      }
658
 
      
659
 
      synchronize(p);
660
 
    }
661
 
 
662
 
  } // end namespace cc_detail
663
 
 
664
 
  template<typename Graph, typename ParentMap, typename ComponentMap>
665
 
  typename property_traits<ComponentMap>::value_type
666
 
  number_components_from_parents(const Graph& g, ParentMap p, ComponentMap c)
667
 
  {
668
 
    typedef typename graph_traits<Graph>::vertex_descriptor
669
 
      vertex_descriptor;
670
 
    typedef typename boost::graph::parallel::process_group_type<Graph>::type
671
 
      process_group_type;
672
 
    typedef typename property_traits<ComponentMap>::value_type
673
 
      ComponentMapType;
674
 
 
675
 
    process_group_type pg = process_group(g);
676
 
 
677
 
    /* Build list of roots */
678
 
    std::vector<vertex_descriptor> my_roots, all_roots;
679
 
 
680
 
    BGL_FORALL_VERTICES_T(v, g, Graph) {
681
 
      if( find( my_roots.begin(), my_roots.end(), get(p, v) )
682
 
          == my_roots.end() )
683
 
        my_roots.push_back( get(p, v) );
684
 
    }
685
 
 
686
 
    all_gather(pg, my_roots.begin(), my_roots.end(), all_roots);
687
 
 
688
 
    /* Number components */
689
 
    std::map<vertex_descriptor, ComponentMapType> comp_numbers;
690
 
    ComponentMapType c_num = 0;
691
 
 
692
 
    // Compute component numbers
693
 
    for (std::size_t i = 0; i < all_roots.size(); i++ )
694
 
      if ( comp_numbers.count(all_roots[i]) == 0 )
695
 
        comp_numbers[all_roots[i]] = c_num++;
696
 
 
697
 
    // Broadcast component numbers
698
 
    BGL_FORALL_VERTICES_T(v, g, Graph) {
699
 
      put( c, v, comp_numbers[get(p, v)] );
700
 
    }
701
 
 
702
 
    // Broadcast number of components
703
 
    if (process_id(pg) == 0) {
704
 
      typedef typename process_group_type::process_size_type
705
 
        process_size_type;
706
 
      for (process_size_type dest = 1, n = num_processes(pg);
707
 
           dest != n; ++dest)
708
 
        send(pg, dest, 0, c_num);
709
 
    }
710
 
    synchronize(pg);
711
 
 
712
 
    if (process_id(pg) != 0) receive(pg, 0, 0, c_num);
713
 
 
714
 
    synchronize(c);
715
 
 
716
 
    return c_num;
717
 
  }
718
 
 
719
 
  template<typename Graph, typename ParentMap>
720
 
  int
721
 
  number_components_from_parents(const Graph& g, ParentMap p, 
722
 
                                 dummy_property_map)
723
 
  {
724
 
    using boost::parallel::all_reduce;
725
 
 
726
 
    // Count local roots.
727
 
    int num_roots = 0;
728
 
    BGL_FORALL_VERTICES_T(v, g, Graph)
729
 
      if (get(p, v) == v) ++num_roots;
730
 
    return all_reduce(g.process_group(), num_roots, std::plus<int>());
731
 
  }
732
 
 
733
 
  template<typename Graph, typename ComponentMap, typename ParentMap>
734
 
  typename property_traits<ComponentMap>::value_type
735
 
  connected_components
736
 
    (const Graph& g, ComponentMap c, ParentMap p
737
 
     BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag))
738
 
  {
739
 
    cc_detail::parallel_connected_components(g, p);
740
 
    return number_components_from_parents(g, p, c);
741
 
  }
742
 
 
743
 
  /* Construct ParentMap by default */
744
 
  template<typename Graph, typename ComponentMap>
745
 
  typename property_traits<ComponentMap>::value_type
746
 
  connected_components
747
 
    ( const Graph& g, ComponentMap c
748
 
      BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag) )
749
 
  {
750
 
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
751
 
 
752
 
    std::vector<vertex_descriptor> x(num_vertices(g));
753
 
 
754
 
    return connected_components
755
 
             (g, c,
756
 
              make_iterator_property_map(x.begin(), get(vertex_index, g)));
757
 
  }
758
 
} // end namespace distributed
759
 
 
760
 
using distributed::connected_components;
761
 
} // end namespace graph
762
 
 
763
 
using graph::distributed::connected_components;
764
 
} // end namespace boost
765
 
 
766
 
#endif // BOOST_GRAPH_PARALLEL_CC_HPP