c++ - 使用索引提升图边

Question

我正在尝试从一组 pair(int,int) 边（其中每个 int 代表一个顶点索引）中定义一个具有无向边的图。每个这样的边缘都有自己的索引。

问题是我希望图的内部顶点索引与原始顶点索引一致。我还希望能够从边缘描述符中提取原始边缘索引。

从http://www.boost.org/doc/libs/1_47_0/libs/graph/doc/using_property_maps.html（外部属性部分）我知道我应该使用以下图形类型：

typedef adjacency_list<vecS, vecS, udirectedS, 
no_property, property<edge_index_t, std::size_t> > Graph;

不幸的是，没有关于如何使用 edge_index_t 属性的解释。

很明显，我可以只使用 map(pair(int,int),int) 但我正在寻找一个更优雅的面向提升的解决方案。

谢谢你，基里尔

Answer 1

由于您使用向量来定义顶点集合，因此顶点索引和顶点描述符之间存在一对一的对应关系。您只需要按如下方式定义图形对象：

Graph g(N);

其中 N 是顶点数。这分配了 N 个顶点，每个顶点描述符是一个从 0 到 N-1 的数字。

要从边缘描述符中获取边缘索引，您可以使用 get 函数： get(edge_index, g, edge_descriptor);。您可以从函数返回的迭代器中获取的边缘描述符adjacent_vertices(v, g)。

希望是你的意思。