深入理解Boost Graph Library：用户指南与参考手册

unlocked

Boost

需积分: 30 165 浏览量更新于2024-07-17 收藏 1.65MB PDF 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

"《boost-graph-library [Unlocked].pdf》是一本高清无密码的关于Boost Graph Library的用户指南和参考手册，由Jeremy Siek、Lie-Quan Lee和Andrew Lumsdaine合著，包含了详尽的BGL学习资料。" Boost Graph Library（BGL）是Boost库的一部分，它为C++程序员提供了一套强大的工具来处理图数据结构和算法。这个库设计灵活，易于使用，可以处理各种类型和规模的图，包括加权图、无向图、有向图等。BGL的核心理念是将图和图算法作为模板类和函数，使得它们能够与C++的STL（标准模板库）无缝集成。该图书作为用户指南和参考手册，可能包含以下内容： 1. **图的基本概念**：首先，书中会介绍图的基本概念，如顶点、边、邻接矩阵和邻接表等，以及如何在C++中表示这些概念。 2. **图的创建和操作**：读者会学习如何创建和初始化图，包括添加和删除顶点和边，以及遍历图的各种方法，如深度优先搜索（DFS）和广度优先搜索（BFS）。 3. **属性和迭代器**：BGL支持在顶点和边上附加属性，并提供了相应的迭代器以便访问和修改这些属性。这部分会详细解释如何定义和使用这些属性以及迭代器。 4. **算法实现**：书中的核心部分可能涵盖了各种图算法，如最短路径算法（Dijkstra、Floyd-Warshall）、最小生成树算法（Prim、Kruskal）、拓扑排序、二分查找、强连通组件等。 5. **图的并查集**：BGL提供了并查集数据结构，用于处理连通性问题，如寻找两个顶点是否在同一个连通分量中。 6. **剪枝和优化技术**：书中可能讨论了如何通过剪枝策略来优化搜索算法，以提高性能。 7. **实际应用示例**：为了帮助读者更好地理解，书中可能会包含实际编程示例，如网络路由、社交网络分析、图论问题等。 8. **高级主题**：对于更高级的用户，可能会涵盖自定义图适应器、图算法的并行化以及与其他Boost库（如Property Maps和Iterators）的协同使用。 9. **错误处理和调试**：书中可能还会涉及如何在遇到问题时进行调试，以及如何避免常见陷阱。 10. **API参考**：参考部分将详细介绍BGL提供的每个类、函数和宏，方便开发者查阅。《boost-graph-library [Unlocked].pdf》这本书对想要深入学习和应用Boost Graph Library的C++程序员来说，是一份宝贵的资源，它不仅提供了理论知识，还包含了大量的实践指导。

资源详情

资源推荐

xvi FOREWORD

of deﬁnition without looking at the points of call, and full type-checking can be done at the

points of call without looking at the body of the algorithm.

Sometimes we need multiple instances of the same concept. For example,

OutputIterator merge(InputIterator[1] ﬁrst1, InputIterator[1] last1,

InputIterator[2] ﬁrst2, InputIterator[2] last2,

OutputIterator result)

(bool operator<(value type(InputIterator[1]), value type(InputIterator[2])),

value type(InputIterator[1]) == value type(InputIterator[2]),

output type(OutputIterator) == value type(InputIterator[2]));

Note that this merge is not as powerful as the STL merge. It cannot merge a list of ﬂoats

and a vector of doubles into a deque of ints. STL algorithms will often do unexpected and, in

my opinion, undesirable type conversions. If someone needs to merge doubles and ﬂoats into

ints he or she should use an explicit function object for asymmetric comparison and a special

output iterator for conversion.

C++ provides two different abstraction mechanisms: object-orientedness and templates.

Object-orientedness allows for exact interface deﬁnition and for run-time dispatch. But it

cannot handle binary methods or multi-method dispatching, and its run-time binding is often

inefﬁcient. Templates handle richer interfaces and are resolved at compile-time. They can,

however, cause a software engineering nightmare because of the lack of separation between

interfaces and implementation. For example, I recently tried compiling a 10-line STL-based

