图是数学抽象，对于解决计算机科学中的许多类型的问题非常有用。因此，这些抽象也必须在计算机程序中表示。用于遍历图的标准通用接口对于鼓励图算法和数据结构的重用至关重要。Boost 图形库的一部分是一个通用接口，它允许访问图的结构，但隐藏了实现的细节。这是一个“开放”接口，因为任何实现此接口的图形库都将与 BGL 通用算法以及也使用此接口的其他算法互操作。BGL 提供了一些符合此接口的通用图类，但它们并非旨在成为“唯一”的图类；当然会有其他图类更适合某些情况。我们认为 BGL 的主要贡献是此接口的制定。
BGL 图形接口和图形组件是泛型的，与标准模板库 (STL) [2] 中的泛型概念相同。在以下章节中，我们将回顾泛型编程在 STL 中扮演的角色，并将其与我们在图形上下文中应用泛型编程的方式进行比较。
当然，如果您已经熟悉泛型编程，请直接深入了解！这是目录。对于分布式内存并行，您还可以查看 Parallel 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>。这只是冰山一角！
像 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，印第安纳大学 (jsiek@osl.iu.edu) 李乐泉 Lie-Quan Lee，印第安纳大学 (llee@cs.indiana.edu) Andrew Lumsdaine，印第安纳大学 (lums@osl.iu.edu) |
