← Back to branch summary

~ubuntu-branches/ubuntu/wily/deal.ii/wily-proposed

« back to all changes in this revision

Viewing changes to contrib/boost/include/boost/graph/distributed/adjlist/serialization.hpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV, Adam C. Powell, IV, Denis Barbier
  • Date: 2010-07-29 13:47:01 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100729134701-qk60t2om7u7oklkb
Tags: 6.3.1-1
http://bugs.debian.org/562332
[ Adam C. Powell, IV ]
* Changed to source format 3.0 (quilt).
* Changed maintainer to debian-science with Adam Powell as uploader.
* Added source lintian overrides about Adam Powell's name.
* Added Vcs info on git repository.
* Bumped Standards-Version.
* Changed stamp-patch to patch target and fixed its application criterion.
* Moved make_dependencies and expand_instantiations to a versioned directory
  to avoid shlib package conflicts.

[ Denis Barbier ]
* New upstream release (closes: #562332).
  + Added libtbb support.
  + Forward-ported all patches.
* Updates for new PETSc version, including workaround for different versions
  of petsc and slepc.
* Add debian/watch.
* Update to debhelper 7.
* Added pdebuild patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/boost/include/boost/graph/distributed/adjlist/serialization.hpp
 
1
// Copyright Daniel Wallin 2007. Use, modification and distribution is
 
2
// subject to the Boost Software License, Version 1.0. (See accompanying
 
3
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
4
 
 
5
#ifndef BOOST_GRAPH_DISTRIBUTED_ADJLIST_SERIALIZATION_070925_HPP
 
6
#define BOOST_GRAPH_DISTRIBUTED_ADJLIST_SERIALIZATION_070925_HPP
 
7
 
 
8
#ifndef BOOST_GRAPH_USE_MPI
 
9
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
 
10
#endif
 
11
 
 
12
# include <boost/lexical_cast.hpp>
 
13
# include <boost/foreach.hpp>
 
14
# include <boost/filesystem/path.hpp>
 
15
# include <boost/filesystem/operations.hpp>
 
16
# include <cctype>
 
17
# include <fstream>
 
18
 
 
19
namespace boost {
 
20
 
 
21
namespace detail { namespace parallel
 
22
{
 
23
 
 
24
  // Wraps a local descriptor, making it serializable.
 
25
  template <class Local>
 
26
  struct serializable_local_descriptor
 
27
  {
 
28
      serializable_local_descriptor()
 
29
      {}
 
30
 
 
31
      serializable_local_descriptor(Local local)
 
32
        : local(local)
 
33
      {}
 
34
 
 
35
      operator Local const&() const
 
36
      {
 
37
          return local;
 
38
      }
 
39
 
 
40
      bool operator==(serializable_local_descriptor const& other) const
 
41
      {
 
42
          return local == other.local;
 
43
      }
 
44
 
 
45
      bool operator<(serializable_local_descriptor const& other) const
 
46
      {
 
47
          return local < other.local;
 
48
      }
 
49
 
 
50
      template <class Archive>
 
51
      void serialize(Archive& ar, const unsigned int /*version*/)
 
52
      {
 
53
          ar & unsafe_serialize(local);
 
54
      }
 
55
 
 
56
      Local local;
 
57
  };
 
58
 
 
59
  template <class Vertex, class Properties>
 
60
  struct pending_edge
 
61
  {
 
62
      pending_edge(
 
63
          Vertex source, Vertex target
 
64
        , Properties properties, void* property_ptr
 
65
      )
 
66
        : source(source)
 
67
        , target(target)
 
68
        , properties(properties)
 
69
        , property_ptr(property_ptr)
 
70
      {}
 
71
 
 
72
      Vertex source;
 
73
      Vertex target;
 
74
      Properties properties;
 
75
      void* property_ptr;
 
76
  };
 
77
 
 
78
  inline bool is_digit(char c)
 
79
  {
 
80
      return std::isdigit(c);
 
81
  }
 
82
 
 
83
  inline std::vector<int> 
 
84
      available_process_files(std::string const& filename)
 
85
      {
 
86
          if (!filesystem::exists(filename))
 
87
              return std::vector<int>();
 
88
 
 
89
          std::vector<int> result;
 
90
 
 
91
          for (filesystem::directory_iterator i(filename), end; i != end; ++i)
 
92
          {
 
93
              if (!filesystem::is_regular(*i))
 
94
                  boost::throw_exception(std::runtime_error("directory contains non-regular entries"));
 
95
 
 
96
#if BOOST_VERSION >= 103600
 
97
              std::string process_name = i->path().filename();
 
98
#else
 
99
              std::string process_name = i->leaf();
 
100
#endif
 
101
              for (std::string::size_type i = 0; i < process_name.size(); ++i)
 
102
                if (!is_digit(process_name[i]))
 
103
                  boost::throw_exception(std::runtime_error("directory contains files with invalid names"));
 
104
 
 
105
              result.push_back(boost::lexical_cast<int>(process_name));
 
106
          }
 
107
 
 
108
          return result;
 
109
      }
 
110
 
 
111
  template <class Archive, class Tag, class T, class Base>
 
112
  void maybe_load_properties(
 
113
      Archive& ar, char const* name, property<Tag, T, Base>& properties)
 
114
  {
 
115
      ar >> serialization::make_nvp(name, get_property_value(properties, Tag()));
 
116
      maybe_load_properties(ar, name, static_cast<Base&>(properties));
 
117
  }
 
118
 
 
119
  template <class Archive>
 
120
  void maybe_load_properties(
 
121
      Archive&, char const*, no_property&)
 
122
  {}
 
123
 
 
124
  template <class Archive, typename Bundle>
 
125
  void maybe_load_properties(
 
126
      Archive& ar, char const* name, Bundle& bundle)
 
127
  {
 
128
    ar >> serialization::make_nvp(name, bundle);
 
129
    no_property prop;
 
130
    maybe_load_properties(ar, name, prop);
 
131
  }
 
132
 
 
133
 
 
134
 
 
135
 
 
136
 
 
137
 
 
138
  template <class Graph, class Archive, class VertexListS>
 
139
  struct graph_loader
 
140
  {
 
141
      typedef typename Graph::vertex_descriptor vertex_descriptor;
 
142
      typedef typename Graph::local_vertex_descriptor local_vertex_descriptor;
 
143
      typedef typename Graph::vertex_property_type vertex_property_type;
 
144
      typedef typename Graph::edge_descriptor edge_descriptor;
 
145
      typedef typename Graph::local_edge_descriptor local_edge_descriptor;
 
146
      typedef typename Graph::edge_property_type edge_property_type;
 
147
      typedef typename Graph::process_group_type process_group_type;
 
148
      typedef typename process_group_type::process_id_type process_id_type;
 
149
      typedef typename Graph::directed_selector directed_selector;
 
150
      typedef typename mpl::if_<
 
151
          is_same<VertexListS, defaultS>, vecS, VertexListS
 
152
      >::type vertex_list_selector;
 
153
      typedef pending_edge<vertex_descriptor, edge_property_type> 
 
154
          pending_edge_type; 
 
155
      typedef serializable_local_descriptor<local_vertex_descriptor>
 
156
          serializable_vertex_descriptor;
 
157
 
 
158
      graph_loader(Graph& g, Archive& ar)
 
159
        : m_g(g)
 
160
        , m_ar(ar)
 
161
        , m_pg(g.process_group())
 
162
        , m_requested_vertices(num_processes(m_pg))
 
163
        , m_remote_vertices(num_processes(m_pg))
 
164
        , m_property_ptrs(num_processes(m_pg))
 
165
      {
 
166
          g.clear();
 
167
          load_prefix();
 
168
          load_vertices();
 
169
          load_edges();
 
170
          ar >> make_nvp("distribution", m_g.distribution());
 
171
      }
 
172
 
 
173
  private:
 
174
      struct pending_in_edge
 
175
      {
 
176
          pending_in_edge(
 
177
              vertex_descriptor u, vertex_descriptor v, void* property_ptr
 
178
          )
 
179
            : u(u)
 
180
            , v(v)
 
181
            , property_ptr(property_ptr)
 
182
          {}
 
183
 
 
184
          vertex_descriptor u;
 
185
          vertex_descriptor v;
 
186
          void* property_ptr;
 
187
      };
 
188
 
 
189
      bool is_root() const
 
190
      {
 
191
          return process_id(m_pg) == 0;
 
192
      }
 
193
 
 
194
      template <class T>
 
195
      serialization::nvp<T> const make_nvp(char const* name, T& value) const
 
196
      {
 
197
          return serialization::nvp<T>(name, value);
 
198
      }
 
199
 
 
200
      void load_prefix();
 
201
      void load_vertices();
 
202
 
 
203
      template <class Anything>
 
204
      void maybe_load_and_store_local_vertex(Anything);
 
205
      void maybe_load_and_store_local_vertex(vecS);
 
206
 
 
207
      void load_edges();
 
208
      void load_in_edges(bidirectionalS);
 
209
      void load_in_edges(directedS);
 
210
      void add_pending_in_edge(
 
211
          vertex_descriptor u, vertex_descriptor v, void* property_ptr, vecS);
 
212
      template <class Anything>
 
213
      void add_pending_in_edge(
 
214
          vertex_descriptor u, vertex_descriptor v, void* property_ptr, Anything);
 
215
      template <class Anything>
 
216
      void add_edge(
 
217
          vertex_descriptor u, vertex_descriptor v
 
218
        , edge_property_type const& property, void* property_ptr, Anything);
 
219
      void add_edge(
 
220
          vertex_descriptor u, vertex_descriptor v
 
221
        , edge_property_type const& property, void* property_ptr, vecS);
 
222
      void add_remote_vertex_request(
 
223
          vertex_descriptor u, vertex_descriptor v, directedS);
 
224
      void add_remote_vertex_request(
 
225
          vertex_descriptor u, vertex_descriptor v, bidirectionalS);
 
226
      void add_in_edge(
 
227
          edge_descriptor const&, void*, directedS);
 
228
      void add_in_edge(
 
229
          edge_descriptor const& edge, void* old_property_ptr, bidirectionalS);
 
230
 
 
231
      void resolve_remote_vertices(directedS);
 
232
      void resolve_remote_vertices(bidirectionalS);
 
233
      vertex_descriptor resolve_remote_vertex(vertex_descriptor u) const;
 
234
      vertex_descriptor resolve_remote_vertex(vertex_descriptor u, vecS) const;
 
235
      template <class Anything>
 
236
      vertex_descriptor resolve_remote_vertex(vertex_descriptor u, Anything) const;
 
237
 
 
238
      void resolve_property_ptrs();
 
239
 
 
240
      void commit_pending_edges(vecS);
 
241
      template <class Anything>
 
242
      void commit_pending_edges(Anything);
 
243
      void commit_pending_in_edges(directedS);
 
244
      void commit_pending_in_edges(bidirectionalS);
 
245
 
 
246
      void* maybe_load_property_ptr(directedS) { return 0; }
 
247
      void* maybe_load_property_ptr(bidirectionalS);
 
248
 
 
249
      Graph& m_g;
 
250
      Archive& m_ar;
 
251
      process_group_type m_pg;
 
252
 
 
253
      std::vector<process_id_type> m_id_mapping;
 
254
 
 
255
      // Maps local vertices as loaded from the archive to
 
256
      // the ones actually added to the graph. Only used 
 
257
      // when !vecS.
 
258
      std::map<local_vertex_descriptor, local_vertex_descriptor> m_local_vertices;
 
259
 
 
260
      // This is the list of remote vertex descriptors that we
 
261
      // are going to receive from other processes. This is
 
262
      // kept sorted so that we can determine the position of
 
263
      // the matching vertex descriptor in m_remote_vertices.
 
264
      std::vector<std::vector<serializable_vertex_descriptor> > m_requested_vertices;
 
265
 
 
266
      // This is the list of remote vertex descriptors that
 
267
      // we send and receive from other processes.
 
268
      std::vector<std::vector<serializable_vertex_descriptor> > m_remote_vertices;
 
269
 
 
270
      // ...
 
271
      std::vector<pending_edge_type> m_pending_edges;
 
272
 
 
273
      // The pending in-edges that will be added in the commit step, after
 
274
      // the remote vertex descriptors has been resolved. Only used
 
275
      // when bidirectionalS and !vecS.
 
276
      std::vector<pending_in_edge> m_pending_in_edges;
 
277
 
 
278
      std::vector<std::vector<unsafe_pair<void*,void*> > > m_property_ptrs;
 
279
  };
 
280
 
 
281
  template <class Graph, class Archive, class VertexListS>
 
282
  void graph_loader<Graph, Archive, VertexListS>::load_prefix()
 
283
  {
 
284
      typename process_group_type::process_size_type num_processes_;
 
285
      m_ar >> make_nvp("num_processes", num_processes_);
 
286
 
 
287
      if (num_processes_ != num_processes(m_pg))
 
288
          boost::throw_exception(std::runtime_error("number of processes mismatch"));
 
289
 
 
290
      process_id_type old_id;
 
291
      m_ar >> make_nvp("id", old_id);
 
292
 
 
293
      std::vector<typename Graph::distribution_type::size_type> mapping;
 
294
      m_ar >> make_nvp("mapping", mapping);
 
295
 
 
296
      // Fetch all the old id's from the other processes.
 
297
      std::vector<process_id_type> old_ids;
 
298
      all_gather(m_pg, &old_id, &old_id+1, old_ids);
 
299
 
 
300
      m_id_mapping.resize(num_processes(m_pg), -1);
 
301
 
 
302
      for (process_id_type i = 0; i < num_processes(m_pg); ++i)
 
303
      {
 
304
# ifdef PBGL_SERIALIZE_DEBUG
 
305
          if (is_root())
 
306
              std::cout << i << " used to be " << old_ids[i] << "\n"; 
 
307
# endif
 
308
          assert(m_id_mapping[old_ids[i]] == -1);
 
309
          m_id_mapping[old_ids[i]] = i;
 
310
      }
 
311
 
 
312
      std::vector<typename Graph::distribution_type::size_type> new_mapping(
 
313
          mapping.size());
 
314
 
 
315
      for (int i = 0; i < num_processes(m_pg); ++i)
 
316
      {
 
317
          new_mapping[mapping[old_ids[i]]] = i;
 
318
      }
 
319
 
 
320
      m_g.distribution().assign_mapping(
 
321
          new_mapping.begin(), new_mapping.end());
 
322
  }
 
323
 
 
324
  template <class Graph, class Archive, class VertexListS>
 
325
  void graph_loader<Graph, Archive, VertexListS>::load_vertices()
 
326
  {
 
327
      int V;
 
328
      m_ar >> BOOST_SERIALIZATION_NVP(V); 
 
329
 
 
330
# ifdef PBGL_SERIALIZE_DEBUG
 
331
      if (is_root())
 
332
          std::cout << "Loading vertices\n";
 
333
# endif
 
334
 
 
335
      for (int i = 0; i < V; ++i)
 
336
      {
 
337
          maybe_load_and_store_local_vertex(vertex_list_selector());
 
338
      }
 
339
  }
 
340
 
 
341
  template <class Graph, class Archive, class VertexListS>
 
342
  template <class Anything>
 
343
  void graph_loader<Graph, Archive, VertexListS>::maybe_load_and_store_local_vertex(Anything)
 
344
  {
 
345
      // Load the original vertex descriptor
 
346
      local_vertex_descriptor local;
 
347
      m_ar >> make_nvp("local", unsafe_serialize(local)); 
 
348
 
 
349
      // Load the properties
 
350
      vertex_property_type property;
 
351
      detail::parallel::maybe_load_properties(m_ar, "vertex_property",
 
352
                          property);
 
353
 
 
354
      // Add the vertex
 
355
      vertex_descriptor v(process_id(m_pg), add_vertex(property, m_g.base()));
 
356
 
 
357
      if (m_g.on_add_vertex)
 
358
        m_g.on_add_vertex(v, m_g);
 
359
 
 
360
      // Create the mapping from the "old" local descriptor to the new
 
361
      // local descriptor.
 
362
      m_local_vertices[local] = v.local;
 
363
  }
 
364
 
 
365
  template <class Graph, class Archive, class VertexListS>
 
366
  void graph_loader<Graph, Archive, VertexListS>::maybe_load_and_store_local_vertex(vecS)
 
367
  {
 
368
      // Load the properties
 
369
      vertex_property_type property;
 
370
      detail::parallel::maybe_load_properties(m_ar, "vertex_property",
 
371
                          property);
 
372
 
 
373
      // Add the vertex
 
374
      vertex_descriptor v(process_id(m_pg), 
 
375
                          add_vertex(m_g.build_vertex_property(property), 
 
376
                                     m_g.base()));
 
377
 
 
378
      if (m_g.on_add_vertex)
 
379
        m_g.on_add_vertex(v, m_g);
 
380
  }
 
381
 
 
382
  template <class Graph, class Archive, class VertexListS>
 
383
  void graph_loader<Graph, Archive, VertexListS>::load_edges()
 
384
  {
 
385
      int E;
 
386
      m_ar >> BOOST_SERIALIZATION_NVP(E);
 
387
 
 
388
# ifdef PBGL_SERIALIZE_DEBUG
 
389
      if (is_root())
 
390
          std::cout << "Loading edges\n";
 
391
# endif
 
392
 
 
393
      for (int i = 0; i < E; ++i)
 
394
      {
 
395
          local_vertex_descriptor local_src;
 
396
          process_id_type target_owner;
 
397
          local_vertex_descriptor local_tgt;
 
398
 
 
399
          m_ar >> make_nvp("source", unsafe_serialize(local_src)); 
 
400
          m_ar >> make_nvp("target_owner", target_owner); 
 
401
          m_ar >> make_nvp("target", unsafe_serialize(local_tgt)); 
 
402
 
 
403
          process_id_type new_src_owner = process_id(m_pg);
 
404
          process_id_type new_tgt_owner = m_id_mapping[target_owner];
 
405
 
 
406
          vertex_descriptor source(new_src_owner, local_src);
 
407
          vertex_descriptor target(new_tgt_owner, local_tgt);
 
408
 
 
409
          edge_property_type properties;
 
410
          detail::parallel::maybe_load_properties(m_ar, "edge_property", properties);
 
411
 
 
412
          void* property_ptr = maybe_load_property_ptr(directed_selector());
 
413
          add_edge(source, target, properties, property_ptr, vertex_list_selector());
 
414
      }
 
415
 
 
416
      load_in_edges(directed_selector());
 
417
      commit_pending_edges(vertex_list_selector());
 
418
  }
 
419
 
 
420
  template <class Graph, class Archive, class VertexListS>
 
421
  void graph_loader<Graph, Archive, VertexListS>::load_in_edges(bidirectionalS)
 
422
  {
 
423
      std::size_t I;
 
424
      m_ar >> BOOST_SERIALIZATION_NVP(I);
 
425
 
 
426
# ifdef PBGL_SERIALIZE_DEBUG
 
427
      if (is_root())
 
428
          std::cout << "Loading in-edges\n";
 
429
# endif
 
430
 
 
431
      for (int i = 0; i < I; ++i)
 
432
      {
 
433
          process_id_type src_owner;
 
434
          local_vertex_descriptor local_src;
 
435
          local_vertex_descriptor local_target;
 
436
          void* property_ptr;
 
437
 
 
438
          m_ar >> make_nvp("src_owner", src_owner);
 
439
          m_ar >> make_nvp("source", unsafe_serialize(local_src));
 
440
          m_ar >> make_nvp("target", unsafe_serialize(local_target));
 
441
          m_ar >> make_nvp("property_ptr", unsafe_serialize(property_ptr));
 
442
 
 
443
          src_owner = m_id_mapping[src_owner];
 
444
 
 
445
          vertex_descriptor u(src_owner, local_src);
 
446
          vertex_descriptor v(process_id(m_pg), local_target);
 
447
 
 
448
          add_pending_in_edge(u, v, property_ptr, vertex_list_selector());
 
449
      }
 
450
  }
 
451
 
 
452
  template <class Graph, class Archive, class VertexListS>
 
453
  void graph_loader<Graph, Archive, VertexListS>::load_in_edges(directedS)
 
454
  {}
 
455
 
 
456
  template <class Graph, class Archive, class VertexListS>
 
457
  void graph_loader<Graph, Archive, VertexListS>::add_pending_in_edge(
 
458
      vertex_descriptor u, vertex_descriptor v, void* property_ptr, vecS)
 
459
  {
 
460
      m_pending_in_edges.push_back(pending_in_edge(u,v,property_ptr));
 
461
  }
 
462
 
 
463
  template <class Graph, class Archive, class VertexListS>
 
464
  template <class Anything>
 
465
  void graph_loader<Graph, Archive, VertexListS>::add_pending_in_edge(
 
466
      vertex_descriptor u, vertex_descriptor v, void* property_ptr, Anything)
 
467
  {
 
468
      // u and v represent the out-edge here, meaning v is local
 
469
      // to us, and u is always remote.
 
470
      m_pending_in_edges.push_back(pending_in_edge(u,v,property_ptr));
 
471
      add_remote_vertex_request(v, u, bidirectionalS());
 
472
  }
 
473
 
 
474
  template <class Graph, class Archive, class VertexListS> 
 
475
  template <class Anything>
 
476
  void graph_loader<Graph, Archive, VertexListS>::add_edge(
 
477
      vertex_descriptor u, vertex_descriptor v
 
478
    , edge_property_type const& property, void* property_ptr, Anything)
 
479
  {
 
480
      m_pending_edges.push_back(pending_edge_type(u, v, property, property_ptr));
 
481
      add_remote_vertex_request(u, v, directed_selector());
 
482
  }
 
483
 
 
484
  template <class Graph, class Archive, class VertexListS> 
 
485
  void graph_loader<Graph, Archive, VertexListS>::add_remote_vertex_request(
 
486
      vertex_descriptor u, vertex_descriptor v, directedS)
 
487
  {
 
488
      // We have to request the remote vertex.
 
489
      m_requested_vertices[owner(v)].push_back(local(v));
 
490
  }
 
491
 
 
492
  template <class Graph, class Archive, class VertexListS>
 
493
  void graph_loader<Graph, Archive, VertexListS>::add_remote_vertex_request(
 
494
      vertex_descriptor u, vertex_descriptor v, bidirectionalS)
 
495
  {
 
496
      // If the edge spans to another process, we know
 
497
      // that that process has a matching in-edge, so
 
498
      // we can just send our vertex. No requests
 
499
      // necessary.
 
500
      if (owner(v) != m_g.processor())
 
501
      {
 
502
          m_remote_vertices[owner(v)].push_back(local(u));
 
503
          m_requested_vertices[owner(v)].push_back(local(v));
 
504
      }
 
505
  }
 
506
 
 
507
  template <class Graph, class Archive, class VertexListS>
 
508
  void graph_loader<Graph, Archive, VertexListS>::add_edge(
 
509
      vertex_descriptor u, vertex_descriptor v
 
510
    , edge_property_type const& property, void* property_ptr, vecS)
 
511
  {
 
512
      std::pair<local_edge_descriptor, bool> inserted = 
 
513
          detail::parallel::add_local_edge(
 
514
              local(u), local(v)
 
515
            , m_g.build_edge_property(property), m_g.base());
 
516
      assert(inserted.second);
 
517
      put(edge_target_processor_id, m_g.base(), inserted.first, owner(v));
 
518
 
 
519
      edge_descriptor e(owner(u), owner(v), true, inserted.first);
 
520
 
 
521
      if (inserted.second && m_g.on_add_edge)
 
522
        m_g.on_add_edge(e, m_g);
 
523
 
 
524
      add_in_edge(e, property_ptr, directed_selector());
 
525
  }
 
526
 
 
527
  template <class Graph, class Archive, class VertexListS>
 
528
  void graph_loader<Graph, Archive, VertexListS>::add_in_edge(
 
529
      edge_descriptor const&, void*, directedS)
 
530
  {}
 
531
 
 
532
  template <class Graph, class Archive, class VertexListS>
 
533
  void graph_loader<Graph, Archive, VertexListS>::add_in_edge(
 
534
      edge_descriptor const& edge, void* old_property_ptr, bidirectionalS)
 
535
  {
 
536
      if (owner(target(edge, m_g)) == m_g.processor())
 
537
      {
 
538
          detail::parallel::stored_in_edge<local_edge_descriptor>
 
539
              e(m_g.processor(), local(edge));
 
540
          boost::graph_detail::push(get(
 
541
              vertex_in_edges, m_g.base())[local(target(edge, m_g))], e);
 
542
      }
 
543
      else
 
544
      {
 
545
          // We send the (old,new) property pointer pair to
 
546
          // the remote process. This could be optimized to
 
547
          // only send the new one -- the ordering can be
 
548
          // made implicit because the old pointer value is
 
549
          // stored on the remote process.
 
550
          //
 
551
          // Doing that is a little bit more complicated, but
 
552
          // in case it turns out it's important we can do it.
 
553
          void* property_ptr = local(edge).get_property();
 
554
          m_property_ptrs[owner(target(edge, m_g))].push_back(
 
555
              unsafe_pair<void*,void*>(old_property_ptr, property_ptr));
 
556
      }
 
557
  }
 
558
 
 
559
  template <class Graph, class Archive, class VertexListS>
 
560
  void graph_loader<Graph, Archive, VertexListS>::resolve_property_ptrs()
 
561
  {
 
562
# ifdef PBGL_SERIALIZE_DEBUG
 
563
      if (is_root())
 
564
          std::cout << "Resolving property pointers\n";
 
565
# endif
 
566
 
 
567
      for (int i = 0; i < num_processes(m_pg); ++i)
 
568
      {
 
569
          std::sort(
 
570
              m_property_ptrs[i].begin(), m_property_ptrs[i].end());
 
571
      }
 
572
 
 
573
      boost::parallel::inplace_all_to_all(m_pg, m_property_ptrs);
 
574
  }
 
575
 
 
576
  template <class Graph, class Archive, class VertexListS>
 
577
  void graph_loader<Graph, Archive, VertexListS>::resolve_remote_vertices(directedS)
 
578
  {
 
579
      for (int i = 0; i < num_processes(m_pg); ++i)
 
580
      {
 
581
          std::sort(m_requested_vertices[i].begin(), m_requested_vertices[i].end());
 
582
      }
 
583
 
 
584
      boost::parallel::inplace_all_to_all(
 
585
          m_pg, m_requested_vertices, m_remote_vertices);
 
586
 
 
587
      for (int i = 0; i < num_processes(m_pg); ++i)
 
588
      {
 
589
          BOOST_FOREACH(serializable_vertex_descriptor& u, m_remote_vertices[i])
 
590
          {
 
591
              u = m_local_vertices[u];
 
592
          }
 
593
      }
 
594
 
 
595
      boost::parallel::inplace_all_to_all(m_pg, m_remote_vertices);
 
596
  }
 
597
 
 
598
  template <class Graph, class Archive, class VertexListS>
 
599
  void graph_loader<Graph, Archive, VertexListS>::resolve_remote_vertices(bidirectionalS)
 
600
  {
 
601
# ifdef PBGL_SERIALIZE_DEBUG
 
602
      if (is_root())
 
603
          std::cout << "Resolving remote vertices\n";
 
604
# endif
 
605
 
 
606
      for (int i = 0; i < num_processes(m_pg); ++i)
 
607
      {
 
608
          std::sort(m_requested_vertices[i].begin(), m_requested_vertices[i].end());
 
609
          std::sort(m_remote_vertices[i].begin(), m_remote_vertices[i].end());
 
610
 
 
611
          BOOST_FOREACH(serializable_vertex_descriptor& u, m_remote_vertices[i])
 
612
          {
 
613
              u = m_local_vertices[u];
 
614
          }
 
615
      }
 
616
 
 
617
      boost::parallel::inplace_all_to_all(m_pg, m_remote_vertices);
 
618
 
 
619
      for (int i = 0; i < num_processes(m_pg); ++i)
 
620
          assert(m_remote_vertices[i].size() == m_requested_vertices[i].size());
 
621
  }
 
622
 
 
623
  template <class Graph, class Archive, class VertexListS>
 
624
  void graph_loader<Graph, Archive, VertexListS>::commit_pending_edges(vecS)
 
625
  {
 
626
      commit_pending_in_edges(directed_selector());
 
627
  }
 
628
 
 
629
  template <class Graph, class Archive, class VertexListS>
 
630
  template <class Anything>
 
631
  void graph_loader<Graph, Archive, VertexListS>::commit_pending_edges(Anything)
 
632
  {
 
633
      resolve_remote_vertices(directed_selector());
 
634
 
 
635
      BOOST_FOREACH(pending_edge_type const& e, m_pending_edges)
 
636
      {
 
637
          vertex_descriptor u = resolve_remote_vertex(e.source);
 
638
          vertex_descriptor v = resolve_remote_vertex(e.target);
 
639
          add_edge(u, v, e.properties, e.property_ptr, vecS());
 
640
      }
 
641
 
 
642
      commit_pending_in_edges(directed_selector());
 
643
  }
 
644
 
 
645
  template <class Graph, class Archive, class VertexListS>
 
646
  void graph_loader<Graph, Archive, VertexListS>::commit_pending_in_edges(directedS)
 
647
  {}
 
648
 
 
649
  template <class Graph, class Archive, class VertexListS>
 
650
  void graph_loader<Graph, Archive, VertexListS>::commit_pending_in_edges(bidirectionalS)
 
651
  {
 
652
      resolve_property_ptrs();
 
653
 
 
654
      BOOST_FOREACH(pending_in_edge const& e, m_pending_in_edges)
 
655
      {
 
656
          vertex_descriptor u = resolve_remote_vertex(e.u, vertex_list_selector());
 
657
          vertex_descriptor v = resolve_remote_vertex(e.v, vertex_list_selector());
 
658
 
 
659
          typedef detail::parallel::stored_in_edge<local_edge_descriptor> stored_edge;
 
660
 
 
661
          std::vector<unsafe_pair<void*,void*> >::iterator i = std::lower_bound(
 
662
              m_property_ptrs[owner(u)].begin()
 
663
            , m_property_ptrs[owner(u)].end()
 
664
            , unsafe_pair<void*,void*>(e.property_ptr, 0)
 
665
          );
 
666
 
 
667
          if (i == m_property_ptrs[owner(u)].end()
 
668
              || i->first != e.property_ptr)
 
669
          {
 
670
              assert(false);
 
671
          }
 
672
 
 
673
          local_edge_descriptor local_edge(local(u), local(v), i->second);
 
674
          stored_edge edge(owner(u), local_edge);
 
675
          boost::graph_detail::push(
 
676
              get(vertex_in_edges, m_g.base())[local(v)], edge);
 
677
      }
 
678
  }
 
679
 
 
680
  template <class Graph, class Archive, class VertexListS>
 
681
  typename graph_loader<Graph, Archive, VertexListS>::vertex_descriptor 
 
682
  graph_loader<Graph, Archive, VertexListS>::resolve_remote_vertex(
 
683
      vertex_descriptor u) const
 
684
  {
 
685
      if (owner(u) == process_id(m_pg))
 
686
      { 
 
687
          return vertex_descriptor(
 
688
              process_id(m_pg), m_local_vertices.find(local(u))->second);
 
689
      }
 
690
 
 
691
      typename std::vector<serializable_vertex_descriptor>::const_iterator 
 
692
          i = std::lower_bound(
 
693
              m_requested_vertices[owner(u)].begin()
 
694
            , m_requested_vertices[owner(u)].end()
 
695
            , serializable_vertex_descriptor(local(u))
 
696
          );
 
697
 
 
698
      if (i == m_requested_vertices[owner(u)].end()
 
699
          || *i != local(u))
 
700
      {
 
701
          assert(false);
 
702
      }
 
703
 
 
704
      local_vertex_descriptor local =
 
705
          m_remote_vertices[owner(u)][m_requested_vertices[owner(u)].end() - i];
 
706
      return vertex_descriptor(owner(u), local);
 
707
  }
 
708
 
 
709
  template <class Graph, class Archive, class VertexListS>
 
710
  typename graph_loader<Graph, Archive, VertexListS>::vertex_descriptor 
 
711
  graph_loader<Graph, Archive, VertexListS>::resolve_remote_vertex(
 
712
      vertex_descriptor u, vecS) const
 
713
  {
 
714
      return u;
 
715
  }
 
716
 
 
717
  template <class Graph, class Archive, class VertexListS>
 
718
  template <class Anything>
 
719
  typename graph_loader<Graph, Archive, VertexListS>::vertex_descriptor 
 
720
  graph_loader<Graph, Archive, VertexListS>::resolve_remote_vertex(
 
721
      vertex_descriptor u, Anything) const
 
722
  {
 
723
      return resolve_remote_vertex(u);
 
724
  }
 
725
 
 
726
  template <class Graph, class Archive, class VertexListS>
 
727
  void* 
 
728
  graph_loader<Graph, Archive, VertexListS>::maybe_load_property_ptr(bidirectionalS)
 
729
  {
 
730
      void* ptr;
 
731
      m_ar >> make_nvp("property_ptr", unsafe_serialize(ptr));
 
732
      return ptr;
 
733
  }
 
734
 
 
735
template <class Archive, class D>
 
736
void maybe_save_local_descriptor(Archive& ar, D const&, vecS)
 
737
{}
 
738
 
 
739
template <class Archive, class D, class NotVecS>
 
740
void maybe_save_local_descriptor(Archive& ar, D const& d, NotVecS)
 
741
{
 
742
    ar << serialization::make_nvp(
 
743
        "local", unsafe_serialize(const_cast<D&>(d)));
 
744
}
 
745
 
 
746
template <class Archive>
 
747
void maybe_save_properties(
 
748
    Archive&, char const*, no_property const&)
 
749
{}
 
750
 
 
751
template <class Archive, class Tag, class T, class Base>
 
752
void maybe_save_properties(
 
753
    Archive& ar, char const* name, property<Tag, T, Base> const& properties)
 
754
{
 
755
    ar & serialization::make_nvp(name, get_property_value(properties, Tag()));
 
756
    maybe_save_properties(ar, name, static_cast<Base const&>(properties));
 
757
}
 
758
 
 
759
template <class Archive, class Graph>
 
760
void save_in_edges(Archive& ar, Graph const& g, directedS)
 
761
{}
 
762
 
 
763
// We need to save the edges in the base edge
 
764
// list, and the in_edges that are stored in the
 
765
// vertex_in_edges vertex property.
 
766
template <class Archive, class Graph>
 
767
void save_in_edges(Archive& ar, Graph const& g, bidirectionalS)
 
768
{
 
769
    typedef typename Graph::process_group_type
 
770
        process_group_type;
 
771
    typedef typename process_group_type::process_id_type
 
772
        process_id_type;
 
773
    typedef typename graph_traits<
 
774
        Graph>::vertex_descriptor vertex_descriptor;
 
775
    typedef typename vertex_descriptor::local_descriptor_type 
 
776
        local_vertex_descriptor;
 
777
    typedef typename graph_traits<
 
778
        Graph>::edge_descriptor edge_descriptor;
 
779
 
 
780
    process_id_type id = g.processor();
 
781
 
 
782
    typedef std::pair<local_vertex_descriptor, vertex_descriptor> in_edge;
 
783
    std::vector<edge_descriptor> saved_in_edges;
 
784
 
 
785
    BGL_FORALL_VERTICES_T(v, g, Graph) 
 
786
    {
 
787
        BOOST_FOREACH(edge_descriptor const& e, in_edges(v, g))
 
788
        {
 
789
            // Only save the in_edges that isn't owned by this process.
 
790
            if (owner(e) == id)
 
791
                continue;
 
792
 
 
793
            saved_in_edges.push_back(e);
 
794
        }
 
795
    }
 
796
 
 
797
    std::size_t I = saved_in_edges.size();
 
798
    ar << BOOST_SERIALIZATION_NVP(I);
 
799
 
 
800
    BOOST_FOREACH(edge_descriptor const& e, saved_in_edges)
 
801
    {
 
802
        process_id_type src_owner = owner(source(e,g));
 
803
        local_vertex_descriptor local_src = local(source(e,g));
 
804
        local_vertex_descriptor local_target = local(target(e,g));
 
805
        void* property_ptr = local(e).get_property();
 
806
 
 
807
        using serialization::make_nvp;
 
808
 
 
809
        ar << make_nvp("src_owner", src_owner);
 
810
        ar << make_nvp("source", unsafe_serialize(local_src));
 
811
        ar << make_nvp("target", unsafe_serialize(local_target));
 
812
        ar << make_nvp("property_ptr", unsafe_serialize(property_ptr));
 
813
    }
 
814
}
 
815
 
 
816
template <class Archive, class Edge>
 
817
void maybe_save_property_ptr(Archive&, Edge const&, directedS)
 
818
{}
 
819
 
 
820
template <class Archive, class Edge>
 
821
void maybe_save_property_ptr(Archive& ar, Edge const& e, bidirectionalS)
 
822
{
 
823
    void* ptr = local(e).get_property();
 
824
    ar << serialization::make_nvp("property_ptr", unsafe_serialize(ptr));
 
825
}
 
826
 
 
827
template <class Archive, class Graph, class DirectedS>
 
828
void save_edges(Archive& ar, Graph const& g, DirectedS)
 
829
{
 
830
    typedef typename Graph::process_group_type
 
831
        process_group_type;
 
832
    typedef typename process_group_type::process_id_type
 
833
        process_id_type;
 
834
    typedef typename graph_traits<
 
835
        Graph>::vertex_descriptor vertex_descriptor;
 
836
    typedef typename graph_traits<
 
837
        Graph>::edge_descriptor edge_descriptor;
 
838
 
 
839
    // We retag the property list here so that bundled properties are
 
840
    // properly placed into property<edge_bundle_t, Bundle>.
 
841
    typedef typename boost::detail::retag_property_list<
 
842
              edge_bundle_t,
 
843
              typename Graph::edge_property_type>::type
 
844
      edge_property_type;
 
845
 
 
846
    int E = num_edges(g);
 
847
    ar << BOOST_SERIALIZATION_NVP(E);
 
848
 
 
849
    // For *directed* graphs, we can just save
 
850
    // the edge list and be done.
 
851
    //
 
852
    // For *bidirectional* graphs, we need to also
 
853
    // save the "vertex_in_edges" property map,
 
854
    // because it might contain in-edges that
 
855
    // are not locally owned.
 
856
    BGL_FORALL_EDGES_T(e, g, Graph) 
 
857
    {
 
858
        vertex_descriptor src(source(e, g));
 
859
        vertex_descriptor tgt(target(e, g));
 
860
 
 
861
        typename vertex_descriptor::local_descriptor_type
 
862
            local_u(local(src));
 
863
        typename vertex_descriptor::local_descriptor_type
 
864
            local_v(local(tgt));
 
865
 
 
866
        process_id_type target_owner = owner(tgt);
 
867
 
 
868
        using serialization::make_nvp;
 
869
 
 
870
        ar << make_nvp("source", unsafe_serialize(local_u)); 
 
871
        ar << make_nvp("target_owner", target_owner); 
 
872
        ar << make_nvp("target", unsafe_serialize(local_v)); 
 
873
 
 
874
        maybe_save_properties(
 
875
            ar, "edge_property"
 
876
          , static_cast<edge_property_type const&>(get(edge_all_t(), g, e))
 
877
        );
 
878
 
 
879
        maybe_save_property_ptr(ar, e, DirectedS());
 
880
    }
 
881
 
 
882
    save_in_edges(ar, g, DirectedS());
 
883
}
 
884
 
 
885
}} // namespace detail::parallel
 
886
 
 
887
template <PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
 
888
template <class IStreamConstructibleArchive>
 
889
void PBGL_DISTRIB_ADJLIST_TYPE::load(std::string const& filename)
 
890
{
 
891
    typedef typename config_type::VertexListS vertex_list_selector;
 
892
 
 
893
    process_group_type pg = process_group();
 
894
    process_id_type id = process_id(pg);
 
895
 
 
896
    synchronize(pg);
 
897
 
 
898
    std::vector<int> disk_files = detail::parallel::available_process_files(filename);
 
899
    std::sort(disk_files.begin(), disk_files.end());
 
900
 
 
901
    // Negotiate which process gets which file. Serialized.
 
902
    std::vector<int> consumed_files;
 
903
    int picked_file = -1;
 
904
 
 
905
    if (id > 0)
 
906
        receive_oob(pg, id-1, 0, consumed_files);
 
907
 
 
908
    std::sort(consumed_files.begin(), consumed_files.end());
 
909
    std::vector<int> available_files;
 
910
    std::set_difference(
 
911
        disk_files.begin(), disk_files.end()
 
912
      , consumed_files.begin(), consumed_files.end()
 
913
      , std::back_inserter(available_files)
 
914
    );
 
915
 
 
916
    if (available_files.empty())
 
917
        boost::throw_exception(std::runtime_error("no file available"));
 
918
 
 
919
    // back() used for debug purposes. Making sure the
 
920
    // ranks are shuffled.
 
921
    picked_file = available_files.back();
 
922
 
 
923
# ifdef PBGL_SERIALIZE_DEBUG
 
924
    std::cout << id << " picked " << picked_file << "\n";
 
925
# endif
 
926
 
 
927
    consumed_files.push_back(picked_file);
 
928
 
 
929
    if (id < num_processes(pg) - 1)
 
930
        send_oob(pg, id+1, 0, consumed_files);
 
931
 
 
932
    std::string local_filename = filename + "/" + 
 
933
        lexical_cast<std::string>(picked_file);
 
934
 
 
935
    std::ifstream in(local_filename.c_str(), std::ios_base::binary);
 
936
    IStreamConstructibleArchive ar(in);
 
937
 
 
938
    detail::parallel::graph_loader<
 
939
        graph_type, IStreamConstructibleArchive, InVertexListS
 
940
    > loader(*this, ar);
 
941
 
 
942
# ifdef PBGL_SERIALIZE_DEBUG
 
943
    std::cout << "Process " << id << " done loading.\n";
 
944
# endif
 
945
 
 
946
    synchronize(pg);
 
947
}
 
948
 
 
949
template <PBGL_DISTRIB_ADJLIST_TEMPLATE_PARMS>
 
950
template <class OStreamConstructibleArchive>
 
951
void PBGL_DISTRIB_ADJLIST_TYPE::save(std::string const& filename) const
 
952
{
 
953
    // We retag the property list here so that bundled properties are
 
954
    // properly placed into property<vertex_bundle_t, Bundle>.
 
955
    typedef typename boost::detail::retag_property_list<
 
956
        vertex_bundle_t, vertex_property_type
 
957
    >::type vertex_property_type;
 
958
 
 
959
    typedef typename config_type::VertexListS vertex_list_selector;
 
960
 
 
961
    process_group_type pg = process_group();
 
962
    process_id_type id = process_id(pg);
 
963
 
 
964
    if (filesystem::exists(filename) && !filesystem::is_directory(filename))
 
965
        boost::throw_exception(std::runtime_error("entry exists, but is not a directory"));
 
966
 
 
967
    filesystem::remove_all(filename);
 
968
    filesystem::create_directory(filename);
 
969
 
 
970
    synchronize(pg);
 
971
 
 
972
    std::string local_filename = filename + "/" + 
 
973
        lexical_cast<std::string>(id);
 
974
 
 
975
    std::ofstream out(local_filename.c_str(), std::ios_base::binary);
 
976
    OStreamConstructibleArchive ar(out);
 
977
 
 
978
    using serialization::make_nvp;
 
979
 
 
980
    typename process_group_type::process_size_type num_processes_ = num_processes(pg);
 
981
    ar << make_nvp("num_processes", num_processes_);
 
982
    ar << BOOST_SERIALIZATION_NVP(id);
 
983
    ar << make_nvp("mapping", this->distribution().mapping());
 
984
 
 
985
    int V = num_vertices(*this);
 
986
    ar << BOOST_SERIALIZATION_NVP(V);
 
987
 
 
988
    BGL_FORALL_VERTICES_T(v, *this, graph_type)
 
989
    {
 
990
        local_vertex_descriptor local_descriptor(local(v));
 
991
        detail::parallel::maybe_save_local_descriptor(
 
992
            ar, local_descriptor, vertex_list_selector());
 
993
        detail::parallel::maybe_save_properties(
 
994
            ar, "vertex_property"
 
995
          , static_cast<vertex_property_type const&>(get(vertex_all_t(), *this, v))
 
996
        );
 
997
    }
 
998
 
 
999
    detail::parallel::save_edges(ar, *this, directed_selector());
 
1000
 
 
1001
    ar << make_nvp("distribution", this->distribution());
 
1002
}
 
1003
 
 
1004
} // namespace boost
 
1005
 
 
1006
#endif // BOOST_GRAPH_DISTRIBUTED_ADJLIST_SERIALIZATION_070925_HPP
 
1007