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