program using one of the most popular C++ compilers and ran away in shock after getting

several pages of incomprehensible error messages. And often one needs run-time dispatch,

which cannot be handled by templates. I do believe that introduction of concepts will unify

both approaches and resolve both sets of limitations. And after all, it is possible to represent

concepts as virtual tables which are extended by pointers to type descriptors: the virtual table

for input iterator contains not just pointers to operator* and operator++, but also pointers to the

actual type of the iterator, its value type and its distance type. And then one could introduce

pointers to concepts and references to concepts!

Generic programming is a relatively young subdiscipline of computer science. I am happy

to see that the small effort—started twenty years ago by Dave Musser, Deepak Kapur, Aaron

Kershenbaum and me—led to a new generation of libraries such as BGL and MTL. And I

have to congratulate Indiana University on acquiring one of the best generic programming

teams in the world. I am sure they will do other amazing things!

Alexander Stepanov

Palo Alto, California

September, 2001

I would like to thank John Wilkinson, Mark Manasse, Marc Najork and Jeremy Siek for many valuable

suggestions.

Preface

The graph abstraction is a powerful problem-solving tool used to describe relationships be-

tween discrete objects. Many practical problems can be modeled in their essential form by

graphs. Such problems appear in many domains: Internet packet routing, telephone network

design, software build systems, Web search engines, molecular biology, automated road-trip

planning, scientiﬁc computing, and so on. The power of the graph abstraction arises from

the fact that the solution to a graph-theoretic problem can be used to solve problems in a

wide variety of domains. For example, the problem of solving a maze and the problem of

ﬁnding groups of Web pages that are mutually reachable can both be solved using depth-

ﬁrst search, an important concept from graph theory. By concentrating on the essence of

these problems—the graph model describing discrete objects and the relationships between

them—graph theoreticians have created solutions to not just a handful of particular problems,

but to entire families of problems.

Now a question arises. If graph theory is generally and broadly applicable to arbitrary

problem domains, should not the software that implements graph algorithms be just as broadly

applicable? Graph theory would seem to be an ideal area for software reuse. However, up until

now the potential for reuse has been far from realized. Graph problems do not typically occur

in a pure graph-theoretic form, but rather, are embedded in larger domain-speciﬁc problems.

As a result, the data to be modeled as a graph are often not explicitly represented as a graph

but are instead encoded in some application-speciﬁc data structure. Even in the case where

the application data are explicitly represented as a graph, the particular graph representation

chosen by the programmer might not match the representation expected by a library that the

programmer wants to use. Moreover, different applications may place different time and

space requirements on the graph data structure.

This implies a serious problem for the graph library writer who wants to provide reusable

software, for it is impossible to anticipate every possible data structure that might be needed

and to write a different version of the graph algorithm speciﬁcally for each one. The current

state of affairs is that graph algorithms are written in terms of whatever data structure is

most convenient for the algorithm and users must convert their data structures to that format

in order to use the algorithm. This is an inefﬁcient undertaking, consuming programmer

time and computational resources. Often, the cost is perceived not to be worthwhile, and the

programmer instead chooses to rewrite the algorithm in terms of his or her own data structure.

xvii

xviii PREFACE

This approach is also time consuming and error prone, and will tend to lead to sub-optimal

solutions since the application programmer may not be a graph algorithms expert.

Generic Programming

The Standard Template Library (STL) [40] was introduced in 1994 and was adopted shortly

thereafter into the C++ Standard. The STL was a library of interchangeable components for

solving many fundamental problems on sequences of elements. What set the STL apart from

libraries that came before it was that each STL algorithm could work with a wide variety

of sequential data structures: linked-lists, arrays, sets, and so on. The iterator abstraction

provided an interface between containers and algorithms and the C++ template mechanism

provided the needed ﬂexibility to allow implementation without loss of efﬁciency. Each al-

gorithm in the STL is a function template parameterized by the types of iterators upon which

it operates. Any iterator that satisﬁes a minimal set of requirements can be used regardless

of the data structure traversed by the iterator. The systematic approach used in the STL to

construct abstractions and interchangeable components is called generic programming.

