c++ - 使用 Boost Graph Library 删除顶点后无法删除边

Question

我开始深入研究 BGL ，它看起来很棒，但我确实发现它很难使用。

当我使用 this graph 时，事情开始变得更加清晰。例子。但我现在面临一个问题:删除顶点后无法删除图形中的边。到目前为止，这似乎使我对 BGL 的理解无效 :(

这是我必须使问题清楚显示的最短代码。

(我用整数 [1..5] 和字母 [a..g] 确定了顶点)

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

using namespace boost;

//==============================================================
// TL;DR : Skip to the end of `main()` where the real problem is
//==============================================================

// lazy iterate over the graph: // {{{
#define VERTEXITERATE(nameV, graph, ...)                                       \
    {                                                                          \
    auto GRAPHITERATOR(vertices(graph));                                       \
    auto& nameV(GRAPHITERATOR.first);                                          \
    for(; GRAPHITERATOR.first != GRAPHITERATOR.second; ++GRAPHITERATOR.first) {\
        __VA_ARGS__                                                            \
    }                                                                          \
    }
#define EDGEITERATE(nameE, graph, ...)                                         \
    {                                                                          \
    auto GRAPHITERATOR(edges(graph));                                          \
    auto& nameE(GRAPHITERATOR.first);                                          \
    for(; GRAPHITERATOR.first != GRAPHITERATOR.second; ++GRAPHITERATOR.first) {\
        __VA_ARGS__                                                            \
    }                                                                          \
    }
    // }}}

// Properties of the graph // {{{
struct VertexProperties {
    VertexProperties() : id(0) {};
    VertexProperties(int id) : id(id) {};
    int id;
};
struct EdgeProperties {
    EdgeProperties() : id(0) {};
    EdgeProperties(char id) : id(id) {};
    char id;
};
struct GraphProperties {
    GraphProperties() : id(0) {};
    GraphProperties(std::string id) : id(id) {};
    std::string id;
};
// }}}

// Type definitions // {{{
typedef adjacency_list<
      hash_setS // vecS would allow parallel edges, which I don't want.
    , vecS
    , bidirectionalS
    , VertexProperties
    , EdgeProperties
    , GraphProperties
    > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;
// }}}

// Glance at the state of the graph
void printGraph(Graph const& g) { // {{{
    // Print graph properties
    std::cout << get_property(g).id << " : |V| = " << num_vertices(g);
    std::cout << ", |E| =  " << num_edges(g) << std::endl;
    std::cout << "vertices: " << std::endl;
    VERTEXITERATE(v, g,
            Vertex vertex(*v);
            std::cout << g[vertex].id << " :";
            std::cout << " in " << in_degree(vertex, g);
            std::cout << ", out " << out_degree(vertex, g);
            std::cout << std::endl;
        );
    std::cout << "edges: " << std::endl;
    EDGEITERATE(e, g,
            Edge edge(*e);
            std::cout << g[edge].id << " :";
            std::cout << g[source(edge, g)].id << " \u2192 ";
            std::cout << g[target(edge, g)].id;
            std::cout << std::endl;
            );
    std::cout << std::endl;
}
// }}}

int main() {

    // Build the graph
    Graph g(GraphProperties("Graph"));
    const int nV(5); // number of vertices
    const int nE(7); // number of edges
    std::cout << "Created." << std::endl;
    // should be empty:
    printGraph(g);

    // Vertices
    std::array<Vertex, nV> V;
    int vId(0);
    for (Vertex& v : V)
        v = add_vertex(VertexProperties(++vId), g);

    // Edges
    typedef struct {         // store here everything we need to define an edge:
        Vertex source, target;
        EdgeProperties props;
    } BuildEdge;
    std::array<BuildEdge, nE> builds { {
           {V[0], V[1], 'a'} // define the graph topology in this initializer
        ,  {V[0], V[2], 'b'}
        ,  {V[0], V[3], 'c'}
        ,  {V[2], V[3], 'd'}
        ,  {V[1], V[4], 'e'}
        ,  {V[2], V[4], 'f'}
        ,  {V[3], V[4], 'g'}
    }};
    for(auto p : builds)
        add_edge(p.source, p.target, p.props, g);

    // See what happened:
    std::cout << "Filled up." << std::endl;
    printGraph(g); // ok.

    //==============================================================
    // HERE is the interesting part :
    // remove an edge by its vertices:
    std::array<Vertex, 2> toRemove {{V[0], V[1]}};
    remove_edge(toRemove[0], toRemove[1], g);
    std::cout << "Edge removed." << std::endl;
    printGraph(g); // ok.

    // remove a vertex:
    toRemove[0] = V[3];
    clear_vertex(toRemove[0], g);
    remove_vertex(toRemove[0], g);
    std::cout << "Vertex removed" << std::endl;
    printGraph(g); // success.

    // remove another vertex:
    toRemove = {{ V[2], V[4] }};
    remove_edge(toRemove[0], toRemove[1], g);
    std::cout << "Edge removed." << std::endl;
    printGraph(g); // FAIL!

    // Why does this fail?
    // Is `V` outdated after a call to remove_edge?
    //==============================================================

    return EXIT_SUCCESS;

}

为什么最后一次删除没有发生？当然，删除中间 block (即保留第四个顶点)将允许正确删除边。

我知道在删除边的一个绑定(bind)顶点后删除边没有多大意义，但这里恰恰不是这种情况。

Answer 1

哇哦! `刚刚找到一个really interesting page关于这个话题。这是官方的 Boost 文档。

使用 VertexList = vecS 定义 adjacency_list 会导致调用 remove_vertex 使所有顶点描述符失效。选择另一种数据结构，例如 hash_setS 将使它们保持有效。

因此:重写 typedef:

typedef adjacency_list<
      hash_setS // vecS would allow parallel edges, which I don't want.
    , hash_setS // vecS would make the descriptor invalid on graph change
    , bidirectionalS
    , VertexProperties
    , EdgeProperties
    , GraphProperties
    > Graph;

解决问题。

它不仅会这样做，还会影响 adjacency_list 的其他属性例如底层算法的复杂性。这对我来说仍然很复杂，因为我是 BGL 的新手，但请参阅 docs . :)