Boost图库：通过int类型的索引获取edge_descriptor或访问边缘 [英] Boost graph library: Get edge_descriptor or access edge by index of type int

问题描述

我是一个带有（可能）简单问题的BGL新手：我有一个有向图并使用边的绑定属性，其中一个是int类型的索引。知道一个唯一的索引，我想获得该边的相应edge_descriptor以便对其执行操作。下面的例子总结了我的问题：

I'm a BGL newbie with a (possibly) easy question: I have a directed graph and use bundled properties for edges, one of them being an index of type int. Knowing a unique index, I would like to get the corresponding edge_descriptor of that edge in order to perform operations on it. The following example summarizes my problem:

#include <boost/graph/adjacency_list.hpp>

struct EdgeProperties {
    EdgeProperties(): distance(10), time_limit(5) {};
    int index;
    int distance;
    int time_limit;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, EdgeProperties> Graph;

int main() {

    Graph graph;

    EdgeProperties edge_prop1, edge_prop2, edge_prop3, edge_prop4;

    // Define edge properties
    edge_prop1.index = 0;
    edge_prop2.index = 1;
    edge_prop3.index = 2;
    edge_prop4.index = 3;

    // Add edges to graph
    boost::add_edge(0, 1, edge_prop1, graph);
    boost::add_edge(0, 2, edge_prop2, graph);
    boost::add_edge(1, 3, edge_prop3, graph);
    boost::add_edge(2, 3, edge_prop4, graph);

    // Get vertex_descriptor from an (int) index:
    int vertex_index = 2;
    boost::graph_traits<Graph>::vertex_descriptor v = boost::vertex(vertex_index, graph);

    // I would like to get an edge_descriptor from an (int) index property:
    // The following DOES NOT work:
    boost::graph_traits<Graph>::edge_descriptor e = boost::edge(edge_prop1.index, graph);
}

我也阅读了有关房产地图的信息，但找不到解决方案我的问题。我希望捆绑属性超过内部属性。
是否有一种方法通过bundle属性为遍历这些int类型值的边和边访问分配唯一的int类型索引？

I read about property maps as well, but could not find a solution my problem. I would prefer bundled properties over internal properties. Is there a way of assigning unique int type indices via a bundle property to edges and access edges through these int type values?

推荐答案

可悲的是，我不认为 boost :: graph 在这里有直接的帮助。

Sadly, I don't think boost::graph is of immediate help here.

第一，没有任何机制可以根据边缘属性的字段找到边缘（或顶点） - BGL保留任何这样的映射，而索引字段完全是为了您的目的。

First, there is no mechanism to find an edge (or vertex, for that matter), based on a field of an edge property - BGL keeps any such mapping, and the 'index' field you have is entirely for your purposes.

其次， boost :: edges 函数返回图的所有边的迭代器范围。我认为你可以将vecS作为边缘容器类型传递给adjacency_list模板，然后查看这个范围，但是根据 http://www.boost.org/doc/libs/1_61_0/libs/graph/doc/EdgeListGraph.html 迭代器只需要多次传递输入迭代器，并且实现确实如此 - 甚至以vecS作为边缘类型，您也无法进行随机访问。

Second, there is the boost::edges function that returns an iterator range for all edges of the graph. I though that you could pass vecS as edge container type to adjacency_list template, and then look inside this range, but per http://www.boost.org/doc/libs/1_61_0/libs/graph/doc/EdgeListGraph.html the iterators are only required to be multi-pass input iterators, and the implementation does exactly that -- even with vecS as edge type, you can't do random access.

因此，似乎只有这样完成你想要的是将自己的 unodered_map 从索引保留到边描述符。

Therefore, it seems that the only way to accomplish what you want is to keep your own unodered_map from index to edge descriptor.

这篇关于Boost图库：通过int类型的索引获取edge_descriptor或访问边缘的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！