图是数学抽象，可用于解决计算机科学中的许多类型的问题。因此，这些抽象也必须在计算机程序中表示。用于遍历图的标准化通用接口对于鼓励重用图算法和数据结构至关重要。Boost 图形库的一部分是一个通用接口，它允许访问图的结构，但隐藏了实现的细节。这是一种“开放”接口，因为实现此接口的任何图形库都将与 BGL 通用算法以及其他也使用此接口的算法互操作。BGL 提供了一些符合此接口的通用图类，但它们并不意味着是“唯一”的图类；当然会有其他更适合某些情况的图类。我们相信 BGL 的主要贡献是制定了这个接口。
BGL 图接口和图组件是*通用的*，与标准模板库 (STL) 的意义相同 [2]。在以下部分中，我们将回顾泛型编程在 STL 中的作用，并将其与我们在图的上下文中应用泛型编程的方式进行比较。
当然，如果您已经熟悉泛型编程，请直接进入！这是目录。对于分布式内存并行，您还可以查看并行 BGL。
BGL 的源代码作为 Boost 发行版的一部分提供，您可以从此处下载。
**不要！** Boost 图形库是一个仅包含头文件的库，不需要构建即可使用。唯一的例外是GraphViz 输入解析器和GraphML 解析器。
编译使用 BGL 的程序时，**请务必使用优化进行编译**。例如，使用 Microsoft Visual C++ 选择“发布”模式或提供标志-O2或-O3给 GCC。
STL 的泛型有三种方式。
首先，每个算法都是以数据结构中立的方式编写的，允许单个模板函数对许多不同类型的容器进行操作。迭代器的概念是算法和数据结构解耦的关键因素。这种技术的影响是将 STL 的代码大小从 *O(M*N)* 减少到 *O(M+N)*，其中 *M* 是算法的数量，*N* 是容器的数量。考虑到 20 个算法和 5 个数据结构的情况，这将是编写 100 个函数与仅编写 25 个函数之间的区别！随着算法和数据结构数量的增加，差异会越来越大。
STL 泛型的第二种方式是它的算法和容器是可扩展的。用户可以通过使用函数对象来调整和自定义 STL。这种灵活性使 STL 成为解决实际问题的绝佳工具。每个编程问题都带来其自身的一组实体和交互，必须对其进行建模。函数对象提供了一种扩展 STL 以处理每个问题域的 specifics 的机制。
STL 泛型的第三种方式是它的容器在元素类型上参数化。虽然非常重要，但这可能是 STL 泛型中最不“有趣”的方式。泛型编程通常通过参数化列表的简短描述来概括，例如std::list<T>。这几乎是 scratching 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 目前提供两个图类和一个边列表适配器
邻接表类是图类的通用“瑞士军刀”。它高度参数化，因此可以针对不同的情况进行优化：图是有向图还是无向图，允许还是不允许平行边，有效访问仅出边还是也访问入边，快速顶点插入和删除，但代价是额外的空间开销，等等。
邻接矩阵类将边存储在 *|V| x |V|* 矩阵中（其中 *|V|* 是顶点的数量）。此矩阵的元素表示图中的边。邻接矩阵表示特别适用于非常稠密的图，即边数接近 *|V|2* 的图。
边列表类是一个适配器，它接受任何类型的边迭代器并实现边列表图。
| 版权所有 © 2000-2001 |
Jeremy Siek，印第安纳大学 ([email protected]) 李列权，印第安纳大学 ([email protected]) Andrew Lumsdaine，印第安纳大学 ([email protected]) |
