1

在 BGL 的上下文中，我需要迭代in_edgesandout_edges但我想排除那些属于反向边缘的部分，即排除那些属于反向边缘的部分property_map。下面的代码显示了我想做的事情，但当然property_map没有find和end方法。

更新：一种可能的解决方案是在构建图形时维护一个单独的结构，例如包含反向边的地图。如果我可以控制图形构建，这将起作用，但我没有，因为我使用该函数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
4

1 回答 1

2

您的edge_reverse属性映射会将边缘描述符关联到图形的每个边缘。因此，“查找”函数没有任何意义，因为所有边都将在该属性映射中具有相应的条目（请记住，此类属性映射不一定作为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 样式的属性映射，您就不能再使用“查找”机制来确定是否为给定边设置了属性。

于 2012-07-20T17:57:39.100 回答