关于计算的公理表达通常颇具争论。然而，现代计算最重要的理论支柱之一的图论并不是这些公理表达之一。无数工程领域（从设计路由器和网络到设计构成移动设备核心的芯片）都是图论的应用。
作为 C++ 应用程序软件开发人员，我们通常需要直接将实际工程问题转化成一个等价的图论问题。如果有一个可靠的基于 C++ 的通用图库，就可以帮助我们实现这个转换，这样的图库显然非常受欢迎：Boost Graph Library (BGL) 将填补这项空白。
在本文中，您首先将创建一个无向图，然后按照常规的遍历例程创建一个有向图。随后，您可以应用一些经典算法，所有算法都不需要添加大量代码。这就是 BGL 的神奇之处。
下载和安装BGL 可从 Boost 网站免费下载（请参阅 ，获取有关的链接）。BGL 是一个仅有头文件的库，因此，以后在应用程序代码中使用该库时，需要在源代码中包含相关的头文件。但是 BGL 需要这个序列化库来进行链接 。以下是一个典型的命令行格式：
1
| root# g++ test_bgl.cpp I/usr/boost/boost_1_44/ -L/usr/boost/boost_1_44/lib
|
如果要试验本文中的代码，您需要安装 Boost 1.44 版本。
邻接表（Adjacency lists）任何图实现的头文件中都有一个邻接表 (adjacency list) 或邻接矩阵。 显示了在 Boost 头文件 adjacency_list.hpp 中如何声明邻接表。
清单 1. 在 Boost 中声明一个邻接表1
2
3
4
5
6
7
8
| template <class OutEdgeListS = vecS,
// a Sequence or an AssociativeContainer class VertexListS = vecS,
// a Sequence or a RandomAccessContainer class DirectedS = directedS,
class VertexProperty = no_property,
class EdgeProperty = no_property,
class GraphProperty = no_property,
class EdgeListS = listS>
class adjacency_list { };
|
为了简便起见，我们将重点放在前三个模板参数。
OutEdgeList 模板参数决定了将用于存储边列表（ edge-list）信息的容器类型。回顾一下图论基础知识就可以知道，对于有向图，只具有入边的那些顶点都有一个对应的空邻接表。默认值被设置为 vecS，该值对应于 std::vector。VertexList 模板参数决定了用于表示该图顶点列表的容器类型，默认值同样被设置为 std::vector。DirectedS 模板参数根据提供的值是 directedS 还是 undirectedS 来确定该图是有向图还是无向图。
在 BGL 中创建一个图在声明邻接表的同时，清单 2 中的代码在 BGL 中创建了一个简单的无向图，边信息将存储在 std::list 中，顶点信息存储在 std::vector 中。
清单 2. 创建一个无向图1
2
3
4
5
6
7
8
9
10
11
| #include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef boost::adjacency_list<listS, vecS, undirectedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
}
|
在清单 2 中，在没有在构造函数中提供任何顶点或边信息的情况下创建了图 g。在运行的时候，会使用诸如 add_edge 和 add_vertex 之类的帮助函数创建边和顶点。add_edge 函数，顾名思义：在一个图的两个顶点之间添加一条边。清单 2 中的代码执行结束后，图 g 应该有 4 个顶点，分别标记为 0、1、2 和 3，顶点 1 与顶点 0 和顶点 2 连接，等等。
遍历图遍历图涉及到使用 vertex_iterator 和 adjacency_iterator 类。前者遍历图的所有顶点，后者遍历相应邻接表。清单 3 展示了该代码。
清单 3. 使用 BGL 遍历图1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #include <boost/graph/adjacency_list.hpp>
using namespace boost;
typedef boost::adjacency_list<listS, vecS, undirectedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
mygraph::vertex_iterator vertexIt, vertexEnd;
mygraph::adjacency_iterator neighbourIt, neighbourEnd;
tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
cout << *vertexIt << " is connected with ";
tie(neighbourIt, neighbourEnd) = adjacent_vertices(*vertexIt, g);
for (; neighbourIt != neighbourEnd; ++neighbourIt)
cout << *neighbourIt << " ";
cout << "\n";
}
}
|
要创建一个有向图，只需要将 清单 3 中的图类型修改为 directedS：
1
2
3
4
5
6
7
8
9
| #include <boost/graph/adjacency_list.hpp> using namespace boost;
typedef boost::adjacency_list<listS, vecS, directedS> mygraph;
int main()
{
mygraph g; add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g); // Same as Listing 3
}
|
帮助函数 vertices 返回一个 std::pair<vertex_iterator 和 vertex_iterator>，前者指向图的第一个顶点。结果存储在多元组 tie (vertexIt, vertexEnd) 中，随后会使用 vertexIt 遍历该图。同样，帮助函数 adjacent_vertices 将会返回 std::pair<adjacency_iterator, adjacency_iterator>，第一个 adjacency_iterator 指向邻接表中的第一个元素。
配置一个邻接表BGL 的优势之一是它是高度可配置的。BGL 允许您使用下列任何选择器类型来配置顶点集和边集合，这些选择器类型都是在头文件中定义的；您需要做的就是在声明图时使用它们：
- vecS 选择 std::vector
- lists 适用于 std::list
- slistS 选择 std::slist
- setS 选择 std::set
- multiSetS 选择 std::multiset
- hash_setS 选择 std::hash_set
如果代码中可能有很多顶点插入操作，但删除操作却不是太多，那么 VertexList 可能是 vecS 或 listS。除了向量需要再分配之外，push_back 通常是一个常量。如果您要执行很多插入和删除操作，那么与 vecS 相比，listS 是一个不错的选择，因为从向量中删除一个元素通常是代价昂贵的，而且很耗时。
创建无向图的另一种方法如果不使用基于邻接表的方法创建无向图，那么您可以使用 BGL 提供的 undirected_graph 类（在 undirected_graph.hpp 中定义）创建该图。但是，该类在内部使用了一个邻接表，而且使用基于邻接表的图通常会提供更大的灵活性。清单 4 展示了有关代码。
清单 4. 使用 undirected_graph.hpp 创建一个无向图1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <undirected_graph.hpp> #include <iostream> using namespace boost;
using namespace std;
int main( )
{
undirected_graph<>g;
undirected_graph<>:vertex_descriptor u = g.add_vertex();
undirected_graph<>:vertex_descriptor v = g.add_vertex();
undirected_graph<>:vertex_descriptor w = g.add_vertex();
undirected_graph<>:vertex_descriptor x = g.add_vertex();
add_edge(u, v, g); add_edge(u, w, g); add_edge(u, x, g);
cout << "Degree of u: " << degree(u, g);
return 0;
}
|
在清单 4 中，我使用 add_vertex 向图中添加独立的顶点，使用 add_edge 向图中添加边。最后，通过调用 degree 方法得出单个顶点的度数。清单 5 提供了 undirected_graph 的声明和定义（来自 Boost 源代码）。
清单 5. 解密 BGL undirected_graph1
2
3
4
5
6
7
8
9
10
11
12
| template < typename VertexProp = no_property,
typename EdgeProp = no_property,
typename GraphProp = no_property> class undirected_graph
{ // public:
typedef adjacency_list<listS,
listS, undirectedS,
vertex_property,
edge_property,
GraphProp,
listS> graph_type;
private: graph_type m_graph; //
};
|
跟踪一个顶点的入边（in-edges）和出边（out-edges）可以使用 out_edges 帮助函数访问一个顶点的出边，使用 in_edges 访问入边。BGL 的优势之一就是可以使用 cout 直接输出一条边，显示这条边连接的顶点。清单 6 展示了相关代码。
清单 6. 遍历有向图的顶点1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| #include <boost/graph/adjacency_list.hpp> using namespace boost;
typedef boost::adjacency_list<listS, vecS, directedS> mygraph;
int main()
{
mygraph g;
add_edge (0, 1, g);
add_edge (0, 3, g);
add_edge (1, 2, g);
add_edge (2, 3, g);
mygraph::vertex_iterator vertexIt, vertexEnd;
mygraph::in_edge_iterator inedgeIt, inedgeEnd;
mygraph::in_edge_iterator outedgeIt, outedgeEnd; tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
cout << "incoming edges for " << *vertexIt << ": ";
tie(inedgeIt, inedgeEnd) = in_edges(*vertexIt, g);
for(; inedgeIt != inedgeEnd; ++inedgeIt)
{
cout << *inedgeIt << " ";
}
cout << "\n";
}
for (; vertexIt != vertexEnd; ++vertexIt)
{
std::cout << "out-edges for " << *vertexIt << : ;
tie(outedgeIt, outedgeEnd) = out_edges(*vertexIt, g); // Similar to incoming edges
}
}
|
编译清单 6 中的顶点将会出现错误。要修复该错误，只需在 mygraph 声明中使用 bidirectionalS 代替 directedS。在 BGL 中使用 directedS 标签时，只允许您使用 out_edges 帮助函数以及相关遍历。使用 in_edges 需要将图的类型更改为 bidirectionalS，尽管该图或多或少仍然是一个有向图。
注意：使用 in_edges 会产生额外的空间开销（与使用 directedS 相比，每条边成本增加了一倍），所以要确保该成本是您可以承受的。 |
