The Boost Graph Library: User Guide and Reference Manual [With CDROM]

✍ Scribed by Siek, Jeremy G;Lumsdaine, Andrew

• Publisher: Addison-Wesley Professional
• Year: 2001
• Tongue: English
• Leaves: 350
• Series: With CD-ROM
• Category: Library

✦ Synopsis

The first complete tutorial and reference on the Boost Graphic Library (BGL) -- by its creators -- New graph data structures and algorithms that can help experienced C++ developers save time and dramatically improve code reliability and performance.-- Practical new insights into generic programming -- techniques you can use to build your own libraries-- CD-ROM includes complete electronic version of the book, in hyperlinked, searchable PDF format, as well as the BGL itself.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.

✦ Table of Contents

Cover......Page 1
Contents......Page 10
Foreword......Page 16
Preface......Page 20
I: User Guide......Page 28
1.1 Some Graph Terminology......Page 30
1.2 Graph Concepts......Page 32
1.3 Graph Classes and Adaptors......Page 38
1.4 Generic Graph Algorithms......Page 40
2.1 Introduction......Page 46
2.2 Generic Programming and the STL......Page 52
2.3 Concepts and Models......Page 54
2.4 Associated Types and Traits Classes......Page 57
2.5 Concept Checking......Page 61
2.6 The Boost Namespace......Page 64
2.7 Named Function Parameters......Page 66
3.1 File Dependencies......Page 68
3.2 Graph Setup......Page 69
3.3 Compilation Order......Page 71
3.4 Cyclic Dependencies......Page 75
3.5 Toward a Generic DFS: Visitors......Page 76
3.6 Graph Setup: Internal Properties......Page 79
3.7 Compilation Time......Page 81
3.8 A Generic Topological Sort and DFS......Page 82
3.9 Parallel Compilation Time......Page 84
3.10 Summary......Page 86
4.1 Breadth-First Search......Page 88
4.2 Depth-First Search......Page 94
5.1 Definitions......Page 102
5.2 Internet Routing......Page 103
5.3 Bellman–Ford and Distance Vector Routing......Page 104
5.4 Dijkstra and Link-State Routing......Page 108
6.2 Telephone Network Planning......Page 116
6.3 Kruskal’s Algorithm......Page 118
6.4 Prim’s Algorithm......Page 121
7.1 Definitions......Page 124
7.2 Connected Components and Internet Connectivity......Page 125
7.3 Strongly Connected Components and Web Page Links......Page 129
8.1 Definitions......Page 132
8.2 Edge Connectivity......Page 133
9 Implicit Graphs: A Knight’s Tour......Page 140
9.1 Knight’s Jumps as a Graph......Page 141
9.2 Backtracking Graph Search......Page 143
9.3 Warnsdorff’s Heuristic......Page 144
10 Interfacing with Other Graph Libraries......Page 146
10.1 Using BGL Topological Sort with a LEDA Graph......Page 147
10.2 Using BGL Topological Sort with a SGB Graph......Page 149
10.3 Implementing Graph Adaptors......Page 150
11.1 Graph Class Comparisons......Page 154
11.2 Conclusion......Page 159
II: Reference Manual......Page 162
12.1 Graph Traversal Concepts......Page 164
12.2 Graph Modification Concepts......Page 177
12.3 Visitor Concepts......Page 185
13.1 Overview......Page 190
13.2 Basic Algorithms......Page 192
13.3 Shortest-Path Algorithms......Page 204
13.4 Minimum-Spanning-Tree Algorithms......Page 216
13.5 Static Connected Components......Page 222
13.6 Incremental Connected Components......Page 228
13.7 Maximum-Flow Algorithms......Page 233
14.1 Graph Classes......Page 240
14.2 Auxiliary Classes......Page 269
14.3 Graph Adaptors......Page 278
15 Property Map Library......Page 304
15.1 Property Map Concepts......Page 305
15.2 Property Map Classes......Page 308
15.3 Creating Your Own Property Maps......Page 312
16.1 Buffer......Page 316
16.2 ColorValue......Page 317
16.4 Monoid......Page 318
16.5 mutable_queue......Page 319
16.6 Disjoint Sets......Page 320
16.7 tie......Page 322
16.8 graph_property_iter_range......Page 324
Bibliography......Page 326
A......Page 330
B......Page 331
C......Page 332
D......Page 334
E......Page 335
F......Page 336
G......Page 338
I......Page 339
L......Page 340
N......Page 341
P......Page 342
R......Page 344
S......Page 345
T......Page 346
V......Page 347
W......Page 348

✦ Subjects

Science;Computer Science