adjacency_list with VertexList different from vecS

Question

I have two structs containing some fields: struct MyNodeData, and struct MyEdgeData. When I create a graph with VertexList as vecS, there is no problem to access the descriptor of vertices etc. For example:

typedef adjacency_list<setS, vecS, undirectedS, MyNodeData, MyEdgeData> Graph;

typedef Graph::vertex_descriptor MyNodeDataID;
typedef Graph::edge_descriptor MyEdgeDataID;
typedef graph_traits < Graph >::vertex_iterator VertexIterator;
typedef graph_traits < Graph >::edge_iterator EdgeIterator;
typedef graph_traits < Graph >::adjacency_iterator AdjacencyIterator;
typedef property_map < Graph, vertex_index_t >::type IndexMap;

Graph g;
const IndexMap index = get(vertex_index, g);

/* Puis après avoir ajouté des vertex et edges, je peux accéder par exemple à la liste des vertex comme suite: */
pair<VertexIterator, VertexIterator> vi;
for(vi = vertices(g); vi.first != vi.second; ++vi.first)
{
   cout << "vertex: " << index[*vi.first] << endl;
   // or: cout << "vertex: " << *vi.first << endl;
}

But I usually need to add/delete edges and vertices from my graph. So I want to use setS or listS as a VertexList, instead of vecS, since with vecS the indexes are invalidated when we delete one of them ! The problem is that if I define VertexList as setS or listS, I can not browse the list of vertices/edges and access there descriptors like I did before !

To make it short, my question is: Since an adjacency_list that uses listS or setS as the vertex container does not automatically provide this vertex_id property, how can I add it to the code above ?

Answer 1

Currently, you just need to provide an associative property map.

<...>
typedef Graph::vertex_descriptor NodeID;

typedef map<NodeID, size_t> IndexMap;
IndexMap mapIndex;
associative_property_map<IndexMap> propmapIndex(mapIndex);
<...>

// indexing all vertices
int i=0;
BGL_FORALL_VERTICES(v, g, Graph)
{
   put(propmapIndex, v, i++);
}

Answer 2

But I usually need to add/delete edges and vertices from my graph.

Removing vertices and edges is possible with vecS, setS and listS. Just call remove_vertex\remove_edge with the vertex\edge descriptor. In all above containers, removing \ adding a vertex \ edge will invalidate the iterator. This means that after you had modified the graph, you'll have to call vertices(g) again. In most containers, modifying the container invalidates iterators to it. In listS, adding a vertex may not invalidate the iterator, but this is implementation specific and should not be relied on.

You could add a vertex_id property to the graph, thus allowing you to get access to the vertex descriptors whenever.