Can't remove an edge after having removed a vertex with Boost Graph Library

Question

I am starting to delve into BGL, which looks wonderful but which I do find pretty hard to use.

Things are starting to get more clear to me as I play around with this graph example. But I am now facing a problem: an edge from my graph cannot be removed after a vertex has been removed. And this seems to invalidate my understanding of BGL so far :(

Here is the shortest code I have to make the problem clearly appear.

(I identified vertices with integers [1..5] and edges with letters [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;

}

Why does the last removal not happen? Of course, deleting the intermediate block (i.e. keeping the fourth vertex) will allow the edge to be correctly removed.

I am aware that removing an edge after one of its bound vertices has been removed does not make much sense, but this is precisely not the case here.

Answer 1

Wop! `just found a really interesting page on this topic. This is the official Boost documentation.

Defining an adjacency_list with VertexList = vecS causes all vertex descriptors to be invalidated by a call to remove_vertex. Choosing another data structure such as hash_setS will keep them valid.

Therefore: rewriting the 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;

solves the problem.

Not only does it do so, but it also affect other properties of the adjacency_list such as the underlying algorithms complexity. This still looks quite intricate to me as I am new to BGL, but see the docs. :)