Boost logo

Boost Users :

Subject: [Boost-users] BGL: is it safe to store vertex_descriptors?
From: Cory Riddell (cory_at_[hidden])
Date: 2009-03-04 10:49:30

Is it safe to store vertex descriptors? Does adding a new vertex / edge
ever renumber existing vertices? (I know removing does this)

Say I have a class to represent a state from the USA.
  class State { ... };

and I have a bunch of instances:
  State california, oregon, nevada, hawaii, ...;

I want a graph with a vertex for each state and an edge for each border:
  typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
  Graph graph;

I build my graph like this:
  Graph::vertex_descriptor v_california = add_vertex(graph);
  Graph::vertex_descriptor v_oregon = add_vertex(graph);
  Graph::vertex_descriptor v_nevada = add_vertex(graph);
  Graph::vertex_descriptor v_hawaii = add_vertex(graph);
  add_edge(v_california, v_oregon, graph);
  add_edge(v_california, v_nevada, graph);
  add_edge(v_nevada, v_oregon, graph);

To associate each State instance with a vertex, I make a map:
  map<State, Graph::vertex_descriptor> state_to_vtx_map;
  state_to_vtx_map[california] = v_california;
  state_to_vtx_map[oregon ] = v_oregon ;
  state_to_vtx_map[nevada ] = v_nevada ;
  state_to_vtx_map[hawaii ] = v_hawaii ;

Now I can find all the states Nevada has a border with by doing this:
  Graph::vertex_descriptor v = state_to_vtx_map[nevada];
  tie(begin, end) = out_edges(v, g);
(please assume that I didn't store v_nevada from above)

Is my state_to_vtx_map safe? Since a delete can totally renumber
everything, I don't think it is safe. What's the correct way of
associating a vertex with a State instance?


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at