mirror of
https://github.com/boostorg/graph.git
synced 2026-01-22 05:12:33 +00:00
290 lines
11 KiB
HTML
290 lines
11 KiB
HTML
<HTML>
|
|
<!--
|
|
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
|
|
--
|
|
-- Permission to use, copy, modify, distribute and sell this software
|
|
-- and its documentation for any purpose is hereby granted without fee,
|
|
-- provided that the above copyright notice appears in all copies and
|
|
-- that both that copyright notice and this permission notice appear
|
|
-- in supporting documentation. We make no
|
|
-- representations about the suitability of this software for any
|
|
-- purpose. It is provided "as is" without express or implied warranty.
|
|
-->
|
|
<Head>
|
|
<Title>The Boost Graph Library</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../c++boost.gif"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
<h1>The Boost Graph Library (BGL)
|
|
<a href="http://cseng.awl.com/book/0,3828,0201729148,00.html">
|
|
<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 an interface for how the structure
|
|
of a graph can be accessed using a generic interface that hides the
|
|
details of the graph data structure 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. 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 better for certain situations. We believe
|
|
that the main contribution of 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 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 are familiar with generic programming,
|
|
please dive right in! Here's the <a
|
|
href="./table_of_contents.html">Table of Contents</a>.
|
|
|
|
<P>
|
|
The source for the BGL is available as part of the Boost distribution
|
|
which you can <a href="http://www.boost.org/more/download.html">
|
|
download from here</a>.
|
|
|
|
<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 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</A>
|
|
</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 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 a programmer wants 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, and 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 BGL using <I>external
|
|
adaptation</I> (see Section <A HREF="./leda_conversion.html">How to
|
|
Convert Existing Graphs to 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 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 BGL are extensible. 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 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 with both the
|
|
vertices and the edges of the graph (we will call an associated value
|
|
a property). In addition, it will often be necessary to associate
|
|
multiple properties with each vertex and edge, which is what we mean
|
|
by multi-parameterization. Similar to how the <TT>std::list<T></TT>
|
|
class has the parameter <TT>T</TT> for its element type, 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, which is used to distinguish
|
|
between the multiple properties. The property value attached to a
|
|
particular vertex or edge can be obtained via a <I>property
|
|
map</I>, of which there is one 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>
|
|
The algorithm patterns by themselves do not compute any meaningful
|
|
quantities over graphs, they are merely building blocks for
|
|
constructing graph algorithms. The graph algorithms in 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>
|
|
BGL currently provides two graph classes that implement a generalized
|
|
adjacency list and an edge list adaptor.
|
|
|
|
<P>
|
|
|
|
<UL>
|
|
<LI><TT>adjacency_list</TT></LI>
|
|
<LI><TT>adjacency_matrix</TT></LI>
|
|
<LI><TT>edge_list</TT></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>edge_list</TT> class is an adaptor that takes any kind of edge
|
|
iterator and implements an <a href="./EdgeListGraph.html">EdgeListGraph</a>.
|
|
|
|
|
|
<br>
|
|
<HR>
|
|
<TABLE>
|
|
<TR valign=top>
|
|
<TD nowrap>Copyright © 2000-2001</TD><TD>
|
|
<A HREF="../../../people/jeremy_siek.htm">Jeremy Siek</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</A>)<br>
|
|
<A HREF="../../../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=http://www.osl.iu.edu/~lums>Andrew Lumsdaine</A>,
|
|
Indiana University (<A
|
|
HREF="mailto:lums@osl.iu.edu">lums@osl.iu.edu</A>)
|
|
</TD></TR></TABLE>
|
|
|
|
</BODY>
|
|
</HTML>
|