Boost labeled graph doesn't delete vertices

I am using boost::labeled_graph in order to get vertices by their name. But labeled_graph doesn't have a remove_vertex_by_label function, so I remove vertices like in a code below. But vertex_by_label return nonexistent vertex after deletion.

#include <string.h>
#include <iostream>

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

using namespace std;
using namespace boost;
typedef adjacency_list<
    listS,
    vecS,
    undirectedS
> Graph;
typedef labeled_graph<
    Graph,
    string
> LabeledGraph;

int main(int argc, char* argv[]) {

    LabeledGraph lg;
    vector<string> names{"a", "b", "c", "d", "e"};
    for(auto& name : names)
        add_vertex(name, lg);

    remove_vertex(vertex_by_label("c", lg), lg.graph());

    cout << "num_vertices = " << num_vertices(lg) << endl;
    for(auto& name : names)
        cout << name + " = "
             << vertex_by_label(name, lg) << endl;
    for(auto v : make_iterator_range(vertices(lg.graph())))
        cout << v << endl;
}

And the output is:

num_vertices = 4
a = 0
b = 1
c = 2
d = 3
e = 4
0
1
2
3

The questions are:

1) Why does vertex_by_label return nonexistent vertex, while there are 4 vertices (vertex was successfully deleted)?

UPD: It happened that labeled_graph has a bug - https://svn.boost.org/trac10/ticket/9493

Unfortunately, the current implementation has a serious bug that might lead to a crash. The problem appears when removing a vertex from labeled_graph by its label. My investigation shown that despite of vertex being actually removed, the label is not and it still refers to the removed vertex.

2) Is there any way to delete a vertex from a labeled_graph?

3) If no, then what is the most convenient method to keep track of vertices by their names? Saving maps from strings to vertex descriptors is not an option, since the documentation says that old vertex descriptors become invalid after vertex deletion (this is happening when vecS is a vertex list container).

Solution

The problem is clear from what you write:

remove_vertex(vertex_by_label("c", lg), lg.graph());

You wrote lg.graph(), not lg. So you shouldn't expect anything to get removed from lg. You expressly asked to remove something from the underlying graph model only.

Here's the correct version:

lg.remove_vertex("c");

For maximum convenience, you can use the overloaded free function:

remove_vertex("c", lg);

NOTE On Iterator Stability

I haven't looked at the implementation, but it looks like the labeled_graph<> adaptor relies on iterator stability for the underlying graph.

Using adjacency_list<> with vecS for the vertex container selector documents all subsequent iterators and references to be invalidated on removal of a vertex.

Here's a fixed demo using listS as the vertex container selector, and it does exactly what you expect.

Note: I used a vertex property bundle as the "friendly" vertex id so you don't have to print out raw vertex-descriptors.

Live On Coliru

#include <iostream>
#include <string.h>

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

using namespace boost;

typedef adjacency_list<listS, listS, undirectedS, int> Graph;
typedef labeled_graph<Graph, std::string> LabeledGraph;

int main() {

    LabeledGraph lg;
    auto vid = get(vertex_bundle, lg.graph());

    int id = 0;
    for (std::string name : { "a", "b", "c", "d", "e" })
        add_vertex(name, id++, lg);

    std::cout << "===================\nnum_vertices = " << num_vertices(lg) << "\n";
    for (std::string name : { "a", "b", "c", "d", "e" })
        std::cout << name + " = " << vid[vertex_by_label(name, lg)] << "\n";
    for (auto v : make_iterator_range(vertices(lg)))
        std::cout << vid[v] << " ";
    std::cout << "\n";

    // lg.remove_vertex("c");
    remove_vertex("c", lg);

    std::cout << "===================\nnum_vertices = " << num_vertices(lg) << "\n";
    for (std::string name : { "a", "b", /* "c",*/ "d", "e" })
        std::cout << name + " = " << vid[vertex_by_label(name, lg)] << "\n";
    for (auto v : make_iterator_range(vertices(lg)))
        std::cout << vid[v] << " ";
    std::cout << "\n";
}

Prints

===================
num_vertices = 5
a = 0
b = 1
c = 2
d = 3
e = 4
0 1 2 3 4 
===================
num_vertices = 4
a = 0
b = 1
d = 3
e = 4
0 1 3 4