Re: [boost] graph library questions

From: jsiek_at_[hidden]
Date: 2000-10-01 10:53:11

Hi Krishna,

Actually, I was wrong. add_vertex() does not invalidate vertex
descriptors (or vertex iterators), however remove_vertex() does.

When VertexList=vecS, vertex descriptors are an integer index into the
vector of vertices. add_vertex() resizes the vector, but the indices
are still valid. remove_vertex() also resizes the vector, but it
shifts the positions of vertices in the array (filling in the gap),
which invalidates the indices. The vertex iterator is also based on
integer indices (instead of the underlying iterator) so the
invalidation behaviour is the same as for vertex descriptors.

Krishna Padmasola writes:
 > Jeremy,
 > 
 > Thanks for the response, it clarified a lot of things for me. Please see
 > below:
 > 
 > jeremy siek wrote:
 > > 
 > > When VertexList=vecS, add_vertex() will invalidate earlier vertex
 > > descriptors. When VertexList=listS, vertex descriptors are never
 > > invalidated.
 > >
 > 
 > Is this due to the fact that the underlying vector<> may resize itself
 > automatically when more storage is needed by the program?
 > 
 > If the above is true, the Kevin Bacon example may not work correctly 
 > since it uses VertexList=vecS and keeps references to the vertices
 > inserted using add_vertex in a map for later use.
 > 
 > http://www.boost.org/libs/graph/docs/kevin_bacon.html
 > 
 > Please correct me if I am wrong.
 > 
 > regards,
 > Krishna.
 > 
 > 
 > 
 >