ceph/src/boost/libs/graph/doc/using_adjacency_list.html

   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>Using the Boost Graph Library</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="SECTION00830000000000000000"></A>
  19 <A NAME="sec:using-adjacency-list"></A>
  20 <BR>
  21 Using <TT>adjacency_list</TT>
  22 </H1>
  23
  24 This section describes the details of how use the
  25 <tt>adjacency_list</tt> class. The presentation is divided into the
  26 following topics:
  27
  28 <OL>
  29 <li><A href="#sec:choosing-graph-type">Choosing the <TT>Edgelist</TT> and <TT>VertexList</TT></A>
  30 <li><a href="#sec:directed-and-undirected">Directed and Undirected
  31 Adjacency Lists</a>
  32 <li><A href="#sec:adjacency-list-properties">Internal Properties</A>
  33 <li><A href="#sec:custom-storage">Customizing the Adjacency List Storage</A>
  34 </ol>
  35
  36 <P>
  37
  38 <H2><A NAME="SECTION00831000000000000000"></A>
  39 <A NAME="sec:choosing-graph-type"></A>
  40 <BR>
  41 Choosing the <TT>Edgelist</TT> and <TT>VertexList</TT>
  42 </H2>
  43
  44 <P>
  45 This section focuses on how to decide which version of the <a
  46 href="./adjacency_list.html"><TT>adjacency_list</TT></a> class to use
  47 in different situations. The <TT>adjacency_list</TT> is like a
  48 swiss-army knife in that it can be configured in many ways. The
  49 parameters that we will focus on in this section are <TT>OutEdgeList</TT>
  50 and <TT>VertexList</TT>, which control the underlying data structures
  51 that will be used to represent the graph.  The choice of
  52 <TT>OutEdgeList</TT> and <TT>VertexList</TT> affects the time complexity
  53 of many of the graph operations and the space complexity of the graph
  54 object.
  55
  56 <P>
  57 BGL uses containers from the STL such as
  58 <a href="http://www.sgi.com/tech/stl/Vector.html"><TT>std::vector</TT></a>,
  59 <a href="http://www.sgi.com/tech/stl/List.html"><TT>std::list</TT></a>,
  60 and <a href="http://www.sgi.com/tech/stl/set.html"><TT>std::set</TT></a>
  61 to represent the set of vertices and the adjacency structure
  62 (out-edges and in-edges) of the graph.  There are several selector
  63 types that are used to specify the choice of container for
  64 <TT>OutEdgeList</TT> and <TT>VertexList</TT>.
  65
  66 <P>
  67
  68 <UL>
  69 <LI><TT>vecS</TT> selects <TT>std::vector</TT>.</LI>
  70 <LI><TT>listS</TT> selects <TT>std::list</TT>.</LI>
  71 <LI><TT>slistS</TT> selects <TT>std::slist</TT>.</LI>
  72 <LI><TT>setS</TT> selects <TT>std::set</TT>.</LI>
  73 <LI><TT>multisetS</TT> selects <TT>std::multiset</TT>.</LI>
  74 <LI><TT>hash_setS</TT> selects <TT>boost::unordered_set</TT>.</LI>
  75 </UL>
  76
  77 <P>
  78
  79 <H3>Choosing the <TT>VertexList</TT> type</A></H3>
  80
  81 <P>
  82 The <TT>VertexList</TT> parameter determines what kind of container
  83 will be used to represent the vertex set, or two-dimensional structure
  84 of the graph.  The container must model <a
  85 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a> or
  86 <a
  87 href="http://www.sgi.com/tech/stl/RandomAccessContainer.html">RandomAccessContainer</a>. In
  88 general, <TT>listS</TT> is a good choice if you need to add and remove
  89 vertices quickly. The price for this is extra space overhead compared
  90 to choosing <TT>vecS</TT>.
  91
  92 <P>
  93
  94 <H4>Space Complexity</H4>
  95
  96 <P>
  97 The <TT>std::list</TT> has a higher per-vertex space overhead than the
  98 <TT>std::vector</TT>, storing three extra pointers per vertex.
  99
 100 <P>
 101
 102 <H4>Time Complexity</H4>
 103
 104 <P>
 105 The choice of <TT>VertexList</TT> affects the time complexity of the
 106 following operations.
 107
 108 <ul>
 109
 110 <li>
 111 <pre>
 112 add_vertex()
 113 </PRE>
 114 This operation is amortized constant time for both <TT>vecS</TT> and
 115 <TT>listS</TT> (implemented with <TT>push_back()</TT>). However, when
 116 the <TT>VertexList</TT> type is <TT>vecS</TT> the time for this
 117 operation is occasionally large because the vector will be
 118 reallocated and the whole graph copied.
 119 <P></p>
 120
 121 <li>
 122 <PRE>
 123 remove_vertex()
 124 </PRE>
 125 This operation is constant time for <TT>listS</TT> and <i>O(V + E)</i> for
 126 <TT>vecS</TT>. The large time complexity for <TT>vecS</TT> is because
 127 the vertex descriptors (which in this case are indices that correspond
 128 to the vertices' place in the vertex list) must be adjusted in the
 129 out-edges for the whole graph.
 130 <P></P>
 131
 132 <li>
 133 <PRE>
 134 vertex()
 135 </PRE>
 136 This operation is constant time for <TT>vecS</TT> and  for
 137 <TT>listS</TT>.
 138
 139 </ul>
 140
 141
 142 <P>
 143
 144 <H3><A NAME="SECTION00831200000000000000">
 145 Choosing the <TT>OutEdgeList</TT> type</A>
 146 </H3>
 147
 148 <P>
 149 The <TT>OutEdgeList</TT> parameter determines what kind of container will
 150 be used to store the out-edges (and possibly in-edges) for each vertex
 151 in the graph. The containers used for edge lists must either satisfy
 152 the requirements for <a
 153 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a> or for
 154 <a
 155 href="http://www.sgi.com/tech/stl/AssociativeContainer.html">AssociativeContainer</a>.
 156
 157 <P>
 158 One of the first things to consider when choosing the
 159 <TT>OutEdgeList</TT> is whether you want <TT>adjacency_list</TT> to
 160 enforce the absence of parallel edges in the graph (that is, enforce
 161 that the graph not become a multi-graph). If you want this enforced
 162 then use the <TT>setS</TT> or <TT>hash_setS</TT> selectors.  If you
 163 want to represent a multi-graph, or know that you will not be
 164 inserting parallel edges into the graph, then choose one of the <a
 165 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a>
 166 types: <TT>vecS</TT>, <TT>listS</TT>, or <TT>slistS</TT>.
 167 You will also want to take into account the differences in time and space
 168 complexity for the various graph operations. Below we use <i>V</i> for
 169 the total number of vertices in the graph and <i>E</i> for the total
 170 number of edges.  Operations not discussed here are constant time.
 171
 172 <P>
 173
 174 <H4>Space Complexity</H4>
 175
 176 <P>
 177 The selection of the <TT>OutEdgeList</TT> affects the amount of space
 178 overhead per edge in the graph object. In the order of least space to
 179 most space, the selectors are <TT>vecS</TT>, <TT>slistS</TT>,
 180 <TT>listS</TT>, and <TT>setS</TT>.
 181
 182 <P>
 183
 184 <H4>Time Complexity</H4>
 185
 186 <P>
 187 In the following description of the time complexity for various
 188 operations, we use <i>E/V</i> inside of the ``big-O'' notation to
 189 express the length of an out-edge list. Strictly speaking this is not
 190 accurate because <i>E/V</i> merely gives the average number of edges
 191 per vertex in a random graph. The worst-case number of out-edges for a
 192 vertex is <i>V</i> (unless it is a multi-graph). For sparse graphs
 193 <i>E/V</i> is typically much smaller than <i>V</i> and can be
 194 considered a constant.
 195
 196 <P>
 197
 198 <P> <P>
 199 <UL>
 200 <LI>
 201 <PRE>
 202 add_edge()
 203 </PRE>
 204 When the <TT>OutEdgeList</TT> is a <a
 205 href="http://www.sgi.com/tech/stl/UniqueAssociativeContainer.html">UniqueAssociativeContainer</a>
 206 like <TT>std::set</TT> the absence of parallel edges is enforced when
 207 an edge is added. The extra lookup involved has time complexity
 208 <i>O(log(E/V))</i>. The <TT>OutEdgeList</TT> types that model <a
 209 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a> do
 210 not perform this check and therefore <TT>add_edge()</TT> is amortized
 211 constant time.  This means that it if you don't care whether the graph
 212 has parallel edges, or know that the input to the graph does not
 213 contain them, then it is better to use the sequence-based
 214 <TT>OutEdgeList</TT>. The <TT>add_edge()</TT> for the sequence-based
 215 <TT>OutEdgeList</TT> is implemented with <TT>push_front()</TT> or
 216 <TT>push_back()</TT>.  However, for <TT>std::list</TT> and
 217 <TT>std::slist</TT> this operation will typically be faster than with
 218 <TT>std::vector</TT> which occasionally reallocates and copies all
 219 elements.
 220 <p></p>
 221
 222 <li>
 223 <PRE>
 224 remove_edge()
 225 </PRE>
 226 For sequence-based <TT>OutEdgeList</TT> types this operation is
 227 implemented with <TT>std::remove_if()</TT> which means the average
 228 time is <i>E/V</i>. For set-based <TT>OutEdgeList</TT> types this is
 229 implemented with the <TT>erase()</TT> member function, which has
 230 average time <i>log(E/V)</i>.
 231 <p></p>
 232
 233 <li>
 234 <PRE>
 235 edge()
 236 </PRE>
 237 The time complexity for this operation is <i>O(E/V)</i> when the
 238 <TT>OutEdgeList</TT> type is a <a
 239 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a> and it
 240 is <i>O(log(E/V))</i> when the <TT>OutEdgeList</TT> type is an <a
 241 href="http://www.sgi.com/tech/stl/AssociativeContainer.html">AssociativeContainer</a>.
 242 <p></p>
 243
 244 <li>
 245 <PRE>
 246 clear_vertex()
 247 </PRE>
 248 For directed graphs with sequence-based <TT>OutEdgeList</TT> types the time
 249 complexity is <i>O(V + E)</i>, while for associative container based
 250 <TT>OutEdgeList</TT> types the operation is faster, with time complexity
 251 <i>O(V log(E/V))</i>.  For undirected graphs this operation is
 252 <i>O(E<sup>2</sup>/V<sup>2</sup>)</i> or <i>O(E/V log(E/V))</i>.
 253 <p></p>
 254
 255 <li>
 256 <PRE>
 257 remove_vertex()
 258 </PRE>
 259 The time complexity for this operation is <i>O(V + E)</i> regardless of the
 260 <TT>OutEdgeList</TT> type.
 261 <p></p>
 262
 263 <li>
 264 <PRE>
 265 out_edge_iterator::operator++()
 266 </PRE>
 267 This operation is constant time for all the <TT>OneD</TT> types.
 268 However, there is a significant constant factor time difference
 269 between the various types, which is important since this operation is
 270 the work-horse of most graph algorithms. The speed of
 271 this operation in order of fastest to slowest is
 272 <TT>vecS</TT>, <TT>slistS</TT>, <TT>listS</TT>, <TT>setS</TT>,
 273 <TT>hash_setS</TT>.
 274 <p></p>
 275
 276 <li>
 277 <PRE>
 278 in_edge_iterator::operator++()
 279 </PRE>
 280 This operation is constant time and exhibits a similar speed
 281 ordering as the <TT>out_edge_iterator</TT> with respect to
 282 the <TT>OutEdgeList</TT> selection.
 283 <p></p>
 284
 285 <li>
 286 <PRE>
 287 vertex_iterator::operator++()
 288 </PRE>
 289 This operation is constant time and fast (same speed as incrementing a
 290 pointer). The selection of <TT>OneD</TT> does not affect the speed of
 291 this operation.
 292 <p></p>
 293
 294 <li>
 295 <PRE>
 296 edge_iterator::operator++()
 297 </PRE>
 298 This operation is constant time and exhibits a similar speed ordering
 299 as the <TT>out_edge_iterator</TT> with respect to the <TT>OutEdgeList</TT>
 300 selection. Traversing through the whole edge set is <i>O(V + E)</i>.
 301 <p></p>
 302
 303 <li>
 304 <PRE>
 305 adjacency_iterator::operator++()
 306 </PRE>
 307 This operation is constant time and exhibits a similar speed
 308 ordering as the <TT>out_edge_iterator</TT> with respect to
 309 the <TT>OutEdgeList</TT> selection.
 310 <p></p>
 311
 312 </ul>
 313
 314 <P>
 315
 316 <P>
 317
 318 <H2><a name="sec:directed-and-undirected">Directed and Undirected Adjacency Lists</H2>
 319
 320 <P>
 321 The <TT>adjacency_list</TT> class can be used to represent both
 322 directed and undirected graphs, depending on the argument passed to
 323 the <TT>Directed</TT> template parameter. Selecting <TT>directedS</TT>
 324 or <TT>bidirectionalS</TT> choose a directed graph, whereas
 325 <TT>undirectedS</TT> selects the representation for an undirected
 326 graph.  See Section <A
 327 HREF="graph_concepts.html#sec:undirected-graphs">Undirected Graphs</A>
 328 for a description of the difference between directed and undirected
 329 graphs in BGL.  The <TT>bidirectionalS</TT> selector specifies that the
 330 graph will provide the <TT>in_edges()</TT> function as well as the
 331 <TT>out_edges()</TT> function. This imposes twice as much space
 332 overhead per edge, which is why <TT>in_edges()</TT> is optional.
 333
 334 <P>
 335
 336 <H2><A NAME="sec:adjacency-list-properties"></A>
 337 Internal Properties
 338 </H2>
 339
 340 <P>
 341 Properties can be attached to the vertices or edges of an
 342 <TT>adjacency_list</TT> graph via the property interface.  The template
 343 parameters <TT>VertexProperty</TT> and <TT>EdgeProperty</TT> of the
 344 <TT>adjacency_list</TT> class are meant to be filled by these interior
 345  properties.
 346
 347 <p><b>NOTE</b>: The Boost Graph Library supports two interchangeable methods for
 348 specifying interior properties: <a href="bundles.html">bundled properties</a>
 349 and property lists. The former is easier to use and requires less effort,
 350 whereas the latter is compatible with older, broken compilers and is
 351 backward-compatible with Boost versions prior to 1.32.0. If you absolutely
 352 require these compatibility features, read on to learn about property lists.
 353 Otherwise, we strongly suggest that you read about the <a href="bundles.html">bundled
 354 properties</a> mechanism.
 355
 356 <p>One may specify internal properties via property lists, which are build from instances of the
 357 property class declared as follows.
 358
 359 <P>
 360 <PRE>
 361 template &lt;class PropertyTag, class T, class NextProperty = no_property&gt;
 362 struct property;
 363 </PRE>
 364
 365 <P>
 366 The <a href="./PropertyTag.html"><TT>PropertyTag</TT></a> template
 367 parameter is a tag class that simply identifies or gives a unique name
 368 to the property. There are several predefined tags, and it is easy to
 369 add more.
 370
 371 <P>
 372 <PRE>
 373   struct vertex_index_t { };
 374   struct vertex_index1_t { };
 375   struct vertex_index2_t { };
 376   struct edge_index_t { };
 377   struct graph_name_t { };
 378   struct vertex_name_t { };
 379   struct edge_name_t { };
 380   struct edge_weight_t { };
 381   struct edge_weight2_t { };
 382   struct edge_capacity_t { };
 383   struct edge_residual_capacity_t { };
 384   struct edge_reverse_t { };
 385   struct vertex_distance_t { };
 386   struct vertex_root_t { };
 387   struct vertex_all_t { };
 388   struct edge_all_t { };
 389   struct graph_all_t { };
 390   struct vertex_color_t { };
 391   struct vertex_rank_t { };
 392   struct vertex_predecessor_t { };
 393   struct vertex_isomorphism_t { };
 394   struct vertex_invariant_t { };
 395   struct vertex_invariant1_t { };
 396   struct vertex_invariant2_t { };
 397   struct vertex_degree_t { };
 398   struct vertex_out_degree_t { };
 399   struct vertex_in_degree_t { };
 400   struct vertex_discover_time_t { };
 401   struct vertex_finish_time_t { };
 402 </PRE>
 403
 404 <P>
 405 The <b><TT>T</TT></b> template parameter of <TT>property</TT>
 406 specifies the type of the property values. The type <tt>T</tt> must be
 407 <a
 408 href="http://www.sgi.com/tech/stl/DefaultConstructible.html">Default
 409 Constructible</a>, <a
 410 href="../../utility/Assignable.html">Assignable</a>, and <a
 411 href="../../utility/CopyConstructible.html">Copy Constructible</a>.
 412 Like the containers of the C++ Standard Library, the property objects
 413 of type <tt>T</tt> are held by-value inside of the graph.
 414
 415 <p>
 416 The <b><TT>NextProperty</TT></b> parameter allows <TT>property</TT>
 417 types to be nested, so that an arbitrary number of properties can be
 418 attached to the same graph.
 419
 420 <P>
 421 The following code shows how a vertex and edge property type can be
 422 assembled and used to create a graph type. We have attached a distance
 423 property with values of type <TT>float</TT> and a name property with
 424 values of type <TT>std::string</TT> to the vertices of the graph.  We
 425 have attached a weight property with values of type <TT>float</TT> to
 426 the edges of the graph.
 427
 428 <P>
 429 <PRE>
 430   typedef property&lt;vertex_distance_t, float,
 431             property&lt;vertex_name_t, std::string&gt; &gt; VertexProperty;
 432   typedef property&lt;edge_weight_t, float&gt; EdgeProperty;
 433
 434   typedef adjacency_list&lt;mapS, vecS, undirectedS,
 435                          VertexProperty, EdgeProperty&gt; Graph;
 436
 437   Graph g(num_vertices); // construct a graph object
 438 </PRE>
 439
 440 <P>
 441 The property values are then read from and written to using property
 442 maps. See Section <A HREF="using_property_maps.html#sec:interior-properties">Interior
 443 Properties</A> for a description of how to obtain property maps
 444 from a graph, and read Section <A
 445 HREF="./using_property_maps.html">Property Maps</A> for how
 446 to use property maps.
 447
 448 <P>
 449
 450 <H3><A NAME="sec:custom-edge-properties"></A>
 451 Custom Edge Properties
 452 </H3>
 453
 454 <P>
 455 Creating your own property types and properties is easy; just define
 456 a tag class for your new property. The property tag class will need to
 457 define <tt>num</tt> with a unique integer ID, and <tt>kind</tt> which
 458 should be either <tt>edge_property_tag</tt>,
 459 <tt>vertex_property_tag</tt>, or <tt>graph_property_tag</tt>.
 460
 461 <P>
 462 <PRE>
 463 struct flow_t {
 464   typedef edge_property_tag kind;
 465 };
 466
 467 struct capacity_t {
 468   typedef edge_property_tag kind;
 469 };
 470 </PRE>
 471
 472 <p>
 473 You can also use enum's instead of struct's to create tag types. Create an enum
 474 type for each property inside the boost namespace. The first part of the name of
 475 the enum type must be <tt>edge</tt>, <tt>vertex</tt>, or <tt>graph</tt> followed
 476 by an underscore, the new property name, and a <tt>_t</tt> at the end. Inside
 477 the enum, define a value with the same name minus the <tt>_t</tt>. Then invoke
 478 the <tt>BOOST_INSTALL_PROPERTY</tt> macro.
 479
 480 <pre>
 481 namespace boost {
 482   enum edge_flow_t { edge_flow };
 483   enum edge_capacity_t { edge_capacity };
 484
 485   BOOST_INSTALL_PROPERTY(edge, flow);
 486   BOOST_INSTALL_PROPERTY(edge, capacity);
 487 }
 488 </pre>
 489
 490 <P>
 491 Now you can use your new property tag in the definition of properties just as
 492 you would one of the builtin tags.
 493
 494 <P>
 495 <PRE>
 496   typedef property&lt;capacity_t, int&gt; Cap;
 497   typedef property&lt;flow_t, int, Cap&gt; EdgeProperty;
 498   typedef adjacency_list&lt;vecS, vecS, no_property, EdgeProperty&gt; Graph;
 499 </PRE>
 500
 501 <P>
 502 Just as before, the property maps for these properties can be
 503 obtained from the graph via the
 504 <TT>get(Property, g)</TT> function.
 505
 506 <P>
 507 <PRE>
 508   property_map&lt;Graph, capacity_t&gt;::type capacity
 509     = get(capacity_t(), G);
 510   property_map&lt;Graph, flow_t&gt;::type flow
 511     = get(flow_t(), G);
 512 </PRE>
 513
 514 <P>
 515 The file <TT>edge_property.cpp</TT> shows the complete source
 516 code for this example.
 517
 518 <P>
 519
 520 <H3><A NAME="SECTION00833200000000000000"></A>
 521 <A NAME="sec:custom-vertex-properties"></A>
 522 <BR>
 523 Custom Vertex Properties
 524 </H3>
 525
 526 <P>
 527 Creating your own properties to attach to vertices is just as easy as
 528 for edges. Here we want to attach people's first names to the vertices
 529 in the graph.
 530
 531 <P>
 532 <PRE>
 533   struct first_name_t {
 534     typedef vertex_property_tag kind;
 535   };
 536 </PRE>
 537
 538 <P>
 539 Now we can use the new tag in the <TT>property</TT> class and use that in
 540 the assembly of a graph type. The following code shows creating the
 541 graph type, and then creating the graph object. We fill in the edges
 542 and also assign names to the vertices. The edges will represent ``who
 543 owes who''.
 544
 545 <P>
 546 <PRE>
 547   typedef property&lt;first_name_t, std::string&gt; FirstNameProperty;
 548   typedef adjacency_list&lt;vecS, vecS, directedS,
 549                          FirstNameProperty&gt; MyGraphType;
 550
 551   typedef pair&lt;int,int&gt; Pair;
 552   Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
 553                           Pair(0,4), Pair(2,0), Pair(3,0),
 554                           Pair(2,4), Pair(3,1), Pair(3,4),
 555                           Pair(4,0), Pair(4,1) };
 556
 557   MyGraphType G(5);
 558   for (int i = 0; i &lt; 11; ++i)
 559     add_edge(edge_array[i].first, edge_array[i].second, G);
 560
 561   property_map&lt;MyGraphType, first_name_t&gt;::type
 562     name = get(first_name_t(), G);
 563
 564   boost::put(name, 0, "Jeremy");
 565   boost::put(name, 1, "Rich");
 566   boost::put(name, 2, "Andrew");
 567   boost::put(name, 3, "Jeff");
 568   name[4] = "Kinis"; // you can use operator[] too
 569
 570   who_owes_who(edges(G).first, edges(G).second, G);
 571 </PRE>
 572
 573 <P>
 574 The <TT>who_owes_who()</TT> function written for this example was
 575 implemented in a generic style. The input is templated so we do not
 576 know the actual graph type. To find out the type of the property
 577 map for our first-name property, we need to use the
 578 <TT>property_map</TT> traits class. The <TT>const_type</TT>
 579 is used since the graph parameter is const. Once we have the property
 580 map type, we can deduce the value type of the property using the
 581 <TT>property_traits</TT> class. In this example, we know that the
 582 property's value type will be <TT>std::string</TT>, but written in this
 583 generic fashion the <TT>who_owes_who()</TT> function could work with
 584 other property value types.
 585
 586 <P>
 587 <PRE>
 588   template &lt;class EdgeIter, class Graph&gt;
 589   void who_owes_who(EdgeIter first, EdgeIter last, const Graph&amp; G)
 590   {
 591     // Access the propety acessor type for this graph
 592     typedef typename property_map&lt;Graph,
 593       first_name_t&gt;::const_type NameMap;
 594     NameMap name = get(first_name, G);
 595
 596     typedef typename boost::property_traits&lt;NameMap&gt;
 597       ::value_type NameType;
 598
 599     NameType src_name, targ_name;
 600
 601     while (first != last) {
 602       src_name = boost::get(name, source(*first, G));
 603       targ_name = boost::get(name, target(*first, G));
 604       cout &lt;&lt; src_name &lt;&lt; " owes "
 605            &lt;&lt; targ_name &lt;&lt; " some money" &lt;&lt; endl;
 606       ++first;
 607     }
 608 </PRE>
 609
 610 The output is:
 611 <PRE>
 612 Jeremy owes Rich some money
 613 Jeremy owes Andrew some money
 614 Jeremy owes Jeff some money
 615 Jeremy owes Kinis some money
 616 Andrew owes Jeremy some money
 617 Andrew owes Kinis some money
 618 Jeff owes Jeremy some money
 619 Jeff owes Rich some money
 620 Jeff owes Kinis some money
 621 Kinis owes Jeremy some money
 622 Kinis owes Rich some money
 623 </PRE>
 624
 625 The complete source code to this example is in the file
 626 <TT>interior_property_map.cpp</TT>.
 627
 628 <P>
 629
 630 <H2><A NAME="sec:custom-storage"></A>
 631 Customizing the Adjacency List Storage
 632 </H2>
 633
 634 <P>
 635 The <TT>adjacency_list</TT> is constructed out of two kinds of
 636 containers. One type of container to hold all the vertices in the
 637 graph, and another type of container for the out-edge list (and
 638 potentially in-edge list) for each vertex. BGL provides selector
 639 classes that allow the user to choose between several of the containers
 640 from the STL. It is also possible to use your own container types.
 641 When customizing the <TT>VertexList</TT> you need to define a container
 642 generator as described below. When customizing the <TT>OutEdgeList</TT> you
 643 will need to define a container generator and the parallel edge
 644 traits. The file <TT>container_gen.cpp</TT> has an example of
 645 how to use a custom storage type.
 646
 647 <P>
 648
 649 <H3><A NAME="SECTION00834100000000000000">
 650 Container Generator</A>
 651 </H3>
 652
 653 <P>
 654 The <TT>adjacency_list</TT> class uses a traits class called
 655 <TT>container_gen</TT> to map the <TT>OutEdgeList</TT> and <TT>VertexList</TT>
 656 selectors to the actual container types used for the graph storage.
 657 The default version of the traits class is listed below, along with an
 658 example of how the class is specialized for the <TT>listS</TT> selector.
 659
 660 <P>
 661 <PRE>
 662 namespace boost {
 663   template &lt;class Selector, class ValueType&gt;
 664   struct container_gen { };
 665
 666   template &lt;class ValueType&gt;
 667   struct container_gen&lt;listS, ValueType&gt; {
 668     typedef std::list&lt;ValueType&gt; type;
 669   };
 670 }
 671 </PRE>
 672
 673 <P>
 674 To use some other container of your choice, define a
 675 selector class and then specialize the <TT>container_gen</TT>
 676 for your selector.
 677
 678 <P>
 679 <PRE>
 680   struct custom_containerS { }; // your selector
 681
 682   namespace boost {
 683     // the specialization for your selector
 684     template &lt;class ValueType&gt;
 685     struct container_gen&lt;custom_containerS, ValueType&gt; {
 686       typedef custom_container&lt;ValueType&gt; type;
 687     };
 688   }
 689 </PRE>
 690
 691 <P>
 692 There may also be situations when you want to use a container that has
 693 more template parameters than just <TT>ValueType</TT>.  For instance,
 694 you may want to supply the allocator type. One way to do this is to
 695 hard-code in the extra parameters within the specialization of
 696 <TT>container_gen</TT>. However, if you want more flexibility then you
 697 can add a template parameter to the selector class. In the code below
 698 we show how to create a selector that lets you specify the allocator
 699 to be used with the <TT>std::list</TT>.
 700
 701 <P>
 702 <PRE>
 703   template &lt;class Allocator&gt;
 704   struct list_with_allocatorS { };
 705
 706   namespace boost {
 707     template &lt;class Alloc, class ValueType&gt;
 708     struct container_gen&lt;list_with_allocatorS&lt;Alloc&gt;, ValueType&gt;
 709     {
 710       typedef typename Alloc::template rebind&lt;ValueType&gt;::other Allocator;
 711       typedef std::list&lt;ValueType, Allocator&gt; type;
 712     };
 713   }
 714
 715   // now you can define a graph using std::list
 716   //   and a specific allocator
 717   typedef adjacency_list&lt; list_with_allocatorS&lt; std::allocator&lt;int&gt; &gt;, vecS, directedS&gt; MyGraph;
 718 </PRE>
 719
 720 <P>
 721
 722 <H3><A NAME="SECTION00834300000000000000">
 723 Push and Erase for the Custom Container</A>
 724 </H3>
 725
 726 <P>
 727 You must also tell the <TT>adjacency_list</TT> how elements can be
 728 efficiently added and removed from the custom container. This is
 729 accomplished by overloading the <TT>push()</TT> and <TT>erase()</TT>
 730 functions for the custom container type. The <TT>push()</TT> function
 731 should return an iterator pointing to the newly inserted element and a
 732 <TT>bool</TT> flag saying whether the edge was inserted.
 733
 734 <PRE>
 735   template &lt;class T&gt;
 736   std::pair&lt;typename custom_container&lt;T&gt;::iterator, bool&gt;
 737   push(custom_container&lt;T&gt;&amp; c, const T&amp; v)
 738   {
 739     // this implementation may need to change for your container
 740     c.push_back(v);
 741     return std::make_pair(boost::prior(c.end()), true);
 742   }
 743
 744   template &lt;class T&gt;
 745   void erase(custom_container&lt;T&gt;&amp; c, const T&amp; x)
 746   {
 747     // this implementation may need to change for your container
 748     c.erase(std::remove(c.begin(), c.end(), x), c.end());
 749   }
 750 </PRE>
 751
 752
 753 <P> There are default <TT>push()</TT> and <TT>erase()</TT> functions
 754 implemented for the STL container types.
 755
 756
 757 <H3><A NAME="SECTION00834200000000000000">
 758 Parallel Edge Traits</A>
 759 </H3>
 760
 761 <P>
 762 When customizing the <TT>OutEdgeList</TT>, you must also specialize
 763 the <TT>parallel_edge_traits</TT> class to specify whether the
 764 container type allows parallel edges (and is a <a
 765 href="http://www.sgi.com/tech/stl/Sequence.html">Sequence</a>) or if
 766 the container does not allow parallel edges (and is an <a
 767 href="http://www.sgi.com/tech/stl/AssociativeContainer.html">AssociativeContainer</a>).
 768
 769 <P>
 770 <PRE>
 771   template &lt;&gt;
 772   struct parallel_edge_traits&lt;custom_containerS&gt; {
 773     typedef allow_parallel_edge_tag type;
 774   };
 775 </PRE>
 776
 777
 778 <br>
 779 <HR>
 780 <TABLE>
 781 <TR valign=top>
 782 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 783 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>, Indiana University (<A HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)
 784 </TD></TR></TABLE>
 785
 786 </BODY>
 787 </HTML>