The Boost Graph Library User Guide and Reference Manual

by Siek, Jeremy G.; Lee, Lie-Quan; Lumsdaine, Andrew

• ISBN13: 9780201729146
• ISBN10: 0201729148
• Edition: 1st
• Format: Paperback
• Copyright: 2001-12-20
• Publisher: Addison-Wesley Professional

Summary

The first C++ library to apply the principles of generic programming to the construction of the advanced data structures and algorithms used in graph computations. Offers the key to unlocking the power of the BGL for the C++ programmer looking to extend the reach of generic programming beyond the Standard Template Library. Softcover. CD-ROM included.

Author Biography

Jeremy G. Siek is a leading expert in C++ and generic programming and is currently pursuing his doctoral degree at Indiana University. He is interested in the design of programming languages that support generic programming and in high performance libraries. Jeremy is a member of the ISO C++ Standards Committee and is an active member of the Boost C++ Library Group, where he has contributed several libraries in addition to the BGL.

Lie-Quan (Rich) Lee developed the first version of the BGL. A doctoral candidate at the University of Notre Dame, his research interests include generic programming, scientific component libraries, and high performance computing. Rich is an active member of the Boost C++ Library Group.

Andrew Lumsdaine is an Associate Professor in the Computer Science Department and Associate Director of the Open Systems Laboratory at Indiana University. In addition to generic programming and software engineering, his research program includes projects in computational science and engineering, parallel and distributed computing, mathematical software, and numerical analysis. Andrew is a member of the ISO C++ Standards Committee and the Boost C++ Library Group.

0201729148AB11212001

Table of Contents

