Boost C++ 库
...这是世界上最受推崇、设计最精良的 C++ 库项目之一。
— Herb Sutter 和 Andrei Alexandrescu, C++ Coding Standards
Boost C++ 库
...这是世界上最受推崇、设计最精良的 C++ 库项目之一。
— Herb Sutter 和 Andrei Alexandrescu, C++ Coding Standards
图是数学抽象，可用于解决计算机科学中的许多类型的问题。因此，这些抽象也必须在计算机程序中表示。用于遍历图的标准通用接口对于鼓励图算法和数据结构的重用至关重要。Boost 图形库的一部分是一个通用接口，它允许访问图的结构，但隐藏了实现的细节。这是一个“开放”接口，意味着任何实现此接口的图库都将与 BGL 通用算法以及使用此接口的其他算法互操作。BGL 提供了一些符合此接口的通用图类，但它们并非 meant to be “唯一”的图类；肯定会有其他图类在某些情况下更好。我们相信 BGL 的主要贡献在于该接口的制定。
BGL 图接口和图组件是*通用*的，与标准模板库 (STL) [2] 的意义相同。在以下各节中，我们将回顾通用编程在 STL 中扮演的角色，并将其与我们在图的上下文中应用通用编程的方式进行比较。
当然，如果您已经熟悉通用编程，请直接开始！这是目录。对于分布式内存并行，您也可以查看并行 BGL。
BGL 的源代码可作为 Boost 发行版的一部分提供，您可以在此处下载。
不要！ Boost 图形库是仅头文件库，无需构建即可使用。唯一的例外是GraphViz 输入解析器和GraphML 解析器。
在编译使用 BGL 的程序时，务必启用优化。例如，在 Microsoft Visual C++ 中选择“Release”模式或提供标志-O2或-O3对于 GCC。
STL 在三个方面是通用的。
首先，每个算法都以一种数据结构无关的方式编写，允许单个模板函数操作许多不同类别的容器。迭代器的概念是算法和数据结构解耦的关键要素。这项技术的影响是将 STL 的代码大小从 *O(M*N)* 减小到 *O(M+N)*，其中 M 是算法的数量，N 是容器的数量。考虑到有 20 个算法和 5 个数据结构的情况，这将是从编写 100 个函数与仅编写 25 个函数之间的区别！随着算法和数据数量的增加，差异会越来越大。
STL 通用的第二个方式是其算法和容器是可扩展的。用户可以通过使用函数对象来适应和定制 STL。这种灵活性是 STL 成为解决现实世界问题的强大工具的原因。每个编程问题都带来自己的一组实体和交互，必须对其进行建模。函数对象提供了一种机制，用于扩展 STL 以处理每个问题域的特定问题。
STL 通用的第三个方式是其容器是按元素类型参数化的。虽然这非常重要，但这可能是 STL 通用性中最不“有趣”的方式。通用编程通常通过对参数化列表的简要描述来总结，例如std::list<T>。这 hardly scratches the surface！
与 STL 类似，BGL 在三个方面是通用的。
首先，BGL 的图算法是针对一个抽象了特定图数据结构细节的接口编写的。与 STL 类似，BGL 使用迭代器来定义数据结构遍历的接口。有三种不同的图遍历模式：遍历图中的所有顶点、遍历所有边以及沿图的邻接结构（从一个顶点到其每个邻居）。每种遍历模式都有单独的迭代器。
这个通用接口允许模板函数，如breadth_first_search()，在各种图数据结构上工作，从用指针连接的节点实现的图到用数组编码的图。这种灵活性在图领域尤其重要。图数据结构通常是为特定应用程序定制的。传统上，如果程序员想重用算法实现，他们必须将自己的图数据转换为/复制到图库规定的图结构中。LEDA、GTL、Stanford GraphBase 等库就是这种情况；用 Fortran 编写的图算法尤其如此。这极大地限制了其图算法的重用。
相比之下，使用 BGL 的通用图算法，可以通过*外部适配*（参见第 如何将现有图转换为 BGL 节）来按原样使用定制（甚至遗留）的图结构。外部适配在不复制数据也不将数据放入适配器对象的情况下，围绕数据结构包装新接口。BGL 接口经过精心设计，易于进行这种适配。为了说明这一点，我们构建了用于在 BGL 图算法中使用各种图结构（LEDA 图、Stanford GraphBase 图，甚至 Fortran 风格的数组）的接口代码。
其次，BGL 的图算法是可扩展的。BGL 引入了*访问者*的概念，它只是一个具有多个方法的函数对象。在图算法中，通常有几个关键的“事件点”，在这些点上插入用户定义的运算很有用。访问者对象有一个在每个事件点调用的不同方法。特定的事件点和相应的访问者方法取决于特定的算法。它们通常包括诸如start_vertex(), discover_vertex(), examine_edge(), tree_edge()和finish_vertex().
BGL 通用的第三种方式类似于 STL 容器中元素类型的参数化，尽管对于图来说，情况又复杂一些。我们需要将值（称为“属性”）与图的顶点和边相关联。此外，通常需要将多个属性与每个顶点和边相关联；这就是我们所说的多参数化。STLstd::list<T>类有一个参数T用于其元素类型。类似地，BGL 图类具有用于顶点和边“属性”的模板参数。属性指定属性的参数化类型，并为属性分配一个标识标签。此标签用于区分边或顶点可能拥有的多个属性。通过*属性映射*可以获得附加到特定顶点或边的属性值。每个属性都有一个单独的属性映射。
传统的图库和图结构在图属性参数化方面存在不足。这是图数据结构必须为应用程序定制构建的主要原因之一。BGL 图类中属性的参数化使其非常适合重用。
BGL 算法由一组核心算法*模式*（实现为通用算法）和一组更大的图算法组成。核心算法模式是
算法模式本身不计算图上的任何有意义的数量；它们仅仅是构建图算法的构建块。BGL 中的图算法目前包括
BGL 目前提供了两个图类和一个边列表适配器
该adjacency_list类是通用的“瑞士军刀”图类。它经过高度参数化，可以针对不同情况进行优化：图是有向的还是无向的，允许或禁止并行边，高效地访问出边或也访问入边，以额外的空间开销为代价进行快速的顶点插入和删除等。
该adjacency_matrix类将边存储在*|V| x |V|* 矩阵中（其中 |V| 是顶点的数量）。此矩阵的元素表示图中的边。邻接矩阵表示尤其适用于非常稠密的图，即边数接近 |V|2 的图。
该edge_list类是一个适配器，它接受任何类型的边迭代器并实现边列表图。
| 版权所有 © 2000-2001 |
Jeremy Siek, Indiana University (jsiek@osl.iu.edu) 李列权，印第安纳大学 (llee@cs.indiana.edu) Andrew Lumsdaine，印第安纳大学 (lums@osl.iu.edu) |