Generic programming lends itself well to solving the reusability problem for graph li-

braries. With generic programming, graph algorithms can be made much more ﬂexible, al-

lowing them to be easily used in a wide variety applications. Each graph algorithm is written

not in terms of a speciﬁc data structure, but instead to a graph abstraction that can be eas-

ily implemented by many different data structures. Writing generic graph algorithms has

the additional advantage of being more natural; the abstraction inherent in the pseudo-code

description of an algorithm is retained in the generic function.

The Boost Graph Library (BGL) is the ﬁrst C++ graph library to apply the notions of

generic programming to the construction of graph algorithms.

Some BGL History

The Boost Graph Library began its life as the Generic Graph Component Library (GGCL),

a software project at the Lab for Scientiﬁc Computing (LSC). The LSC, under the direction

of Professor Andrew Lumsdaine, was an interdisciplinary laboratory dedicated to research in

algorithms, software, tools, and run-time systems for high-performance computational sci-

ence and engineering

. Special emphasis was put on developing industrial-strength, high-

performance software using modern programming languages and techniques—most notably,

generic programming.

Soon after the Standard Template Library was released, work began at the LSC to apply

generic programming to scientiﬁc computing. The Matrix Template Library (MTL) was one

The LSC has since evolved into the Open Systems Laboratory (OSL) http://www.osl.iu.edu. Although the

name and location have changed, the research agenda remains the same.

xix

of the ﬁrst projects. Many of the lessons learned during construction of the MTL were applied

to the design and implementation of the GGCL.

An important class of linear algebra computations in scientiﬁc computing is that of sparse

matrix computations, an area where graph algorithms play an important role. As the LSC

was developing the sparse matrix capabilities of the MTL, the need for high-performance

reusable (and generic) graph algorithms became apparent. However, none of the graph li-

braries available at the time (LEDA, GTL, Stanford GraphBase) were written using the

generic programming style of the MTL and the STL, and hence did not fulﬁll the ﬂexibil-

ity and high-performance requirements of the LSC. Other researchers were also expressing

interest in a generic C++ graph library. During a meeting with Bjarne Stroustrup we were

introduced to several individuals at AT&T who needed such a library. Other early work in

the area of generic graph algorithms included some codes written by Alexander Stepanov, as

well as Dietmar K

uhl’s master’s thesis.

With this in mind, and motivated by homework assignments in his algorithms class,

Jeremy Siek began prototyping an interface and some graph classes in the spring of 1998.

Lie-Quan Lee then developed the ﬁrst version of the GGCL, which became his master’s the-

sis project.

During the following year, the authors began collaborating with Alexander Stepanov and

Matthew Austern. During this time, Stepanov’s disjoint-sets-based connected components

implementation was added to the GGCL, and work began on providing concept documenta-

tion for the GGCL, similar to Austern’s STL documentation.

During this year the authors also became aware of Boost and were excited to ﬁnd an

organization interested in creating high-quality, open source C++ libraries. Boost included

several people interested in generic graph algorithms, most notably Dietmar K

uhl. Some

discussions about generic interfaces for graph structures resulted in a revision of the GGCL

which closely resembles the current Boost Graph Library interface.

On September 4, 2000, the GGCL passed the Boost formal review (managed by David

Abrahams) and became the Boost Graph Library. The ﬁrst release of the BGL was September

27, 2000. The BGL is not a “frozen” library. It continues to grow as new algorithms are con-

tributed, and it continues to evolve to meet user’s needs. We encourage readers to participate

in the Boost group and help with extensions to the BGL.

What Is Boost?

Boost is an online community that encourages development and peer-review of free C++

libraries. The emphasis is on portable and high-quality libraries that work well with (and are

in the same spirit as) the C++ Standard Library. Members of the community submit proposals

(library designs and implementations) for review. The Boost community (led by a review

manager) then reviews the library, provides feedback to the contributors, and ﬁnally renders

a decision as to whether the library should be included in the Boost library collection. The

xx PREFACE

libraries are available at the Boost Web site http://www.boost.org. In addition, the Boost mailing

