图是数学抽象，可用于解决计算机科学中的多种问题。因此，这些抽象也必须在计算机程序中表示。拥有标准化的通用遍历图的接口至关重要，这有助于鼓励图算法和数据结构的重用。Boost 图形库的一部分提供了一个通用接口，允许访问图的结构，同时隐藏了实现的细节。这是一个“开放”的接口，意味着任何实现了此接口的图库都将与 BGL 的通用算法以及使用此接口的其他算法相互操作。BGL 提供了一些符合此接口的通用图类，但它们并非旨在成为“唯一”的图类；在某些情况下，肯定会有其他图类更合适。我们认为 BGL 的主要贡献在于该接口的制定。
BGL 的图接口和图组件是*通用的*，这一点与标准模板库 (STL) [2] 的含义相同。在接下来的章节中，我们将回顾泛型编程在 STL 中扮演的角色，并将其与我们在图的背景下应用泛型编程的方式进行比较。
当然，如果您已经熟悉泛型编程，请直接开始阅读！这是目录。对于分布式内存并行，您还可以查看并行 BGL。
BGL 的源代码可作为 Boost 发行版的一部分获取，您可以在此处下载。
不要！ Boost 图形库是纯头文件库，无需构建即可使用。唯一的例外是GraphViz 输入解析器和GraphML 解析器。
在编译使用 BGL 的程序时，务必启用优化。例如，在 Microsoft Visual C++ 中选择“Release”模式，或为 GCC 提供标志-O2或-O3。
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! (这 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) |
