转使用BoostGraphlibrary（一）emyyu

本文翻译自"ManipulatingC++GraphDataStructureswiththeBoostGraphLibrary"，原文请见：

使用Boost创建一个简单的图

一般地，在计算机中图可以表示为一组顶点和一组连接顶点的边的集合；边简单地表示为顶点对。进一步每一个顶点和每一条边可能还依附着额外的数据，比如对边来说会有一个数来表示权重。这就是Boost库如何工作的本质。

BoostGraphlibrary是以模板的形式提供的，这意味着你可以在这些模板的基础上创建自己的类型。然而，这些模板的所有类型参数都有默认值，所以你无需任何定制，就可以创建一个图。

下面的一小段代码展示了创建一个图和插入顶点和边的过程，这段代码可以被完全编译，但它除了创建一个图外，并没有做其他什么事情。

#include

#include

#include

usingnamespaceboost;

intmain(intargc,char*argv[])

{

adjacency_list<>mygraph;

add_edge(1,2,mygraph);

add_edge(1,3,mygraph);

add_edge(1,4,mygraph);

add_edge(2,4,mygraph);

return0;

}

mygraph变量就是一个图，其类型是adjacency_list，它是图库中基本的图模板类型。在这里我们使用了默认参数，在<>中的参数列表是空的。

函数add_edge是一个模板协助函数，它用来给图增加顶点或边的。为了使用它，你需要传递两个顶点参数，如果在该图中这些顶点不存在，则它们会被加入；然后连接这两个顶点的边也会被加入。这样，上面的这段代码就创建了一个图，它具有四个顶点，编号是1,2,3,4，边有(1,2)、(1,3)、(1,4)、(2,4)。

这只是一个很基本的例子。为了创建更加复杂的图，你需要定义更多的数据关联到你的边和顶点，我们将在下一节讨论。

给顶点和边增加属性值

当你使用图，通常你会附加一些信息给顶点和边，图库使用了一个很有趣的方法来做到这一点。诸如名字或颜色信息作为一种属性来存储，一个属性由一个名字（或标识），如距离，和类型，如浮点数或字符串，组成。你可以给顶点和边增加属性。

提示

在图库中，有几个常用的，已经内建好了的属性标识，如颜色，名字和权重。所有的内建标识都列在在线帮助中，同样你可以在graph/properties.hpp这个头文件中找到它们。它们是用宏的方式来定义的，形成了枚举常量。比如，在properties.hpp中有一行属性定义：

BOOST_DEF_PROPERTY(edge,name);

这个宏的结果是产生了一个枚举常量edge_name，它的类型是edge_name_t。你还能看到其他的内建属性标识定义。

typedefpropertyEdgeWeightProperty;

typedefpropertyVertexNameProperty;

第一行定义了EdgeWeightProperty类型，模板的第一个参数是这个属性的标识，在这里我们使用的是预先定义好的标识edge_weight_t，它的意思是边的权重，第二个参数是int，意思是这个属性具有一个整型数值。第二行定义了第二个属性，它的标识是vertex_name_t，类型是string。

现在你已经定义好属性，你可以定义一个图类型了：

typedefadjacency_list

VertexNameProperty,EdgeWeightProperty>Graph;

这个定义中的前三个模板参数是预先定义好的，第一和第二个参数（都是vecS）表示我们要求图使用vector来作为图的内部存储方式，第三个参数说明这是一个无向图，第四、五个参数是我们刚刚定义的属性类型，前者是顶点的属性类型，后者是边的属性类型。

这个时候，你可能会有疑问：如何给顶点和边指定不止一个属性类型呢？事实上，可以把属性串联在一起。基本类型模板包含了一个模板参数，它可以是你已经定义的属性类型。下面是顶点类型定义，不过，这时我们定义了为顶点定义了两个属性，一个是name，一个是index（下面的代码使用了预定义的标识vertex_index2_t）：

typedefproperty

VertexIndexProperty;

typedefproperty

VertexIndexProperty>VertexNameProperty;

注意：

这里使用的是vertex_index2_t，而不是vertex_index_t，这是因为后者有一些与它有关的内建模板已经做了我们正在做的。

我们首先定义了index属性，不过这个顺序无关紧要。属性VertexNameProperty就包含了VertexIndexProperty作为它的第三个参数，这样就创建了一个链。然后你也可以象前面一样将VertexNameProperty作为第四个参数传递给图定义。

你也可以精简你的代码，不过精简过的代码对于图库初学者来说可读性要差一些，虽然一旦你理解了属性的这种机制后，这种精简的过程也是十分的直接。

property>VertexProperties;

我们重命名了类型VertexProperties，这是由于它现在包含了两种不同的属性。有个地方请大家注意，C++标准要求在两个>之间要有空格，这是为了同>>运算符区分开来。别忘了这个空格，否则你将得到编译错误。

操纵属性

property_map::type

city_name=get(vertex_name,g);

property_map::type

city_index2=get(vertex_index2,g);

property_map::type

edge_distance=get(edge_weight,g);

别担心这里的函数名字是一个很通用的单词get，这个函数是得到很好定义的模板函数，它会编译的很好。

请记住，这里的三个调用你可以用来获得顶点的属性和边的属性，虽然我们这里给出的代码片段是针对顶点来做的。下面的一行代码将来要用于获得属性：

std::cout<

这里的vp.first是一个指向vertex的指针。对象city_name象map一样地工作，它将一个顶点对象作为参数，然后返回该顶点合适的属性，在这个例子中，返回的是城市名。

加入顶点和边

在你指定了属性类型和定义了图类型之后，你已经可以去创建一个图实例，然后向图结构中加入顶点和边，这些顶点和边是具有你所定义的属性的。