在 BGL 的上下文中,我需要迭代 in_edges
和 out_edges
但我想排除那些属于反向边缘的部分,即排除那些属于反向边缘的部分反向边缘 property_map
。下面的代码显示了我想做什么,但是 property_map
当然没有 find
和 end
方法。
更新:
一种可能的解决方案是在构建图形时维护一个单独的结构,例如包含反向边的 map 。如果我控制了图形构建,这将起作用,但我没有,因为我使用函数 read_dimacs_max_flow
读取 DIMACS 格式的图形文件。所以我只能依靠BGL的无障碍方法来弄清楚什么是什么。
图定义:
typedef adjacency_list_traits<vecS, vecS, bidirectionalS> ttraits;
typedef adjacency_list<vecS, vecS, bidirectionalS,
// vertex properties
property<vertex_index_t, int,
property<vertex_color_t, default_color_type> >,
// edge properties
property<edge_capacity_t, int,
property<edge_residual_capacity_t, int,
property<edge_reverse_t, ttraits::edge_descriptor> > >, no_property, vecS> tbgl_adjlist_bidir;
typedef graph_traits<tbgl_adjlist_bidir>::vertex_descriptor tvertex;
typedef graph_traits<tbgl_adjlist_bidir>::edge_descriptor tedge;
typedef property_map<tbgl_adjlist_bidir, edge_capacity_t>::type tedge_capacity_map;
typedef property_map<tbgl_adjlist_bidir, edge_reverse_t>::type treverse_edge_map;
typedef property_map<tbgl_adjlist_bidir, vertex_color_t>::type tvertex_color_map;
typedef property_map<tbgl_adjlist_bidir, vertex_index_t>::type tvertex_index_map;
typedef graph_traits<tbgl_adjlist_bidir>::vertex_iterator tvertex_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::edge_iterator tedge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::out_edge_iterator tout_edge_iterator;
typedef graph_traits<tbgl_adjlist_bidir>::in_edge_iterator tin_edge_iterator;
以及我想做的示例片段(但没有编译并出现以下错误):
tvertex_index_map indices = get(vertex_index, bgl_adjlist_bidir);
tedge_capacity_map capacities = get(edge_capacity, bgl_adjlist_bidir);
treverse_edge_map rev_edges = get(edge_reverse, bgl_adjlist_bidir);
// iterate all vertices in the right order
for (int current = 0; current < m_num_vertices; ++current) {
printf("processing vertex=%d\n", current);
tin_edge_iterator ei1, ei1_end;
for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
// exclude reverse edges <<<<<<<======= HOW DO I DO THIS??
if (rev_edges.find(*ei1) != rev_edges.end()) {
continue;
}
int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
printf("in edge: %d <- %d \n", current, in);
}
}
和编译器错误:
/Users/bravegag/code/fastcode_project/build_debug$ make 2> out ; grep -i "error" ./out
[ 2%] Building CXX object CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:18: error: 'treverse_edge_map' has no member named 'find'
/Users/bravegag/code/fastcode_project/code/src/api/hp_adjlist_bidir.h:146:42: error: 'treverse_edge_map' has no member named 'end'
make[2]: *** [CMakeFiles/submodularity.dir/src/graph/hp_adjlist_bidir.cc.o] Error 1
make[1]: *** [CMakeFiles/submodularity.dir/all] Error 2
make: *** [all] Error 2
最佳答案
你的 edge_reverse
property-map 会将边描述符关联到图的每条边。因此,“查找”函数没有任何意义,因为所有边在该属性映射中都有对应的条目(请记住,此类属性映射不一定实现为 std::map
对象,事实上,它们不是在内部属性的情况下)。
您可以而且应该做的一件事是为每条边设置反向边缘属性的值,使其要么是反向边缘的边缘描述符,要么是无效的边缘描述符(对于非反向边缘) .然后,检查(而不是“查找”)仅仅是检查反向边缘属性是否是有效的边缘描述符之一。
不幸的是,BGL 没有提供 null_edge()
静态函数(就像它对 null_vertex()
所做的那样)。这可能是开发人员的疏忽(我开发了一些自己的图形结构,并且包含了一个 null_edge()
函数,但在 Boost 中没有)。这意味着可能很难想出一个好的、可移植的“空边”描述符值来使用。一种选择是使用特定的位模式,如下所示:
ttraits::edge_descriptor my_null_edge;
memset((char*)&my_null_edge, 0xFF, sizeof(ttraits::edge_descriptor));
然后,确保非反转边的所有反转边属性都设置为 my_null_edge
然后用这个比较实现你的循环:
for (tie(ei1, ei1_end) = in_edges(tvertex(current), bgl_adjlist_bidir); ei1 != ei1_end; ++ei1) {
// exclude reverse edges
if (rev_edges[*ei1] != my_null_edge) {
continue;
}
int in = indices[boost::source(*ei1, bgl_adjlist_bidir)];
printf("in edge: %d <- %d \n", current, in);
}
如果您的反向边缘属性非常稀疏,您可能希望使用像 std::map
这样的映射类来拥有一个外部属性映射。 (或 std::unordered_map
)。您在邻接列表类模板中指定为 EdgeProperty 或 VertexProperty 的内容按图的每个顶点或边的值(种类)存储。如果你想要std::map
行为(仅存储具有指定属性的子集),然后您可以简单地在邻接列表图的外部执行此操作,属性映射的好处是它们不必对应于内部属性,这很有用也。所以,你可以这样做:
typedef std::map< tedge, tedge > treverse_edge_map;
treverse_edge_map rev_edges;
如果你需要使用rev_edges
作为 BGL 属性映射,那么您可以使用:
typedef boost::associative_property_map< treverse_edge_map > tbgl_reverse_edge_map;
tbgl_reverse_edge_map bgl_rev_edges = boost::make_assoc_property_map(rev_edges);
但是,当然,一旦它是 BGL 样式的属性映射,您就不能再使用“查找”机制来确定是否为给定边设置了属性。
关于c++ - Boost的property_map测试key是否存在?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11583711/