c++ - 是否可以在邻接列表中删除我的 Boost Graph 中的顶点？

Question

我创建了一个使用内部邻接表的简单 Boost 标记图。当我调用 remove_vertex(v1, graph.graph()); 时，我可以看到顶点的数量已经减少到 1，但是当我检查顶点是否仍然存在时存在，它仍然返回 true。

我已经尝试过 graph.remove_vertex("1"); 以及 remove_vertex(v1, graph.graph());，两者都不行似乎正在删除顶点。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/labeled_graph.hpp>
#include <cmath> // infinity

using namespace std;

struct EdgeProperties {
    double weight = INFINITY;
    EdgeProperties() = default;
    EdgeProperties(const double d) : weight(d) {}
};

struct Node
{
    string id;
    Node() = default;
    Node(const string i) : id(i) {} 
};

typedef boost::labeled_graph<boost::adjacency_list<boost::hash_setS, boost::hash_setS, boost::directedS, Node, EdgeProperties>, std::string> BoostGraph;
typedef BoostGraph::vertex_descriptor Vertex;
typedef BoostGraph::edge_descriptor Edge;

int main(){

    BoostGraph graph;

    const Vertex& v1 = add_vertex("1", Node("1"), graph);
    const Vertex& v2 = add_vertex("2", Node("2"), graph);

    const pair<Edge, bool>& edge = add_edge(v1, v2, EdgeProperties(INFINITY), graph);

    assert(2 == boost::num_vertices(graph));
    assert(1 == boost::num_edges(graph));
    assert(boost::edge(v1, v2, graph).second); // edge from v1->v2 exists

    // delete v1
    clear_vertex(v1, graph);
    graph.remove_vertex("1");

    assert(graph.vertex("1") == graph.null_vertex());

    assert(1 == boost::num_vertices(graph));
    assert(0 == boost::num_edges(graph));
    assert(not boost::edge(v1, v2, graph).second); // edge from v1->v2 shouldn't exist anymore

    cout << "All tests passed" << endl;
    return 0;
}

我可以看到 assert(1 == boost::num_vertices(graph)); 正在工作，但是当我使用 assert(graph.vertex("1 ") == graph.null_vertex());，它返回 false，即顶点 1 仍然存在。

Answer 1

不，labeled_graph_adapter 不知道如何更新或删除标签，这意味着当相应的描述符无效时(例如，当相应的图形元素被删除或在添加任何其他顶点/边时的一些图形模型)。

根据您使用的确切模型，更新标签可以通过简单地重新标记现有顶点来完成，但删除不是受支持的操作(只需扫描代码库以了解在 _map 上执行的所有操作)。

咆哮笔记:

• labeled_graph 适配器不是文档库接口(interface)的一部分
• 过去有很多问题，eg. :

  • Cheers. Rest assured, I have learned about labeled_graph the hard way. Frankly I was a bit shocked at the state of maintenance it is in. It's probably easier to write some more verbose code than grappling with the leaky abstraction. Of course, you are free to judge it for yourself. If you keep using it, perhaps you can improve it!

  • copy_graph - adjacency_list with bundled properties
  • https://github.com/boostorg/graph/pull/58