c++ - BGL : vertices in listS and index_map

Question

我是 BGL 的新手，几天来我一直在用头撞墙试图实现一个带有顶点移除的图形，直到我发现一个特别有用的 SO 问题(this 一个)保存我的一天。

现在我的代码结构是这样的(下面是简化的代码):

struct NodeProperties
{
    int32_t data;
};

typedef property<edge_weight_t, uint32_t> EdgeProperties;

typedef adjacency_list<listS, listS, bidirectionalS,
                       property<vertex_index_t, int, NodeProperties>,
                       EdgeProperties> Graph;

/* In the graph initialization function */
Graph graph;
/* many add_vertex() and add_edge() here */

/* Assign indices */
int i = 0;
BGL_FORALL_VERTICES(v, graph, Graph) {
    get(vertex_index, graph)[v] = i++;
}

/* Make many manipulations, in particular, edge/vertex removal according 
   to certain criteria, NO add_vertex (though some edge are created) */

/* In another function */
vector<int32_t> component(num_vertices(graph));
int num = connected_components(graph, make_iterator_property_map(component.begin(), get(vertex_index, graph), component[0]));

就我目前所了解的而言，对顶点使用 listS 可防止 boost 使用每个节点的位置作为索引，因此我必须使用一种“添加的属性”自行提供此索引。

我对此很好，但上面的代码不 工作——在 connected_components 行出现段错误——除非我重做索引分配。这样做会使一切都完美运行，但在我创建的心理画面中毫无意义。

有人能

• 给我一个很好的引用，以通俗易懂的方式解释所有这些 index_map“诡计”？好的，有大量的官方文档，但它们对我来说看起来方式太复杂了(我是一名 C 程序员)。我打算学习高级 C++，但我目前必须为我的工作实现这个图算法，我不能在开始真正的代码之前花 3 个月的时间学习 C++...(已经让上面的代码工作花了我大约 10 个小时，在那段时间里，我会很容易地用 C 语言重新实现上述所有内容...)
• 向我解释为什么我必须这样做(或者我在这里做错了什么)？

提前致谢，祝您有愉快的一天!

R

Answer 1

connected_components 函数构造一个默认的 color_map，其大小为 num_vertices(g)，在您的图形中它小于您指定的最大顶点索引。当算法尝试为索引大于 num_vertices(g) 的顶点之一写入颜色时，将访问无效内存。

当您重新分配所有索引时，它们都在 num_vertices(g) 范围内。

要快速引用属性，您应该阅读 http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/quick_tour.html 中的“为图形添加一些颜色” .