Boost Graph Library 快速入门

by 燕飞龙 南亮亮

采用boost中的邻接链表：adjacency_list<> 实现图的定义

下面是一个邻接链表定义的例子：

#include <boost/graph/adjacency_list.hpp>

// 首先定义图中节点和边的属性

struct VertexProperty { // 图节点中保存的信息

       unsigned int index;

Color        color;

};

struct EdgeProperty {  // 图边中保存的信息

      unsigned int index;

      float         weight;

};

// 图的定义。后面两个参数分别是节点属性和边属性

typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;

// 节点描述符

typedef graph_traits<Graph>::vertex_descriptor   VertexDescriptor; 

// 边描述符

typedef graph_traits<Graph>::edge_descriptor     EdgeDescriptor;  

// 下面是邻接链表的一些遍历器

typedef graph_traits<GGraph>::vertex_iterator     VertexIterator;

typedef graph_traits<GGraph>::edge_iterator      EdgeIterator;

typedef graph_traits<GGraph>::adjacency_iterator  AdjacencyIterator;

typedef graph_traits<GGraph>::out_edge_iterator   OutEdgeIterator;

关键操作：

1． 在图中加入节点  add_vertex()

VertexProperty vp;

vp.index = i;

vp.color = c;

add_vertex(vp, graph);

当然可以不加属性：add_vertex(graph)在图中加入一个节点，但是除了描述符没有其它信息。

2． 在图中加入边 add_edge()

EdgeProperty ep;

ep.index = i;

ep.weight = w;

add_edge(id1, id2, ep, graph); // 同样，可以不加边的属性，只用三个参数。

3． 利用描述符访问相应节点 / 边的属性

VertexProperty vp = graph[vd];      // vd为VertexDescriptor

const EdgeProperty& ep = graph[ed];  // ed为EdgeDescriptor

4． 利用节点迭代器遍历节点。vertices()返回迭代器的头和尾。节点迭代器指向该节点的描述符。

std::pair<VertexIterator, VertexIterator> vi = vertices(graph);

for (VertexIterator vit = vi.first; vit! = vi.second; ++vit) {

VertexDescriptor vd = *vit;

VertexProperty&  vp = graph[vd]; // 可以读取和修改顶点属性

…

 }

5． 利用边迭代器遍历边。edges()返回迭代器的头和尾。边迭代器指向该边的描述符。

std::pair<EdgeIterator, EdgeIterator> ei = edges(graph);

for (EdgeIterator eit = ei.first; eit! = ei.second; ++eit) {

EdgeDescriptor  ed = *eit; 

EdgePropperty&  ep = graph[ed];  // 可以读取和修改边的属性

…

VertexDescriptor sd = source(ed, graph);

VertexDescriptor td = target(ed, graph);

VertexProperty& s_vp = graph[sd]; // 可以读取和修改顶点属性

VertexProperty& t_vp = graph[td];

…

 }

6． 判断两节点是否相邻 / 访问两相邻节点关联的边

std::pair<EdgeDescriptor, bool> test = edge(vd1, vd2, graph);

if (test.second == true) { // 判断vd1和vd2所指的两节点是否相邻  

EdgeDescriptor  ed = test.first;

…

 }

7． 访问某一节点的相邻节点

std::pair<AdjacencyIterator, AdjacencyIterator> ai = adjacent_vertices(vd, graph);

for (AdjacencyIterator ait = ai.first; ait! = ai.second; ++ait) {

        VertexDescriptor vd = *ait;

VertexProperty&  vp = graph[vd]; // 可以读取和修改顶点属性

…

 }