Foreword	p. xiii
Preface	p. xvii
User Guide	p. 1
Introduction	p. 3
Some Graph Terminology	p. 3
Graph Concepts	p. 5
Vertex and Edge Descriptors	p. 5
Property Maps	p. 6
Graph Traversal	p. 7
Graph Construction and Modification	p. 9
Algorithm Visitors	p. 10
Graph Classes and Adaptors	p. 11
Graph Classes	p. 11
Graph Adaptors	p. 13
Generic Graph Algorithms	p. 13
The Topological Sort Generic Algorithm	p. 14
The Depth-First Search Generic Algorithm	p. 18
Generic Programming in C++	p. 19
Introduction	p. 19
Polymorphism in Object-Oriented Programming	p. 20
Polymorphism in Generic Programming	p. 21
Comparison of GP and OOP	p. 22
Generic Programming and the STL	p. 25
Concepts and Models	p. 27
Sets of Requirements	p. 28
Example: InputIterator	p. 28
Associated Types and Traits Classes	p. 30
Associated Types Needed in Function Template	p. 30
Typedefs Nested in Classes	p. 30
Definition of a Traits Class	p. 31
Partial Specialization	p. 32
Tag Dispatching	p. 33
Concept Checking	p. 34
Concept-Checking Classes	p. 35
Concept Archetypes	p. 36
The Boost Namespace	p. 37
Classes	p. 37
Koenig Lookup	p. 38
Named Function Parameters	p. 39
A BGL Tutorial	p. 41
File Dependencies	p. 41
Graph Setup	p. 42
Compilation Order	p. 44
Topological Sort via DFS	p. 44
Marking Vertices Using External Properties	p. 46
Accessing Adjacent Vertices	p. 46
Traversing All the Vertices	p. 47
Cyclic Dependencies	p. 48
Toward a Generic DFS: Visitors	p. 49
Graph Setup: Internal Properties	p. 52
Compilation Time	p. 54
A Generic Topological Sort and DFS	p. 55
Parallel Compilation Time	p. 57
Summary	p. 59
Basic Graph Algorithms	p. 61
Breadth-First Search	p. 61
Definitions	p. 61
Six Degrees of Kevin Bacon	p. 62
Depth-First Search	p. 67
Definitions	p. 67
Finding Loops in Program-Control-Flow Graphs	p. 69
Shortest-Paths Problems	p. 75
Definitions	p. 75
Internet Routing	p. 76
Bellman-Ford and Distance Vector Routing	p. 77
Dijkstra and Link-State Routing	p. 81
Minimum-Spanning-Tree Problem	p. 89
Definitions	p. 89
Telephone Network Planning	p. 89
Kruskal's Algorithm	p. 91
Prim's Algorithm	p. 94
Connected Components	p. 97
Definitions	p. 97
Connected Components and Internet Connectivity	p. 98
Strongly Connected Components and Web Page Links	p. 102
Maximum Flow	p. 105
Definitions	p. 105
Edge Connectivity	p. 106
Implicit Graphs: A Knight's Tour	p. 113
Knight's Jumps as a Graph	p. 114
Backtracking Graph Search	p. 116
Warnsdorff's Heuristic	p. 117
Interfacing with Other Graph Libraries	p. 119
Using BGL Topological Sort with a LEDA Graph	p. 120
Using BGL Topological Sort with a SGB Graph	p. 122
Implementing Graph Adaptors	p. 123
Performance Guidelines	p. 127
Graph Class Comparisons	p. 127
The Results and Discussion	p. 128
Conclusion	p. 132
Reference Manual	p. 135
BGL Concepts	p. 137
Graph Traversal Concepts	p. 137
Undirected Graphs	p. 138
Graph	p. 142
IncidenceGraph	p. 143
BidirectionalGraph	p. 145
AdjacencyGraph	p. 146
VertexListGraph	p. 147
EdgeListGraph	p. 148
AdjacencyMatrix	p. 149
Graph Modification Concepts	p. 150
VertexMutableGraph	p. 152
EdgeMutableGraph	p. 152
MutableIncidenceGraph	p. 154
MutableBidirectionalGraph	p. 154
MutableEdgeListGraph	p. 155
PropertyGraph	p. 155
VertexMutablePropertyGraph	p. 156
EdgeMutablePropertyGraph	p. 157
Visitor Concepts	p. 158
BFSVisitor	p. 158
DFSVisitor	p. 160
DijkstraVisitor	p. 161
BellmanFordvisitor	p. 162
BGL Algorithms	p. 163
Overview	p. 163
Basic Algorithms	p. 165
Breadth_first_search	p. 165
Breadth_first_visit	p. 169
Depth_first_search	p. 170
Depth_first_visit	p. 175
Topological_sort	p. 176
Shortest-Path Algorithms	p. 177
Dijkstra_shortest_paths	p. 177
Bellman_ford_shortest_paths	p. 182
Johnson_all_pairs_shortest_paths	p. 186
Minimum-Spanning-Tree Algorithms	p. 189
Kruskal_minimum_spanning_tree	p. 189
Prim_minimum_spanning_tree	p. 192
Static Connected Components	p. 195
Connected_components	p. 195
Strong_components	p. 198
Incremental Connected Components	p. 201
Initialize_incremental_components	p. 203
Incremental_components	p. 203
same_component	p. 204
component_index	p. 204
Maximum-Flow Algorithms	p. 206
edmunds_karp_max_flow	p. 206
push_relabel_max_flow	p. 209
BGL Classes	p. 213
Graph Classes	p. 213
adjacency_list	p. 213
adjacency_matrix	p. 235
Auxiliary Classes	p. 242
graph_traits	p. 242
adjacency_list_traits	p. 245
adjacency_matrix_traits	p. 247
property_map	p. 248
property	p. 249
Graph Adaptors	p. 251
edge_list	p. 251
reverse_graph	p. 252
filtered_graph	p. 257
SGB Graph Pointer	p. 262
LEDA GRAPH[left angle bracket]V,E[right angle bracket]	p. 267
std::vector[left angle bracket]EdgeList[right angle bracket]	p. 272
Property Map Library	p. 277
Property Map Concepts	p. 278
ReadablePropertyMap	p. 279
WritablePropertyMap	p. 280
ReadWritePropertyMap	p. 281
LvaluePropertyMap	p. 281
Property Map Classes	p. 281
property_traits	p. 281
iterator_property_map	p. 283
Property Tags	p. 285
Creating Your Own Property Maps	p. 285
Property Maps for Stanford GraphBase	p. 286
A Property Map Implemented with std::map	p. 287
Auxiliary Concepts, Classes, and Functions	p. 289
Buffer	p. 289
ColorValue	p. 290
MultiPassInputlterator	p. 291
Monoid	p. 291
mutable_queue	p. 292
Disjoint Sets	p. 293
disjoint_sets	p. 293
find_with_path_halving	p. 295
find_with_full_path_compression	p. 295
tie	p. 295
graph_property_iter_range	p. 297
Bibliography	p. 299
Index	p. 303
Table of Contents provided by Syndetics. All Rights Reserved.

Excerpts

