The Boost Graph Library: User Guide and Reference Manual

Description

CD-ROM contains: Source code of BGL -- Fully searchable hyperlinked version of text. 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