[C++/C] Boost 定义顶点属性

 BGL实现尽可能灵活地适应图的附加属性，举个例子，属性如边的权重存在于在图对象的整个生命周期都，因此让图对象管理这个属性的存储将会带来很多便利；另外，属性如顶点颜色只在某个算法的运行期内需要，将此属性和图对象分开存储将会更好。第一种属性称为内在存储属性，而第二种称为外在存储属性。BGL 在图算法中为两种属性提供了一致的访问接口property map，此接口在章节Property Map Concepts中有详细描述。另外，PropertyGraph 配接器也为获得一个内在存储属性的property map 对象定义了接口
       BGL 邻接表类允许用户通过设置图对象模版参数来指定内在存储属性，如何实现这些在Internal Properties 章节有详细论述。外在存储属性有多种创建方法，尽管他们基本上作为分离参数传递给图算法。一个简单存储外在属性的办法是通过顶点或边的索引来创建一个索引数组。如邻接表中的VertexList模版参数指定为vecS，每个顶点的索引将会自动建立。通过指定vertex_index_t作为模版参数的property map对象来访问这些索引。每个边虽不能自动建立索引。但是可以通过使用属性机制把索引和边联系起来，来索引其他的外在存储属性。

  在下面的例子中，我们创建一个图并执行dijkstra_shortest_paths()算法，完整的源代码在例子examples/dijkstra-example.cpp中。Dijkstra 算法用来计算从起始顶点到其他顶点的最短路径。Dijkstra 算法要求设置每个边的权重和每个顶点的距离，这里我们把权重做为一个内在属性，距离作为外在属性。对于权重属性，我们创建属性类并指定int 作为权重类型，edge_weight_t 作为属性标记(一个BGL预定义的属性标记)。此权重属性类将作为邻接表adjacency_list 的一个模版参数

  选择listS或者vecS类型取决于我要在邻接表中使用的数据结构(可以看 Choosing the Edgelist and VertexList章节)。directedS 类型指定图为有向图（相对的是无向图）。后面的代码展示了一个图类型的声明和初始化，以及带权重属性的边如何传递给（使用迭代器作为参数的）图构造函数（要求随机迭代器）
     typedef adjacency_list<listS, vecS, directedS,
     no_property, property<edge_weight_t, int> > Graph;
     typedef graph_traits<Graph>::vertex_descriptor Vertex;
     typedef std::pair<int,int> E;
     const int num_nodes = 5;
     E edges[] = { E(0,2),
     E(1,1), E(1,3), E(1,4),
     E(2,1), E(2,3),
     E(3,4),
     E(4,0), E(4,1) };
     int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
     Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);

 对于外部距离属性，我们使用std::vector 来存储， BGL 算法视随机迭代器为property maps。所以我们能够传递距离数组vector迭代器到Dijkstra's 算法。紧接上面的例子，下面的代码创建了一个distance vector, 然后调用Dijkstra's 算法(内部使用了权重属性)，输出结果:
// vector for storing distance property
std::vector<int> d(num_vertices(G));
// get the first vertex
Vertex s = *(vertices(G).first);
// invoke variant 2 of Dijkstra's algorithm
dijkstra_shortest_paths(G, s, distance_map(&d[0]));
std::cout << "distances from start vertex:" << std::endl;
graph_traits<Graph>::vertex_iterator vi;
for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
std::cout << "distance(" << index(*vi) << ") = "
<< d[*vi] << std::endl;
std::cout << std::endl;
结果是:
distances from start vertex:
distance(0) = 0
distance(1) = 6
distance(2) = 1
distance(3) = 4
distance(4) = 5