Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/index.html @ 14

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

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