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? Thanks, Cory