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 Adjacency List</title> 8<link rel="stylesheet" href="../../../../rst.css" type="text/css" /> 9</head> 10<body> 11<div class="document" id="logo-distributed-adjacency-list"> 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 Adjacency List</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<div class="contents topic" id="contents"> 19<p class="topic-title first">Contents</p> 20<ul class="simple"> 21<li><a class="reference internal" href="#introduction" id="id1">Introduction</a><ul> 22<li><a class="reference internal" href="#defining-a-distributed-adjacency-list" id="id2">Defining a Distributed Adjacency List</a></li> 23<li><a class="reference internal" href="#distributed-vertex-and-edge-properties" id="id3">Distributed Vertex and Edge Properties</a></li> 24<li><a class="reference internal" href="#named-vertices" id="id4">Named Vertices</a></li> 25<li><a class="reference internal" href="#building-a-distributed-graph" id="id5">Building a Distributed Graph</a></li> 26<li><a class="reference internal" href="#graph-concepts" id="id6">Graph Concepts</a></li> 27</ul> 28</li> 29<li><a class="reference internal" href="#reference" id="id7">Reference</a><ul> 30<li><a class="reference internal" href="#where-defined" id="id8">Where Defined</a></li> 31<li><a class="reference internal" href="#associated-types" id="id9">Associated Types</a></li> 32<li><a class="reference internal" href="#member-functions" id="id10">Member Functions</a></li> 33<li><a class="reference internal" href="#non-member-functions" id="id11">Non-Member Functions</a></li> 34<li><a class="reference internal" href="#structure-modification" id="id12">Structure Modification</a></li> 35<li><a class="reference internal" href="#property-map-accessors" id="id13">Property Map Accessors</a></li> 36</ul> 37</li> 38</ul> 39</div> 40<div class="section" id="introduction"> 41<h1><a class="toc-backref" href="#id1">Introduction</a></h1> 42<p>The distributed adjacency list implements a graph data structure using 43an adjacency list representation. Its interface and behavior are 44roughly equivalent to the Boost Graph Library's <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a> 45class template. However, the distributed adjacency list partitions the 46vertices of the graph across several processes (which need not share 47an address space). Edges outgoing from any vertex stored by a process 48are also stored on that process, except in the case of undirected 49graphs, where either the source or the target may store the edge.</p> 50<pre class="literal-block"> 51template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS, 52 typename DirectedS, typename VertexProperty, typename EdgeProperty, 53 typename GraphProperty, typename EdgeListS> 54class adjacency_list<OutEdgeListS, 55 distributedS<ProcessGroup, VertexListS>, 56 DirectedS, VertexProperty, 57 EdgeProperty, GraphProperty, EdgeListS>; 58</pre> 59<div class="section" id="defining-a-distributed-adjacency-list"> 60<h2><a class="toc-backref" href="#id2">Defining a Distributed Adjacency List</a></h2> 61<p>To create a distributed adjacency list, first determine the 62representation of the graph in a single address space using these 63<a class="reference external" href="http://www.boost.org/libs/graph/doc/using_adjacency_list.html">guidelines</a>. Next, replace the vertex list selector (<tt class="docutils literal"><span class="pre">VertexListS</span></tt>) 64with an instantiation of <a class="reference external" href="distributedS.html">distributedS</a>, which includes:</p> 65<ul class="simple"> 66<li>Selecting a <a class="reference external" href="process_group.html">process group</a> type that represents the various 67coordinating processes that will store the distributed graph. For 68example, the <a class="reference external" href="process_group.html">MPI process group</a>.</li> 69<li>A selector indicating how the vertex lists in each process will be 70stored. Only the <tt class="docutils literal"><span class="pre">vecS</span></tt> and <tt class="docutils literal"><span class="pre">listS</span></tt> selectors are well-supported 71at this time.</li> 72</ul> 73<p>The following <tt class="docutils literal"><span class="pre">typedef</span></tt> defines a distributed adjacency list 74containing directed edges. The vertices in the graph will be 75distributed over several processes, using the MPI process group 76for communication. In each process, the vertices and outgoing edges 77will be stored in STL vectors. There are no properties attached to the 78vertices or edges of the graph.</p> 79<pre class="literal-block"> 80using namespace boost; 81typedef adjacency_list<vecS, 82 distributedS<parallel::mpi::bsp_process_group, vecS>, 83 directedS> 84 Graph; 85</pre> 86</div> 87<div class="section" id="distributed-vertex-and-edge-properties"> 88<h2><a class="toc-backref" href="#id3">Distributed Vertex and Edge Properties</a></h2> 89<p>Vertex and edge properties for distributed graphs mirror their 90counterparts for non-distributed graphs. With a distributed graph, 91however, vertex and edge properties are stored only in the process 92that owns the vertex or edge.</p> 93<p>The most direct way to attach properties to a distributed graph is to 94create a structure that will be attached to each of the vertices and 95edges of the graph. For example, if we wish to model a simplistic map 96of the United States interstate highway system, we might state that 97the vertices of the graph are cities and the edges are highways, then 98define the information that we maintain for each city and highway:</p> 99<pre class="literal-block"> 100struct City { 101 City() { } 102 City(const std::string& name, const std::string& mayor = "Unknown", int population = 0) 103 : name(name), mayor(mayor), population(population) { } 104 105 std::string name; 106 std::string mayor; 107 int population; 108 109 // Serialization support is required! 110 template<typename Archiver> 111 void serialize(Archiver& ar, const unsigned int /*version*/) { 112 ar & name & mayor & population; 113 } 114}; 115 116struct Highway { 117 Highway() { } 118 Highway(const std::string& name, int lanes, int miles_per_hour, int length) 119 : name(name), lanes(lanes), miles_per_hour(miles_per_hour), length(length) { } 120 121 std::string name; 122 int lanes; 123 int miles_per_hour; 124 int length; 125 126 // Serialization support is required! 127 template<typename Archiver> 128 void serialize(Archiver& ar, const unsigned int /*version*/) { 129 ar & name & lanes & miles_per_hour & length; 130 } 131}; 132</pre> 133<p>To create a distributed graph for a road map, we supply <tt class="docutils literal"><span class="pre">City</span></tt> and 134<tt class="docutils literal"><span class="pre">Highway</span></tt> as the fourth and fifth parameters to <tt class="docutils literal"><span class="pre">adjacency_list</span></tt>, 135respectively:</p> 136<pre class="literal-block"> 137typedef adjacency_list<vecS, 138 distributedS<parallel::mpi::bsp_process_group, vecS>, 139 directedS, 140 City, Highway> 141 RoadMap; 142</pre> 143<p>Property maps for internal properties retain their behavior with 144distributed graphs via <a class="reference external" href="distributed_property_map.html">distributed property maps</a>, which automate 145communication among processes so that <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations 146may be applied to non-local vertices and edges. However, for 147distributed adjacency lists that store vertices in a vector 148(<tt class="docutils literal"><span class="pre">VertexListS</span></tt> is <tt class="docutils literal"><span class="pre">vecS</span></tt>), the automatic <tt class="docutils literal"><span class="pre">vertex_index</span></tt> 149property map restricts the domain of <tt class="docutils literal"><span class="pre">put</span></tt> and <tt class="docutils literal"><span class="pre">get</span></tt> operations 150to vertices local to the process executing the operation. For example, 151we can create a property map that accesses the length of each highway 152as follows:</p> 153<pre class="literal-block"> 154RoadMap map; // distributed graph instance 155 156typedef property_map<RoadMap, int Highway::*>::type 157 road_length = get(&Highway::length, map); 158</pre> 159<p>Now, one can access the length of any given road based on its edge 160descriptor <tt class="docutils literal"><span class="pre">e</span></tt> with the expression <tt class="docutils literal"><span class="pre">get(road_length,</span> <span class="pre">e)</span></tt>, 161regardless of which process stores the edge <tt class="docutils literal"><span class="pre">e</span></tt>.</p> 162</div> 163<div class="section" id="named-vertices"> 164<h2><a class="toc-backref" href="#id4">Named Vertices</a></h2> 165<p>The vertices of a graph typically correspond to named entities within 166the application domain. In the road map example from the previous 167section, the vertices in the graph represent cities. The distributed 168adjacency list supports named vertices, which provides an implicit 169mapping from the names of the vertices in the application domain 170(e.g., the name of a city, such as "Bloomington") to the actual vertex 171descriptor stored within the distributed graph (e.g., the third vertex 172on processor 1). By enabling support for named vertices, one can refer 173to vertices by name when manipulating the graph. For example, one can 174add a highway from Indianapolis to Chicago:</p> 175<pre class="literal-block"> 176add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map); 177</pre> 178<p>The distributed adjacency list will find vertices associated with the 179names "Indianapolis" and "Chicago", then add an edge between these 180vertices that represents I-65. The vertices may be stored on any 181processor, local or remote.</p> 182<p>To enable named vertices, specialize the <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt> 183property for the structure attached to the vertices in your 184graph. <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt> contains a single member, <tt class="docutils literal"><span class="pre">type</span></tt>, 185which is the type of a function object that accepts a vertex property 186and returns the name stored within that vertex property. In the case 187of our road map, the <tt class="docutils literal"><span class="pre">name</span></tt> field contains the name of each city, so 188we use the <tt class="docutils literal"><span class="pre">member</span></tt> function object from the <a class="reference external" href="http://www.boost.org/libs/multi_index/doc/index.html">Boost.MultiIndex</a> 189library to extract the name, e.g.,</p> 190<pre class="literal-block"> 191namespace boost { namespace graph { 192 193template<> 194struct internal_vertex_name<City> 195{ 196 typedef multi_index::member<City, std::string, &City::name> type; 197}; 198 199} } 200</pre> 201<p>That's it! One can now refer to vertices by name when interacting with 202the distributed adjacency list.</p> 203<p>What happens when one uses the name of a vertex that does not exist? 204For example, in our <tt class="docutils literal"><span class="pre">add_edge</span></tt> call above, what happens if the 205vertex named "Indianapolis" has not yet been added to the graph? By 206default, the distributed adjacency list will throw an exception if a 207named vertex does not yet exist. However, one can customize this 208behavior by specifying a function object that constructs an instance 209of the vertex property (e.g., <tt class="docutils literal"><span class="pre">City</span></tt>) from just the name of the 210vertex. This customization occurs via the 211<tt class="docutils literal"><span class="pre">internal_vertex_constructor</span></tt> trait. For example, using the 212<tt class="docutils literal"><span class="pre">vertex_from_name</span></tt> template (provided with the Parallel BGL), we can 213state that a <tt class="docutils literal"><span class="pre">City</span></tt> can be constructed directly from the name of the 214city using its second constructor:</p> 215<pre class="literal-block"> 216namespace boost { namespace graph { 217 218template<> 219struct internal_vertex_constructor<City> 220{ 221 typedef vertex_from_name<City> type; 222}; 223 224} } 225</pre> 226<p>Now, one can add edges by vertex name freely, without worrying about 227the explicit addition of vertices. The <tt class="docutils literal"><span class="pre">mayor</span></tt> and <tt class="docutils literal"><span class="pre">population</span></tt> 228fields will have default values, but the graph structure will be 229correct.</p> 230</div> 231<div class="section" id="building-a-distributed-graph"> 232<h2><a class="toc-backref" href="#id5">Building a Distributed Graph</a></h2> 233<p>Once you have determined the layout of your graph type, including the 234specific data structures and properties, it is time to construct an 235instance of the graph by adding the appropriate vertices and 236edges. Construction of distributed graphs can be slightly more 237complicated than construction of normal, non-distributed graph data 238structures, because one must account for both the distribution of the 239vertices and edges and the multiple processes executing 240concurrently. There are three main ways to construct distributed 241graphs:</p> 242<p>1. <em>Sequence constructors</em>: if your data can easily be generated by a 243pair of iterators that produce (source, target) pairs, you can use the 244sequence constructors to build the distributed graph in parallel. This 245method is often preferred when creating benchmarks, because random 246graph generators like the <a class="reference external" href="http://www.boost.org/libs/graph/doc/sorted_erdos_renyi_gen.html">sorted_erdos_renyi_iterator</a> create the 247appropriate input sequence. Note that one must provide the same input 248iterator sequence on all processes. This method has the advantage that 249the sequential graph-building code is identical to the parallel 250graph-building code. An example constructing a random graph this way:</p> 251<blockquote> 252<pre class="literal-block"> 253typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter; 254boost::minstd_rand gen; 255unsigned long n = 1000000; // 1M vertices 256Graph g(ERIter(gen, n, 0.00005), ERIter(), n); 257</pre> 258</blockquote> 259<p>2. <em>Adding edges by vertex number</em>: if you are able to map your 260vertices into values in the random [0, <em>n</em>), where <em>n</em> is the number 261of vertices in the distributed graph. Use this method rather than the 262sequence constructors when your algorithm cannot easily be moved into 263input iterators, or if you can't replicate the input sequence. For 264example, you might be reading the graph from an input file:</p> 265<blockquote> 266<pre class="literal-block"> 267Graph g(n); // initialize with the total number of vertices, n 268if (process_id(g.process_group()) == 0) { 269 // Only process 0 loads the graph, which is distributed automatically 270 int source, target; 271 for (std::cin >> source >> target) 272 add_edge(vertex(source, g), vertex(target, g), g); 273} 274 275// All processes synchronize at this point, then the graph is complete 276synchronize(g.process_group()); 277</pre> 278</blockquote> 279<p>3. <em>Adding edges by name</em>: if you are using named vertices, you can 280construct your graph just by calling <tt class="docutils literal"><span class="pre">add_edge</span></tt> with the names of 281the source and target vertices. Be careful to make sure that each edge 282is added by only one process (it doesn't matter which process it is), 283otherwise you will end up with multiple edges. For example, in the 284following program we read edges from the standard input of process 0, 285adding those edges by name. Vertices and edges will be created and 286distributed automatically.</p> 287<blockquote> 288<pre class="literal-block"> 289Graph g; 290if (process_id(g.process_group()) == 0) { 291 // Only process 0 loads the graph, which is distributed automatically 292 std:string source, target; 293 for(std::cin >> source >> target) 294 add_edge(source, target, g); 295} 296 297// All processes synchronize at this point, then the graph is complete 298synchronize(g.process_group()); 299</pre> 300</blockquote> 301</div> 302<div class="section" id="graph-concepts"> 303<h2><a class="toc-backref" href="#id6">Graph Concepts</a></h2> 304<p>The distributed adjacency list models the <a class="reference external" href="http://www.boost.org/libs/graph/doc/Graph.html">Graph</a> concept, and in 305particular the <a class="reference external" href="DistributedGraph.html">Distributed Graph</a> concept. It also models the 306<a class="reference external" href="http://www.boost.org/libs/graph/doc/IncidenceGraph.html">Incidence Graph</a> and <a class="reference external" href="http://www.boost.org/libs/graph/doc/AdjacencyGraph.html">Adjacency Graph</a> concept, but restricts the 307input domain of the operations to correspond to local vertices 308only. For instance, a process may only access the outgoing edges of a 309vertex if that vertex is stored in that process. Undirected and 310bidirectional distributed adjacency lists model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional 311Graph</a> concept, with the same domain restrictions. Distributed 312adjacency lists also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutableGraph.html">Mutable Graph</a> concept (with domain 313restrictions; see the <a class="reference internal" href="#reference">Reference</a> section), <a class="reference external" href="http://www.boost.org/libs/graph/doc/PropertyGraph.html">Property Graph</a> concept, 314and <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutablePropertyGraph.html">Mutable Property Graph</a> concept.</p> 315<p>Unlike its non-distributed counterpart, the distributed adjacency 316list does <strong>not</strong> model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/VertexListGraph.html">Vertex List Graph</a> or <a class="reference external" href="http://www.boost.org/libs/graph/doc/EdgeListGraph.html">Edge List 317Graph</a> concepts, because one cannot enumerate all vertices or edges 318within a distributed graph. Instead, it models the weaker 319<a class="reference external" href="DistributedVertexListGraph.html">Distributed Vertex List Graph</a> and <a class="reference external" href="DistributedEdgeListGraph.html">Distributed Edge List Graph</a> 320concepts, which permit access to the local edges and vertices on each 321processor. Note that if all processes within the process group over 322which the graph is distributed iterator over their respective vertex 323or edge lists, all vertices and edges will be covered once.</p> 324</div> 325</div> 326<div class="section" id="reference"> 327<h1><a class="toc-backref" href="#id7">Reference</a></h1> 328<p>Since the distributed adjacency list closely follows the 329non-distributed <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>, this reference documentation 330only describes where the two implementations differ.</p> 331<div class="section" id="where-defined"> 332<h2><a class="toc-backref" href="#id8">Where Defined</a></h2> 333<p><boost/graph/distributed/adjacency_list.hpp></p> 334</div> 335<div class="section" id="associated-types"> 336<h2><a class="toc-backref" href="#id9">Associated Types</a></h2> 337<pre class="literal-block"> 338adjacency_list::process_group_type 339</pre> 340<p>The type of the process group over which the graph will be 341distributed.</p> 342<hr class="docutils" /> 343<blockquote> 344adjacency_list::distribution_type</blockquote> 345<p>The type of distribution used to partition vertices in the graph.</p> 346<hr class="docutils" /> 347<blockquote> 348adjacency_list::vertex_name_type</blockquote> 349<p>If the graph supports named vertices, this is the type used to name 350vertices. Otherwise, this type is not present within the distributed 351adjacency list.</p> 352</div> 353<div class="section" id="member-functions"> 354<h2><a class="toc-backref" href="#id10">Member Functions</a></h2> 355<pre class="literal-block"> 356adjacency_list(const ProcessGroup& pg = ProcessGroup()); 357 358adjacency_list(const GraphProperty& g, 359 const ProcessGroup& pg = ProcessGroup()); 360</pre> 361<p>Construct an empty distributed adjacency list with the given process 362group (or default) and graph property (or default).</p> 363<hr class="docutils" /> 364<pre class="literal-block"> 365adjacency_list(vertices_size_type n, const GraphProperty& p, 366 const ProcessGroup& pg, const Distribution& distribution); 367 368adjacency_list(vertices_size_type n, const ProcessGroup& pg, 369 const Distribution& distribution); 370 371adjacency_list(vertices_size_type n, const GraphProperty& p, 372 const ProcessGroup& pg = ProcessGroup()); 373 374adjacency_list(vertices_size_type n, 375 const ProcessGroup& pg = ProcessGroup()); 376</pre> 377<p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices, 378optionally providing the graph property, process group, or 379distribution. The <tt class="docutils literal"><span class="pre">n</span></tt> vertices will be distributed via the given 380(or default-constructed) distribution. This operation is collective, 381requiring all processes with the process group to execute it 382concurrently.</p> 383<hr class="docutils" /> 384<pre class="literal-block"> 385template <class EdgeIterator> 386adjacency_list(EdgeIterator first, EdgeIterator last, 387 vertices_size_type n, 388 const ProcessGroup& pg = ProcessGroup(), 389 const GraphProperty& p = GraphProperty()); 390 391template <class EdgeIterator, class EdgePropertyIterator> 392adjacency_list(EdgeIterator first, EdgeIterator last, 393 EdgePropertyIterator ep_iter, 394 vertices_size_type n, 395 const ProcessGroup& pg = ProcessGroup(), 396 const GraphProperty& p = GraphProperty()); 397 398template <class EdgeIterator> 399adjacency_list(EdgeIterator first, EdgeIterator last, 400 vertices_size_type n, 401 const ProcessGroup& process_group, 402 const Distribution& distribution, 403 const GraphProperty& p = GraphProperty()); 404 405template <class EdgeIterator, class EdgePropertyIterator> 406adjacency_list(EdgeIterator first, EdgeIterator last, 407 EdgePropertyIterator ep_iter, 408 vertices_size_type n, 409 const ProcessGroup& process_group, 410 const Distribution& distribution, 411 const GraphProperty& p = GraphProperty()); 412</pre> 413<p>Construct a distributed adjacency list with <tt class="docutils literal"><span class="pre">n</span></tt> vertices and with 414edges specified in the edge list given by the range <tt class="docutils literal"><span class="pre">[first,</span> <span class="pre">last)</span></tt>. The 415<tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a model of <a class="reference external" href="http://www.boost.org/doc/html/InputIterator.html">InputIterator</a>. The value type of the 416<tt class="docutils literal"><span class="pre">EdgeIterator</span></tt> must be a <tt class="docutils literal"><span class="pre">std::pair</span></tt>, where the type in the pair is an 417integer type. The integers will correspond to vertices, and they must 418all fall in the range of <tt class="docutils literal"><span class="pre">[0,</span> <span class="pre">n)</span></tt>. When provided, <tt class="docutils literal"><span class="pre">ep_iter</span></tt> 419refers to an edge property list <tt class="docutils literal"><span class="pre">[ep_iter,</span> <span class="pre">ep_iter</span> <span class="pre">+</span> <span class="pre">m)</span></tt> contains 420properties for each of the edges.</p> 421<p>This constructor is a collective operation and must be executed 422concurrently by each process with the same argument list. Most 423importantly, the edge lists provided to the constructor in each process 424should be equivalent. The vertices will be partitioned among the 425processes according to the <tt class="docutils literal"><span class="pre">distribution</span></tt>, with edges placed on the 426process owning the source of the edge. Note that this behavior 427permits sequential graph construction code to be parallelized 428automatically, regardless of the underlying distribution.</p> 429<hr class="docutils" /> 430<pre class="literal-block"> 431void clear() 432</pre> 433<p>Removes all of the edges and vertices from the local graph. To 434eliminate all vertices and edges from the graph, this routine must be 435executed in all processes.</p> 436<hr class="docutils" /> 437<pre class="literal-block"> 438process_group_type& process_group(); 439const process_group_type& process_group() const; 440</pre> 441<p>Returns the process group over which this graph is distributed.</p> 442<hr class="docutils" /> 443<pre class="literal-block"> 444distribution_type& distribution(); 445const distribution_type& distribution() const; 446</pre> 447<p>Returns the distribution used for initial placement of vertices.</p> 448<hr class="docutils" /> 449<pre class="literal-block"> 450template<typename VertexProcessorMap> 451 void redistribute(VertexProcessorMap vertex_to_processor); 452</pre> 453<p>Redistributes the vertices (and, therefore, the edges) of the 454graph. The property map <tt class="docutils literal"><span class="pre">vertex_to_processor</span></tt> provides, for each 455vertex, the process identifier indicating where the vertex should be 456moved. Once this collective routine has completed, the distributed 457graph will reflect the new distribution. All vertex and edge 458descsriptors and internal and external property maps are invalidated 459by this operation.</p> 460<hr class="docutils" /> 461<pre class="literal-block"> 462template<typename OStreamConstructibleArchive> 463 void save(std::string const& filename) const; 464 465template<typename IStreamConstructibleArchive> 466 void load(std::string const& filename); 467</pre> 468<p>Serializes the graph to a Boost.Serialization archive. 469<tt class="docutils literal"><span class="pre">OStreamConstructibleArchive</span></tt> and <tt class="docutils literal"><span class="pre">IStreamConstructibleArchive</span></tt> 470are models of Boost.Serialization <em>Archive</em> with the extra 471requirement that they can be constructed from a <tt class="docutils literal"><span class="pre">std::ostream</span></tt> 472and <tt class="docutils literal"><span class="pre">std::istream</span></tt>. 473<tt class="docutils literal"><span class="pre">filename</span></tt> names a directory that will hold files for 474the different processes.</p> 475</div> 476<div class="section" id="non-member-functions"> 477<h2><a class="toc-backref" href="#id11">Non-Member Functions</a></h2> 478<pre class="literal-block"> 479std::pair<vertex_iterator, vertex_iterator> 480vertices(const adjacency_list& g); 481</pre> 482<p>Returns an iterator-range providing access to the vertex set of graph 483<tt class="docutils literal"><span class="pre">g</span></tt> stored in this process. Each of the processes that contain <tt class="docutils literal"><span class="pre">g</span></tt> 484will get disjoint sets of vertices.</p> 485<hr class="docutils" /> 486<pre class="literal-block"> 487std::pair<edge_iterator, edge_iterator> 488edges(const adjacency_list& g); 489</pre> 490<p>Returns an iterator-range providing access to the edge set of graph 491<tt class="docutils literal"><span class="pre">g</span></tt> stored in this process.</p> 492<hr class="docutils" /> 493<pre class="literal-block"> 494std::pair<adjacency_iterator, adjacency_iterator> 495adjacent_vertices(vertex_descriptor u, const adjacency_list& g); 496</pre> 497<p>Returns an iterator-range providing access to the vertices adjacent to 498vertex <tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p> 499<hr class="docutils" /> 500<pre class="literal-block"> 501std::pair<out_edge_iterator, out_edge_iterator> 502out_edges(vertex_descriptor u, const adjacency_list& g); 503</pre> 504<p>Returns an iterator-range providing access to the out-edges of vertex 505<tt class="docutils literal"><span class="pre">u</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. If the graph is undirected, this iterator-range 506provides access to all edges incident on vertex <tt class="docutils literal"><span class="pre">u</span></tt>. For both 507directed and undirected graphs, for an out-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">source(e,</span> <span class="pre">g)</span> 508<span class="pre">==</span> <span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> where <tt class="docutils literal"><span class="pre">v</span></tt> is a vertex adjacent to 509<tt class="docutils literal"><span class="pre">u</span></tt>. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to this process.</p> 510<hr class="docutils" /> 511<pre class="literal-block"> 512std::pair<in_edge_iterator, in_edge_iterator> 513in_edges(vertex_descriptor v, const adjacency_list& g); 514</pre> 515<p>Returns an iterator-range providing access to the in-edges of vertex 516<tt class="docutils literal"><span class="pre">v</span></tt> in graph <tt class="docutils literal"><span class="pre">g</span></tt>. This operation is only available if 517<tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the <tt class="docutils literal"><span class="pre">Directed</span></tt> template 518parameter. For an in-edge <tt class="docutils literal"><span class="pre">e</span></tt>, <tt class="docutils literal"><span class="pre">target(e,</span> <span class="pre">g)</span> <span class="pre">==</span> <span class="pre">v</span></tt> and <tt class="docutils literal"><span class="pre">source(e,</span> 519<span class="pre">g)</span> <span class="pre">==</span> <span class="pre">u</span></tt> for some vertex <tt class="docutils literal"><span class="pre">u</span></tt> that is adjacent to <tt class="docutils literal"><span class="pre">v</span></tt>, whether the 520graph is directed or undirected. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local to 521this process.</p> 522<hr class="docutils" /> 523<pre class="literal-block"> 524degree_size_type 525out_degree(vertex_descriptor u, const adjacency_list& g); 526</pre> 527<p>Returns the number of edges leaving vertex <tt class="docutils literal"><span class="pre">u</span></tt>. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must 528be local to the executing process.</p> 529<hr class="docutils" /> 530<pre class="literal-block"> 531degree_size_type 532in_degree(vertex_descriptor u, const adjacency_list& g); 533</pre> 534<p>Returns the number of edges entering vertex <tt class="docutils literal"><span class="pre">u</span></tt>. This operation is 535only available if <tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> was specified for the 536<tt class="docutils literal"><span class="pre">Directed</span></tt> template parameter. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local to the 537executing process.</p> 538<hr class="docutils" /> 539<pre class="literal-block"> 540vertices_size_type 541num_vertices(const adjacency_list& g); 542</pre> 543<p>Returns the number of vertices in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in 544the executing process.</p> 545<hr class="docutils" /> 546<pre class="literal-block"> 547edges_size_type 548num_edges(const adjacency_list& g); 549</pre> 550<p>Returns the number of edges in the graph <tt class="docutils literal"><span class="pre">g</span></tt> that are stored in the 551executing process.</p> 552<hr class="docutils" /> 553<pre class="literal-block"> 554vertex_descriptor 555vertex(vertices_size_type n, const adjacency_list& g); 556</pre> 557<p>Returns the <tt class="docutils literal"><span class="pre">n``th</span> <span class="pre">vertex</span> <span class="pre">in</span> <span class="pre">the</span> <span class="pre">graph's</span> <span class="pre">vertex</span> <span class="pre">list,</span> <span class="pre">according</span> <span class="pre">to</span> <span class="pre">the</span> 558<span class="pre">distribution</span> <span class="pre">used</span> <span class="pre">to</span> <span class="pre">partition</span> <span class="pre">the</span> <span class="pre">graph.</span> <span class="pre">``n</span></tt> must be a value 559between zero and the sum of <tt class="docutils literal"><span class="pre">num_vertices(g)</span></tt> in each process (minus 560one). Note that it is not necessarily the case that <tt class="docutils literal"><span class="pre">vertex(0,</span> <span class="pre">g)</span> <span class="pre">==</span> 561<span class="pre">*num_vertices(g).first</span></tt>. This function is only guaranteed to be 562accurate when no vertices have been added to or removed from the 563graph after its initial construction.</p> 564<hr class="docutils" /> 565<pre class="literal-block"> 566std::pair<edge_descriptor, bool> 567edge(vertex_descriptor u, vertex_descriptor v, 568 const adjacency_list& g); 569</pre> 570<p>Returns an edge connecting vertex <tt class="docutils literal"><span class="pre">u</span></tt> to vertex <tt class="docutils literal"><span class="pre">v</span></tt> in graph 571<tt class="docutils literal"><span class="pre">g</span></tt>. For bidirectional and undirected graphs, either vertex <tt class="docutils literal"><span class="pre">u</span></tt> or 572vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local; for directed graphs, vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be 573local.</p> 574<hr class="docutils" /> 575<pre class="literal-block"> 576std::pair<out_edge_iterator, out_edge_iterator> 577edge_range(vertex_descriptor u, vertex_descriptor v, 578 const adjacency_list& g); 579</pre> 580<p>TODO: Not implemented. Returns a pair of out-edge iterators that give 581the range for all the parallel edges from <tt class="docutils literal"><span class="pre">u</span></tt> to <tt class="docutils literal"><span class="pre">v</span></tt>. This function only 582works when the <tt class="docutils literal"><span class="pre">OutEdgeList</span></tt> for the <tt class="docutils literal"><span class="pre">adjacency_list</span></tt> is a container that 583sorts the out edges according to target vertex, and allows for 584parallel edges. The <tt class="docutils literal"><span class="pre">multisetS</span></tt> selector chooses such a 585container. Vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored in the executing process.</p> 586</div> 587<div class="section" id="structure-modification"> 588<h2><a class="toc-backref" href="#id12">Structure Modification</a></h2> 589<pre class="literal-block"> 590unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g); 591unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g); 592unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g); 593unspecified add_edge(vertex_name_type u, vertex_name_type v, adjacency_list& g); 594</pre> 595<p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph. The return type itself is 596unspecified, but the type can be copy-constructed and implicitly 597converted into a <tt class="docutils literal"><span class="pre">std::pair<edge_descriptor,bool></span></tt>. The edge 598descriptor describes the added (or found) edge. For graphs that do not 599allow parallel edges, if the edge 600is already in the graph then a duplicate will not be added and the 601<tt class="docutils literal"><span class="pre">bool</span></tt> flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. Also, if u and v are descriptors for 602the same vertex (creating a self loop) and the graph is undirected, 603then the edge will not be added and the flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. When 604the flag is <tt class="docutils literal"><span class="pre">false</span></tt>, the returned edge descriptor points to the 605already existing edge.</p> 606<p>The parameters <tt class="docutils literal"><span class="pre">u</span></tt> and <tt class="docutils literal"><span class="pre">v</span></tt> can be either vertex descriptors or, if 607the graph uses named vertices, the names of vertices. If no vertex 608with the given name exists, the internal vertex constructor will be 609invoked to create a new vertex property and a vertex with that 610property will be added to the graph implicitly. The default internal 611vertex constructor throws an exception.</p> 612<hr class="docutils" /> 613<pre class="literal-block"> 614unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g); 615unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g); 616unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g); 617unspecified add_edge(vertex_name_type u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g); 618</pre> 619<p>Adds edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> to the graph and attaches <tt class="docutils literal"><span class="pre">p</span></tt> as the value of the edge's 620internal property storage. See the previous <tt class="docutils literal"><span class="pre">add_edge()</span></tt> member 621function for more details.</p> 622<hr class="docutils" /> 623<pre class="literal-block"> 624void 625remove_edge(vertex_descriptor u, vertex_descriptor v, 626 adjacency_list& g); 627</pre> 628<p>Removes the edge <tt class="docutils literal"><span class="pre">(u,v)</span></tt> from the graph. If the directed selector is 629<tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target 630vertex of the graph must be local. If the directed selector is 631<tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p> 632<hr class="docutils" /> 633<pre class="literal-block"> 634void 635remove_edge(edge_descriptor e, adjacency_list& g); 636</pre> 637<p>Removes the edge <tt class="docutils literal"><span class="pre">e</span></tt> from the graph. If the directed selector is 638<tt class="docutils literal"><span class="pre">bidirectionalS</span></tt> or <tt class="docutils literal"><span class="pre">undirectedS</span></tt>, either the source or target 639vertex of the graph must be local. If the directed selector is 640<tt class="docutils literal"><span class="pre">directedS</span></tt>, then the source vertex must be local.</p> 641<hr class="docutils" /> 642<pre class="literal-block"> 643void remove_edge(out_edge_iterator iter, adjacency_list& g); 644</pre> 645<p>This has the same effect as <tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>. For directed 646(but not bidirectional) graphs, this will be more efficient than 647<tt class="docutils literal"><span class="pre">remove_edge(*iter,</span> <span class="pre">g)</span></tt>.</p> 648<hr class="docutils" /> 649<pre class="literal-block"> 650template <class Predicate > 651void remove_out_edge_if(vertex_descriptor u, Predicate predicate, 652 adjacency_list& g); 653</pre> 654<p>Removes all out-edges of vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the graph that satisfy the 655predicate. That is, if the predicate returns <tt class="docutils literal"><span class="pre">true</span></tt> when applied to an 656edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be local.</p> 657<p>The affect on descriptor and iterator stability is the same as that of 658invoking remove_edge() on each of the removed edges.</p> 659<hr class="docutils" /> 660<pre class="literal-block"> 661template <class Predicate > 662void remove_in_edge_if(vertex_descriptor v, Predicate predicate, 663 adjacency_list& g); 664</pre> 665<p>Removes all in-edges of vertex <tt class="docutils literal"><span class="pre">v</span></tt> from the graph that satisfy the 666predicate. That is, if the predicate returns true when applied to an 667edge descriptor, then the edge is removed. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local.</p> 668<p>The affect on descriptor and iterator stability is the same as that of 669invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p> 670<p>This operation is available for undirected and bidirectional 671adjacency_list graphs, but not for directed.</p> 672<hr class="docutils" /> 673<pre class="literal-block"> 674template <class Predicate> 675void remove_edge_if(Predicate predicate, adjacency_list& g); 676</pre> 677<p>Removes all edges from the graph that satisfy the predicate. That is, 678if the predicate returns true when applied to an edge descriptor, then 679the edge is removed.</p> 680<p>The affect on descriptor and iterator stability is the same as that 681of invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> on each of the removed edges.</p> 682<hr class="docutils" /> 683<pre class="literal-block"> 684vertex_descriptor add_vertex(adjacency_list& g); 685</pre> 686<p>Adds a vertex to the graph and returns the vertex descriptor for the 687new vertex. The vertex will be stored in the local process. This 688function is not available when using named vertices.</p> 689<hr class="docutils" /> 690<pre class="literal-block"> 691unspecified add_vertex(const VertexProperties& p, adjacency_list& g); 692unspecified add_vertex(const vertex_name_type& p, adjacency_list& g); 693</pre> 694<p>Adds a vertex to the graph with the specified properties. If the graph 695is using vertex names, the vertex will be added on whichever process 696"owns" that name. Otherwise, the vertex will be stored in the local 697process. Note that the second constructor will invoke the 698user-customizable internal vertex constructor, which (by default) 699throws an exception when it sees an unknown vertex.</p> 700<p>The return type is of unspecified type, but can be copy-constructed 701and can be implicitly converted into a vertex descriptor.</p> 702<hr class="docutils" /> 703<pre class="literal-block"> 704void clear_vertex(vertex_descriptor u, adjacency_list& g); 705</pre> 706<p>Removes all edges to and from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears 707in the vertex set of the graph.</p> 708<p>The affect on descriptor and iterator stability is the same as that of 709invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the source 710or target.</p> 711<p>This operation is not applicable to directed graphs, because the 712incoming edges to vertex <tt class="docutils literal"><span class="pre">u</span></tt> are not known.</p> 713<hr class="docutils" /> 714<pre class="literal-block"> 715void clear_out_edges(vertex_descriptor u, adjacency_list& g); 716</pre> 717<p>Removes all out-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in 718the vertex set of the graph.</p> 719<p>The affect on descriptor and iterator stability is the same as that of 720invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the 721source.</p> 722<p>This operation is not applicable to undirected graphs (use 723<tt class="docutils literal"><span class="pre">clear_vertex()</span></tt> instead).</p> 724<hr class="docutils" /> 725<pre class="literal-block"> 726void clear_in_edges(vertex_descriptor u, adjacency_list& g); 727</pre> 728<p>Removes all in-edges from vertex <tt class="docutils literal"><span class="pre">u</span></tt>. The vertex still appears in 729the vertex set of the graph.</p> 730<p>The affect on descriptor and iterator stability is the same as that of 731invoking <tt class="docutils literal"><span class="pre">remove_edge()</span></tt> for all of the edges that have <tt class="docutils literal"><span class="pre">u</span></tt> as the 732target.</p> 733<p>This operation is only applicable to bidirectional graphs.</p> 734<hr class="docutils" /> 735<pre class="literal-block"> 736void remove_vertex(vertex_descriptor u, adjacency_list& g); 737</pre> 738<p>Remove vertex <tt class="docutils literal"><span class="pre">u</span></tt> from the vertex set of the graph. It is assumed 739that there are no edges to or from vertex <tt class="docutils literal"><span class="pre">u</span></tt> when it is 740removed. One way to make sure of this is to invoke <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt> 741beforehand. The vertex <tt class="docutils literal"><span class="pre">u</span></tt> must be stored locally.</p> 742</div> 743<div class="section" id="property-map-accessors"> 744<h2><a class="toc-backref" href="#id13">Property Map Accessors</a></h2> 745<pre class="literal-block"> 746template <class PropertyTag> 747property_map<adjacency_list, PropertyTag>::type 748get(PropertyTag, adjacency_list& g); 749 750template <class PropertyTag> 751property_map<adjacency_list, Tag>::const_type 752get(PropertyTag, const adjacency_list& g); 753</pre> 754<p>Returns the property map object for the vertex property specified by 755<tt class="docutils literal"><span class="pre">PropertyTag</span></tt>. The <tt class="docutils literal"><span class="pre">PropertyTag</span></tt> must match one of the properties 756specified in the graph's <tt class="docutils literal"><span class="pre">VertexProperty</span></tt> template argument. The 757returned property map will be a <a class="reference external" href="distributed_property_map.html">distributed property map</a>.</p> 758<hr class="docutils" /> 759<pre class="literal-block"> 760template <class PropertyTag , class X> 761typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type 762get(PropertyTag, const adjacency_list& g, X x); 763</pre> 764<p>This returns the property value for <tt class="docutils literal"><span class="pre">x</span></tt>, where <tt class="docutils literal"><span class="pre">x</span></tt> is either a vertex or 765edge descriptor. The entity referred to by descriptor <tt class="docutils literal"><span class="pre">x</span></tt> must be 766stored in the local process.</p> 767<hr class="docutils" /> 768<pre class="literal-block"> 769template <class PropertyTag , class X, class Value> 770void put(PropertyTag, const adjacency_list& g, X x, const Value& value); 771</pre> 772<p>This sets the property value for <tt class="docutils literal"><span class="pre">x</span></tt> to value. <tt class="docutils literal"><span class="pre">x</span></tt> is either a 773vertex or edge descriptor. <tt class="docutils literal"><span class="pre">Value</span></tt> must be convertible to <tt class="docutils literal"><span class="pre">typename</span> 774<span class="pre">property_traits<property_map<adjacency_list,</span> 775<span class="pre">PropertyTag>::type>::value_type</span></tt>.</p> 776<hr class="docutils" /> 777<pre class="literal-block"> 778template <class GraphProperties, class GraphPropertyTag> 779typename graph_property<adjacency_list, GraphPropertyTag>::type& 780get_property(adjacency_list& g, GraphPropertyTag); 781 782template <class GraphProperties, class GraphPropertyTag > 783const typename graph_property<adjacency_list, GraphPropertyTag>::type& 784get_property(const adjacency_list& g, GraphPropertyTag); 785</pre> 786<p>TODO: not implemented.</p> 787<p>Return the property specified by <tt class="docutils literal"><span class="pre">GraphPropertyTag</span></tt> that is attached 788to the graph object <tt class="docutils literal"><span class="pre">g</span></tt>. The <tt class="docutils literal"><span class="pre">graph_property</span></tt> traits class is 789defined in <tt class="docutils literal"><span class="pre">boost/graph/adjacency_list.hpp</span></tt>.</p> 790<hr class="docutils" /> 791<p>Copyright (C) 2004 The Trustees of Indiana University.</p> 792<p>Copyright (C) 2007 Douglas Gregor</p> 793<p>Authors: Douglas Gregor and Andrew Lumsdaine</p> 794</div> 795</div> 796</div> 797<div class="footer"> 798<hr class="footer" /> 799Generated on: 2009-05-31 00:21 UTC. 800Generated 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. 801 802</div> 803</body> 804</html> 805
