The Boost Graph Library
User Guide and Reference Manual
Published on 8. January 2002
Book
Mixed media product
352 pages
978-0-201-72914-6 (ISBN)
Description
The Boost Graphic Library (BGL) gives experienced C++ developers high quality implementations of a wide range of graph data structures and algorithms -- helping them save time that would otherwise have been spent on developing and debugging. Now, the BGL's creators offer a complete tutorial and reference designed to help developers get results with the BGL quickly. They also offer practical, hard-to-find guidance on generic programming that can help developers build their own software development libraries. For practicing programmers, the book introduces high quality implementations of graph data structures and algorithms that deliver outstanding efficiency and performance, and presents the BGL's flexible interface, which enables programmers to apply graph algorithms in settings where a graph may exist only implicitly. For all intermediate-to-advanced C++ programmers.
More details
Language
English
Place of publication
Boston
United States
Publishing group
Pearson Education (US)
Target group
College/higher education
Dimensions
Height: 230 mm
Width: 180 mm
Thickness: 20 mm
Weight
569 gr
ISBN-13
978-0-201-72914-6 (9780201729146)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Persons
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
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
Content
Foreword.
Preface.
I User Guide.
1. Introduction.
Some Graph Terminology.
Graph Concepts.
Vertex and Edge Descriptors.
Property Maps.
Graph Traversa.
Graph Construction and Modification
Algorithm Visitors.
Graph Classes and Adaptors.
Graph Classes.
Graph Adaptors.
Generic Graph Algorithms.
The Topological Sort Generic Algorithm.
The Depth-First Search Generic Algorithm.
2.Generic Programming in C++.
Introduction.
Polymorphism in Object-Oriented Programming.
Polymorphism in Generic Programming.
Comparison of GP and OOP.
Generic Programming and the STL.
Concepts and Models.
Sets of Requirements.
Example: InputIterator.
Associated Types and Traits Classes.
Associated Types Needed in Function Template.
Typedefs Nested in Classes.
Definition of a Traits Class.
Partial Specialization.
Tag Dispatching.
Concept Checking.
Concept-Checking Classes.
Concept Archetypes.
The Boost Namespace.
Classes.
Koenig Lookup.
Named Function Parameters.
3. A BGL Tutorial.
File Dependencies.
Graph Setup.
Compilation Order.
Topological Sort via DFS.
Marking Vertices Using External Properties.
Accessing Adjacent Vertices.
Traversing All the Vertices.
Cyclic Dependencies.
Toward a Generic DFS: Visitors.
Graph Setup: Internal Properties.
Compilation Time.
A Generic Topological Sort and DFS.
Parallel Compilation Time.
Summary.
4. Basic Graph Algorithms.
Breadth-First Search.
Definitions.
Six Degrees of Kevin Bacon.
Depth-First Search.
Definitions.
Finding Loops in Program-Control-Flow Graphs.
5. Shortest-Paths Problems.
Definitions.
Internet Routing.
Bellman-Ford and Distance Vector Routing.
Dijkstra and Link-State Routing.
6. Minimum-Spanning-Tree Problem.
Definitions.
Telephone Network Planning.
Kruskal's Algorithm.
Prim's Algorithm.
7. Connected Components.
Definitions.
Connected Components and Internet Connectivity.
Strongly Connected Components and Web Page Links.
8. Maximum Flow.
Definitions.
Edge Connectivity.
9. Implicit Graphs: A Knight's Tour.
Knight's Jumps as a Graph.
Backtracking Graph Search.
Warnsdorff's Heuristic.
10. Interfacing with Other Graph Libraries.
Using BGL Topological Sort with a LEDA Graph.
Using BGL Topological Sort with a SGB Graph.
Implementing Graph Adaptors.
11. Performance Guidelines.
Graph Class Comparisons.
The Results and Discussion.
Conclusion.
II Reference Manual.
12. BGL Concepts.
Graph Traversal Concepts.
Undirected Graphs.
Graph.
IncidenceGraph.
BidirectionalGraph.
AdjacencyGraph.
VertexListGraph.
EdgeListGraph.
AdjacencyMatrix.
Graph Modification Concepts.
VertexMutableGraph.
EdgeMutableGraph.
MutableIncidenceGraph.
MutableBidirectionalGraph.
MutableEdgeListGraph.
PropertyGraph.
VertexMutablePropertyGraph.
EdgeMutablePropertyGraph.
Visitor Concepts.
BFSVisitor.
DFSVisitor.
DijkstraVisitor.
BellmanFordVisitor.
13. BGL Algorithms.
Overview.
Basic Algorithms.
breadth_first_search.
breadth_first_visit.
depth_first_search.
depth_first_visit.
topological_sort.
Shortest-Path Algorithms.
dijkstra_shortest_paths.
bellman_ford_shortest_paths.
johnson_all_pairs_shortest_paths.
Minimum-Spanning-Tree Algorithms.
kruskal_minimum_spanning_tree.
prim_minimum_spanning_tree.
Static Connected Components.
connected_components.
strong_components.
Incremental Connected Components.
initialize_incremental_components.
incremental_components.
same_component.
component_index.
Maximum-Flow Algorithms.
edmunds_karp_max_flow.
push_relabel_max_flow.
14. BGL Classes.
Graph Classes.
adjacency_list.
adjacency_matrix.
Auxiliary Classes.
graph_traits.
adjacency_list_traits.
adjacency_matrix_traits.
property_map.
property.
Graph Adaptors.
edge_list.
reverse_graph.
filtered_graph.
SGB GraphPointer.
LEDA GRAPH.
std::vector.
15. Property Map Library.
Property Map Concepts.
ReadablePropertyMap.
WritablePropertyMap.
ReadWritePropertyMap.
LvaluePropertyMap.
Property Map Classes.
property_traits.
iterator_property_map.
Property Tags.
Creating Your Own Property Maps.
Property Maps for Stanford GraphBase.
A Property Map Implemented with std::map.
16 Auxiliary Concepts, Classes, and Functions.
Buffer.
ColorValue.
MultiPassInputIterator.
Monoid.
mutable queue.
Disjoint Sets.
disjoint_sets.
find_with_path_halving.
find_with_full_path_compression.
tie.
graph_property_iter_range.
Bibliography.
Index. 0201729148T12172001
Preface.
I User Guide.
1. Introduction.
Some Graph Terminology.
Graph Concepts.
Vertex and Edge Descriptors.
Property Maps.
Graph Traversa.
Graph Construction and Modification
Algorithm Visitors.
Graph Classes and Adaptors.
Graph Classes.
Graph Adaptors.
Generic Graph Algorithms.
The Topological Sort Generic Algorithm.
The Depth-First Search Generic Algorithm.
2.Generic Programming in C++.
Introduction.
Polymorphism in Object-Oriented Programming.
Polymorphism in Generic Programming.
Comparison of GP and OOP.
Generic Programming and the STL.
Concepts and Models.
Sets of Requirements.
Example: InputIterator.
Associated Types and Traits Classes.
Associated Types Needed in Function Template.
Typedefs Nested in Classes.
Definition of a Traits Class.
Partial Specialization.
Tag Dispatching.
Concept Checking.
Concept-Checking Classes.
Concept Archetypes.
The Boost Namespace.
Classes.
Koenig Lookup.
Named Function Parameters.
3. A BGL Tutorial.
File Dependencies.
Graph Setup.
Compilation Order.
Topological Sort via DFS.
Marking Vertices Using External Properties.
Accessing Adjacent Vertices.
Traversing All the Vertices.
Cyclic Dependencies.
Toward a Generic DFS: Visitors.
Graph Setup: Internal Properties.
Compilation Time.
A Generic Topological Sort and DFS.
Parallel Compilation Time.
Summary.
4. Basic Graph Algorithms.
Breadth-First Search.
Definitions.
Six Degrees of Kevin Bacon.
Depth-First Search.
Definitions.
Finding Loops in Program-Control-Flow Graphs.
5. Shortest-Paths Problems.
Definitions.
Internet Routing.
Bellman-Ford and Distance Vector Routing.
Dijkstra and Link-State Routing.
6. Minimum-Spanning-Tree Problem.
Definitions.
Telephone Network Planning.
Kruskal's Algorithm.
Prim's Algorithm.
7. Connected Components.
Definitions.
Connected Components and Internet Connectivity.
Strongly Connected Components and Web Page Links.
8. Maximum Flow.
Definitions.
Edge Connectivity.
9. Implicit Graphs: A Knight's Tour.
Knight's Jumps as a Graph.
Backtracking Graph Search.
Warnsdorff's Heuristic.
10. Interfacing with Other Graph Libraries.
Using BGL Topological Sort with a LEDA Graph.
Using BGL Topological Sort with a SGB Graph.
Implementing Graph Adaptors.
11. Performance Guidelines.
Graph Class Comparisons.
The Results and Discussion.
Conclusion.
II Reference Manual.
12. BGL Concepts.
Graph Traversal Concepts.
Undirected Graphs.
Graph.
IncidenceGraph.
BidirectionalGraph.
AdjacencyGraph.
VertexListGraph.
EdgeListGraph.
AdjacencyMatrix.
Graph Modification Concepts.
VertexMutableGraph.
EdgeMutableGraph.
MutableIncidenceGraph.
MutableBidirectionalGraph.
MutableEdgeListGraph.
PropertyGraph.
VertexMutablePropertyGraph.
EdgeMutablePropertyGraph.
Visitor Concepts.
BFSVisitor.
DFSVisitor.
DijkstraVisitor.
BellmanFordVisitor.
13. BGL Algorithms.
Overview.
Basic Algorithms.
breadth_first_search.
breadth_first_visit.
depth_first_search.
depth_first_visit.
topological_sort.
Shortest-Path Algorithms.
dijkstra_shortest_paths.
bellman_ford_shortest_paths.
johnson_all_pairs_shortest_paths.
Minimum-Spanning-Tree Algorithms.
kruskal_minimum_spanning_tree.
prim_minimum_spanning_tree.
Static Connected Components.
connected_components.
strong_components.
Incremental Connected Components.
initialize_incremental_components.
incremental_components.
same_component.
component_index.
Maximum-Flow Algorithms.
edmunds_karp_max_flow.
push_relabel_max_flow.
14. BGL Classes.
Graph Classes.
adjacency_list.
adjacency_matrix.
Auxiliary Classes.
graph_traits.
adjacency_list_traits.
adjacency_matrix_traits.
property_map.
property.
Graph Adaptors.
edge_list.
reverse_graph.
filtered_graph.
SGB GraphPointer.
LEDA GRAPH.
std::vector.
15. Property Map Library.
Property Map Concepts.
ReadablePropertyMap.
WritablePropertyMap.
ReadWritePropertyMap.
LvaluePropertyMap.
Property Map Classes.
property_traits.
iterator_property_map.
Property Tags.
Creating Your Own Property Maps.
Property Maps for Stanford GraphBase.
A Property Map Implemented with std::map.
16 Auxiliary Concepts, Classes, and Functions.
Buffer.
ColorValue.
MultiPassInputIterator.
Monoid.
mutable queue.
Disjoint Sets.
disjoint_sets.
find_with_path_halving.
find_with_full_path_compression.
tie.
graph_property_iter_range.
Bibliography.
Index. 0201729148T12172001