The graph abstraction is a powerful problem-solving tool used to describe relationships between discrete objects. Many practical problems can be modeled in their essential form by graphs. Such problems appear in many domains: Internet packet routing, telephone network design, software build systems, Web search engines, molecular biology, automated road-trip planning, scientific computing, and so on. The power of the graph abstraction arises from the fact that the solution to a graph-theoretic problem can be used to solve problems in a wide variety of domains. For example, the problem of solving a maze and the problem of finding groups of Web pages that are mutually reachable can both be solved using depth-first search, an important concept from graph theory. By concentrating on the essence of these problemsthe graph model describing discrete objects and the relationships between themgraph theoreticians have created solutions to not just a handful of particular problems, but to entire families of problems. Now a question arises. If graph theory is generally and broadly applicable to arbitrary problem domains, should not the software that implements graph algorithms be just as broadly applicable? Graph theory would seem to be an ideal area for software reuse. However, up until now the potential for reuse has been far from realized. Graph problems do not typically occur in a pure graph-theoretic form, but rather are embedded in larger domain-specific problems. As a result, the data to be modeled as a graph are often not explicitly represented as a graph but are instead encoded in some application-specific data structure. Even in the case where the application data are explicitly represented as a graph, the particular graph representation chosen by the programmer might not match the representation expected by a library that the programmer wants to use. Moreover, different applications may place different time and space requirements on the graph data structure. This implies a serious problem for the graph library writer who wants to provide reusable software, for it is impossible to anticipate every possible data structure that might be needed and to write a different version of the graph algorithm specifically for each one. The current state of affairs is that graph algorithms are written in terms of whatever data structure is most convenient for the algorithm and users must convert their data structures to that format in order to use the algorithm. This is an inefficient undertaking, consuming programmer time and computational resources. Often, the cost is perceived not to be worthwhile, and the programmer instead chooses to rewrite the algorithm in terms of his or her own data structure. This approach is also time consuming and error prone, and will tend to lead to sub-optimal solutions since the application programmer may not be a graph algorithms expert. Generic Programming The Standard Template Library (STL) was introduced in 1994 and was adopted shortly thereafter into the C++ Standard. The STL was a library of interchangeable components for solving many fundamental problems on sequences of elements. What set the STL apart from libraries that came before it was that each STL algorithm could work with a wide variety of sequential datastructures: linked-lists, arrays, sets, and so on. The iterator abstraction provided an interface between containers and algorithms and the C++ template mechanism provided the needed flexibility to allow implementation without loss of efficiency. Each algorithm in the STL is a function template parameterized by the types of iterators upon which it operates. Any iterator that satisfies a minimal set of requirements can be used regardless of the data structure traversed by the iterator. The systematic approach used in the STL to construct abstractions and interchangeable components is called generic programming. Generic programming lends itself well to solving the reusability problem for graph libraries. With generic programming, graph algorithms can be made much more flexible, allowing them to be easily used in a wide variety applications. Each graph algorithm is written not in terms of a specific data structure, but instead to a graph abstraction that can be easily implemented by many different data structures. Writing generic graph algorithms has the additional advantage of being more natural; the abstraction inherent in the pseudo-code description of an algorithm is retained in the generic function. The Boost Graph Library (BGL) is the first C++ graph library to apply the notions of generic programming to the construction of graph algorithms. Some BGL History The Boost Graph Library began its life as the Generic Graph Component Library (GGCL), a software project at the Lab for Scientific Computing (LSC). The LSC, under the direction of Professor Andrew Lumsdaine, was an interdisciplinary laboratory dedicated to research in algorithms, software, tools, and run-time systems for high-performance computational science and engineering.2Special emphasis was put on developing industrial-strength, high performance software using modern programming languages and techniquesmost notably, generic programming. Soon after the Standard Template Library was released, work began at the LSC to apply generic programming to scientific computing. The Matrix Template Library (MTL) was one of the first projects. Many of the lessons learned during construction of the MTL were applied to the design and implementation of the GGCL. The LSC has since evolved into the Open Systems Laboratory (OSL) http://www.osl.iu.edu.Although the name and location have changed, the research agenda remains the same. An important class of linear algebra computations in scientific computing is that of sparse matrix computations, an area where graph algorithms play an important role. As the LSC was developing the sparse matrix capabilities of the MTL, the need for high-performance reusable (and generic) graph algorithms became apparent. However, none of the graph libraries available at the time (LEDA, GTL, Stanford GraphBase) were written using the generic programming style of the MTL and the STL, and hence did not fulfill the flexibility and high-performance requirements of the LSC. Other researchers were also expressing interest in a generic C++ graph library. During a meeting with Bjarne Stroustrup, we were introduced to several individuals at AT&T who needed such a library. Other early work in the area of generic graph algorithms included some codes written by Alexander Stepanov, as well as Dietmar Kuhl's master's thesis. With this in mind, and motivated by homework assignments in his algorithms class ,Jeremy Siek began prototyping an interface and some graph classes in the spring of1998. Lie-Quan Lee then developed the first version of the GGCL, which became his master's thesis project. During the following year, the authors began collaborating with Alexander Stepanov and Matthew Austern. During this time, Stepanov's disjoint-sets-based connected components implementation was added to the GGCL, and work began on providing concept documentation for the GGCL, similar to Austern's STL documentation. During this year the authors also became aware of Boost and were excited to find an organization interested in creating high-quality, open source C++ libraries. Boost included several people interested in generic graph algorithms, most notably Dietmar Kuhl. Some discussions about generic interfaces for graph structures resulted in a revision of the GGCL that closely resembles the current Boost Graph Library interface. On September 4, 2000, the GGCL passed the Boost formal review (managed by David Abrahams) and became the Boost Graph Library. The first release of the BGL was September 27, 20