The Boost Graph Library: User Guide and Reference Manual

Foreword
Preface
I User Guide
Introduction
Some Graph Terminology
Graph Concepts
Vertex and Edge Descriptors
Property Maps
Graph Traversal
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
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
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
Basic Graph Algorithms
Breadth-First Search
Definitions
Six Degrees of Kevin Bacon
Depth-First Search
Definitions
Finding Loops in Program-Control-Flow Graphs
Shortest-Path Problems
Definitions
Internet Routing
Bellman--Ford and Distance Vector Routing
Dijkstra and Link-State Routing
Minimum-Spanning-Tree Problem
Definitions
Telephone Network Planning
Kruskal's Algorithm
Prim's Algorithm
Connected Components
Definitions
Connected Components and Internet Connectivity
Strongly Connected Components and Web Page Links
Maximum Flow
Definitions
Edge Connectivity
Implicit Graphs: A Knight's Tour
Knight's Jumps as a Graph
Backtracking Graph Search
Warnsdorff's Heuristic
Interfacing with Other Graph Libraries
Using BGL Topological Sort with a LEDA Graph
Using BGL Topological Sort with a SGB Graph
Implementing Graph Adaptors
Performance Guidelines
Graph Class Comparisons
The Results and Discussion
Conclusion
II Reference Manual
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
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
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 Graph Pointer
LEDA GRAPH
std::vector
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
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