]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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. | |
15 | Use, modification and distribution is subject to the Boost Software | |
16 | License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at | |
17 | http://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 | |
43 | an adjacency list representation. Its interface and behavior are | |
44 | roughly 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> | |
45 | class template. However, the distributed adjacency list partitions the | |
46 | vertices of the graph across several processes (which need not share | |
47 | an address space). Edges outgoing from any vertex stored by a process | |
48 | are also stored on that process, except in the case of undirected | |
49 | graphs, where either the source or the target may store the edge.</p> | |
50 | <pre class="literal-block"> | |
51 | template<typename OutEdgeListS, typename ProcessGroup, typename VertexListS, | |
52 | typename DirectedS, typename VertexProperty, typename EdgeProperty, | |
53 | typename GraphProperty, typename EdgeListS> | |
54 | class 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 | |
62 | representation 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>) | |
64 | with 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 | |
67 | coordinating processes that will store the distributed graph. For | |
68 | example, 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 | |
70 | stored. 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 | |
71 | at this time.</li> | |
72 | </ul> | |
73 | <p>The following <tt class="docutils literal"><span class="pre">typedef</span></tt> defines a distributed adjacency list | |
74 | containing directed edges. The vertices in the graph will be | |
75 | distributed over several processes, using the MPI process group | |
76 | for communication. In each process, the vertices and outgoing edges | |
77 | will be stored in STL vectors. There are no properties attached to the | |
78 | vertices or edges of the graph.</p> | |
79 | <pre class="literal-block"> | |
80 | using namespace boost; | |
81 | typedef 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 | |
90 | counterparts for non-distributed graphs. With a distributed graph, | |
91 | however, vertex and edge properties are stored only in the process | |
92 | that owns the vertex or edge.</p> | |
93 | <p>The most direct way to attach properties to a distributed graph is to | |
94 | create a structure that will be attached to each of the vertices and | |
95 | edges of the graph. For example, if we wish to model a simplistic map | |
96 | of the United States interstate highway system, we might state that | |
97 | the vertices of the graph are cities and the edges are highways, then | |
98 | define the information that we maintain for each city and highway:</p> | |
99 | <pre class="literal-block"> | |
100 | struct 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 | ||
116 | struct 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>, | |
135 | respectively:</p> | |
136 | <pre class="literal-block"> | |
137 | typedef 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 | |
144 | distributed graphs via <a class="reference external" href="distributed_property_map.html">distributed property maps</a>, which automate | |
145 | communication 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 | |
146 | may be applied to non-local vertices and edges. However, for | |
147 | distributed 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> | |
149 | property 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 | |
150 | to vertices local to the process executing the operation. For example, | |
151 | we can create a property map that accesses the length of each highway | |
152 | as follows:</p> | |
153 | <pre class="literal-block"> | |
154 | RoadMap map; // distributed graph instance | |
155 | ||
156 | typedef 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 | |
160 | descriptor <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>, | |
161 | regardless 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 | |
166 | the application domain. In the road map example from the previous | |
167 | section, the vertices in the graph represent cities. The distributed | |
168 | adjacency list supports named vertices, which provides an implicit | |
169 | mapping 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 | |
171 | descriptor stored within the distributed graph (e.g., the third vertex | |
172 | on processor 1). By enabling support for named vertices, one can refer | |
173 | to vertices by name when manipulating the graph. For example, one can | |
174 | add a highway from Indianapolis to Chicago:</p> | |
175 | <pre class="literal-block"> | |
176 | add_edge("Indianapolis", "Chicago", Highway("I-65", 4, 65, 151), map); | |
177 | </pre> | |
178 | <p>The distributed adjacency list will find vertices associated with the | |
179 | names "Indianapolis" and "Chicago", then add an edge between these | |
180 | vertices that represents I-65. The vertices may be stored on any | |
181 | processor, local or remote.</p> | |
182 | <p>To enable named vertices, specialize the <tt class="docutils literal"><span class="pre">internal_vertex_name</span></tt> | |
183 | property for the structure attached to the vertices in your | |
184 | graph. <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>, | |
185 | which is the type of a function object that accepts a vertex property | |
186 | and returns the name stored within that vertex property. In the case | |
187 | of our road map, the <tt class="docutils literal"><span class="pre">name</span></tt> field contains the name of each city, so | |
188 | we 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> | |
189 | library to extract the name, e.g.,</p> | |
190 | <pre class="literal-block"> | |
191 | namespace boost { namespace graph { | |
192 | ||
193 | template<> | |
194 | struct 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 | |
202 | the distributed adjacency list.</p> | |
203 | <p>What happens when one uses the name of a vertex that does not exist? | |
204 | For example, in our <tt class="docutils literal"><span class="pre">add_edge</span></tt> call above, what happens if the | |
205 | vertex named "Indianapolis" has not yet been added to the graph? By | |
206 | default, the distributed adjacency list will throw an exception if a | |
207 | named vertex does not yet exist. However, one can customize this | |
208 | behavior by specifying a function object that constructs an instance | |
209 | of the vertex property (e.g., <tt class="docutils literal"><span class="pre">City</span></tt>) from just the name of the | |
210 | vertex. 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 | |
213 | state that a <tt class="docutils literal"><span class="pre">City</span></tt> can be constructed directly from the name of the | |
214 | city using its second constructor:</p> | |
215 | <pre class="literal-block"> | |
216 | namespace boost { namespace graph { | |
217 | ||
218 | template<> | |
219 | struct 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 | |
227 | the 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> | |
228 | fields will have default values, but the graph structure will be | |
229 | correct.</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 | |
234 | specific data structures and properties, it is time to construct an | |
235 | instance of the graph by adding the appropriate vertices and | |
236 | edges. Construction of distributed graphs can be slightly more | |
237 | complicated than construction of normal, non-distributed graph data | |
238 | structures, because one must account for both the distribution of the | |
239 | vertices and edges and the multiple processes executing | |
240 | concurrently. There are three main ways to construct distributed | |
241 | graphs:</p> | |
242 | <p>1. <em>Sequence constructors</em>: if your data can easily be generated by a | |
243 | pair of iterators that produce (source, target) pairs, you can use the | |
244 | sequence constructors to build the distributed graph in parallel. This | |
245 | method is often preferred when creating benchmarks, because random | |
246 | graph 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 | |
247 | appropriate input sequence. Note that one must provide the same input | |
248 | iterator sequence on all processes. This method has the advantage that | |
249 | the sequential graph-building code is identical to the parallel | |
250 | graph-building code. An example constructing a random graph this way:</p> | |
251 | <blockquote> | |
252 | <pre class="literal-block"> | |
253 | typedef boost::sorted_erdos_renyi_iterator<boost::minstd_rand, Graph> ERIter; | |
254 | boost::minstd_rand gen; | |
255 | unsigned long n = 1000000; // 1M vertices | |
256 | Graph 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 | |
260 | vertices into values in the random [0, <em>n</em>), where <em>n</em> is the number | |
261 | of vertices in the distributed graph. Use this method rather than the | |
262 | sequence constructors when your algorithm cannot easily be moved into | |
263 | input iterators, or if you can't replicate the input sequence. For | |
264 | example, you might be reading the graph from an input file:</p> | |
265 | <blockquote> | |
266 | <pre class="literal-block"> | |
267 | Graph g(n); // initialize with the total number of vertices, n | |
268 | if (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 | |
276 | synchronize(g.process_group()); | |
277 | </pre> | |
278 | </blockquote> | |
279 | <p>3. <em>Adding edges by name</em>: if you are using named vertices, you can | |
280 | construct your graph just by calling <tt class="docutils literal"><span class="pre">add_edge</span></tt> with the names of | |
281 | the source and target vertices. Be careful to make sure that each edge | |
282 | is added by only one process (it doesn't matter which process it is), | |
283 | otherwise you will end up with multiple edges. For example, in the | |
284 | following program we read edges from the standard input of process 0, | |
285 | adding those edges by name. Vertices and edges will be created and | |
286 | distributed automatically.</p> | |
287 | <blockquote> | |
288 | <pre class="literal-block"> | |
289 | Graph g; | |
290 | if (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 | |
298 | synchronize(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 | |
305 | particular 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 | |
307 | input domain of the operations to correspond to local vertices | |
308 | only. For instance, a process may only access the outgoing edges of a | |
309 | vertex if that vertex is stored in that process. Undirected and | |
310 | bidirectional distributed adjacency lists model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/BidirectionalGraph.html">Bidirectional | |
311 | Graph</a> concept, with the same domain restrictions. Distributed | |
312 | adjacency lists also model the <a class="reference external" href="http://www.boost.org/libs/graph/doc/MutableGraph.html">Mutable Graph</a> concept (with domain | |
313 | restrictions; 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, | |
314 | and <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 | |
316 | list 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 | |
317 | Graph</a> concepts, because one cannot enumerate all vertices or edges | |
318 | within 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> | |
320 | concepts, which permit access to the local edges and vertices on each | |
321 | processor. Note that if all processes within the process group over | |
322 | which the graph is distributed iterator over their respective vertex | |
323 | or 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 | |
329 | non-distributed <a class="reference external" href="http://www.boost.org/libs/graph/doc/adjacency_list.html">adjacency_list</a>, this reference documentation | |
330 | only 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"> | |
338 | adjacency_list::process_group_type | |
339 | </pre> | |
340 | <p>The type of the process group over which the graph will be | |
341 | distributed.</p> | |
342 | <hr class="docutils" /> | |
343 | <blockquote> | |
344 | adjacency_list::distribution_type</blockquote> | |
345 | <p>The type of distribution used to partition vertices in the graph.</p> | |
346 | <hr class="docutils" /> | |
347 | <blockquote> | |
348 | adjacency_list::vertex_name_type</blockquote> | |
349 | <p>If the graph supports named vertices, this is the type used to name | |
350 | vertices. Otherwise, this type is not present within the distributed | |
351 | adjacency 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"> | |
356 | adjacency_list(const ProcessGroup& pg = ProcessGroup()); | |
357 | ||
358 | adjacency_list(const GraphProperty& g, | |
359 | const ProcessGroup& pg = ProcessGroup()); | |
360 | </pre> | |
361 | <p>Construct an empty distributed adjacency list with the given process | |
362 | group (or default) and graph property (or default).</p> | |
363 | <hr class="docutils" /> | |
364 | <pre class="literal-block"> | |
365 | adjacency_list(vertices_size_type n, const GraphProperty& p, | |
366 | const ProcessGroup& pg, const Distribution& distribution); | |
367 | ||
368 | adjacency_list(vertices_size_type n, const ProcessGroup& pg, | |
369 | const Distribution& distribution); | |
370 | ||
371 | adjacency_list(vertices_size_type n, const GraphProperty& p, | |
372 | const ProcessGroup& pg = ProcessGroup()); | |
373 | ||
374 | adjacency_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, | |
378 | optionally providing the graph property, process group, or | |
379 | distribution. 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, | |
381 | requiring all processes with the process group to execute it | |
382 | concurrently.</p> | |
383 | <hr class="docutils" /> | |
384 | <pre class="literal-block"> | |
385 | template <class EdgeIterator> | |
386 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
387 | vertices_size_type n, | |
388 | const ProcessGroup& pg = ProcessGroup(), | |
389 | const GraphProperty& p = GraphProperty()); | |
390 | ||
391 | template <class EdgeIterator, class EdgePropertyIterator> | |
392 | adjacency_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 | ||
398 | template <class EdgeIterator> | |
399 | adjacency_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 | ||
405 | template <class EdgeIterator, class EdgePropertyIterator> | |
406 | adjacency_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 | |
414 | edges 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 | |
417 | integer type. The integers will correspond to vertices, and they must | |
418 | all 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> | |
419 | refers 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 | |
420 | properties for each of the edges.</p> | |
421 | <p>This constructor is a collective operation and must be executed | |
422 | concurrently by each process with the same argument list. Most | |
423 | importantly, the edge lists provided to the constructor in each process | |
424 | should be equivalent. The vertices will be partitioned among the | |
425 | processes according to the <tt class="docutils literal"><span class="pre">distribution</span></tt>, with edges placed on the | |
426 | process owning the source of the edge. Note that this behavior | |
427 | permits sequential graph construction code to be parallelized | |
428 | automatically, regardless of the underlying distribution.</p> | |
429 | <hr class="docutils" /> | |
430 | <pre class="literal-block"> | |
431 | void clear() | |
432 | </pre> | |
433 | <p>Removes all of the edges and vertices from the local graph. To | |
434 | eliminate all vertices and edges from the graph, this routine must be | |
435 | executed in all processes.</p> | |
436 | <hr class="docutils" /> | |
437 | <pre class="literal-block"> | |
438 | process_group_type& process_group(); | |
439 | const 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"> | |
444 | distribution_type& distribution(); | |
445 | const 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"> | |
450 | template<typename VertexProcessorMap> | |
451 | void redistribute(VertexProcessorMap vertex_to_processor); | |
452 | </pre> | |
453 | <p>Redistributes the vertices (and, therefore, the edges) of the | |
454 | graph. The property map <tt class="docutils literal"><span class="pre">vertex_to_processor</span></tt> provides, for each | |
455 | vertex, the process identifier indicating where the vertex should be | |
456 | moved. Once this collective routine has completed, the distributed | |
457 | graph will reflect the new distribution. All vertex and edge | |
458 | descsriptors and internal and external property maps are invalidated | |
459 | by this operation.</p> | |
460 | <hr class="docutils" /> | |
461 | <pre class="literal-block"> | |
462 | template<typename OStreamConstructibleArchive> | |
463 | void save(std::string const& filename) const; | |
464 | ||
465 | template<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> | |
470 | are models of Boost.Serialization <em>Archive</em> with the extra | |
471 | requirement that they can be constructed from a <tt class="docutils literal"><span class="pre">std::ostream</span></tt> | |
472 | and <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 | |
474 | the 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"> | |
479 | std::pair<vertex_iterator, vertex_iterator> | |
480 | vertices(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> | |
484 | will get disjoint sets of vertices.</p> | |
485 | <hr class="docutils" /> | |
486 | <pre class="literal-block"> | |
487 | std::pair<edge_iterator, edge_iterator> | |
488 | edges(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"> | |
494 | std::pair<adjacency_iterator, adjacency_iterator> | |
495 | adjacent_vertices(vertex_descriptor u, const adjacency_list& g); | |
496 | </pre> | |
497 | <p>Returns an iterator-range providing access to the vertices adjacent to | |
498 | vertex <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"> | |
501 | std::pair<out_edge_iterator, out_edge_iterator> | |
502 | out_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 | |
506 | provides access to all edges incident on vertex <tt class="docutils literal"><span class="pre">u</span></tt>. For both | |
507 | directed 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"> | |
512 | std::pair<in_edge_iterator, in_edge_iterator> | |
513 | in_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 | |
518 | parameter. 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 | |
520 | graph is directed or undirected. The vertex <tt class="docutils literal"><span class="pre">v</span></tt> must be local to | |
521 | this process.</p> | |
522 | <hr class="docutils" /> | |
523 | <pre class="literal-block"> | |
524 | degree_size_type | |
525 | out_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 | |
528 | be local to the executing process.</p> | |
529 | <hr class="docutils" /> | |
530 | <pre class="literal-block"> | |
531 | degree_size_type | |
532 | in_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 | |
535 | only 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 | |
537 | executing process.</p> | |
538 | <hr class="docutils" /> | |
539 | <pre class="literal-block"> | |
540 | vertices_size_type | |
541 | num_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 | |
544 | the executing process.</p> | |
545 | <hr class="docutils" /> | |
546 | <pre class="literal-block"> | |
547 | edges_size_type | |
548 | num_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 | |
551 | executing process.</p> | |
552 | <hr class="docutils" /> | |
553 | <pre class="literal-block"> | |
554 | vertex_descriptor | |
555 | vertex(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 | |
559 | between zero and the sum of <tt class="docutils literal"><span class="pre">num_vertices(g)</span></tt> in each process (minus | |
560 | one). 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 | |
562 | accurate when no vertices have been added to or removed from the | |
563 | graph after its initial construction.</p> | |
564 | <hr class="docutils" /> | |
565 | <pre class="literal-block"> | |
566 | std::pair<edge_descriptor, bool> | |
567 | edge(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 | |
572 | vertex <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 | |
573 | local.</p> | |
574 | <hr class="docutils" /> | |
575 | <pre class="literal-block"> | |
576 | std::pair<out_edge_iterator, out_edge_iterator> | |
577 | edge_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 | |
581 | the 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 | |
582 | works 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 | |
583 | sorts the out edges according to target vertex, and allows for | |
584 | parallel edges. The <tt class="docutils literal"><span class="pre">multisetS</span></tt> selector chooses such a | |
585 | container. 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"> | |
590 | unspecified add_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g); | |
591 | unspecified add_edge(vertex_name_type u, vertex_descriptor v, adjacency_list& g); | |
592 | unspecified add_edge(vertex_descriptor u, vertex_name_type v, adjacency_list& g); | |
593 | unspecified 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 | |
596 | unspecified, but the type can be copy-constructed and implicitly | |
597 | converted into a <tt class="docutils literal"><span class="pre">std::pair<edge_descriptor,bool></span></tt>. The edge | |
598 | descriptor describes the added (or found) edge. For graphs that do not | |
599 | allow parallel edges, if the edge | |
600 | is 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 | |
602 | the same vertex (creating a self loop) and the graph is undirected, | |
603 | then the edge will not be added and the flag will be <tt class="docutils literal"><span class="pre">false</span></tt>. When | |
604 | the flag is <tt class="docutils literal"><span class="pre">false</span></tt>, the returned edge descriptor points to the | |
605 | already 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 | |
607 | the graph uses named vertices, the names of vertices. If no vertex | |
608 | with the given name exists, the internal vertex constructor will be | |
609 | invoked to create a new vertex property and a vertex with that | |
610 | property will be added to the graph implicitly. The default internal | |
611 | vertex constructor throws an exception.</p> | |
612 | <hr class="docutils" /> | |
613 | <pre class="literal-block"> | |
614 | unspecified add_edge(vertex_descriptor u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g); | |
615 | unspecified add_edge(vertex_name_type u, vertex_descriptor v, const EdgeProperties& p, adjacency_list& g); | |
616 | unspecified add_edge(vertex_descriptor u, vertex_name_type v, const EdgeProperties& p, adjacency_list& g); | |
617 | unspecified 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 | |
620 | internal property storage. See the previous <tt class="docutils literal"><span class="pre">add_edge()</span></tt> member | |
621 | function for more details.</p> | |
622 | <hr class="docutils" /> | |
623 | <pre class="literal-block"> | |
624 | void | |
625 | remove_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 | |
630 | vertex 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"> | |
634 | void | |
635 | remove_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 | |
639 | vertex 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"> | |
643 | void 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"> | |
650 | template <class Predicate > | |
651 | void 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 | |
655 | predicate. That is, if the predicate returns <tt class="docutils literal"><span class="pre">true</span></tt> when applied to an | |
656 | edge 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 | |
658 | invoking remove_edge() on each of the removed edges.</p> | |
659 | <hr class="docutils" /> | |
660 | <pre class="literal-block"> | |
661 | template <class Predicate > | |
662 | void 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 | |
666 | predicate. That is, if the predicate returns true when applied to an | |
667 | edge 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 | |
669 | invoking <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 | |
671 | adjacency_list graphs, but not for directed.</p> | |
672 | <hr class="docutils" /> | |
673 | <pre class="literal-block"> | |
674 | template <class Predicate> | |
675 | void remove_edge_if(Predicate predicate, adjacency_list& g); | |
676 | </pre> | |
677 | <p>Removes all edges from the graph that satisfy the predicate. That is, | |
678 | if the predicate returns true when applied to an edge descriptor, then | |
679 | the edge is removed.</p> | |
680 | <p>The affect on descriptor and iterator stability is the same as that | |
681 | of 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"> | |
684 | vertex_descriptor add_vertex(adjacency_list& g); | |
685 | </pre> | |
686 | <p>Adds a vertex to the graph and returns the vertex descriptor for the | |
687 | new vertex. The vertex will be stored in the local process. This | |
688 | function is not available when using named vertices.</p> | |
689 | <hr class="docutils" /> | |
690 | <pre class="literal-block"> | |
691 | unspecified add_vertex(const VertexProperties& p, adjacency_list& g); | |
692 | unspecified 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 | |
695 | is using vertex names, the vertex will be added on whichever process | |
696 | "owns" that name. Otherwise, the vertex will be stored in the local | |
697 | process. Note that the second constructor will invoke the | |
698 | user-customizable internal vertex constructor, which (by default) | |
699 | throws an exception when it sees an unknown vertex.</p> | |
700 | <p>The return type is of unspecified type, but can be copy-constructed | |
701 | and can be implicitly converted into a vertex descriptor.</p> | |
702 | <hr class="docutils" /> | |
703 | <pre class="literal-block"> | |
704 | void 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 | |
707 | in the vertex set of the graph.</p> | |
708 | <p>The affect on descriptor and iterator stability is the same as that of | |
709 | invoking <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 | |
710 | or target.</p> | |
711 | <p>This operation is not applicable to directed graphs, because the | |
712 | incoming 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"> | |
715 | void 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 | |
718 | the vertex set of the graph.</p> | |
719 | <p>The affect on descriptor and iterator stability is the same as that of | |
720 | invoking <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 | |
721 | source.</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"> | |
726 | void 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 | |
729 | the vertex set of the graph.</p> | |
730 | <p>The affect on descriptor and iterator stability is the same as that of | |
731 | invoking <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 | |
732 | target.</p> | |
733 | <p>This operation is only applicable to bidirectional graphs.</p> | |
734 | <hr class="docutils" /> | |
735 | <pre class="literal-block"> | |
736 | void 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 | |
739 | that there are no edges to or from vertex <tt class="docutils literal"><span class="pre">u</span></tt> when it is | |
740 | removed. One way to make sure of this is to invoke <tt class="docutils literal"><span class="pre">clear_vertex()</span></tt> | |
741 | beforehand. 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"> | |
746 | template <class PropertyTag> | |
747 | property_map<adjacency_list, PropertyTag>::type | |
748 | get(PropertyTag, adjacency_list& g); | |
749 | ||
750 | template <class PropertyTag> | |
751 | property_map<adjacency_list, Tag>::const_type | |
752 | get(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 | |
756 | specified in the graph's <tt class="docutils literal"><span class="pre">VertexProperty</span></tt> template argument. The | |
757 | returned 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"> | |
760 | template <class PropertyTag , class X> | |
761 | typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type | |
762 | get(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 | |
765 | edge descriptor. The entity referred to by descriptor <tt class="docutils literal"><span class="pre">x</span></tt> must be | |
766 | stored in the local process.</p> | |
767 | <hr class="docutils" /> | |
768 | <pre class="literal-block"> | |
769 | template <class PropertyTag , class X, class Value> | |
770 | void 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 | |
773 | vertex 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"> | |
778 | template <class GraphProperties, class GraphPropertyTag> | |
779 | typename graph_property<adjacency_list, GraphPropertyTag>::type& | |
780 | get_property(adjacency_list& g, GraphPropertyTag); | |
781 | ||
782 | template <class GraphProperties, class GraphPropertyTag > | |
783 | const typename graph_property<adjacency_list, GraphPropertyTag>::type& | |
784 | get_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 | |
788 | to 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 | |
789 | defined 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" /> | |
799 | Generated on: 2009-05-31 00:21 UTC. | |
800 | Generated 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> |