Is it possible to delete a vertex in my Boost Graph in an adjacency list?

Question

I created a simple Boost labeled graph that uses an internal adjacency list. When I call remove_vertex(v1, graph.graph());, I can see that the number of vertices has reduced to 1, but when I check whether the vertex still exists, it still returns true.

I've tried graph.remove_vertex("1"); as well as remove_vertex(v1, graph.graph());, which both don't appear to be deleting the vertices.

#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;
}

I can see that assert(1 == boost::num_vertices(graph)); is working but when I check if the vertex exists using assert(graph.vertex("1") == graph.null_vertex());, it is returning false, i.e, the vertex 1 still exists.

score 2 · Answer 1 · answered Jun 11 '19 at 16:42

No, labeled_graph_adapter doesn't know how to update or remove the label, which means that any label will be invalidated when the corresponding descriptor is invalidated (e.g. when the corresponding graph element is removed OR in some graph models when any other vertex/edge is added).

Depending on the exact models you use, updating labels could be done by simply re-labelling the existing vertices, but removal is not a supported operations (just scan the code base for all the operations performed on _map).

Rant Notes:

labeled_graph adaptor is NOT part of the documented library interface
there have been many issues in the past, 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

Added some historical perspective to this part of the library — sehe, Jun 11 '19 at 16:47

Is it possible to delete a vertex in my Boost Graph in an adjacency list?

1 Answers1