]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | .. Copyright (C) 2004-2008 The Trustees of Indiana University. |
2 | Use, modification and distribution is subject to the Boost Software | |
3 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
4 | http://www.boost.org/LICENSE_1_0.txt) | |
5 | ||
6 | =============================== | |
7 | |Logo| Distributed Property Map | |
8 | =============================== | |
9 | ||
10 | A distributed property map adaptor is a property map whose stored | |
11 | values are distributed across multiple non-overlapping memory spaces | |
12 | on different processes. Values local to the current process are stored | |
13 | within a local property map and may be immediately accessed via | |
14 | ``get`` and ``put``. Values stored on remote processes may also be | |
15 | accessed via ``get`` and ``put``, but the behavior differs slightly: | |
16 | ||
17 | - ``put`` operations update a local ghost cell and send a "put" | |
18 | message to the process that owns the value. The owner is free to | |
19 | update its own "official" value or may ignore the put request. | |
20 | ||
21 | - ``get`` operations returns the contents of the local ghost | |
22 | cell. If no ghost cell is available, one is created using a | |
23 | (customizable) default value. | |
24 | ||
25 | Using distributed property maps requires a bit more care than using | |
26 | local, sequential property maps. While the syntax and semantics are | |
27 | similar, distributed property maps may contain out-of-date | |
28 | information that can only be guaranteed to be synchronized by | |
29 | calling the ``synchronize`` function in all processes. | |
30 | ||
31 | To address the issue of out-of-date values, distributed property | |
32 | maps support multiple `consistency models`_ and may be supplied with a | |
33 | `reduction operation`_. | |
34 | ||
35 | Distributed property maps meet the requirements of the `Readable | |
36 | Property Map`_ and, potentially, the `Writable Property Map`_ and | |
37 | `Read/Write Property Map`_ concepts. Distributed property maps do | |
38 | *not*, however, meet the requirements of the `Lvalue Property Map`_ | |
39 | concept, because elements residing in another process are not | |
40 | directly addressible. There are several forms of distributed property | |
41 | maps: | |
42 | ||
43 | - `Distributed property map adaptor`_ | |
44 | - `Distributed iterator property map`_ | |
45 | - `Distributed safe iterator property map`_ | |
46 | - `Local property map`_ | |
47 | ||
48 | ------------------ | |
49 | Consistency models | |
50 | ------------------ | |
51 | ||
52 | Distributed property maps offer many consistency models, which affect | |
53 | how the values read from and written to remote keys relate to the | |
54 | "official" value for that key stored in the owning process. The | |
55 | consistency model of a distributed property map can be set with the | |
56 | member function ``set_consistency_model`` to a bitwise-OR of the | |
57 | flags in the ``boost::parallel::consistency_model`` enumeration. The | |
58 | individual flags are: | |
59 | ||
60 | - ``cm_forward``: The default consistency model, which propagates | |
61 | values forward from ``put`` operations on remote processors to | |
62 | the owner of the value being changed. | |
63 | ||
64 | - ``cm_backward``: After all values have been forwarded or flushed | |
65 | to the owning processes, each process receives updates values for | |
66 | each of its ghost cells. After synchronization, the values in | |
67 | ghost cells are guaranteed to match the values stored on the | |
68 | owning processor. | |
69 | ||
70 | - ``cm_bidirectional``: A combination of both ``cm_forward`` and | |
71 | ``cm_backward``. | |
72 | ||
73 | - ``cm_flush``: At the beginning of synchronization, all of the | |
74 | values stored locally in ghost cells are sent to their owning | |
75 | processors. | |
76 | ||
77 | - ``cm_reset``: Executes a ``reset()`` operation after | |
78 | synchronization, setting the values in each ghost cell to their | |
79 | default value. | |
80 | ||
81 | - ``cm_clear``: Executes a ``clear()`` operation after | |
82 | synchronizing, eliminating all ghost cells. | |
83 | ||
84 | ||
85 | There are several common combinations of flags that result in | |
86 | interesting consistency models. Some of these combinations are: | |
87 | ||
88 | - ``cm_forward``: By itself, the forward consistency model enables | |
89 | algorithms such as `Dijkstra's shortest paths`_ and | |
90 | `Breadth-First Search`_ to operate correctly. | |
91 | ||
92 | - ``cm_flush & cm_reset``: All updates values are queued locally, | |
93 | then flushed during the synchronization step. Once the flush has | |
94 | occurred, the ghost cells are restored to their default | |
95 | values. This consistency model is used by the PageRank_ | |
96 | implementation to locally accumulate rank for each node. | |
97 | ||
98 | ||
99 | ------------------- | |
100 | Reduction operation | |
101 | ------------------- | |
102 | ||
103 | The reduction operation maintains consistency by determining how | |
104 | multiple writes to a property map are resolved and what the property | |
105 | map should do if unknown values are requested. More specifically, a | |
106 | reduction operation is used in two cases: | |
107 | ||
108 | 1. When a value is needed for a remote key but no value is | |
109 | immediately available, the reduction operation provides a | |
110 | suitable default. For instance, a distributed property map | |
111 | storing distances may have a reduction operation that returns | |
112 | an infinite value as the default, whereas a distributed | |
113 | property map for vertex colors may return white as the | |
114 | default. | |
115 | ||
116 | 2. When a value is received from a remote process, the process | |
117 | owning the key associated with that value must determine which | |
118 | value---the locally stored value, the value received from a | |
119 | remote process, or some combination of the two---will be | |
120 | stored as the "official" value in the property map. The | |
121 | reduction operation transforms the local and remote values | |
122 | into the "official" value to be stored. | |
123 | ||
124 | The reduction operation of a distributed property map can be set with | |
125 | the ``set_reduce`` method of ``distributed_property_map``. The reduce | |
126 | operation is a function object with two signatures. The first | |
127 | signature takes a (remote) key and returns a default value for it, | |
128 | whereas the second signatures takes a key and two values (local first, | |
129 | then remote) and will return the combined value that will be stored in | |
130 | the local property map. Reduction operations must also contain a | |
131 | static constant ``non_default_resolver", which states whether the | |
132 | reduction operation's default value actually acts like a default | |
133 | value. It should be ``true`` when the default is meaningful (e.g., | |
134 | infinity for a distance) and ``false`` when the default should not be | |
135 | used. | |
136 | ||
137 | The following reduction operation is used by the distributed PageRank | |
138 | algorithm. The default rank for a remote node is 0. Rank is | |
139 | accumulated locally, and then the reduction operation combines local | |
140 | and remote values by adding them. Combined with a consistency model | |
141 | that flushes all values to the owner and then resets the values | |
142 | locally in each step, the resulting property map will compute partial | |
143 | sums on each processor and then accumulate the results on the owning | |
144 | processor. The PageRank reduction operation is defined as follows. | |
145 | ||
146 | :: | |
147 | ||
148 | template<typename T> | |
149 | struct rank_accumulate_reducer { | |
150 | static const bool non_default_resolver = true; | |
151 | ||
152 | // The default rank of an unknown node | |
153 | template<typename K> | |
154 | T operator()(const K&) const { return T(0); } | |
155 | ||
156 | template<typename K> | |
157 | T operator()(const K&, const T& x, const T& y) const { return x + y; } | |
158 | }; | |
159 | ||
160 | ||
161 | -------------------------------- | |
162 | Distributed property map adaptor | |
163 | -------------------------------- | |
164 | ||
165 | The distributed property map adaptor creates a distributed property | |
166 | map from a local property map, a `process group`_ over which | |
167 | distribution should occur, and a `global descriptor`_ type that | |
168 | indexes the distributed property map. | |
169 | ||
170 | ||
171 | Synopsis | |
172 | ~~~~~~~~ | |
173 | ||
174 | :: | |
175 | ||
176 | template<typename ProcessGroup, typename LocalPropertyMap, typename Key, | |
177 | typename GhostCellS = gc_mapS> | |
178 | class distributed_property_map | |
179 | { | |
180 | public: | |
181 | typedef ... ghost_regions_type; | |
182 | ||
183 | distributed_property_map(); | |
184 | ||
185 | distributed_property_map(const ProcessGroup& pg, | |
186 | const LocalPropertyMap& pm); | |
187 | ||
188 | template<typename Reduce> | |
189 | distributed_property_map(const ProcessGroup& pg, | |
190 | const LocalPropertyMap& pm, | |
191 | const Reduce& reduce); | |
192 | ||
193 | template<typename Reduce> void set_reduce(const Reduce& reduce); | |
194 | void set_consistency_model(int model); | |
195 | ||
196 | void flush(); | |
197 | void reset(); | |
198 | void clear(); | |
199 | }; | |
200 | ||
201 | reference get(distributed_property_map pm, const key_type& key); | |
202 | ||
203 | void | |
204 | put(distributed_property_map pm, const key_type& key, const value_type& value); | |
205 | local_put(distributed_property_map pm, const key_type& key, const value_type& value); | |
206 | ||
207 | void request(distributed_property_map pm, const key_type& key); | |
208 | ||
209 | void synchronize(distributed_property_map& pm); | |
210 | ||
211 | template<typename Key, typename ProcessGroup, typename LocalPropertyMap> | |
212 | distributed_property_map<ProcessGroup, LocalPropertyMap, Key> | |
213 | make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap); | |
214 | ||
215 | template<typename Key, typename ProcessGroup, typename LocalPropertyMap, | |
216 | typename Reduce> | |
217 | distributed_property_map<ProcessGroup, LocalPropertyMap, Key> | |
218 | make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap, | |
219 | Reduce reduce); | |
220 | ||
221 | Template parameters | |
222 | ~~~~~~~~~~~~~~~~~~~ | |
223 | ||
224 | **ProcessGroup**: | |
225 | The type of the process group over which the | |
226 | property map is distributed and is also the medium for | |
227 | communication. | |
228 | ||
229 | ||
230 | **LocalPropertyMap**: | |
231 | The type of the property map that will store values | |
232 | for keys local to this processor. The ``value_type`` of this | |
233 | property map will become the ``value_type`` of the distributed | |
234 | property map. The distributed property map models the same property | |
235 | map concepts as the ``LocalPropertyMap``, with one exception: a | |
236 | distributed property map cannot be an `Lvalue Property Map`_ | |
237 | (because remote values are not addressable), and is therefore | |
238 | limited to `Read/Write Property Map`_. | |
239 | ||
240 | ||
241 | **Key**: | |
242 | The ``key_type`` of the distributed property map, which | |
243 | must model the `Global Descriptor`_ concept. The process ID type of | |
244 | the ``Key`` parameter must match the process ID type of the | |
245 | ``ProcessGroup``, and the local descriptor type of the ``Key`` must | |
246 | be convertible to the ``key_type`` of the ``LocalPropertyMap``. | |
247 | ||
248 | ||
249 | **GhostCellS**: | |
250 | A selector type that indicates how ghost cells should be stored in | |
251 | the distributed property map. There are either two or three | |
252 | options, depending on your compiler: | |
253 | ||
254 | - ``boost::parallel::gc_mapS`` (default): Uses an STL ``map`` to | |
255 | store the ghost cells for each process. | |
256 | ||
257 | - ``boost::parallel::gc_vector_mapS``: Uses a sorted STL | |
258 | ``vector`` to store the ghost cells for each process. This | |
259 | option works well when there are likely to be few insertions | |
260 | into the ghost cells; for instance, if the only ghost cells used | |
261 | are for neighboring vertices, the property map can be | |
262 | initialized with cells for each neighboring vertex, providing | |
263 | faster lookups than a ``map`` and using less space. | |
264 | ||
265 | - ``boost::parallel::gc_hash_mapS``: Uses the GCC ``hash_map`` to | |
266 | store ghost cells. This option may improve performance over | |
267 | ``map`` for large problems sizes, where the set of ghost cells | |
268 | cannot be predetermined. | |
269 | ||
270 | ||
271 | Member functions | |
272 | ~~~~~~~~~~~~~~~~ | |
273 | ||
274 | :: | |
275 | ||
276 | distributed_property_map(); | |
277 | ||
278 | Default-construct a distributed property map. The property map is in | |
279 | an invalid state, and may only be used if it is reassigned to a valid | |
280 | property map. | |
281 | ||
282 | ------------------------------------------------------------------------------ | |
283 | ||
284 | :: | |
285 | ||
286 | distributed_property_map(const ProcessGroup& pg, | |
287 | const LocalPropertyMap& pm); | |
288 | ||
289 | template<typename Reduce> | |
290 | distributed_property_map(const ProcessGroup& pg, | |
291 | const LocalPropertyMap& pm, | |
292 | const Reduce& reduce); | |
293 | ||
294 | Construct a property map from a process group and a local property | |
295 | map. If a ``reduce`` operation is not supplied, a default of | |
296 | ``basic_reduce<value_type>`` will be used. | |
297 | ||
298 | ------------------------------------------------------------------------------ | |
299 | ||
300 | :: | |
301 | ||
302 | template<typename Reduce> void set_reduce(const Reduce& reduce); | |
303 | ||
304 | Replace the current reduction operation with the new operation | |
305 | ``reduce``. | |
306 | ||
307 | ------------------------------------------------------------------------------ | |
308 | ||
309 | :: | |
310 | ||
311 | void set_consistency_model(int model); | |
312 | ||
313 | Sets the consistency model of the distributed property map, which will | |
314 | take effect on the next synchronization step. See the section | |
315 | `Consistency models`_ for a description of the effect of various | |
316 | consistency model flags. | |
317 | ||
318 | ------------------------------------------------------------------------------ | |
319 | ||
320 | :: | |
321 | ||
322 | void flush(); | |
323 | ||
324 | Emits a message sending the contents of all local ghost cells to the | |
325 | owners of those cells. | |
326 | ||
327 | ------------------------------------------------------------------------------ | |
328 | ||
329 | :: | |
330 | ||
331 | void reset(); | |
332 | ||
333 | Replaces the values stored in each of the ghost cells with the default | |
334 | value generated by the reduction operation. | |
335 | ||
336 | ------------------------------------------------------------------------------ | |
337 | ||
338 | :: | |
339 | ||
340 | void clear(); | |
341 | ||
342 | Removes all ghost cells from the property map. | |
343 | ||
344 | ||
345 | Free functions | |
346 | ~~~~~~~~~~~~~~ | |
347 | ||
348 | :: | |
349 | ||
350 | reference get(distributed_property_map pm, const key_type& key); | |
351 | ||
352 | Retrieves the element in ``pm`` associated with the given ``key``. If | |
353 | the key refers to data stored locally, returns the actual value | |
354 | associated with the key. If the key refers to nonlocal data, returns | |
355 | the value of the ghost cell. If no ghost cell exists, the behavior | |
356 | depends on the current reduction operation: if a reduction operation | |
357 | has been set and has ``non_default_resolver`` set ``true``, then a | |
358 | ghost cell will be created according to the default value provided by | |
359 | the reduction operation. Otherwise, the call to ``get`` will abort | |
360 | because no value exists for this remote cell. To avoid this problem, | |
361 | either set a reduction operation that generates default values, | |
362 | ``request()`` the value and then perform a synchronization step, or | |
363 | ``put`` a value into the cell before reading it. | |
364 | ||
365 | ------------------------------------------------------------------------------ | |
366 | ||
367 | :: | |
368 | ||
369 | void | |
370 | put(distributed_property_map pm, const key_type& key, const value_type& value); | |
371 | ||
372 | Places the given ``value`` associated with ``key`` into property map | |
373 | ``pm``. If the key refers to data stored locally, the value is | |
374 | immediately updates. If the key refers to data stored in a remote | |
375 | process, updates (or creates) a local ghost cell containing this | |
376 | value for the key and sends the new value to the owning process. Note | |
377 | that the owning process may reject this value based on the reduction | |
378 | operation, but this will not be detected until the next | |
379 | synchronization step. | |
380 | ||
381 | ------------------------------------------------------------------------------ | |
382 | ||
383 | :: | |
384 | ||
385 | void | |
386 | local_put(distributed_property_map pm, const key_type& key, const value_type& value); | |
387 | ||
388 | Equivalent to ``put(pm, key, value)``, except that no message is sent | |
389 | to the owning process when the value is changed for a nonlocal key. | |
390 | ||
391 | ------------------------------------------------------------------------------ | |
392 | ||
393 | :: | |
394 | ||
395 | void synchronize(distributed_property_map& pm); | |
396 | ||
397 | Synchronize the values stored in the distributed property maps. Each | |
398 | process much execute ``synchronize`` at the same time, after which | |
399 | the ghost cells in every process will reflect the actual value stored | |
400 | in the owning process. | |
401 | ||
402 | ------------------------------------------------------------------------------ | |
403 | ||
404 | :: | |
405 | ||
406 | void request(distributed_property_map pm, const key_type& key); | |
407 | ||
408 | Request that the element "key" be available after the next | |
409 | synchronization step. For a non-local key, this means establishing a | |
410 | ghost cell and requesting. | |
411 | ||
412 | ------------------------------------------------------------------------------ | |
413 | ||
414 | :: | |
415 | ||
416 | template<typename Key, typename ProcessGroup, typename LocalPropertyMap> | |
417 | distributed_property_map<ProcessGroup, LocalPropertyMap, Key> | |
418 | make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap); | |
419 | ||
420 | template<typename Key, typename ProcessGroup, typename LocalPropertyMap, | |
421 | typename Reduce> | |
422 | distributed_property_map<ProcessGroup, LocalPropertyMap, Key> | |
423 | make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap, | |
424 | Reduce reduce); | |
425 | ||
426 | Create a distributed property map over process group ``pg`` and local | |
427 | property map ``pmap``. A default reduction operation will be generated | |
428 | if it is not provided. | |
429 | ||
430 | --------------------------------- | |
431 | Distributed iterator property map | |
432 | --------------------------------- | |
433 | ||
434 | The distributed iterator property map adaptor permits the creation of | |
435 | distributed property maps from random access iterators using the same | |
436 | syntax as non-distributed iterator property maps. The specialization | |
437 | is based on a `local property map`_, which contains the | |
438 | indices for local descriptors and is typically returned to describe | |
439 | the vertex indices of a distributed graph. | |
440 | ||
441 | Synopsis | |
442 | ~~~~~~~~ | |
443 | ||
444 | :: | |
445 | ||
446 | template<typename RandomAccessIterator, typename ProcessGroup, | |
447 | typename GlobalKey, typename LocalMap, typename ValueType, | |
448 | typename Reference> | |
449 | class iterator_property_map<RandomAccessIterator, | |
450 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
451 | ValueType, Reference> | |
452 | { | |
453 | public: | |
454 | typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type; | |
455 | ||
456 | iterator_property_map(); | |
457 | iterator_property_map(RandomAccessIterator iter, const index_map_type& id); | |
458 | }; | |
459 | ||
460 | reference get(iterator_property_map pm, const key_type& key); | |
461 | void put(iterator_property_map pm, const key_type& key, const value_type& value); | |
462 | ||
463 | template<typename RandomAccessIterator, typename ProcessGroup, | |
464 | typename GlobalKey, typename LocalMap> | |
465 | iterator_property_map<RandomAccessIterator, | |
466 | local_property_map<ProcessGroup, GlobalKey, LocalMap> > | |
467 | make_iterator_property_map(RandomAccessIterator iter, | |
468 | local_property_map<ProcessGroup, GlobalKey, LocalMap> id); | |
469 | ||
470 | ||
471 | Member functions | |
472 | ~~~~~~~~~~~~~~~~ | |
473 | ||
474 | :: | |
475 | ||
476 | iterator_property_map(); | |
477 | ||
478 | Default-constructs a distributed iterator property map. The property | |
479 | map is in an invalid state, and must be reassigned before it may be | |
480 | used. | |
481 | ||
482 | ------------------------------------------------------------------------------ | |
483 | ||
484 | :: | |
485 | ||
486 | iterator_property_map(RandomAccessIterator iter, const index_map_type& id); | |
487 | ||
488 | Constructs a distributed iterator property map using the property map | |
489 | ``id`` to map global descriptors to local indices. The random access | |
490 | iterator sequence ``[iter, iter + n)`` must be a valid range, where | |
491 | ``[0, n)`` is the range of local indices. | |
492 | ||
493 | Free functions | |
494 | ~~~~~~~~~~~~~~ | |
495 | ||
496 | :: | |
497 | ||
498 | reference get(iterator_property_map pm, const key_type& key); | |
499 | ||
500 | Returns the value associated with the given ``key`` from the | |
501 | distributed property map. | |
502 | ||
503 | ------------------------------------------------------------------------------ | |
504 | ||
505 | :: | |
506 | ||
507 | void put(iterator_property_map pm, const key_type& key, const value_type& value); | |
508 | ||
509 | Associates the value with the given key in the distributed property map. | |
510 | ||
511 | ------------------------------------------------------------------------------ | |
512 | ||
513 | :: | |
514 | ||
515 | template<typename RandomAccessIterator, typename ProcessGroup, | |
516 | typename GlobalKey, typename LocalMap, typename ValueType, | |
517 | typename Reference> | |
518 | iterator_property_map<RandomAccessIterator, | |
519 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
520 | ValueType, Reference> | |
521 | make_iterator_property_map(RandomAccessIterator iter, | |
522 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
523 | ValueType, Reference> id); | |
524 | ||
525 | Creates a distributed iterator property map using the given iterator | |
526 | ``iter`` and local index property map ``id``. | |
527 | ||
528 | -------------------------------------- | |
529 | Distributed safe iterator property map | |
530 | -------------------------------------- | |
531 | ||
532 | The distributed safe iterator property map adaptor permits the | |
533 | creation of distributed property maps from random access iterators | |
534 | using the same syntax as non-distributed safe iterator property | |
535 | maps. The specialization is based on a `local property map`_, which | |
536 | contains the indices for local descriptors and is typically returned | |
537 | to describe the vertex indices of a distributed graph. Safe iterator | |
538 | property maps check the indices of accesses to ensure that they are | |
539 | not out-of-bounds before attempting to access an value. | |
540 | ||
541 | Synopsis | |
542 | ~~~~~~~~ | |
543 | ||
544 | :: | |
545 | ||
546 | template<typename RandomAccessIterator, typename ProcessGroup, | |
547 | typename GlobalKey, typename LocalMap, typename ValueType, | |
548 | typename Reference> | |
549 | class safe_iterator_property_map<RandomAccessIterator, | |
550 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
551 | ValueType, Reference> | |
552 | { | |
553 | public: | |
554 | typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type; | |
555 | ||
556 | safe_iterator_property_map(); | |
557 | safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, | |
558 | const index_map_type& id); | |
559 | }; | |
560 | ||
561 | reference get(safe_iterator_property_map pm, const key_type& key); | |
562 | void put(safe_iterator_property_map pm, const key_type& key, const value_type& value); | |
563 | ||
564 | template<typename RandomAccessIterator, typename ProcessGroup, | |
565 | typename GlobalKey, typename LocalMap, typename ValueType, | |
566 | typename Reference> | |
567 | safe_iterator_property_map<RandomAccessIterator, | |
568 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
569 | ValueType, Reference> | |
570 | make_safe_iterator_property_map(RandomAccessIterator iter, | |
571 | std::size_t n, | |
572 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
573 | ValueType, Reference> id); | |
574 | ||
575 | Member functions | |
576 | ~~~~~~~~~~~~~~~~ | |
577 | ||
578 | :: | |
579 | ||
580 | safe_iterator_property_map(); | |
581 | ||
582 | Default-constructs a distributed safe iterator property map. The property | |
583 | map is in an invalid state, and must be reassigned before it may be | |
584 | used. | |
585 | ||
586 | ------------------------------------------------------------------------------ | |
587 | ||
588 | :: | |
589 | ||
590 | safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, | |
591 | const index_map_type& id); | |
592 | ||
593 | Constructs a distributed safe iterator property map using the property map | |
594 | ``id`` to map global descriptors to local indices. The random access | |
595 | iterator sequence ``[iter, iter + n)``. | |
596 | ||
597 | Free functions | |
598 | ~~~~~~~~~~~~~~ | |
599 | ||
600 | :: | |
601 | ||
602 | reference get(safe_iterator_property_map pm, const key_type& key); | |
603 | ||
604 | Returns the value associated with the given ``key`` from the | |
605 | distributed property map. | |
606 | ||
607 | ------------------------------------------------------------------------------ | |
608 | ||
609 | :: | |
610 | ||
611 | void put(safe_iterator_property_map pm, const key_type& key, const value_type& value); | |
612 | ||
613 | Associates the value with the given key in the distributed property map. | |
614 | ||
615 | ------------------------------------------------------------------------------ | |
616 | ||
617 | :: | |
618 | ||
619 | template<typename RandomAccessIterator, typename ProcessGroup, | |
620 | typename GlobalKey, typename LocalMap, typename ValueType, | |
621 | typename Reference> | |
622 | safe_iterator_property_map<RandomAccessIterator, | |
623 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
624 | ValueType, Reference> | |
625 | make_safe_iterator_property_map(RandomAccessIterator iter, | |
626 | std::size_t n, | |
627 | local_property_map<ProcessGroup, GlobalKey, LocalMap>, | |
628 | ValueType, Reference> id); | |
629 | ||
630 | Creates a distributed safe iterator property map using the given iterator | |
631 | ``iter`` and local index property map ``id``. The indices in ``id`` must | |
632 | ||
633 | ------------------ | |
634 | Local property map | |
635 | ------------------ | |
636 | ||
637 | A property map adaptor that accesses an underlying property map whose | |
638 | key type is the local part of the ``Key`` type for the local subset | |
639 | of keys. Local property maps are typically used by distributed graph | |
640 | types for vertex index properties. | |
641 | ||
642 | Synopsis | |
643 | ~~~~~~~~ | |
644 | ||
645 | :: | |
646 | ||
647 | template<typename ProcessGroup, typename GlobalKey, typename LocalMap> | |
648 | class local_property_map | |
649 | { | |
650 | public: | |
651 | typedef typename property_traits<LocalMap>::value_type value_type; | |
652 | typedef GlobalKey key_type; | |
653 | typedef typename property_traits<LocalMap>::reference reference; | |
654 | typedef typename property_traits<LocalMap>::category category; | |
655 | ||
656 | explicit | |
657 | local_property_map(const ProcessGroup& process_group = ProcessGroup(), | |
658 | const LocalMap& local_map = LocalMap()); | |
659 | ||
660 | reference operator[](const key_type& key); | |
661 | }; | |
662 | ||
663 | reference get(const local_property_map& pm, key_type key); | |
664 | void put(local_property_map pm, const key_type& key, const value_type& value); | |
665 | ||
666 | Template parameters | |
667 | ~~~~~~~~~~~~~~~~~~~ | |
668 | ||
669 | :ProcessGroup: the type of the process group over which the global | |
670 | keys are distributed. | |
671 | ||
672 | :GlobalKey: The ``key_type`` of the local property map, which | |
673 | must model the `Global Descriptor`_ concept. The process ID type of | |
674 | the ``GlobalKey`` parameter must match the process ID type of the | |
675 | ``ProcessGroup``, and the local descriptor type of the ``GlobalKey`` | |
676 | must be convertible to the ``key_type`` of the ``LocalMap``. | |
677 | ||
678 | :LocalMap: the type of the property map that will store values | |
679 | for keys local to this processor. The ``value_type`` of this | |
680 | property map will become the ``value_type`` of the local | |
681 | property map. The local property map models the same property | |
682 | map concepts as the ``LocalMap``. | |
683 | ||
684 | Member functions | |
685 | ~~~~~~~~~~~~~~~~ | |
686 | ||
687 | :: | |
688 | ||
689 | explicit | |
690 | local_property_map(const ProcessGroup& process_group = ProcessGroup(), | |
691 | const LocalMap& local_map = LocalMap()); | |
692 | ||
693 | Constructs a local property map whose keys are distributed across the | |
694 | given process group and which accesses the given local map. | |
695 | ||
696 | ------------------------------------------------------------------------------ | |
697 | ||
698 | :: | |
699 | ||
700 | reference operator[](const key_type& key); | |
701 | ||
702 | Access the value associated with the given key, which must be local | |
703 | to this process. | |
704 | ||
705 | Free functions | |
706 | ~~~~~~~~~~~~~~ | |
707 | ||
708 | :: | |
709 | ||
710 | reference get(const local_property_map& pm, key_type key); | |
711 | ||
712 | Return the value associated with the given key, which must be local | |
713 | to this process. | |
714 | ||
715 | ------------------------------------------------------------------------------ | |
716 | ||
717 | :: | |
718 | ||
719 | void put(local_property_map pm, const key_type& key, const value_type& value); | |
720 | ||
721 | Set the value associated with the given key, which must be local to | |
722 | this process. | |
723 | ||
724 | ----------------------------------------------------------------------------- | |
725 | ||
726 | Copyright (C) 2004, 2005 The Trustees of Indiana University. | |
727 | ||
728 | Authors: Douglas Gregor and Andrew Lumsdaine | |
729 | ||
730 | .. |Logo| image:: pbgl-logo.png | |
731 | :align: middle | |
732 | :alt: Parallel BGL | |
733 | :target: http://www.osl.iu.edu/research/pbgl | |
734 | ||
735 | .. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html | |
736 | .. _Writable Property Map: http://www.boost.org/libs/property_map/WritablePropertyMap.html | |
737 | .. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html | |
738 | .. _Lvalue Property Map: http://www.boost.org/libs/property_map/LvaluePropertyMap.html | |
739 | .. _Process Group: process_group.html | |
740 | .. _Global Descriptor: GlobalDescriptor.html | |
741 | .. _Dijkstra's shortest paths: dijkstra_shortest_paths.html | |
742 | .. _Breadth-First Search: breadth_first_search.html | |
743 | .. _PageRank: page_rank.html | |
744 |