list provides an important forum for discussing library plans and for organizing collaboration.

Obtaining and Installing the BGL Software

The Boost Graph Library is available as part of the Boost library collection, which can

be obtained in several different ways. The CD accompanying this book contains version

1.25.1 of the Boost library collection. In addition, releases of the Boost library collec-

tion can be obtained with your Web browser at http://www.boost.org/boost all.zip for the Win-

dows zip archive of the latest release and http://www.boost.org/boost all.tar.gz for the Unix

archive of the latest release. The Boost libraries can also be downloaded via FTP at

ftp://boost.sourceforge.net/pub/boost/release/.

The zip archive of the Boost library collection can be unzipped by using WinZip or other

similar tools. The Unix “tar ball” can be expanded using the following command:

gunzip −cd boost all.tar.gz | tar xvf −

Extracting the archive creates a directory whose name consists of the word boost and a ver-

sion number. For example, extracting the Boost release 1.25.1 creates a directory boost 1 25 1.

Under this top directory, are two principal subdirectories: boost and libs. The subdirectory

boost contains the header ﬁles for all the libraries in the collection. The subdirectory libs

contains a separate subdirectory for each library in the collection. These subdirectories con-

tain library-speciﬁc source and documentation ﬁles. You can point your Web browser to

boost 1 25 1/index.htm and navigate the whole Boost library collection.

All of the BGL header ﬁles are in the directory boost/graph/. However, other Boost header

ﬁles are needed since BGL uses other Boost components. The HTML documentation is in

libs/graph/doc/ and the source code for the examples is in libs/graph/example/. Regression tests

for BGL are in libs/graph/test/. The source ﬁles in libs/graph/src/ implement the Graphviz ﬁle

parsers and printers.

Except as described next, there are no compilation and build steps necessary to use BGL.

All that is required is that the Boost header ﬁle directory be added to your compiler’s in-

clude path. For example, using Windows 2000, if you have unzipped release 1.25.1 from

boost all.zip into the top level directory of your C drive, for Borland, GCC, and Metrowerks

compilers add ’-Ic:/boost 1 25 1’ to the compiler command line, and for the Microsoft Vi-

sual C++ compiler add ’/I ”c:/boost 1 25 1”’. For IDEs, add ’c:/boost 1 25 1’ (or whatever

you have renamed it to) to the include search paths using the appropriate dialog. Before

using the BGL interface to LEDA or Stanford GraphBase, LEDA or GraphBase must be

installed according to their installation instructions. To use the read graphviz() functions

(for reading AT&T Graphviz ﬁles), you must build and link to an additional library under

boost 1 25 1/libs/graph/src.

The Boost Graph Library is written in ANSI Standard C++ and compiles with most C++

compilers. For an up-to-date summary of the compatibility with a particular compiler, see the

剩余344页未读，继续阅读

davidwkj

粉丝: 2
资源: 3

深入理解Boost Graph Library：用户指南与参考手册

Boost Graph Library快速入门

Boost Graph Library

Boost Graph Library:The User Guide and Reference Manual.pdf

S7-GRAPH编程指南：V5.X Step 7详解与实战应用

神经结构搜索中的可转移方法——Arch-Graph

neo4j-graph-data-science-2.4.0.jar

G_tmp = nx.read_edgelist('../input/google-web-graph/web-Google.txt', create_using = nx.DiGraph)啥意思

graph = image.img_to_graph(img, mask=mask) graph.data = np.exp(-graph.data / graph.data.std()) labels = spectral_clustering(graph, n_clusters=2, eigen_solver="arpack") label_im = np.full(mask.shape, -1.0) label_im[mask] = labels这段的代码是什么意思

opt -dot-callgraph test.ll

configure: error: boost library not found (boost/graph/adjacency_list.hpp).

vis-timeline-graph2d 解决vue.runtime.esm.js:619 [Vue warn]: Error in created hook: "Error: No container provided"

docker驱动器是btrfs，但是docker inspect --format '{{ .GraphDriver.Data.Device }}' 提示no value 是什么意思

用C语言写多段图的最短路径问题算法完整程序代码，可以运行的

最新资源