]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 “open” 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 | “only” 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) [<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 “Release” 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 “interesting” 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<T></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 | “event points” 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 | “properties”) 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<T></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 “properties”. 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 “swiss army | |
273 | knife” 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 © 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> |