Boost Graph Library: The User Guide and Reference Manual(解密pdf).pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：1.47M 资料格式：pdf 举报版权申诉

sjiagc-6039273-16359647703564048287.pdf-第1页.png

第1页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第2页.png

第2页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第3页.png

第3页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第4页.png

第4页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第5页.png

第5页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第6页.png

第6页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第7页.png

第7页 / 共345页

sjiagc-6039273-16359647703564048287.pdf-第8页.png

第8页 / 共345页

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

SiekFM.qk 11/9/01 10:55 AM Page i The Boost Graph Library

SiekFM.qk 11/9/01 10:55 AM Page iii The Boost Graph Library User Guide and Reference Manual Jeremy Siek Lie-Quan Lee Andrew Lumsdaine Boston • San Francisco • New York • Toronto Montreal • London • Munich • Paris • Madrid • Capetown Sydney • Tokyo • Singapore • Mexico City

SiekFM.qk 11/9/01 10:55 AM Page iv Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed with initial capital letters or in all capitals. The authors and publisher have taken care in the preparation of this book, but make no expressed or implied warranty of any kind and assume no responsibil- ity for errors or omissions. No liability is assumed for incidental or consequen- tial damages in connection with or arising out of the use of the information or programs contained herein. The publisher offers discounts on this book when ordered in quantity for special sales. For more information, please contact: Pearson Education Corporate Sales Division One Lake Street Upper Saddle River, NJ 07458 (800) 382-3419 corpsales@pearsontechgroup.com Visit AW on the Web: www.aw.com/cseng/ Library of Congress Cataloging-in-Publication Data Siek, Jeremy G. The Boost graph library : user guide and reference manual/ Jeremy G. Siek, Lie-Quan Lee, Andrew Lumsdaine p. cm. Includes bibliographical references and index. ISBN 0-201-72914-8 (alk. paper) 1. C++ (Computer language). I. Lee, Lie-Quan. II. Lumsdaine, Andrew. III. Title. T385 .S515 2002 006.6—dc21 2001053553 Copyright © 2002 Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form, or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior consent of the publisher. Printed in the United States of America. Published simultane- ously in Canada. ISBN 0-201-72914-8 Text printed on recycled paper 1 2 3 4 5 6 7 8 9 10—MA—0504030201 First printing, December 2001

To Richard and Elisabeth. —J.G.S. To Yun. —L-Q.L. To Wendy, Ben, Emily, and Bethany. —A.L.

Contents Foreword Preface I User Guide 1 . . . . . . . . . . . . Introduction 1.1 Some Graph Terminology . 1.2 Graph Concepts . . Property Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.1 Vertex and Edge Descriptors . . . . . . . . . . . . . . . . . . . . . . 1.2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 Graph Construction and Modiﬁcation . . . . . . . . . . . . . . . . . 1.2.5 Algorithm Visitors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Graph Classes and Adaptors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 The Topological Sort Generic Algorithm . . . . . . . . . . . . . . . 1.4.2 The Depth-First Search Generic Algorithm . . . . . . . . . . . . . . . . 1.4 Generic Graph Algorithms . 1.3.1 Graph Classes . . 1.3.2 Graph Adaptors . 2 Generic Programming in C++ . 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction . Polymorphism in Object-Oriented Programming . . . . . . . . . . . 2.1.1 Polymorphism in Generic Programming . . . . . . . . . . . . . . . . 2.1.2 2.1.3 Comparison of GP and OOP . . . . . . . . . . . . . . . . . . . . . . 2.2 Generic Programming and the STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Concepts and Models . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 2.3.2 Example: InputIterator . . . . . . . . . . . . . . . . . . . . . . . . . Sets of Requirements . . . . xiii xvii 1 3 3 5 5 6 7 9 10 11 11 13 13 14 18 19 19 20 21 22 25 27 28 28 vii

viii CONTENTS 2.5 Concept Checking . Partial Specialization . . . 2.4 Associated Types and Traits Classes . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Associated Types Needed in Function Template . . . . . . . . . . . . 2.4.2 Typedefs Nested in Classes . . . . . . . . . . . . . . . . . . . . . . . 2.4.3 Deﬁnition of a Traits Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4 . . . . . . . . . . . . . . . . . . . . . . . 2.4.5 Tag Dispatching . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.1 Concept-Checking Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5.2 Concept Archetypes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.7 Named Function Parameters . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Classes . . 2.6.2 Koenig Lookup . 2.6 The Boost Namespace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 A BGL Tutorial . . . . . . . . . . . . . . . . . . . . . . 3.1 File Dependencies . 3.2 Graph Setup . . . 3.3 Compilation Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Topological Sort via DFS . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Marking Vertices using External Properties . . . . . . . . . . . . . . 3.3.3 Accessing Adjacent Vertices . . . . . . . . . . . . . . . . . . . . . . 3.3.4 Traversing All the Vertices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.4 Cyclic Dependencies . . . . . . . . . . . . . . . . . . . . . . . . . 3.5 Toward a Generic DFS: Visitors . . . . . . . . . . . . . . . . . . . . . . . . 3.6 Graph Setup: Internal Properties . 3.7 Compilation Time . . . . . . . . . . . . . . . . . . . . . . . . . 3.8 A Generic Topological Sort and DFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.9 Parallel Compilation Time . 3.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 Basic Graph Algorithms . . . . . . . . . . . 4.1 Breadth-First Search . . 4.1.1 Deﬁnitions 4.1.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Six Degrees of Kevin Bacon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Finding Loops in Program-Control-Flow Graphs . . . . . . . . . . . 4.2 Depth-First Search . . 4.2.1 Deﬁnitions 4.2.2 . . . . . . . . . . . . . . . . 5 Shortest-Path Problems . . 5.1 Deﬁnitions . 5.2 . Internet Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 30 30 31 32 33 34 35 36 37 37 38 39 41 41 42 44 44 46 46 47 48 49 52 54 55 57 59 61 61 61 62 67 67 69 75 75 76

分享到：

赞收藏

资料库

Boost Graph Library: The User Guide and Reference Manual(解密pdf).pdf

相关推荐

课程资源

热门标签

最新资料