CODEWITHSUNDEEP
c++boostboost-graph
Saleem gagguturu
Saleem gagguturu

Reputation: 145

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

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.

Upvotes: 3

Views: 546

Answers (1)

sehe
sehe

Reputation: 393084

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.:

Upvotes: 2

Related Questions