C++图常用库boost graph library(一)

接下来一段日子，会写一些跟bgl相关的内容。bgl是一个性能很不错的库，但是源码跟鬼畜一样…文档也写得很乱。因为最近做的论文需要比较好的性能，实在不得不硬着头皮重新用起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
28
29
30
31
32
33
34
#include <iostream>                  // for std::cout
#include <utility>                   // for std::pair
#include <algorithm>                 // for std::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using namespace boost;

int main(int,char*[])
{
  // create a typedef for the Graph type
  typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;

  // Make convenient labels for the vertices
  enum { A, B, C, D, E, N };
  const int num_vertices = N;
  const char* name = "ABCDE";

  // writing out the edges in the graph
  typedef std::pair<int, int> Edge;
  Edge edge_array[] = 
  { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
    Edge(C,E), Edge(B,D), Edge(D,E) };
  const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);

  // declare a graph object
  Graph g(num_vertices);

  // add the edges to the graph object
  for (int i = 0; i < num_edges; ++i)
    add_edge(edge_array[i].first, edge_array[i].second, g);
  return 0;
}

基本概念

  1. Vertex Descriptors 与 Edge Descriptors

    在BGL里面，我们需要对点和边进行相应的操作。于是BGL定义了点描述符和边描述符，也可以称为句柄。要对一个点或者边进行操作，我们需要用过句柄（描述符）进行操作。对于一个图，要获取描述符的类型，只能通过一个graph_traits的类进行获取。graph_traits是对图类型进行描述的一个类，包含了图结构的各种信息。

1
2
3
4
5
6
7
template <typename Graph> bool is_self_loop(typename graph_traits<Graph>::edge_descriptor e, const Graph& g) 
{
	typename graph traits<Graph>::vertex_descriptor u, v; 
	u = source(e, g); 
	v = target(e, g); 
	return u == v;
}

上面这个例子是判断一条边是不是自环。函数传进两个参数，第一个参数是边的修饰符，第二个参数是图。line 3创建两个点修饰符，source和target分别是获取边修饰符所代表的边的首尾两个顶点的修饰符。最后判断是否相同。

  1. Property Maps

    在BGL里面，另外比较重要的一个结构是Property Maps。这个概念可以理解成点或者边上的属性，比如点上可以有attribute（attribute graph），边上可以有权重。当然，用户也可以在自己的代码里面自己定义，比如存在hashmap。但是BGL提供了这样一个统一的结构，用户就可以写一些可以通用的算法。

    1
    2
    3
    4
    5
    template <typename VertexDescriptor, typename VertexNameMap> void 
    print_vertex_name(VertexDescriptor v, VertexNameMap name_map) 
    {
    	std::cout << get(name_map, v); 
    }

  2. 图的访问/遍历

BGL提供了五种方式对图的访问，都是通过迭代器来完成的。

a. 点迭代器（vertex iterator）：迭代器里面的元素是点描述符（点句柄）。

b. 边迭代器（edge iterator）：迭代器里面的元素是边描述符（边句柄）。

c. 出边迭代器（out-edge iterator）。用来访问某个点的所有出边的迭代器，迭代器里面的元素是边描述符（边句柄）。

d. 入边迭代器（in-edge iterator）。用来访问某个点的所有入边的迭代器，迭代器里面的元素是边描述符（边句柄）。

e. 邻接迭代器（adjacency iterator）。用来访问一个顶点的所有邻接点。迭代器里面的元素是点描述符（点句柄）。

跟描述符一样，迭代器的类型也是通过graph_traits这个类来确定与获取。

1
2
3
4
5
6
7
8
9
10
11
12
template <typename Graph, typename VertexNameMap> void print_vertex_names(const Graph& g, VertexNameMap name_map) 
{
	std::cout << "vertices(g) = { "; 
	typedef typename graph traits<Graph>::vertex iterator_iter t; 
	for (std::pair<iter_t, iter_t> p = vertices(g);
	p.first != p.second; ++p.first) 
	{ 
		print_vertex_name(*p.first, name_map); 
		std::cout << ’ ’;
	} 
	std::cout << "}" << std::endl; 
}

  1. 图的创建与修改

下面这个例子添加了五个点，同时添加了七条边。

a. 添加点
add_vertex 传入的参数是graph，返回是一个点描述符。
a. 添加边
add_edge(a, b, g)传入的参数是首尾两个点的描述符，第三个参数是要插边的图。返回一个tie，tie中第一个元素是边描述符，第二个元素表示是否成功插入图中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
template <typename Graph, typename VertexNameMap, typename TransDelayMap> void build_router_network(Graph& g, VertexNameMap name_map, TransDelayMap delay_map)
{
	typename graph traits<Graph>::vertex descriptor a, b, c, d, e; 
	a = add_vertex(g); name_map[a] = ’a’; 
	b = add_vertex(g); name_map[b] = ’b’; 
	c = add_vertex(g); name_map[c] = ’c’; 
	d = add_vertex(g); name_map[d] = ’d’; 
	e = add_vertex(g); name_map[e] = ’e’;
	typename graph traits<Graph>::edge_descriptor ed;
	bool inserted;
	tie(ed, inserted) = add_edge(a, b, g); delay_map[ed] = 1.2; 
	tie(ed, inserted) = add_edge(a, d, g); delay_map[ed] = 4.5; 
	tie(ed, inserted) = add_edge(b, d, g); delay_map[ed] = 1.8; 
	tie(ed, inserted) = add_edge(c, a, g); delay_map[ed] = 2.6; 
	tie(ed, inserted) = add_edge(c, e, g); delay_map[ed] = 5.2;
	tie(ed, inserted) = add_edge(d, c, g); 
	delay_map[ed] = 0.4; 
	tie(ed, inserted) = add_edge(d, e, g); 
	delay_map[ed] = 3.3;
}

  1. 算法访问器（Algorithm Visitors）

这个机制有点像排序中的compare()函数。对于内置的算法，会作为参数把函数传递进去，进而执行特定的操作。比如我们有一个任务，需要对图进行宽度优先遍历。bgl是提供宽度优先遍历的算法。但是如果我们要输出每个顶点的名字，就需要我们提供一个vistor的函数。下面是一个vistor的例子。

1
2
3
4
5
6
7
8
9
template <typename VertexNameMap> class bfs name printer : public default_bfs_visitor 
{ // inherit default (empty) event point actions
	public: bfs_name_printer(VertexNameMap n map) : m name map(n_map) { } 
	template <typename Vertex, typename Graph> void discover_vertex(Vertex u, const Graph& ) const 
	{ 
		std::cout << get(m_name_map, u) << ’ ’;
	}
	private: VertexNameMap m_name_map;
};

当用户调用宽度优先遍历的函数时，可以如下将vistor传递进去。

1
2
3
4
bfs_name_printer<VertexNameMap> vis(name_map);
std::cout << "BFS vertex discover order: "; 
breadth_first_search(g, a, visitor(vis)); 
std::cout << std::endl;

资源