constant vertex ids in adjacency_list

I would like to keep external properties for vertices and edges of an adjacency_list graph (and for groups of vertices). I need to be able to access vertices by their properties. For example, I would like to iterate over all vertices assigned some weight, and get their out edges.

However, I also need my vertex container to be setS. In this container, adding \ removing a vertex may invalidate the vertex descriptors.

The problem is that the external properties could now be mapped to invalid vertex_descriptors.

    class manage_data {
...
    auto get_interesting(int weight) {
        return ver_by_weight.equal_range(weight);
    }
    void do_stuff (...) {
        auto for_later_use = get_interesting();
        ...
        boost::remove_vertex(unrelated_vertex, graph_);
        ...
        use_vec(for_later_use.front()); //bug
    }
    }

One approach seems to be to add a vertex_index property. This doesn't work, as it is one directional- you could get the vertex_index via the vertex_descriptor, but not the other way round. This means I can't add an edge between two vertices that I only know the index of.

Another promising solution was using a labeled graph. This graph can add edges only by labels. I could have gotten pretty far by storing external data with a label id. Unfortunately, not all of the adjacency_list interface is reimplemented using labels - e.g. out_edges. This means I still need to be able to access the vertex descriptor, and it is impossible (in reasonable time) using only the label, as can be seen here

An even better solution will be to combine the above two - have a vertex_label property. This seems overly complex, and it doesn't work (above example).

Shouldn't it be common for vertices to relate to external data? How can you do it?

Solution

You can use a bidirectional mapping from vertex-descriptor to your own ID.

Now, as long as you use any node-based container selector for the vertex container, you're all set.

Have a look at BiMap and possibly transform_value_property_map for maximum convenience (although you might not require all the fancies especially if the graph is mostly read-only - or shrink-only e.g.)