123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306 |
- <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
- "http://www.w3.org/TR/html4/loose.dtd">
- <HTML>
- <!--
- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
-
- Distributed under the Boost Software License, Version 1.0.
- (See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt)
- -->
- <Head>
- <meta http-equiv="Content-Type" content="text/html;charset=utf-8" >
- <Title>The Boost Graph Library</Title>
- <BODY bgcolor="#ffffff" link="#0000ee" text="#000000" vlink="#551a8b"
- alink="#ff0000">
- <IMG src="../../../boost.png"
- alt="C++ Boost" width="277" height="86">
- <h1>The Boost Graph Library (BGL)
- <a href="http://www.awprofessional.com/title/0201729148">
- <img src="bgl-cover.jpg" alt="BGL Book" align="RIGHT"></a>
- </h1>
- <P>
- Graphs are mathematical abstractions that are useful for solving many
- types of problems in computer science. Consequently, these
- abstractions must also be represented in computer programs. A
- standardized generic interface for traversing graphs is of utmost
- importance to encourage reuse of graph algorithms and data structures.
- Part of the Boost Graph Library is a generic interface that allows
- access to a graph's structure, but hides the details of the
- implementation. This is an “open” interface in the sense that any
- graph library that implements this interface will be interoperable
- with the BGL generic algorithms and with other algorithms that also
- use this interface. The BGL provides some general purpose graph classes
- that conform to this interface, but they are not meant to be the
- “only” graph classes; there certainly will be other graph classes
- that are better for certain situations. We believe that the main
- contribution of the The BGL is the formulation of this interface.
- <P>
- The BGL graph interface and graph components are <I>generic</I>, in the
- same sense as the Standard Template Library (STL) [<A
- HREF="bibliography.html#austern99:_gener_progr_stl">2</A>].
- In the following sections, we review the role that generic programming
- plays in the STL and compare that to how we applied generic
- programming in the context of graphs.
- <P>
- Of course, if you are already familiar with generic programming,
- please dive right in! Here's the <a
- href="./table_of_contents.html">Table of Contents</a>. For distributed-memory
- parallelism, you can also look at the <a
- href="../../graph_parallel/doc/html/index.html">Parallel BGL</a>.
- <P>
- The source for the BGL is available as part of the Boost distribution,
- which you can <a href="http://sourceforge.net/project/showfiles.php?group_id=7586">
- download from here</a>.
- <H2>How to Build the BGL</H2>
- <p><b>DON'T!</b> The Boost Graph Library is a header-only library and
- does not need to be built to be used. The only exceptions are the <a
- href="read_graphviz.html">GraphViz input parser</a> and the <a
- href="read_graphml.html">GraphML parser</a>.</p>
- <p>When compiling programs that use the BGL, <b>be sure to compile
- with optimization</b>. For instance, select “Release” mode with
- Microsoft Visual C++ or supply the flag <tt>-O2</tt> or <tt>-O3</tt>
- to GCC. </p>
- <H2>Genericity in STL</H2>
- <P>
- There are three ways in which the STL is generic.
- <P>
- <H3>Algorithm/Data-Structure Interoperability</H3>
- <P>
- First, each algorithm is written in a data-structure neutral way,
- allowing a single template function to operate on many different
- classes of containers. The concept of an iterator is the key
- ingredient in this decoupling of algorithms and data-structures. The
- impact of this technique is a reduction in the STL's code size from
- <i>O(M*N)</i> to <i>O(M+N)</i>, where <i>M</i> is the number of
- algorithms and <i>N</i> is the number of containers. Considering a
- situation of 20 algorithms and 5 data-structures, this would be the
- difference between writing 100 functions versus only 25 functions! And
- the differences continues to grow faster and faster as the number of
- algorithms and data-structures increase.
- <P>
- <H3>Extension through Function Objects</H3>
- <P>
- The second way that STL is generic is that its algorithms and containers
- are extensible. The user can adapt and customize the STL through the
- use of function objects. This flexibility is what makes STL such a
- great tool for solving real-world problems. Each programming problem
- brings its own set of entities and interactions that must be
- modeled. Function objects provide a mechanism for extending the STL to
- handle the specifics of each problem domain.
- <P>
- <H3>Element Type Parameterization</H3>
- <P>
- The third way that STL is generic is that its containers are
- parameterized on the element type. Though hugely important, this is
- perhaps the least “interesting” way in which STL is generic.
- Generic programming is often summarized by a brief description of
- parameterized lists such as <TT>std::list<T></TT>. This hardly scratches
- the surface!
- <P>
- <H2>Genericity in the Boost Graph Library
- </H2>
- <P>
- Like the STL, there are three ways in which the BGL is generic.
- <P>
- <H3>Algorithm/Data-Structure Interoperability</H3>
- <P>
- First, the graph algorithms of the BGL are written to an interface that
- abstracts away the details of the particular graph data-structure.
- Like the STL, the BGL uses iterators to define the interface for
- data-structure traversal. There are three distinct graph traversal
- patterns: traversal of all vertices in the graph, through all of the
- edges, and along the adjacency structure of the graph (from a vertex
- to each of its neighbors). There are separate iterators for each
- pattern of traversal.
- <P>
- This generic interface allows template functions such as <a
- href="./breadth_first_search.html"><TT>breadth_first_search()</TT></a>
- to work on a large variety of graph data-structures, from graphs
- implemented with pointer-linked nodes to graphs encoded in
- arrays. This flexibility is especially important in the domain of
- graphs. Graph data-structures are often custom-made for a particular
- application. Traditionally, if programmers want to reuse an
- algorithm implementation they must convert/copy their graph data into
- the graph library's prescribed graph structure. This is the case with
- libraries such as LEDA, GTL, Stanford GraphBase; it is especially true
- of graph algorithms written in Fortran. This severely limits the reuse
- of their graph algorithms.
- <P>
- In contrast, custom-made (or even legacy) graph structures can be used
- as-is with the generic graph algorithms of the BGL, using <I>external
- adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
- Convert Existing Graphs to the BGL</A>). External adaptation wraps a new
- interface around a data-structure without copying and without placing
- the data inside adaptor objects. The BGL interface was carefully
- designed to make this adaptation easy. To demonstrate this, we have
- built interfacing code for using a variety of graph structures (LEDA
- graphs, Stanford GraphBase graphs, and even Fortran-style arrays) in
- BGL graph algorithms.
- <P>
- <H3>Extension through Visitors</H3>
- <P>
- Second, the graph algorithms of the BGL are extensible. The BGL introduces the
- notion of a <I>visitor</I>, which is just a function object with
- multiple methods. In graph algorithms, there are often several key
- “event points” at which it is useful to insert user-defined
- operations. The visitor object has a different method that is invoked
- at each event point. The particular event points and corresponding
- visitor methods depend on the particular algorithm. They often
- include methods like <TT>start_vertex()</TT>,
- <TT>discover_vertex()</TT>, <TT>examine_edge()</TT>,
- <tt>tree_edge()</tt>, and <TT>finish_vertex()</TT>.
- <P>
- <H3>Vertex and Edge Property Multi-Parameterization</H3>
- <P>
- The third way that the BGL is generic is analogous to the parameterization
- of the element-type in STL containers, though again the story is a bit
- more complicated for graphs. We need to associate values (called
- “properties”) with both the vertices and the edges of the graph.
- In addition, it will often be necessary to associate
- multiple properties with each vertex and edge; this is what we mean
- by multi-parameterization.
- The STL <tt>std::list<T></tt> class has a parameter <tt>T</tt>
- for its element type. Similarly, BGL graph classes have template
- parameters for vertex and edge “properties”. A
- property specifies the parameterized type of the property and also assigns
- an identifying tag to the property. This tag is used to distinguish
- between the multiple properties which an edge or vertex may have. A
- property value that is attached to a
- particular vertex or edge can be obtained via a <I>property
- map</I>. There is a separate property map for each property.
- <P>
- Traditional graph libraries and graph structures fall down when it
- comes to the parameterization of graph properties. This is one of the
- primary reasons that graph data-structures must be custom-built for
- applications. The parameterization of properties in the BGL graph
- classes makes them well suited for re-use.
- <p>
- <H2>Algorithms</H2>
- <P>
- The BGL algorithms consist of a core set of algorithm <I>patterns</I>
- (implemented as generic algorithms) and a larger set of graph
- algorithms. The core algorithm patterns are
- <P>
- <UL>
- <LI>Breadth First Search
- </LI>
- <LI>Depth First Search
- </LI>
- <LI>Uniform Cost Search
- </LI>
- </UL>
- <P>
- By themselves, the algorithm patterns do not compute any meaningful
- quantities over graphs; they are merely building blocks for
- constructing graph algorithms. The graph algorithms in the BGL currently
- include
- <P>
- <UL>
- <LI>Dijkstra's Shortest Paths</LI>
- <LI>Bellman-Ford Shortest Paths</LI>
- <LI>Johnson's All-Pairs Shortest Paths</LI>
- <LI>Kruskal's Minimum Spanning Tree</LI>
- <LI>Prim's Minimum Spanning Tree</LI>
- <LI>Connected Components</LI>
- <LI>Strongly Connected Components</LI>
- <LI>Dynamic Connected Components (using Disjoint Sets)</LI>
- <LI>Topological Sort</LI>
- <LI>Transpose</LI>
- <LI>Reverse Cuthill Mckee Ordering</LI>
- <LI>Smallest Last Vertex Ordering</LI>
- <LI>Sequential Vertex Coloring</LI>
- </UL>
- <P>
- <H2>Data Structures</H2>
- <P>
- The BGL currently provides two graph classes and an edge list adaptor:
- <P>
- <UL>
- <LI><a href="adjacency_list.html"><TT>adjacency_list</TT></a></LI>
- <LI><a href="adjacency_matrix.html"><TT>adjacency_matrix</TT></a></LI>
- <LI><a href="edge_list.html"><TT>edge_list</TT></a></LI>
- </UL>
- <P>
- The <TT>adjacency_list</TT> class is the general purpose “swiss army
- knife” of graph classes. It is highly parameterized so that it can be
- optimized for different situations: the graph is directed or
- undirected, allow or disallow parallel edges, efficient access to just
- the out-edges or also to the in-edges, fast vertex insertion and
- removal at the cost of extra space overhead, etc.
- <P>
- The <tt>adjacency_matrix</tt> class stores edges in a <i>|V| x |V|</i>
- matrix (where <i>|V|</i> is the number of vertices). The elements of
- this matrix represent edges in the graph. Adjacency matrix
- representations are especially suitable for very dense graphs, i.e.,
- those where the number of edges approaches <i>|V|<sup>2</sup></i>.
- <P>
- The <TT>edge_list</TT> class is an adaptor that takes any kind of edge
- iterator and implements an <a href="./EdgeListGraph.html">Edge List Graph</a>.
- <br>
- <HR>
- <TABLE>
- <TR valign=top>
- <TD nowrap>Copyright © 2000-2001</TD><TD>
- <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>)<br>
- <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>
- <A HREF="https://homes.cs.washington.edu/~al75">Andrew Lumsdaine</A>,
- Indiana University (<A
- HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
- </TD></TR></TABLE>
- </BODY>
- </HTML>
|