Li Min's Blog

今天因为程序要用，把The Boost Graph Library: User Guide and Reference Manual这本书借了过来，发现作者Lie-Quan Lee竟然是浙江大学物理系毕业的,牛人啊，景仰，因为BGL的代码是在太复杂了。

拿着书看还是很明白的，总结如下：

1. vertex descriptor 和 edge descriptors 就是图中vertex和edge的类型，如果知道一个图的类型为graph_t，总可以通过以下代码得到相应的vertex and edge descriptor

graph_traits< graph_t >::vertex_descriptor
graph_traits< graph_t >::edge_descriptor

2.Porperty Maps。这个比较复杂，我是写了一个例程才明白一二的。

using namespace boost;

typedef adjacency_list < listS, listS, undirectedS,
        property < vertex_name_t, std::string > > graph_t;
typedef property_map < graph_t, vertex_name_t >::type name_map_t;
typedef graph_traits < graph_t >::vertex_descriptor VertexDescrip;

graph_t myG(3);

VertexDescrip a, b, c;
name_map_t vertexNameMap = get(vertex_name, myG);

a = add_vertex(myG); vertexNameMap[a] = std::string("first");
b = add_vertex(myG); vertexNameMap[b] = "second";
c = add_vertex(myG); vertexNameMap[c] = "third";

其中property < vertex_name_t, std::string >就是定义vertex_name_t的类型是std::string. vertex_name_t是内置类型，我们也可以自定义类型，比如property < vertex_color_t, RGB >，只要符合vertex_***_t这个命名规则并且事先注册之就可以了。注册方法如下：

namespace boost {
    enum vertex_color_t    { vertex_color = 123}; // a unique #
    BOOST_INSTALL_PROPERTY(vertex, color);
}

定义好property之后就可以定义vertex和此property之间对应的map

typedef property_map < graph_t, vertex_name_t >::type name_map_t;
...
name_map_t vertexNameMap = get(vertex_name, myG); //实例化

之后就可以通过这个MAP用vertex作为key存取相应的属性值

a = add_vertex(myG); vertexNameMap[a] = std::string("first");

3. 端点和边的遍历

这个例子演示了如何遍历所有vertices

graph_traits< graph_t >::vertex_iterator vi, vi_end;
for (tie(vi, vi_end)= vertices(myG); vi != vi_end; ++vi)
{
    std::cout << vertexNameMap(*vi);
}

还有一种写法

typedef graph_traits< graph_t >::vertex_iterator v_iter_t
for (std::pair< v_iter_t, v_iter_t > p = vertices(myG); p.first!= p.second; ++p.first)
{
    std::cout << vertexNameMap(*p.first);
}

同时用edges(myG)获得所有边

4. 加入点和边。

// Add vertices
vertex1 = add_vertex(g);
vertex2 = add_vertex(g);

// Add edges
typedef graph_traits<graph_t>::edge_descriptor EdgeDescrip;
EdgeDescrip edge1;
bool inserted = false;

tie(edge1, inserted) = add_edge( vertex1, vertex2, g);
assert ( inserted );

5.图的种类和若干算法

一般用adjacency_list表示，若是密度大的图dense graph (if |E| == square(|V|)),可以用adjacency_matrix表示。

• reverse_graph()用来翻转边的指向
• filtered_graph()可以指定条件来过滤某些边或者端点
• depth_first_search()
• breadth_first_search()
• for a vertex, in_edges(), out_edges(), and adjacent_vertices()
• for a edge, source(e, g) and target(e, g)

# posted by Li Min : 10:27 PM