[boost] [graph] Dangerous undocumented EdgeList parameter for adjacency_list.

From: Jurko Gospodnetiæ (jurko.gospodnetic_at_[hidden])
Date: 2008-04-12 22:44:18

   Hi.

   We have just finished a painful three day track-down for a mysterious 
access violation/crash/undefined behavior bug and the cause has been 
tracked down to some graph library edge descriptors getting invalidated 
in a case that is completely undocumented (that in turn causing memory 
trashing and all the lovely things that follow...)

   When you have an adjacency_list graph with its EdgeList (not 
OutEdgeList) parameter set to vecS, then any add_edge() operation may 
invalidate all existing edge descriptors. This is not documented 
anywhere - not under the add_edge() operation and not under the 
'Iterator and Descriptor Stability/Invalidation' section in 
adjacency_list.html which in fact explicitly states that add_edge() 
operation does not invalidate edge descriptors.

   Please, please, please document this whole EdgeList concept and how 
it interacts with the rest of the graph library.

  Also, this behavior is not consistent with add_vertex() which does not 
invalidate any existing vertex descriptors. Edge descriptors seem to 
contain a pointer directly into their graph's edge storage, and that 
causes them to be invalidated whenever that storage gets reallocated. 
Any reason why they should not be holding an index to that storage in 
case EdgeList=vecS similar to how vertex descriptors identify their 
vertex? That way this whole problem with add_edge() invalidating all 
existing edge descriptors would be avoided.

   Thanks in advance.

   Best regards,
     Jurko Gospodnetiæ