]>
Commit | Line | Data |
---|---|---|
1 | <HTML> | |
2 | <!-- | |
3 | Copyright (c) Jeremy Siek 2000 | |
4 | ||
5 | Distributed under the Boost Software License, Version 1.0. | |
6 | (See accompanying file LICENSE_1_0.txt or copy at | |
7 | http://www.boost.org/LICENSE_1_0.txt) | |
8 | --> | |
9 | <Head> | |
10 | <Title>Boost Graph Library: Adjacency List</Title> | |
11 | <BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" | |
12 | ALINK="#ff0000"> | |
13 | <IMG SRC="../../../boost.png" | |
14 | ALT="C++ Boost" width="277" height="86"> | |
15 | ||
16 | <BR Clear> | |
17 | ||
18 | <H1><A NAME="sec:adjacency-list-class"></A> | |
19 | <pre> | |
20 | adjacency_list<OutEdgeList, VertexList, Directed, | |
21 | VertexProperties, EdgeProperties, | |
22 | GraphProperties, EdgeList> | |
23 | </pre> | |
24 | </H1> | |
25 | ||
26 | ||
27 | <P> | |
28 | The <TT>adjacency_list</TT> class implements a generalized adjacency | |
29 | list graph structure. The template parameters provide many | |
30 | configuration options so that you can pick a version of the class that | |
31 | best meets your needs. An <a | |
32 | href="graph_theory_review.html#sec:adjacency-list-representation">adjacency-list</a> | |
33 | is basically a two-dimensional structure, where each element of the | |
34 | first dimension represents a vertex, and each of the vertices contains | |
35 | a one-dimensional structure that is its edge list. <a | |
36 | href="#fig:adj-list-graph">Figure 1</a> shows an adjacency list | |
37 | representation of a directed graph. | |
38 | ||
39 | <P></P> | |
40 | <DIV ALIGN="center"><A NAME="fig:adj-list-graph"></A> | |
41 | <TABLE> | |
42 | <CAPTION ALIGN="BOTTOM"><STRONG>Figure 1:</STRONG> Adjacency List Representation of a Directed Graph.</CAPTION> | |
43 | <TR><TD><IMG SRC="./figs/adj-matrix-graph2.gif" width="386" height="284"></TD> | |
44 | <TD><IMG SRC="./figs/adj-list2.gif" width="62" height="122"></TD></TR> | |
45 | </TABLE> | |
46 | </DIV><P></P> | |
47 | ||
48 | The | |
49 | <TT>VertexList</TT> template parameter of the <TT>adjacency_list</TT> | |
50 | class controls what kind of container is used to represent the outer | |
51 | two-dimensional container. The <TT>OutEdgeList</TT> template parameter | |
52 | controls what kind of container is used to represent the edge | |
53 | lists. The choices for <TT>OutEdgeList</TT> and <TT>VertexList</TT> will | |
54 | determine the space complexity of the graph structure, and will | |
55 | determine the time complexity of the various graph operations. The | |
56 | possible choices and tradeoffs are discussed in Section <A | |
57 | HREF="./using_adjacency_list.html#sec:choosing-graph-type">Choosing | |
58 | the <TT>Edgelist</TT> and <TT>VertexList</TT></A>. | |
59 | ||
60 | <P> | |
61 | The <TT>Directed</TT> template parameter controls whether the graph is | |
62 | directed, undirected, or directed with access to both the in-edges and | |
63 | out-edges (which we call bidirectional). The bidirectional graph takes | |
64 | up twice the space (per edge) of a directed graph since each edge will | |
65 | appear in both an out-edge and in-edge list. <a | |
66 | href="#fig:undir-adj-list-graph">Figure 2</a> shows an adjacency list | |
67 | representation of an undirected graph. | |
68 | ||
69 | <P></P> | |
70 | <DIV ALIGN="center"><A NAME="fig:undir-adj-list-graph"></A> | |
71 | <TABLE> | |
72 | <CAPTION ALIGN="BOTTOM"><STRONG>Figure 2:</STRONG> Adjacency List Representation of an Undirected Graph.</CAPTION> | |
73 | <TR><TD><IMG SRC="./figs/undir-adj-matrix-graph2.gif" width="260" height="240"></TD> | |
74 | <TD><IMG SRC="./figs/undir-adj-list.gif" width="62" height="122"></TD></TR> | |
75 | </TABLE> | |
76 | </DIV><P></P> | |
77 | ||
78 | <P> | |
79 | A tutorial on how to use the <TT>adjacency_list</TT> class is in | |
80 | Section <A HREF="./using_adjacency_list.html">Using | |
81 | <TT>adjacency_list</TT></A>. | |
82 | ||
83 | <P> | |
84 | ||
85 | <H3>Example</H3> | |
86 | ||
87 | <P> | |
88 | The example in <a | |
89 | href="../example/family-tree-eg.cpp"><tt>examples/family-tree-eg.cpp</tt></a> | |
90 | shows how to represent a family tree with a graph. | |
91 | ||
92 | <H3>Template Parameters</H3> | |
93 | ||
94 | <P> | |
95 | <TABLE border> | |
96 | <TR> | |
97 | <th>Parameter</th><th>Description</th><th>Default</th> | |
98 | </tr> | |
99 | ||
100 | <TR><TD><TT>OutEdgeList</TT></TD> | |
101 | <TD>The selector for the container used to represent the | |
102 | edge-list for each of the vertices.</TD> | |
103 | <TD><TT>vecS</TT></TD> | |
104 | </TR> | |
105 | ||
106 | <TR> | |
107 | <TD><TT>VertexList</TT></TD> | |
108 | <TD>The selector for the container used to represent the | |
109 | vertex-list of the graph.</TD> | |
110 | <TD><TT>vecS</TT></TD> | |
111 | </TR> | |
112 | ||
113 | <TR> | |
114 | <TD><TT>Directed</TT></TD> | |
115 | <TD>A selector to choose whether the graph is directed, undirected, or directed with bidirectional edge access (access to both out-edges and in-edges). The options are <TT>directedS</TT>, <TT>undirectedS</TT>, and <TT>bidirectionalS</TT>.</TD> | |
116 | <TD><TT>directedS</TT></TD> | |
117 | </TR> | |
118 | ||
119 | <TR> | |
120 | <TD><TT>VertexProperties</TT></TD> | |
121 | <TD>for specifying internal property storage.</TD> | |
122 | <TD><TT>no_property</TT></TD> | |
123 | </TR> | |
124 | ||
125 | <TR> | |
126 | <TD><TT>EdgeProperties</TT></TD> | |
127 | <TD>for specifying internal property storage.</TD> | |
128 | <TD><TT>no_property</TT></TD> | |
129 | </TR> | |
130 | ||
131 | <TR> | |
132 | <TD><TT>GraphProperties</TT></TD> | |
133 | <TD>for specifying property storage for the graph object.</TD> | |
134 | <TD><TT>no_property</TT></TD> | |
135 | </TR> | |
136 | ||
137 | <TR><TD><TT>EdgeList</TT></TD> | |
138 | <TD>The selector for the container used to represent the | |
139 | edge-list for the graph.</TD> | |
140 | <TD><TT>listS</TT></TD> | |
141 | </TR> | |
142 | ||
143 | </TABLE> | |
144 | <P> | |
145 | ||
146 | <H3>Model of</H3> | |
147 | ||
148 | <P> | |
149 | <a href="./VertexAndEdgeListGraph.html">VertexAndEdgeListGraph</a>, | |
150 | <a href="./MutablePropertyGraph.html">MutablePropertyGraph</a>, | |
151 | <a href="../../utility/CopyConstructible.html">CopyConstructible</a>, | |
152 | <a href="../../utility/Assignable.html">Assignable</a>, | |
153 | and <a href="../../serialization/doc/index.html">Serializable</a>. | |
154 | ||
155 | ||
156 | <P> | |
157 | ||
158 | <H3>Where Defined</H3> | |
159 | ||
160 | <P> | |
161 | <a href="../../../boost/graph/adjacency_list.hpp"><TT>boost/graph/adjacency_list.hpp</TT></a><br><br> | |
162 | Also, the serialization functionality is in | |
163 | <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>. | |
164 | <P> | |
165 | ||
166 | <H2>Vertex and Edge Properties</H2> | |
167 | ||
168 | <P> | |
169 | Properties such as color, distance, weight, and user-defined | |
170 | properties can be attached to the vertices and edges of the graph | |
171 | using properties. The property values can be read from and written to | |
172 | via the property maps provided by the graph. The property maps are | |
173 | obtained via the <TT>get(property, g)</TT> function. How to use | |
174 | properties is described in Section <A | |
175 | HREF="./using_adjacency_list.html#sec:adjacency-list-properties">Internal | |
176 | Properties </A>. The property maps are objects that implement the | |
177 | interface defined in Section <A | |
178 | HREF="../../property_map/doc/property_map.html">Property Map | |
179 | Concepts</A> or may be <a href="bundles.html">bundled properties</a>, | |
180 | which have a more succinct syntax. The types of all property values | |
181 | must be Copy Constructible, Assignable, and Default Constructible. | |
182 | The property maps obtained from the | |
183 | <TT>adjacency_list</TT> class are models of the <a | |
184 | href="../../property_map/doc/LvaluePropertyMap.html">Lvalue Property | |
185 | Map</a> concept. If the <TT>adjacency_list</TT> is const, | |
186 | then the property map is constant, otherwise the property | |
187 | map is mutable. | |
188 | ||
189 | <P> | |
190 | If the <TT>VertexList</TT> of the graph is <TT>vecS</TT>, then the | |
191 | graph has a builtin vertex indices accessed via the property map for | |
192 | the <TT>vertex_index_t</TT> property. The indices fall in the range | |
193 | <TT>[0, num_vertices(g))</TT> and are contiguous. When a vertex is | |
194 | removed the indices are adjusted so that they retain these | |
195 | properties. Some care must be taken when using these indices to access | |
196 | exterior property storage. The property map for vertex index is a | |
197 | model of <a href="../../property_map/doc/ReadablePropertyMap.html">Readable | |
198 | Property Map</a>. | |
199 | ||
200 | <P> | |
201 | ||
202 | <h2>Iterator and Descriptor Stability/Invalidation</h2> | |
203 | ||
204 | Some care must be taken when changing the structure of a graph (via | |
205 | adding or removing edges). Depending on the type of | |
206 | <tt>adjacency_list</tt> and on the operation, some of the iterator or | |
207 | descriptor objects that point into the graph may become invalid. For | |
208 | example, the following code will result in undefined (bad) behavior: | |
209 | ||
210 | <pre> | |
211 | typedef adjacency_list<listS, vecS> Graph; <b>// VertexList=vecS</b> | |
212 | Graph G(N); | |
213 | <b>// Fill in the graph...</b> | |
214 | ||
215 | <b>// Attempt to remove all the vertices. Wrong!</b> | |
216 | graph_traits<Graph>::vertex_iterator vi, vi_end; | |
217 | for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) | |
218 | remove_vertex(*vi, G); | |
219 | ||
220 | <b>// Remove all the vertices. This is still wrong!</b> | |
221 | graph_traits<Graph>::vertex_iterator vi, vi_end, next; | |
222 | boost::tie(vi, vi_end) = vertices(G); | |
223 | for (next = vi; vi != vi_end; vi = next) { | |
224 | ++next; | |
225 | remove_vertex(*vi, G); | |
226 | } | |
227 | </pre> | |
228 | ||
229 | The reason this is a problem is that we are invoking | |
230 | <tt>remove_vertex()</tt>, which when used with an | |
231 | <tt>adjacency_list</tt> where <tt>VertexList=vecS</tt>, invalidates | |
232 | all iterators and descriptors for the graph (such as <tt>vi</tt> and | |
233 | <tt>vi_end</tt>), thereby causing trouble in subsequent iterations of | |
234 | the loop. | |
235 | ||
236 | <p> | |
237 | ||
238 | If we use a different kind of <tt>adjacency_list</tt>, where | |
239 | <tt>VertexList=listS</tt>, then the iterators are not invalidated by | |
240 | calling <tt>remove_vertex</tt> unless the iterator is pointing to the | |
241 | actual vertex that was removed. The following code demonstrates this. | |
242 | ||
243 | <pre> | |
244 | typedef adjacency_list<listS, listS> Graph; <b>// VertexList=listS</b> | |
245 | Graph G(N); | |
246 | <b>// Fill in the graph...</b> | |
247 | ||
248 | <b>// Attempt to remove all the vertices. Wrong!</b> | |
249 | graph_traits<Graph>::vertex_iterator vi, vi_end; | |
250 | for (boost::tie(vi, vi_end) = vertices(G); vi != vi_end; ++vi) | |
251 | remove_vertex(*vi, G); | |
252 | ||
253 | <b>// Remove all the vertices. This is OK.</b> | |
254 | graph_traits<Graph>::vertex_iterator vi, vi_end, next; | |
255 | boost::tie(vi, vi_end) = vertices(G); | |
256 | for (next = vi; vi != vi_end; vi = next) { | |
257 | ++next; | |
258 | remove_vertex(*vi, G); | |
259 | } | |
260 | </pre> | |
261 | ||
262 | <p> | |
263 | ||
264 | The stability issue also affects vertex and edge descriptors. For | |
265 | example, suppose you use vector of vertex descriptors to keep track of | |
266 | the parents (or predecessors) of vertices in a shortest paths tree | |
267 | (see <a | |
268 | href="../example/dijkstra-example.cpp"><tt>examples/dijkstra-example.cpp</tt></a>). | |
269 | You create the parent vector with a call to | |
270 | <tt>dijkstra_shortest_paths()</tt>, and then remove a vertex from the | |
271 | graph. Subsequently you try to use the parent vector, but since all | |
272 | vertex descriptors have become invalid, the result is incorrect. | |
273 | ||
274 | <pre> | |
275 | std::vector<Vertex> parent(num_vertices(G)); | |
276 | std::vector<Vertex> distance(num_vertices(G)); | |
277 | ||
278 | dijkstra_shortest_paths(G, s, distance_map(&distance[0]). | |
279 | predecessor_map(&parent[0])); | |
280 | ||
281 | remove_vertex(s, G); <b>// Bad idea! Invalidates vertex descriptors in parent vector.</b> | |
282 | ||
283 | <b>// The following will produce incorrect results</b> | |
284 | for(boost::tie(vi, vend) = vertices(G); vi != vend; ++vi) | |
285 | std::cout << p[*vi] << " is the parent of " << *vi << std::endl; | |
286 | </pre> | |
287 | ||
288 | ||
289 | <p> | |
290 | Note that in this discussion iterator and descriptor invalidation is | |
291 | concerned with the invalidation of iterators and descriptors that are | |
292 | <b>not directly affected</b> by the operation. For example, performing | |
293 | <tt>remove_edge(u, v, g)</tt> will always invalidate any edge | |
294 | descriptor for <i>(u,v)</i> or edge iterator pointing to <i>(u,v)</i>, | |
295 | regardless of the kind <tt>adjacency_list</tt>. In this discussion | |
296 | of iterator and descriptor invalidation, we are only concerned with the | |
297 | affect of <tt>remove_edge(u, v, g)</tt> on edge descriptors and | |
298 | iterators that point to other edges (not <i>(u,v)</i>). | |
299 | ||
300 | <p> | |
301 | In general, if you want your vertex and edge descriptors to be stable | |
302 | (never invalidated) then use <tt>listS</tt> or <tt>setS</tt> for the | |
303 | <tt>VertexList</tt> and <tt>OutEdgeList</tt> template parameters of | |
304 | <tt>adjacency_list</tt>. If you are not as concerned about descriptor | |
305 | and iterator stability, and are more concerned about memory | |
306 | consumption and graph traversal speed, use <tt>vecS</tt> for the | |
307 | <tt>VertexList</tt> and/or <tt>OutEdgeList</tt> template parameters. | |
308 | ||
309 | <p> | |
310 | The following table summarizes which operations cause descriptors and | |
311 | iterators to become invalid. In the table, <tt>EL</tt> is an | |
312 | abbreviation for <tt>OutEdgeList</tt> and <tt>VL</tt> means | |
313 | <tt>VertexList</tt>. The <b>Adj Iter</b> category includes the | |
314 | <tt>out_edge_iterator</tt>, <tt>in_edge_iterator</tt>, and | |
315 | <tt>adjacency_iterator</tt> types. A more detailed description of | |
316 | descriptor and iterator invalidation is given in the documentation for | |
317 | each operation. | |
318 | ||
319 | <p> | |
320 | ||
321 | <table border> | |
322 | <CAPTION ALIGN="BOTTOM"><STRONG>Table:</STRONG> | |
323 | Summary of Descriptor and Iterator Invalidation. | |
324 | </CAPTION> | |
325 | <tr> | |
326 | <th>Function</th> | |
327 | <th>Vertex Desc</th> | |
328 | <th>Edge Desc</th> | |
329 | <th>Vertex Iter</th> | |
330 | <th>Edge Iter</th> | |
331 | <th>Adj Iter</th> | |
332 | </tr> | |
333 | <tr> | |
334 | <td> | |
335 | <tt>add_edge()</tt></td> | |
336 | <td align=center><tt>OK</tt></td> | |
337 | <td align=center><tt>OK</tt></td> | |
338 | <td align=center><tt>OK</tt></td> | |
339 | <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td> | |
340 | <td align=center><tt>EL=vecS</tt></td> | |
341 | </tr> | |
342 | <tr> | |
343 | <td><tt>remove_edge()<br>remove_edge_if()<br>remove_out_edge_if()<br> | |
344 | remove_in_edge_if()<br>clear_vertex()</tt> | |
345 | </td> | |
346 | <td align=center><tt>OK</tt></td> | |
347 | <td align=center><tt>OK</tt></td> | |
348 | <td align=center><tt>OK</tt></td> | |
349 | <td align=center><tt>EL=vecS && <br>Directed=directedS</tt></td> | |
350 | <td align=center><tt>EL=vecS</tt></td> | |
351 | </tr> | |
352 | <tr> | |
353 | <td><tt>add_vertex()</tt></td> | |
354 | <td align=center><tt>OK</tt></td> | |
355 | <td align=center><tt>OK</tt></td> | |
356 | <td align=center><tt>OK</tt></td> | |
357 | <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td> | |
358 | <td align=center><tt>VL=vecS && <br/> Directed=directedS</tt></td> | |
359 | </tr> | |
360 | <tr> | |
361 | <td><tt>remove_vertex()</tt></td> | |
362 | <td align=center><tt>VL=vecS</tt></td> | |
363 | <td align=center><tt>VL=vecS</tt></td> | |
364 | <td align=center><tt>VL=vecS</tt></td> | |
365 | <td align=center><tt>VL=vecS</tt></td> | |
366 | <td align=center><tt>VL=vecS</tt></td> | |
367 | </tr> | |
368 | </table> | |
369 | ||
370 | <H2>Associated Types</H2> | |
371 | ||
372 | <hr> | |
373 | ||
374 | <tt>graph_traits<adjacency_list>::vertex_descriptor</tt> | |
375 | <br> | |
376 | and | |
377 | <br> | |
378 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::vertex_descriptor</tt> | |
379 | <br><br> | |
380 | The type for the vertex descriptors associated with the | |
381 | <TT>adjacency_list</TT>. | |
382 | ||
383 | <hr> | |
384 | ||
385 | <tt>graph_traits<adjacency_list>::edge_descriptor</tt><br> | |
386 | and<br> | |
387 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_descriptor</tt> | |
388 | <br><br> | |
389 | The type for the edge descriptors associated with the | |
390 | <TT>adjacency_list</TT>. | |
391 | ||
392 | <hr> | |
393 | ||
394 | <tt>graph_traits<adjacency_list>::vertex_iterator</tt> | |
395 | <br><br> | |
396 | The type for the iterators returned by <TT>vertices()</TT>. | |
397 | ||
398 | When <tt>VertexList=vecS</tt> then the <tt>vertex_iterator</tt> models | |
399 | <a | |
400 | href="http://www.sgi.com/tech/stl/RandomAccessIterator.html">RandomAccessIterator</a>. Otherwise | |
401 | the <tt>vertex_iterator</tt> models <a | |
402 | href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>. | |
403 | ||
404 | <hr> | |
405 | ||
406 | <tt>graph_traits<adjacency_list>::edge_iterator</tt> | |
407 | <br><br> | |
408 | The type for the iterators returned by <TT>edges()</TT>. | |
409 | The <tt>edge_iterator</tt> models <a | |
410 | href="http://www.sgi.com/tech/stl/BidirectionalIterator.html">BidirectionalIterator</a>. | |
411 | ||
412 | ||
413 | <hr> | |
414 | ||
415 | ||
416 | <tt>graph_traits<adjacency_list>::out_edge_iterator</tt> | |
417 | <br><br> | |
418 | ||
419 | The type for the iterators returned by <TT>out_edges()</TT>. | |
420 | When <tt>OutEdgeList=vecS</tt> then the <tt>out_edge_iterator</tt> models | |
421 | <a href="http://www.sgi.com/tech/stl/RandomAccessIterator.html"> | |
422 | RandomAccessIterator</a>. When <tt>OutEdgeList=slistS</tt> then the | |
423 | <tt>out_edge_iterator</tt> models <a | |
424 | href="http://www.sgi.com/tech/stl/ForwardIterator.html"> | |
425 | ForwardIterator</a>. Otherwise the <tt>out_edge_iterator</tt> models | |
426 | <a | |
427 | href="http://www.sgi.com/tech/stl/BidirectionalIterator.html"> | |
428 | BidirectionalIterator</a>. | |
429 | ||
430 | <hr> | |
431 | ||
432 | <tt>graph_traits<adjacency_list>::adjacency_iterator</tt> | |
433 | <br><br> | |
434 | The type for the iterators returned by <TT>adjacent_vertices()</TT>. | |
435 | The <tt>adjacency_iterator</tt> models the same iterator concept | |
436 | as <tt>out_edge_iterator</tt>. | |
437 | <hr> | |
438 | ||
439 | <tt>adjacency_list::inv_adjacency_iterator</tt> | |
440 | <br><br> | |
441 | The type for the iterators returned by <TT>inv_adjacent_vertices()</TT>. | |
442 | The <tt>inv_adjacency_iterator</tt> models the same iterator concept | |
443 | as <tt>out_edge_iterator</tt>. | |
444 | <hr> | |
445 | ||
446 | <tt>graph_traits<adjacency_list>::directed_category</tt><br> | |
447 | and<br> | |
448 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::directed_category</tt> | |
449 | <br><br> | |
450 | Provides information about whether the graph is | |
451 | directed (<TT>directed_tag</TT>) or undirected | |
452 | (<TT>undirected_tag</TT>). | |
453 | ||
454 | <hr> | |
455 | ||
456 | <tt>graph_traits<adjacency_list>::edge_parallel_category</tt><br> | |
457 | and<br> | |
458 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed, EdgeList>::edge_parallel_category</tt> | |
459 | <br><br> | |
460 | This describes whether the graph class allows the insertion of | |
461 | parallel edges (edges with the same source and target). The two tags | |
462 | are <TT>allow_parallel_edge_tag</TT> and | |
463 | <TT>disallow_parallel_edge_tag</TT>. The | |
464 | <TT>setS</TT> and <TT>hash_setS</TT> variants disallow | |
465 | parallel edges while the others allow parallel edges. | |
466 | ||
467 | <hr> | |
468 | ||
469 | <tt>graph_traits<adjacency_list>::vertices_size_type</tt><br> | |
470 | and<br> | |
471 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::vertices_size_type</tt><br> | |
472 | <br><br> | |
473 | The type used for dealing with the number of vertices in the graph. | |
474 | ||
475 | <hr> | |
476 | ||
477 | <tt>graph_traits<adjacency_list>::edges_size_type</tt><br> | |
478 | and<br> | |
479 | <tt>adjacency_list_traits<OutEdgeList, VertexList, Directed_list, EdgeList>::edges_size_type</tt><br> | |
480 | <br><br> | |
481 | The type used for dealing with the number of edges in the graph. | |
482 | ||
483 | <hr> | |
484 | ||
485 | <tt>graph_traits<adjacency_list>::degree_size_type</tt> | |
486 | <br><br> | |
487 | The type used for dealing with the number of edges incident to a vertex | |
488 | in the graph. | |
489 | ||
490 | <hr> | |
491 | ||
492 | <tt>property_map<adjacency_list, Property>::type</tt><br> | |
493 | and<br> | |
494 | <tt>property_map<adjacency_list, Property>::const_type</tt> | |
495 | <br><br> | |
496 | The property map type for vertex or edge properties in the graph. The | |
497 | specific property is specified by the <TT>Property</TT> template argument, | |
498 | and must match one of the properties specified in the | |
499 | <TT>VertexProperties</TT> or <TT>EdgeProperties</TT> for the graph. | |
500 | ||
501 | <hr> | |
502 | ||
503 | <tt>graph_property<adjacency_list, Property>::type</tt> | |
504 | <br><br> | |
505 | The property value type for the graph property specified by the | |
506 | <tt>Property</tt> tag. | |
507 | ||
508 | <hr> | |
509 | ||
510 | <tt>adjacency_list::out_edge_list_selector</tt> | |
511 | <br><br> | |
512 | The type <tt>OutEdgeListS</tt>. | |
513 | ||
514 | <hr> | |
515 | ||
516 | <tt>adjacency_list::vertex_list_selector</tt> | |
517 | <br><br> | |
518 | The type <tt>VertexListS</tt>. | |
519 | ||
520 | <hr> | |
521 | ||
522 | <tt>adjacency_list::directed_selector</tt> | |
523 | <br><br> | |
524 | The type <tt>DirectedS</tt>. | |
525 | ||
526 | <hr> | |
527 | ||
528 | <tt>adjacency_list::edge_list_selector</tt> | |
529 | <br><br> | |
530 | The type <tt>EdgeListS</tt>. | |
531 | ||
532 | <hr> | |
533 | ||
534 | <H2>Member Functions</H2> | |
535 | ||
536 | <hr> | |
537 | ||
538 | <pre> | |
539 | adjacency_list(const GraphProperty& p = GraphProperty()) | |
540 | </pre> | |
541 | Default constructor. Creates an empty graph object with zero vertices | |
542 | and zero edges. | |
543 | ||
544 | <hr> | |
545 | ||
546 | <pre> | |
547 | adjacency_list(const adjacency_list& x) | |
548 | </pre> | |
549 | Copy constructor. Creates a new graph that is a copy of graph | |
550 | <tt>x</tt>, including the edges, vertices, and properties. | |
551 | ||
552 | <hr> | |
553 | ||
554 | <pre> | |
555 | adjacency_list& operator=(const adjacency_list& x) | |
556 | </pre> | |
557 | Assignment operator. Makes this graph a copy of graph | |
558 | <tt>x</tt>, including the edges, vertices, and properties. | |
559 | ||
560 | <hr> | |
561 | ||
562 | <pre> | |
563 | adjacency_list(vertices_size_type n, | |
564 | const GraphProperty& p = GraphProperty()) | |
565 | </pre> | |
566 | Creates a graph object with <TT>n</TT> vertices and zero edges. | |
567 | ||
568 | <hr> | |
569 | ||
570 | <a name="sec:iterator-constructor"> | |
571 | <pre> | |
572 | template <class EdgeIterator> | |
573 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
574 | vertices_size_type n, | |
575 | edges_size_type m = 0, | |
576 | const GraphProperty& p = GraphProperty()) | |
577 | </pre> | |
578 | Creates a graph object with <TT>n</TT> vertices and with the edges | |
579 | specified in the edge list given by the range <TT>[first, last)</TT>. | |
580 | The <tt>EdgeIterator</tt> must be a model of <a | |
581 | href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
582 | The value type of the <TT>EdgeIterator</TT> must be a | |
583 | <TT>std::pair</TT>, where the type in the pair is an integer type. The | |
584 | integers will correspond to vertices, and they must all fall in the | |
585 | range of <TT>[0, n)</TT>. | |
586 | </a> | |
587 | ||
588 | <hr> | |
589 | ||
590 | <pre> | |
591 | template <class EdgeIterator, class EdgePropertyIterator> | |
592 | adjacency_list(EdgeIterator first, EdgeIterator last, | |
593 | EdgePropertyIterator ep_iter, | |
594 | vertices_size_type n, | |
595 | edges_size_type m = 0, | |
596 | const GraphProperty& p = GraphProperty()) | |
597 | </pre> | |
598 | Creates a graph object with <TT>n</TT> vertices and with the edges | |
599 | specified in the edge list given by the range <TT>[first, last)</TT>. | |
600 | The <tt>EdgeIterator</tt> and <tt>EdgePropertyIterator</tt> must be a | |
601 | model of <a | |
602 | href="http://www.sgi.com/tech/stl/InputIterator.html">InputIterator</a>. | |
603 | The value type of the <TT>EdgeIterator</TT> must be a | |
604 | <TT>std::pair</TT>, where the type in the pair is an integer type. The | |
605 | integers will correspond to vertices, and they must all fall in the | |
606 | range of <TT>[0, n)</TT>. The <TT>value_type</TT> of the | |
607 | <TT>ep_iter</TT> should be <TT>EdgeProperties</TT>. | |
608 | ||
609 | <hr> | |
610 | ||
611 | <pre> | |
612 | void clear() | |
613 | </pre> | |
614 | Remove all of the edges and vertices from the graph. | |
615 | ||
616 | <hr> | |
617 | ||
618 | <pre> | |
619 | void swap(adjacency_list& x) | |
620 | </pre> | |
621 | Swap the vertices, edges, and properties of this graph with the | |
622 | vertices, edges, and properties of graph <tt>x</tt>. | |
623 | <hr> | |
624 | ||
625 | <P> | |
626 | ||
627 | <H2>Non-Member Functions</H2> | |
628 | ||
629 | ||
630 | <h4>Structure Access</h4> | |
631 | ||
632 | <hr> | |
633 | ||
634 | <pre> | |
635 | std::pair<vertex_iterator, vertex_iterator> | |
636 | vertices(const adjacency_list& g) | |
637 | </pre> | |
638 | Returns an iterator-range providing access to the vertex set of graph | |
639 | <tt>g</tt>. | |
640 | ||
641 | <hr> | |
642 | ||
643 | <pre> | |
644 | std::pair<edge_iterator, edge_iterator> | |
645 | edges(const adjacency_list& g) | |
646 | </pre> | |
647 | Returns an iterator-range providing access to the edge set of graph | |
648 | <tt>g</tt>. | |
649 | ||
650 | <hr> | |
651 | ||
652 | <pre> | |
653 | std::pair<adjacency_iterator, adjacency_iterator> | |
654 | adjacent_vertices(vertex_descriptor u, const adjacency_list& g) | |
655 | </pre> | |
656 | Returns an iterator-range providing access to the vertices adjacent to | |
657 | vertex <tt>u</tt> in graph <tt>g</tt>. For example, if <tt>u -> v</tt> | |
658 | is an edge in the graph, then <tt>v</tt> will be in this iterator-range. | |
659 | ||
660 | <hr> | |
661 | ||
662 | <pre> | |
663 | std::pair<inv_adjacency_iterator, inv_adjacency_iterator> | |
664 | inv_adjacent_vertices(vertex_descriptor u, const adjacency_list& g) | |
665 | </pre> | |
666 | ||
667 | Returns an iterator-range providing access to the vertices in graph | |
668 | <tt>g</tt> to which <tt>u</tt> is adjacent. (<tt>inv</tt> is for | |
669 | inverse.) For example, if <tt>v -> u</tt> is an edge in the graph, | |
670 | then <tt>v</tt> will be in this iterator range. This function is only | |
671 | available for bidirectional and undirected <tt>adjacency_list</tt>'s. | |
672 | ||
673 | <hr> | |
674 | ||
675 | ||
676 | <pre> | |
677 | std::pair<out_edge_iterator, out_edge_iterator> | |
678 | out_edges(vertex_descriptor u, const adjacency_list& g) | |
679 | </pre> | |
680 | Returns an iterator-range providing access to the out-edges of vertex | |
681 | <tt>u</tt> in graph <tt>g</tt>. If the graph is undirected, this | |
682 | iterator-range provides access to all edges incident on vertex | |
683 | <tt>u</tt>. For both directed and undirected graphs, for an out-edge | |
684 | <tt>e</tt>, <tt>source(e, g) == u</tt> and <tt>target(e, g) == v</tt> | |
685 | where <tt>v</tt> is a vertex adjacent to <tt>u</tt>. | |
686 | ||
687 | <hr> | |
688 | ||
689 | <pre> | |
690 | std::pair<in_edge_iterator, in_edge_iterator> | |
691 | in_edges(vertex_descriptor v, const adjacency_list& g) | |
692 | </pre> | |
693 | Returns an iterator-range providing access to the in-edges of vertex | |
694 | <tt>v</tt> in graph <tt>g</tt>. This operation is only available if | |
695 | <TT>bidirectionalS</TT> was specified for the <TT>Directed</TT> | |
696 | template parameter. For an in-edge <tt>e</tt>, <tt>target(e, g) == v</tt> | |
697 | and <tt>source(e, g) == u</tt> for some vertex <tt>u</tt> that is | |
698 | adjacent to <tt>v</tt>, whether the graph is directed or undirected. | |
699 | ||
700 | <hr> | |
701 | ||
702 | <pre> | |
703 | vertex_descriptor | |
704 | source(edge_descriptor e, const adjacency_list& g) | |
705 | </pre> | |
706 | Returns the source vertex of edge <tt>e</tt>. | |
707 | ||
708 | <hr> | |
709 | ||
710 | <pre> | |
711 | vertex_descriptor | |
712 | target(edge_descriptor e, const adjacency_list& g) | |
713 | </pre> | |
714 | Returns the target vertex of edge <tt>e</tt>. | |
715 | ||
716 | <hr> | |
717 | ||
718 | <pre> | |
719 | degree_size_type | |
720 | out_degree(vertex_descriptor u, const adjacency_list& g) | |
721 | </pre> | |
722 | Returns the number of edges leaving vertex <tt>u</tt>. | |
723 | ||
724 | <hr> | |
725 | ||
726 | <pre> | |
727 | degree_size_type | |
728 | in_degree(vertex_descriptor u, const adjacency_list& g) | |
729 | </pre> | |
730 | Returns the number of edges entering vertex <tt>u</tt>. This operation | |
731 | is only available if <TT>bidirectionalS</TT> was specified for | |
732 | the <TT>Directed</TT> template parameter. | |
733 | ||
734 | <hr> | |
735 | ||
736 | <pre> | |
737 | vertices_size_type | |
738 | num_vertices(const adjacency_list& g) | |
739 | </pre> | |
740 | Returns the number of vertices in the graph <tt>g</tt>. | |
741 | ||
742 | <hr> | |
743 | ||
744 | <pre> | |
745 | edges_size_type | |
746 | num_edges(const adjacency_list& g) | |
747 | </pre> | |
748 | Returns the number of edges in the graph <tt>g</tt>. | |
749 | ||
750 | <hr> | |
751 | ||
752 | <pre> | |
753 | vertex_descriptor | |
754 | vertex(vertices_size_type n, const adjacency_list& g) | |
755 | </pre> | |
756 | Returns the nth vertex in the graph's vertex list. | |
757 | ||
758 | <hr> | |
759 | ||
760 | ||
761 | <pre> | |
762 | std::pair<edge_descriptor, bool> | |
763 | edge(vertex_descriptor u, vertex_descriptor v, | |
764 | const adjacency_list& g) | |
765 | </pre> | |
766 | If an edge from vertex <tt>u</tt> to vertex <tt>v</tt> exists, return a pair | |
767 | containing one such edge and <tt>true</tt>. If there are no edges between | |
768 | <tt>u</tt> and <tt>v</tt>, return a pair with an arbitrary edge descriptor and | |
769 | <tt>false</tt>. | |
770 | ||
771 | <hr> | |
772 | ||
773 | <pre> | |
774 | std::pair<out_edge_iterator, out_edge_iterator> | |
775 | edge_range(vertex_descriptor u, vertex_descriptor v, | |
776 | const adjacency_list& g) | |
777 | </pre> | |
778 | Returns a pair of out-edge iterators that give the range for | |
779 | all the parallel edges from <tt>u</tt> to <tt>v</tt>. This | |
780 | function only works when the <tt>OutEdgeList</tt> for the | |
781 | <tt>adjacency_list</tt> is a container that sorts the | |
782 | out edges according to target vertex, and allows for | |
783 | parallel edges. The <tt>multisetS</tt> selector chooses | |
784 | such a container. | |
785 | ||
786 | <hr> | |
787 | ||
788 | <h4>Structure Modification</h4> | |
789 | ||
790 | <hr> | |
791 | ||
792 | <pre> | |
793 | std::pair<edge_descriptor, bool> | |
794 | add_edge(vertex_descriptor u, vertex_descriptor v, | |
795 | adjacency_list& g) | |
796 | </pre> | |
797 | Adds edge <i>(u,v)</i> to the graph and returns the edge descriptor | |
798 | for the new edge. For graphs that do not allow parallel edges, if the | |
799 | edge is already in the graph then a duplicate will not be added and | |
800 | the <TT>bool</TT> flag will be <TT>false</TT>. When the flag is | |
801 | <TT>false</TT>, the | |
802 | returned edge descriptor points to the already existing edge. | |
803 | ||
804 | <p> | |
805 | The placement of the new edge in the out-edge list is in general | |
806 | unspecified, though ordering of the out-edge list can be accomplished | |
807 | through the choice of <tt>OutEdgeList</tt>. | |
808 | ||
809 | If the <tt>VertexList</tt> selector is | |
810 | <tt>vecS</tt>, and if either vertex descriptor <tt>u</tt> or | |
811 | <tt>v</tt> (which are integers) has a value greater than the current | |
812 | number of vertices in the graph, the graph is enlarged so that the | |
813 | number of vertices is <tt>std::max(u,v) + 1</tt>. | |
814 | ||
815 | <p> | |
816 | If the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation | |
817 | will invalidate any <tt>out_edge_iterator</tt> for vertex | |
818 | <i>u</i>. This also applies if the <TT>OutEdgeList</TT> is a user-defined | |
819 | container that invalidates its iterators when <TT>push(container, | |
820 | x)</TT> is invoked (see Section <A | |
821 | HREF="./using_adjacency_list.html#sec:custom-storage">Customizing the | |
822 | Adjacency List Storage</A>). If the graph is also bidirectional then | |
823 | any <tt>in_edge_iterator</tt> for <i>v</i> is also invalidated. If | |
824 | instead the graph is undirected then any <tt>out_edge_iterator</tt> | |
825 | for <i>v</i> is also invalidated. If instead the graph is directed, | |
826 | then <tt>add_edge()</tt> also invalidates any <tt>edge_iterator</tt>. | |
827 | ||
828 | ||
829 | <hr> | |
830 | ||
831 | <pre> | |
832 | std::pair<edge_descriptor, bool> | |
833 | add_edge(vertex_descriptor u, vertex_descriptor v, | |
834 | const EdgeProperties& p, | |
835 | adjacency_list& g) | |
836 | </pre> | |
837 | Adds edge <i>(u,v)</i> to the graph and attaches <TT>p</TT> as the | |
838 | value of the edge's internal property storage. Also see the previous | |
839 | <TT>add_edge()</TT> non-member function for more details. | |
840 | ||
841 | <hr> | |
842 | ||
843 | <pre> | |
844 | void remove_edge(vertex_descriptor u, vertex_descriptor v, | |
845 | adjacency_list& g) | |
846 | </pre> | |
847 | Removes the edge <i>(u,v)</i> from the graph. | |
848 | <p> | |
849 | This operation causes any outstanding edge descriptors or iterators | |
850 | that point to edge <i>(u,v)</i> to become invalid. In addition, if | |
851 | the <TT>OutEdgeList</TT> selector is <TT>vecS</TT> then this operation | |
852 | will invalidate any iterators that point into the edge-list for vertex | |
853 | <i>u</i> and also for vertex <i>v</i> in the undirected and | |
854 | bidirectional case. Also, for directed graphs this invalidates any | |
855 | <tt>edge_iterator</tt>. | |
856 | ||
857 | <hr> | |
858 | ||
859 | <pre> | |
860 | void remove_edge(edge_descriptor e, adjacency_list& g) | |
861 | </pre> | |
862 | Removes the edge <tt>e</tt> from the graph. This differs from the | |
863 | <tt>remove_edge(u, v, g)</tt> function in the case of a | |
864 | multigraph. This <tt>remove_edge(e, g)</tt> function removes a single | |
865 | edge, whereas the <tt>remove_edge(u, v, g)</tt> function removes all | |
866 | edges <i>(u,v)</i>. | |
867 | <p> | |
868 | This operation invalidates any outstanding edge descriptors and | |
869 | iterators for the same edge pointed to by descriptor <tt>e</tt>. In | |
870 | addition, this operation will invalidate any iterators that point into | |
871 | the edge-list for the <tt>target(e, g)</tt>. Also, for directed | |
872 | graphs this invalidates any <tt>edge_iterator</tt> for the graph. | |
873 | ||
874 | <hr> | |
875 | ||
876 | <pre> | |
877 | void remove_edge(out_edge_iterator iter, adjacency_list& g) | |
878 | </pre> | |
879 | This has the same effect as <tt>remove_edge(*iter, g)</tt>. The | |
880 | difference is that this function has constant time complexity | |
881 | in the case of directed graphs, whereas <tt>remove_edge(e, g)</tt> | |
882 | has time complexity <i>O(E/V)</i>. | |
883 | ||
884 | <hr> | |
885 | ||
886 | <pre> | |
887 | template <class <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>> | |
888 | void remove_out_edge_if(vertex_descriptor u, Predicate predicate, | |
889 | adjacency_list& g) | |
890 | </pre> | |
891 | Removes all out-edges of vertex <i>u</i> from the graph that satisfy | |
892 | the <tt>predicate</tt>. That is, if the predicate returns true when | |
893 | applied to an edge descriptor, then the edge is removed. | |
894 | <p> | |
895 | The affect on descriptor and iterator stability is the same as that of | |
896 | invoking <tt>remove_edge()</tt> on each of the removed edges. | |
897 | ||
898 | <hr> | |
899 | ||
900 | <pre> | |
901 | template <class <a | |
902 | href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>> | |
903 | void remove_in_edge_if(vertex_descriptor v, Predicate predicate, | |
904 | adjacency_list& g) | |
905 | </pre> | |
906 | Removes all in-edges of vertex <i>v</i> from the graph that satisfy | |
907 | the <tt>predicate</tt>. That is, if the predicate returns true when | |
908 | applied to an edge descriptor, then the edge is removed. | |
909 | <p> | |
910 | The affect on descriptor and iterator stability is the | |
911 | same as that of invoking <tt>remove_edge()</tt> on each of the | |
912 | removed edges. | |
913 | <p> | |
914 | This operation is available for undirected and bidirectional | |
915 | <tt>adjacency_list</tt> graphs, but not for directed. | |
916 | ||
917 | <hr> | |
918 | ||
919 | <pre> | |
920 | template <class <a href="http://www.sgi.com/tech/stl/Predicate.html">Predicate</a>> | |
921 | void remove_edge_if(Predicate predicate, adjacency_list& g) | |
922 | </pre> | |
923 | Removes all edges from the graph that satisfy | |
924 | the <tt>predicate</tt>. That is, if the predicate returns true when | |
925 | applied to an edge descriptor, then the edge is removed. | |
926 | <p> | |
927 | The affect on descriptor and iterator stability is the same as that of | |
928 | invoking <tt>remove_edge()</tt> on each of the removed edges. | |
929 | ||
930 | <hr> | |
931 | ||
932 | <a name="sec:add-vertex"> | |
933 | <pre> | |
934 | vertex_descriptor | |
935 | add_vertex(adjacency_list& g) | |
936 | </pre> | |
937 | Adds a vertex to the graph and returns the vertex descriptor for the | |
938 | new vertex. | |
939 | </a> | |
940 | ||
941 | <hr> | |
942 | ||
943 | <pre> | |
944 | vertex_descriptor | |
945 | add_vertex(const VertexProperties& p, | |
946 | adjacency_list& g) | |
947 | </pre> | |
948 | Adds a vertex to the graph with the specified properties. Returns the | |
949 | vertex descriptor for the new vertex. | |
950 | </a> | |
951 | ||
952 | <hr> | |
953 | ||
954 | <pre> | |
955 | void clear_vertex(vertex_descriptor u, adjacency_list& g) | |
956 | </pre> | |
957 | Removes all edges to and from vertex <i>u</i>. The vertex still appears | |
958 | in the vertex set of the graph. | |
959 | <p> | |
960 | The affect on descriptor and iterator stability is the | |
961 | same as that of invoking <tt>remove_edge()</tt> for all of | |
962 | the edges that have <tt>u</tt> as the source or target. | |
963 | ||
964 | <hr> | |
965 | ||
966 | <pre> | |
967 | void clear_out_edges(vertex_descriptor u, adjacency_list& g) | |
968 | </pre> | |
969 | Removes all out-edges from vertex <i>u</i>. The vertex still appears | |
970 | in the vertex set of the graph. | |
971 | <p> | |
972 | The affect on descriptor and iterator stability is the | |
973 | same as that of invoking <tt>remove_edge()</tt> for all of | |
974 | the edges that have <tt>u</tt> as the source. | |
975 | <p> | |
976 | This operation is not applicable to undirected graphs | |
977 | (use <tt>clear_vertex()</tt> instead). | |
978 | ||
979 | <hr> | |
980 | ||
981 | <pre> | |
982 | void clear_in_edges(vertex_descriptor u, adjacency_list& g) | |
983 | </pre> | |
984 | Removes all in-edges from vertex <i>u</i>. The vertex still appears | |
985 | in the vertex set of the graph. | |
986 | <p> | |
987 | The affect on descriptor and iterator stability is the | |
988 | same as that of invoking <tt>remove_edge()</tt> for all of | |
989 | the edges that have <tt>u</tt> as the target. | |
990 | <p> | |
991 | This operation is only applicable to bidirectional graphs. | |
992 | ||
993 | <hr> | |
994 | ||
995 | <pre> | |
996 | void remove_vertex(vertex_descriptor u, adjacency_list& g) | |
997 | </pre> | |
998 | Remove vertex <i>u</i> from the vertex set of the graph. It is assumed | |
999 | that there are no edges to or from vertex <i>u</i> when it is removed. | |
1000 | One way to make sure of this is to invoke <TT>clear_vertex()</TT> | |
1001 | beforehand. | |
1002 | <p> | |
1003 | If the <TT>VertexList</TT> template parameter of the | |
1004 | <TT>adjacency_list</TT> was <TT>vecS</TT>, then all vertex | |
1005 | descriptors, edge descriptors, and iterators for the graph are | |
1006 | invalidated by this operation. The builtin | |
1007 | <tt>vertex_index_t</tt> property for each vertex is renumbered so that | |
1008 | after the operation the vertex indices still form a contiguous range | |
1009 | <TT>[0, num_vertices(g))</TT>. If you are using external property | |
1010 | storage based on the builtin vertex index, then the external storage | |
1011 | will need to be adjusted. Another option is to not use the builtin | |
1012 | vertex index, and instead use a property to add your own vertex index | |
1013 | property. If you need to make frequent use of the | |
1014 | <TT>remove_vertex()</TT> function the <TT>listS</TT> selector is a | |
1015 | much better choice for the <TT>VertexList</TT> template parameter. | |
1016 | ||
1017 | <hr> | |
1018 | ||
1019 | <h4><a name="property-map-accessors">Property Map Accessors</a></h4> | |
1020 | ||
1021 | <hr> | |
1022 | ||
1023 | <pre> | |
1024 | template <class <a href="./PropertyTag.html">PropertyTag</a>> | |
1025 | property_map<adjacency_list, PropertyTag>::type | |
1026 | get(PropertyTag, adjacency_list& g) | |
1027 | ||
1028 | template <class <a href="./PropertyTag.html">PropertyTag</a>> | |
1029 | property_map<adjacency_list, Tag>::const_type | |
1030 | get(PropertyTag, const adjacency_list& g) | |
1031 | </pre> | |
1032 | Returns the property map object for the vertex property specified by | |
1033 | <TT>PropertyTag</TT>. The <TT>PropertyTag</TT> must match one of the | |
1034 | properties specified in the graph's <TT>VertexProperty</TT> template | |
1035 | argument. | |
1036 | ||
1037 | <hr> | |
1038 | ||
1039 | <pre> | |
1040 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X> | |
1041 | typename property_traits<property_map<adjacency_list, PropertyTag>::const_type>::value_type | |
1042 | get(PropertyTag, const adjacency_list& g, X x) | |
1043 | </pre> | |
1044 | This returns the property value for <tt>x</tt>, where <tt>x</tt> is either | |
1045 | a vertex or edge descriptor. | |
1046 | <hr> | |
1047 | ||
1048 | <pre> | |
1049 | template <class <a href="./PropertyTag.html">PropertyTag</a>, class X, class Value> | |
1050 | void | |
1051 | put(PropertyTag, const adjacency_list& g, X x, const Value& value) | |
1052 | </pre> | |
1053 | This sets the property value for <tt>x</tt> to | |
1054 | <tt>value</tt>. <tt>x</tt> is either a vertex or edge descriptor. | |
1055 | <tt>Value</tt> must be convertible to | |
1056 | <tt>typename property_traits<property_map<adjacency_list, PropertyTag>::type>::value_type</tt> | |
1057 | ||
1058 | <hr> | |
1059 | ||
1060 | <pre> | |
1061 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> | |
1062 | typename graph_property<adjacency_list, GraphPropertyTag>::type& | |
1063 | get_property(adjacency_list& g, GraphPropertyTag); | |
1064 | </pre> | |
1065 | Return the property specified by <tt>GraphPropertyTag</tt> that is | |
1066 | attached to the graph object <tt>g</tt>. The <tt>graph_property</tt> | |
1067 | traits class is defined in <a | |
1068 | href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>. | |
1069 | ||
1070 | <hr> | |
1071 | ||
1072 | <pre> | |
1073 | template <class GraphProperties, class <a href="./PropertyTag.html#GraphPropertyTag">GraphPropertyTag</a>> | |
1074 | const typename graph_property<adjacency_list, GraphPropertyTag>::type& | |
1075 | get_property(const adjacency_list& g, GraphPropertyTag); | |
1076 | </pre> | |
1077 | Return the property specified by <tt>GraphPropertyTag</tt> that is | |
1078 | attached to the graph object <tt>g</tt>. The <tt>graph_property</tt> | |
1079 | traits class is defined in <a | |
1080 | href="../../../boost/graph/adjacency_list.hpp"><tt>boost/graph/adjacency_list.hpp</tt></a>. | |
1081 | ||
1082 | <!-- add the shortcut property functions --> | |
1083 | ||
1084 | <hr> | |
1085 | ||
1086 | ||
1087 | ||
1088 | <h4><a name="serialization">Serialization</a></h4> | |
1089 | ||
1090 | <hr> | |
1091 | ||
1092 | <pre> | |
1093 | template<class <a href="../../serialization/doc/archives.html#saving_interface">SavingArchive</a>> | |
1094 | SavingArchive& operator<<(SavingArchive& ar, const adjacency_list& graph); | |
1095 | </pre> | |
1096 | Serializes the graph into the archive. Requires the vertex and edge properties of the | |
1097 | graph to be <a href="../../serialization/doc/index.html">Serializable</a>. | |
1098 | <br> | |
1099 | Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>. | |
1100 | <hr> | |
1101 | ||
1102 | <pre> | |
1103 | template<class <a href="../../serialization/doc/archives.html#loading_interface">LoadingArchive</a>> | |
1104 | LoadingArchive& operator>>(LoadingArchive& ar, const adjacency_list& graph); | |
1105 | </pre> | |
1106 | Reads the graph from the archive. Requires the vertex and edge properties of the | |
1107 | graph to be <a href="../../serialization/doc/index.html">Serializable</a>. | |
1108 | <br> | |
1109 | Include <a href="../../../boost/graph/adj_list_serialize.hpp"><tt>boost/graph/adj_list_serialize.hpp</tt></a>. | |
1110 | <hr> | |
1111 | ||
1112 | ||
1113 | <h3>See Also</h3> | |
1114 | ||
1115 | <a href="./adjacency_list_traits.html"><tt>adjacency_list_traits</tt></a>, | |
1116 | <a href="./property_map.html"><tt>property_map</tt></a>, | |
1117 | <a href="./graph_traits.html"><tt>graph_traits</tt></a> | |
1118 | ||
1119 | ||
1120 | ||
1121 | <br> | |
1122 | <HR> | |
1123 | <TABLE> | |
1124 | <TR valign=top> | |
1125 | <TD nowrap>Copyright © 2000-2001</TD><TD> | |
1126 | <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, | |
1127 | Indiana University (<A | |
1128 | HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br> | |
1129 | <A HREF="http://www.boost.org/people/liequan_lee.htm">Lie-Quan Lee</A>, Indiana University (<A HREF="mailto:llee@cs.indiana.edu">llee@cs.indiana.edu</A>)<br> | |
1130 | <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>, | |
1131 | Indiana University (<A | |
1132 | HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>) | |
1133 | </TD></TR></TABLE> | |
1134 | ||
1135 | </BODY> | |
1136 | </HTML> | |
1137 | <!-- LocalWords: gif ALT OutEdgeList EdgeList VertexList html VertexProperties EdgeProperties | |
1138 | --> | |
1139 | <!-- LocalWords: GraphPropertyTag cpp enum ai cout endl VertexAndEdgeListGraph | |
1140 | --> | |
1141 | <!-- LocalWords: MutablePropertyGraph hpp const ReadablePropertyMap listS num | |
1142 | --> | |
1143 | <!-- LocalWords: ReadWritePropertyMap vecS dijkstra ucs pre Adj Iter Desc ep | |
1144 | --> | |
1145 | <!-- LocalWords: EdgeIterator EdgePropertyIterator iter bool edge's IDs siek | |
1146 | --> | |
1147 | <!-- LocalWords: multigraph typename htm Univ Quan Lumsdaine | |
1148 | --> |