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

Jeremy G. Siek (Author), Lie-Quan Lee (Author), Andrew Lumsdaine (Author)

Book Description

Publication Date: December 30, 2001 | ISBN-10: 0201729148 | ISBN-13: 978-0201729146

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.

Editorial Reviews

From the Back Cover

“This book is unique because it discusses graph algorithms in terms of generic programming, and because it presents a concrete, usable library that embodies those algorithms.”—Matthew H. Austern, AT & T Labs-Research

The Boost Graph Library (BGL) is 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. Problems in such diverse areas as Internet packet routing, molecular biology, scientific computing, and telephone network design can be solved by using graph theory. This book presents an in-depth description of the BGL and provides working examples designed to illustrate the application of BGL to these real-world problems.

Written by the BGL developers, The Boost Graph Library: User Guide and Reference Manual gives you all the information you need to take advantage of this powerful new library. Part I is a complete user guide that begins by introducing graph concepts, terminology, and generic graph algorithms. This guide also takes the reader on a tour through the major features of the BGL; all motivated with example problems. Part II is a comprehensive reference manual that provides complete documentation of all BGL concepts, algorithms, and classes.

Readers will find coverage of:

Graph terminology and concepts

Generic programming techniques in C++

Shortest-path algorithms for Internet routing

Network planning problems using the minimum-spanning tree algorithms

BGL algorithms with implicitly defined graphs

BGL Interfaces to other graph libraries

BGL concepts and algorithms

BGL classes—graph, auxiliary, and adaptor

Groundbreaking in its scope, this book 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.

0201729148B11212001

About the Author

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

See all Editorial Reviews

Product Details

• Paperback: 352 pages
• Publisher: Addison-Wesley Professional (December 30, 2001)
• Language: English
• ISBN-10: 0201729148
• ISBN-13: 978-0201729146
• Product Dimensions: 9.1 x 7.6 x 0.8 inches
• Shipping Weight: 1.4 pounds (View shipping rates and policies)
• Average Customer Review: 2.9 out of 5 stars  See all reviews (9 customer reviews)
• Amazon Best Sellers Rank: #775,551 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

29 of 29 people found the following review helpful:

4.0 out of 5 stars Solid and entertaining, January 7, 2002

By 

Alex Rosenberg (Saratoga, CA United States) - See all my reviews

This review is from: The Boost Graph Library: User Guide and Reference Manual (Paperback)

The first part of this book applies the algorithms of the Boost Graph Library (BGL) in fun ways. For example, it solves the problem of Make-style file dependency checking using BGL. And it explores everybody's favorite pastime, "Six Degrees of Kevin Bacon" and similar problems. These real-life examples greatly spice up an otherwise very boring topic.

BGL uses concept checking and property maps and a few other Boost approaches that aren't very well explored in the text. Granted, it's not a book about C++ programming in general (like "Modern C++ Design") but a bit more coverage of these key ideas would have been nice. Also, unlike the STL, several of the alogirithms are named by their canonical names instead of simply specifying their behavior and performance (e.g. names like dijkstra_visitor and bellman_visitor vs. list and map) . This means that library users may need to refer back to the text to figure out which algorithm they desire.

The choice to typeset all code in bold italic text was very unfortunate, but the use of C-Web to explain larger routines more than makes up for this.

The latter part of the book is a dry reference to BGL. More of the exploratory material would have been preferrable.

Overall, a great addition to my C++ library.

11 of 11 people found the following review helpful:

4.0 out of 5 stars A fine addition for any STL/C++ programmer, April 22, 2002

By 

G. Powell (Seattle, WA USA) - See all my reviews
(TOP 1000 REVIEWER)    (REAL NAME)   

This review is from: The Boost Graph Library: User Guide and Reference Manual (Paperback)

The boost graph library extends the STL tool box of containers into graph containers. Wished for a general purpose graph? This is the place. Never studied graph's in a CS course, but know basic data structures like lists, hashes and trees? This is a fine place to start. The book goes from basic, what is a graph good for, (solving search, and routing problems) to what are the various drawbacks to the different approaches.

If you are used to using the C++ STL library you will feel right at home using this. (BTW this library works with MSVC 6.5)

8 of 8 people found the following review helpful:

5.0 out of 5 stars Excellent book on applied graph theory with the BGL, February 7, 2002

By 

Bjorn Karlsson - See all my reviews

This review is from: The Boost Graph Library: User Guide and Reference Manual (Paperback)

I really like the BGL book!

What strikes me the most is the accessibility - the introductions hit the right key immediately, so there's really no need to keep reference material at hand. The samples are equally good, and they're the right size to be easily transformed into solutions to related problems. The book currently rests on my bedside table, and only my favorites make it there...
The Boost Graph Library is powerful, and the BGL book is an excellent companion for graph-related studies or real-world graph problem solving.

Room for improvements:
* The index
* Even more samples (maybe not so elaborate in the text, could be on the CD)

Finally: I like the book a lot, and even if you're not "a graph person", chances are that you will be after reading the BGL book.

I highly recommend it!