提升标记图不会删除顶点

Question

我正在使用 boost::labeled_graph 以通过名称获取顶点。但是 labeled_graph 没有 remove_vertex_by_label 函数，所以我像下面的代码一样删除了顶点。但是 vertex_by_label return 删除后不存在的顶点。

#include <string.h>
#include <iostream>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>

using namespace std;
using namespace boost;
typedef adjacency_list<
    listS,
    vecS,
    undirectedS
> Graph;
typedef labeled_graph<
    Graph,
    string
> LabeledGraph;

int main(int argc, char* argv[]) {

    LabeledGraph lg;
    vector<string> names{"a", "b", "c", "d", "e"};
    for(auto& name : names)
        add_vertex(name, lg);

    remove_vertex(vertex_by_label("c", lg), lg.graph());

    cout << "num_vertices = " << num_vertices(lg) << endl;
    for(auto& name : names)
        cout << name + " = "
             << vertex_by_label(name, lg) << endl;
    for(auto v : make_iterator_range(vertices(lg.graph())))
        cout << v << endl;
}

输出为：

num_vertices = 4
a = 0
b = 1
c = 2
d = 3
e = 4
0
1
2
3

问题是：

1) 为什么vertex_by_label return 不存在的顶点，而有4 个顶点（顶点已成功删除）？

更新：碰巧 labeled_graph 有一个错误 - https://svn.boost.org/trac10/ticket/9493

Unfortunately, the current implementation has a serious bug that might lead to a crash. The problem appears when removing a vertex from labeled_graph by its label. My investigation shown that despite of vertex being actually removed, the label is not and it still refers to the removed vertex.

2) 有没有办法从 labeled_graph 中删除一个顶点？

3) 如果不是，那么通过名称跟踪顶点最方便的方法是什么？将映射从字符串保存到顶点描述符不是一个选项，因为文档说旧的顶点描述符在顶点删除后变得无效（当 vecS 是顶点列表容器时会发生这种情况）。

Answer 1

看你写的问题很清楚：

remove_vertex(vertex_by_label("c", lg), lg.graph());

您写的是 lg.graph()，而不是 lg。因此，您不应期望从 lg 中删除任何内容。您明确要求从基础图形模型中删除某些内容仅.

这是正确的版本：

lg.remove_vertex("c");

为了最大程度的方便，您可以使用重载的自由函数：

remove_vertex("c", lg);

关于迭代器稳定性的注意事项

我没有看过实现，但看起来 labeled_graph<> 适配器依赖于底层图形的迭代器稳定性。

对顶点容器选择器使用 adjacency_list<> 和 vecS 记录所有后续迭代器和引用在移除顶点时失效。

这是一个使用 listS 作为顶点容器选择器的固定演示，它完全符合您的期望。

Note: I used a vertex property bundle as the "friendly" vertex id so you don't have to print out raw vertex-descriptors.

Live On Coliru

#include <iostream>
#include <string.h>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>

using namespace boost;

typedef adjacency_list<listS, listS, undirectedS, int> Graph;
typedef labeled_graph<Graph, std::string> LabeledGraph;

int main() {

    LabeledGraph lg;
    auto vid = get(vertex_bundle, lg.graph());

    int id = 0;
    for (std::string name : { "a", "b", "c", "d", "e" })
        add_vertex(name, id++, lg);

    std::cout << "===================\nnum_vertices = " << num_vertices(lg) << "\n";
    for (std::string name : { "a", "b", "c", "d", "e" })
        std::cout << name + " = " << vid[vertex_by_label(name, lg)] << "\n";
    for (auto v : make_iterator_range(vertices(lg)))
        std::cout << vid[v] << " ";
    std::cout << "\n";

    // lg.remove_vertex("c");
    remove_vertex("c", lg);

    std::cout << "===================\nnum_vertices = " << num_vertices(lg) << "\n";
    for (std::string name : { "a", "b", /* "c",*/ "d", "e" })
        std::cout << name + " = " << vid[vertex_by_label(name, lg)] << "\n";
    for (auto v : make_iterator_range(vertices(lg)))
        std::cout << vid[v] << " ";
    std::cout << "\n";
}

版画

===================
num_vertices = 5
a = 0
b = 1
c = 2
d = 3
e = 4
0 1 2 3 4 
===================
num_vertices = 4
a = 0
b = 1
d = 3
e = 4
0 1 3 4

提升标记图不会删除顶点

Boost labeled graph doesn't delete vertices

boost

boost-graph

关于迭代器稳定性的注意事项