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

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
   2 "http://www.w3.org/TR/html4/loose.dtd">
   3 <HTML>
   4 <!--
   5      Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
   6
   7      Distributed under the Boost Software License, Version 1.0.
   8      (See accompanying file LICENSE_1_0.txt or copy at
   9      http://www.boost.org/LICENSE_1_0.txt)
  10   -->
  11 <Head>
  12 <meta http-equiv="Content-Type" content="text/html;charset=utf-8" >
  13 <Title>The Boost Graph Library</Title>
  14 <BODY bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"
  15         alink="#ff0000">
  16 <IMG src="../../../boost.png"
  17      alt="C++ Boost" width="277" height="86">
  18
  19 <h1>The Boost Graph Library (BGL)
  20 <a href="http://www.awprofessional.com/title/0201729148">
  21 <img src="bgl-cover.jpg" alt="BGL Book" align="RIGHT"></a>
  22 </h1>
  23
  24 <P>
  25 Graphs are mathematical abstractions that are useful for solving many
  26 types of problems in computer science. Consequently, these
  27 abstractions must also be represented in computer programs.  A
  28 standardized generic interface for traversing graphs is of utmost
  29 importance to encourage reuse of graph algorithms and data structures.
  30 Part of the Boost Graph Library is a generic interface that allows
  31 access to a graph's structure, but hides the details of the
  32 implementation.  This is an &ldquo;open&rdquo; interface in the sense that any
  33 graph library that implements this interface will be interoperable
  34 with the BGL generic algorithms and with other algorithms that also
  35 use this interface. The BGL provides some general purpose graph classes
  36 that conform to this interface, but they are not meant to be the
  37 &ldquo;only&rdquo; graph classes; there certainly will be other graph classes
  38 that are better for certain situations.  We believe that the main
  39 contribution of the The BGL is the formulation of this interface.
  40
  41 <P>
  42 The BGL graph interface and graph components are <I>generic</I>, in the
  43 same sense as the Standard Template Library (STL)&nbsp;[<A
  44 HREF="bibliography.html#austern99:_gener_progr_stl">2</A>].
  45
  46 In the following sections, we review the role that generic programming
  47 plays in the STL and compare that to how we applied generic
  48 programming in the context of graphs.
  49
  50 <P>
  51 Of course, if you are already familiar with generic programming,
  52 please dive right in! Here's the <a
  53 href="./table_of_contents.html">Table of Contents</a>.  For distributed-memory
  54 parallelism, you can also look at the <a
  55 href="../../graph_parallel/doc/html/index.html">Parallel BGL</a>.
  56
  57 <P>
  58 The source for the BGL is available as part of the Boost distribution,
  59 which you can <a href="http://sourceforge.net/project/showfiles.php?group_id=7586">
  60 download from here</a>.
  61
  62 <H2>How to Build the BGL</H2>
  63 <p><b>DON'T!</b> The Boost Graph Library is a header-only library and
  64 does not need to be built to be used. The only exceptions are the <a
  65 href="read_graphviz.html">GraphViz input parser</a> and the <a
  66 href="read_graphml.html">GraphML parser</a>.</p>
  67
  68 <p>When compiling programs that use the BGL, <b>be sure to compile
  69 with optimization</b>. For instance, select &ldquo;Release&rdquo; mode with
  70 Microsoft Visual C++ or supply the flag <tt>-O2</tt> or <tt>-O3</tt>
  71 to GCC. </p>
  72
  73 <H2>Genericity in STL</H2>
  74
  75 <P>
  76 There are three ways in which the STL is generic.
  77
  78 <P>
  79
  80 <H3>Algorithm/Data-Structure Interoperability</H3>
  81
  82 <P>
  83 First, each algorithm is written in a data-structure neutral way,
  84 allowing a single template function to operate on many different
  85 classes of containers. The concept of an iterator is the key
  86 ingredient in this decoupling of algorithms and data-structures.  The
  87 impact of this technique is a reduction in the STL's code size from
  88 <i>O(M*N)</i> to <i>O(M+N)</i>, where <i>M</i> is the number of
  89 algorithms and <i>N</i> is the number of containers. Considering a
  90 situation of 20 algorithms and 5 data-structures, this would be the
  91 difference between writing 100 functions versus only 25 functions! And
  92 the differences continues to grow faster and faster as the number of
  93 algorithms and data-structures increase.
  94
  95 <P>
  96
  97 <H3>Extension through Function Objects</H3>
  98
  99 <P>
 100 The second way that STL is generic is that its algorithms and containers
 101 are extensible. The user can adapt and customize the STL through the
 102 use of function objects. This flexibility is what makes STL such a
 103 great tool for solving real-world problems. Each programming problem
 104 brings its own set of entities and interactions that must be
 105 modeled. Function objects provide a mechanism for extending the STL to
 106 handle the specifics of each problem domain.
 107
 108 <P>
 109
 110 <H3>Element Type Parameterization</H3>
 111
 112 <P>
 113 The third way that STL is generic is that its containers are
 114 parameterized on the element type. Though hugely important, this is
 115 perhaps the least &ldquo;interesting&rdquo; way in which STL is generic.
 116 Generic programming is often summarized by a brief description of
 117 parameterized lists such as <TT>std::list&lt;T&gt;</TT>. This hardly scratches
 118 the surface!
 119
 120 <P>
 121
 122 <H2>Genericity in the Boost Graph Library
 123 </H2>
 124
 125 <P>
 126 Like the STL, there are three ways in which the BGL is generic.
 127
 128 <P>
 129
 130 <H3>Algorithm/Data-Structure Interoperability</H3>
 131
 132 <P>
 133 First, the graph algorithms of the BGL are written to an interface that
 134 abstracts away the details of the particular graph data-structure.
 135 Like the STL, the BGL uses iterators to define the interface for
 136 data-structure traversal. There are three distinct graph traversal
 137 patterns: traversal of all vertices in the graph, through all of the
 138 edges, and along the adjacency structure of the graph (from a vertex
 139 to each of its neighbors). There are separate iterators for each
 140 pattern of traversal.
 141
 142 <P>
 143 This generic interface allows template functions such as <a
 144 href="./breadth_first_search.html"><TT>breadth_first_search()</TT></a>
 145 to work on a large variety of graph data-structures, from graphs
 146 implemented with pointer-linked nodes to graphs encoded in
 147 arrays. This flexibility is especially important in the domain of
 148 graphs. Graph data-structures are often custom-made for a particular
 149 application. Traditionally, if programmers want to reuse an
 150 algorithm implementation they must convert/copy their graph data into
 151 the graph library's prescribed graph structure.  This is the case with
 152 libraries such as LEDA, GTL, Stanford GraphBase; it is especially true
 153 of graph algorithms written in Fortran. This severely limits the reuse
 154 of their graph algorithms.
 155
 156 <P>
 157 In contrast, custom-made (or even legacy) graph structures can be used
 158 as-is with the generic graph algorithms of the BGL, using <I>external
 159 adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
 160 Convert Existing Graphs to the BGL</A>).  External adaptation wraps a new
 161 interface around a data-structure without copying and without placing
 162 the data inside adaptor objects.  The BGL interface was carefully
 163 designed to make this adaptation easy. To demonstrate this, we have
 164 built interfacing code for using a variety of graph dstructures (LEDA
 165 graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in
 166 BGL graph algorithms.
 167
 168 <P>
 169
 170 <H3>Extension through Visitors</H3>
 171
 172 <P>
 173 Second, the graph algorithms of the BGL are extensible. The BGL introduces the
 174 notion of a <I>visitor</I>, which is just a function object with
 175 multiple methods.  In graph algorithms, there are often several key
 176 &ldquo;event points&rdquo; at which it is useful to insert user-defined
 177 operations. The visitor object has a different method that is invoked
 178 at each event point. The particular event points and corresponding
 179 visitor methods depend on the particular algorithm.  They often
 180 include methods like <TT>start_vertex()</TT>,
 181 <TT>discover_vertex()</TT>, <TT>examine_edge()</TT>,
 182 <tt>tree_edge()</tt>, and <TT>finish_vertex()</TT>.
 183
 184 <P>
 185
 186 <H3>Vertex and Edge Property Multi-Parameterization</H3>
 187
 188 <P>
 189 The third way that the BGL is generic is analogous to the parameterization
 190 of the element-type in STL containers, though again the story is a bit
 191 more complicated for graphs. We need to associate values (called
 192 &ldquo;properties&rdquo;) with both the vertices and the edges of the graph.
 193 In addition, it will often be necessary to associate
 194 multiple properties with each vertex and edge; this is what we mean
 195 by multi-parameterization.
 196 The STL <tt>std::list&lt;T&gt;</tt> class has a parameter <tt>T</tt>
 197 for its element type. Similarly, BGL graph classes have template
 198 parameters for vertex and edge &ldquo;properties&rdquo;. A
 199 property specifies the parameterized type of the property and also assigns
 200 an identifying tag to the property. This tag is used to distinguish
 201 between the multiple properties which an edge or vertex may have. A
 202 property value that is attached to a
 203 particular vertex or edge can be obtained via a <I>property
 204 map</I>. There is a separate property map for each property.
 205
 206 <P>
 207 Traditional graph libraries and graph structures fall down when it
 208 comes to the parameterization of graph properties. This is one of the
 209 primary reasons that graph data-structures must be custom-built for
 210 applications. The parameterization of properties in the  BGL graph
 211 classes makes them well suited for re-use.
 212
 213 <p>
 214
 215 <H2>Algorithms</H2>
 216
 217 <P>
 218 The BGL algorithms consist of a core set of algorithm <I>patterns</I>
 219 (implemented as generic algorithms) and a larger set of graph
 220 algorithms. The core algorithm patterns are
 221
 222 <P>
 223
 224 <UL>
 225 <LI>Breadth First Search
 226 </LI>
 227 <LI>Depth First Search
 228 </LI>
 229 <LI>Uniform Cost Search
 230 </LI>
 231 </UL>
 232
 233 <P>
 234 By themselves, the algorithm patterns do not compute any meaningful
 235 quantities over graphs; they are merely building blocks for
 236 constructing graph algorithms. The graph algorithms in the BGL currently
 237 include
 238
 239 <P>
 240
 241 <UL>
 242 <LI>Dijkstra's Shortest Paths</LI>
 243 <LI>Bellman-Ford Shortest Paths</LI>
 244 <LI>Johnson's All-Pairs Shortest Paths</LI>
 245 <LI>Kruskal's Minimum Spanning Tree</LI>
 246 <LI>Prim's Minimum Spanning Tree</LI>
 247 <LI>Connected Components</LI>
 248 <LI>Strongly Connected Components</LI>
 249 <LI>Dynamic Connected Components (using Disjoint Sets)</LI>
 250 <LI>Topological Sort</LI>
 251 <LI>Transpose</LI>
 252 <LI>Reverse Cuthill Mckee Ordering</LI>
 253 <LI>Smallest Last Vertex Ordering</LI>
 254 <LI>Sequential Vertex Coloring</LI>
 255 </UL>
 256
 257 <P>
 258
 259 <H2>Data Structures</H2>
 260
 261 <P>
 262 The BGL currently provides two graph classes and an edge list adaptor:
 263 <P>
 264
 265 <UL>
 266 <LI><a href="adjacency_list.html"><TT>adjacency_list</TT></a></LI>
 267 <LI><a href="adjacency_matrix.html"><TT>adjacency_matrix</TT></a></LI>
 268 <LI><a href="edge_list.html"><TT>edge_list</TT></a></LI>
 269 </UL>
 270
 271 <P>
 272 The <TT>adjacency_list</TT> class is the general purpose &ldquo;swiss army
 273 knife&rdquo; of graph classes. It is highly parameterized so that it can be
 274 optimized for different situations: the graph is directed or
 275 undirected, allow or disallow parallel edges, efficient access to just
 276 the out-edges or also to the in-edges, fast vertex insertion and
 277 removal at the cost of extra space overhead, etc.
 278
 279 <P>
 280 The <tt>adjacency_matrix</tt> class stores edges in a <i>|V| x |V|</i>
 281 matrix (where <i>|V|</i> is the number of vertices). The elements of
 282 this matrix represent edges in the graph. Adjacency matrix
 283 representations are especially suitable for very dense graphs, i.e.,
 284 those where the number of edges approaches <i>|V|<sup>2</sup></i>.
 285
 286 <P>
 287 The <TT>edge_list</TT> class is an adaptor that takes any kind of edge
 288 iterator and implements an <a href="./EdgeListGraph.html">Edge List Graph</a>.
 289
 290
 291 <br>
 292 <HR>
 293 <TABLE>
 294 <TR valign=top>
 295 <TD nowrap>Copyright &copy; 2000-2001</TD><TD>
 296 <A HREF="http://www.boost.org/people/jeremy_siek.htm">Jeremy Siek</A>,
 297 Indiana University (<A
 298 HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
 299 <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>
 300 <A HREF="http://www.osl.iu.edu/~lums">Andrew Lumsdaine</A>,
 301 Indiana University (<A
 302 HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
 303 </TD></TR></TABLE>
 304
 305 </BODY>
 306 </HTML>