Boost标记图不会删除顶点-Java 学习之路

我使用boost :: labeled_graph来获取名称的顶点 . 但labeled_graph没有remove_vertex_by_label函数，所以我删除顶点，如下面的代码 . 但是vertex_by_label在删除后返回不存在的顶点 .

#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返回不存在的顶点，而有4个顶点（顶点被成功删除）？

UPD：碰巧label_graph有一个错误 - https://svn.boost.org/trac10/ticket/9493

不幸的是，当前的实现有一个严重的错误，可能导致崩溃 . 从labeled_graph中删除顶点时，会出现问题 . 我的研究表明，尽管顶点实际被移除，但标签不是，它仍然引用被移除的顶点 .

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

3）如果不是，那么用它们的名字跟踪顶点的最方便的方法是什么？将字符串从字符串保存到顶点描述符不是一种选择，因为文档说旧的顶点描述符在顶点删除后变为无效（这在vecS是顶点列表容器时发生） .

1 回答

你写的东西很清楚这个问题：

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

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

这是正确的版本：

lg.remove_vertex("c");

为了方便起见，您可以使用重载的自由功能：

remove_vertex("c", lg);

关于迭代器稳定性的说明

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

将 adjacency_list<> 与 vecS 用于顶点容器选择器会记录所有后续迭代器和引用，以便在删除顶点时失效 .

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

注意：我使用顶点属性包作为“友好”顶点id，因此您不必打印出原始顶点描述符 .

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

回复于 2024-04-28T19:42:16+08:00

Boost标记图不会删除顶点

1 回答

关于迭代器稳定性的说明

相关问题