Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_34_1/libs/graph/doc/index.html @ 29

Last change on this file since 29 was 29, checked in by landauf, 17 years ago

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