一些有用的 BGL 函数现在，我们来看一些 BGL 提供的之前我们并没有讨论过的重要实用函数。
您可以使用下列函数进行图访问：
- std::pair<edge_iterator, edge_iterator> edges(const adjacency_list& g)：返回图 g 中边的相对应迭代程序对
- vertices_size_type num_vertices(const adjacency_list& g)： 返回图 g 中顶点的数量
- edges_size_type num_edges(const adjacency_list& g)：返回图 g 中边的数量
- vertex_descriptor source(edge_descriptor e, const adjacency_list& g)：返回一条边的源顶点
- vertex_descriptor target(edge_descriptor e, const adjacency_list& g)：返回一条边的目标顶点
- degree_size_type in_degree(vertex_descriptor u, const adjacency_list& g)：返回一个顶点的入度 (in-degree)
- degree_size_type out_degree(vertex_descriptor u, const adjacency_list& g)：返回一个顶点的出度 (out-degree)
显示了执行大量图访问的代码。
清单 7. 使用 BGL 进行图访问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
| // usual typedefs here, refer to previous listings
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
cout << "Number of edges: " << num_edges(g) << "\n";
cout << "Number of vertices: " << num_vertices(g) << "\n";
mygraph::vertex_iterator vertexIt, vertexEnd; tie(vertexIt, vertexEnd) = vertices(g);
for (; vertexIt != vertexEnd; ++vertexIt)
{
std::cout << "in-degree for " << *vertexIt << ": "
<< in_degree(*vertexIt, g) << "\n";
std::cout << "out-degree for " << *vertexIt << ": "
<< out_degree(*vertexIt, g) << "\n";
}
mygraph::edge_iterator edgeIt,
edgeEnd; tie(edgeIt, edgeEnd) = edges(g);
for (; edgeIt!= edgeEnd; ++edgeIt)
{ std::cout << "edge " << source(*edgeIt, g) << "-->"
<< target(*edgeIt, g) << "\n";
}
}
|
您可以使用下列代码来修改图：
- void remove_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g)：从图 g 中删除一条边
- void remove_edge(edge_descriptor e, adjacency_list& g)：从图 g 中删除一条边
- void clear_vertex(vertex_descriptor u, adjacency_list& g)： 删除顶点 u 的所有边
- void clear_out_edges(vertex_descriptor u, adjacency_list& g)：删除有向图 g 中顶点 u 的所有出边（不适用于无向图）
- void clear_in_edges(vertex_descriptor u, adjacency_list& g)： 删除有向图 g 中顶点 u 的所有入边（不适用于无向图）
- void remove_vertex(vertex_descriptor u, adjacency_list& g)： 从图 g 中删除一个顶点（如果已使用 clear_vertex 或其他适当函数删除与该定顶点相关的所有边。）
使用 BGL 创建一个有向加权图现在，您应该已经对有向图有所了解，下一个逻辑任务是使用 BGL 创建一个加权有向图。回顾一下 中的邻接表声明，您会发现一个名为 EdgeProperty 的模板参数。您可以用这个模板参数来构造有向加权图。
property 是一个可分配给顶点和边的参数。您可以使用一个标签名和一个与 property 相关的类型来定义该属性。BGL 有几个可用的标签名，其中包括 edge_weight_t 和 vertex_name_t。例如，要在图的顶点中存储标签名，可以将一个 property 定义为 typedef property<vertex_name_t, std::string> VertexNameProperty，然后将该属性传递给图的模板声明中的 VertexProperty 参数。
这是一个边权重的 property 声明：
1
| typedef property<edge_weight_t, int> EdgeWeightProperty;
|
既然已经创建了 EdgeWeightProperty，那么现在稍微调整一下 mygraph 定义：
1
2
3
4
| typedef boost::adjacency_list<listS,
vecS, directedS,
no_property,
EdgeWeightProperty> mygraph;
|
最后，如果向图中添加边，则需要使用新加载的 add_edge，并接受权重作为第 3 个参数。 提供了完整的代码。
清单 8. 创建一个加权有向图1
2
3
4
5
6
7
8
9
10
11
12
13
14
| #include <boost/graph/adjacency_list.hpp> using namespace boost;
typedef property<edge_weight_t, int> EdgeWeightProperty;
typedef boost::adjacency_list<listS, vecS, directedS, no_property,
EdgeWeightProperty > mygraph;
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
}
|
BGL 中的最小生成树（spanning tree）BGL 最精彩地方的就是有大量可用于图的预定义算法：Kruskal、Prim、Dijkstra 等，凡是您说得出的，BGL 都有。修改 中的代码，从而拥有一个具有加权边的无向图，然后使用 Kruskal 算法得到最小生成树，此时您就会明白我的意思了。BGL 将每个算法放在不同的头文件中，因此，要使用 Kruskal 算法，必须包含 boost/graph/kruskal_min_spanning_tree.hpp 头文件。 展示了相关代码。
清单 9. 使用 Kruskal 算法得到最小生成树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <boost/graph/adjacency_list.hpp> // typedef boost::adjacency_list<listS,
vecS, directedS, no_property, EdgeWeightProperty > mygraph;
typedef mygraph::edge_descriptor Edge;
int main()
{
mygraph g;
add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
std::list < Edge > spanning_tree;
kruskal_minimum_spanning_tree (g, std::back_inserter(spanning_tree));
for (std::list < Edge >::iterator ei = spanning_tree.begin(); ei != spanning_tree.end();
++ei)
{
cout << *ei << " ";
}
cout << "\n";
}
|
函数 kruskal_minimum_spanning_tree 在后台展示了它的神奇之处。它将图和迭代程序纳入存储边的容器中。请注意，spanning_tree 声明：我在这里使用了一个列表，但它可以是任何对象，比如一个顶点。BGL 所关心的是第二个参数必须是 Standard Template Library (STL) 输出的迭代程序类型。
使用 BGL 进行深度优先搜索宽度优先搜索和深度优先搜索是图遍历的关键，BGL 为这些操作提供了大量支持。需要包含的相关头文件是 boost/graph/depth_first_search.hpp；相关例程是 depth_first_search。BGL 提供多个 depth_first_search 接口；所有接口都需要将所谓的访客对象传递给该方法。
BGL 中的访客（visitor） 在 STL 中充当仿函数角色，除此之外，它还可以做很多事情。访客没有 operator() 之类的单个方法，但可以灵活地定义几种方法，比如 initialize_index、start_index、discover_index 和 examine_edge。毫不夸张地说，BGL 通过提供这些 hook 函数可以让您定制 DFS。首先我们看一个使用 DFS 的样例代码（参见 ）。
清单 10. 使用 BGL 的 DFS 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
29
30
| #include <boost/graph/adjacency_list.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <iostream>
using namespace std;
using namespace boost;
typedef property<edge_weight_t, int>
EdgeWeightProperty;
typedef boost::adjacency_list
< listS, vecS, undirectedS, no_property, EdgeWeightProperty>
mygraph;
class custom_dfs_visitor : public boost::default_dfs_visitor
{ public: template < typename Vertex, typename Graph >
void discover_vertex(Vertex u, const Graph & g)
const { std::cout << "At " << u << std::endl; }
template < typename Edge, typename Graph >
void examine_edge(Edge e, const Graph& g)
const { std::cout << "Examining edges " << e << std::endl;
}
};
int main()
{
mygraph g; add_edge (0, 1, 8, g);
add_edge (0, 3, 18, g);
add_edge (1, 2, 20, g);
add_edge (2, 3, 2, g);
add_edge (3, 1, 1, g);
add_edge (1, 3, 7, g);
custom_dfs_visitor vis;
depth_first_search(g, visitor(vis));
}
|
清单 10 声明了一个名为 custom_dfs_visitor 的类，这个类定义了两个 hook 函数：discover_vertex 和 examine_edges。前者在第一次遇到顶点时调用，后者在找到该顶点之后在该顶点的每个出边上调用。
因此，如果在访客 (vis) 中将 vis 的类型设置为 boost_default_visitor，会发生什么呢？是的，您猜对了：什么都不会显示。 显示了 BGL 提供的 hook 函数的一个简单概述。
表 1. 使用 DFS 进行遍历的 BGL hook 函数Hook 函数用途start_vertex(u, g)在开始遍历之前调用源顶点discover_vertex(u, g)第一次调用顶点时调用finish_vertex(u, g)如果 u 是一个树的根节点，则在调用该树上其他所有元素之后调用 finish_vertex。如果 u 是一个叶子节点，则在完成 u 所有出边的检查之后调用该方法。 examine_edge(u, g)找到顶点 u 后，调用其每个出边tree_edge(u, g)当一条边成为搜索树的边时调用back_edge(u, g)调用一个图的回边（back edges）；用于无向图，因为 (u, v) 和 (v, u) 是同一条边，所以 tree_edge 和 back_edge 均被调用
请注意，BGL 还支持其他访客，比如 dijkstra_visitor、bellman_visitor 和 astar_visitor。 |
