From: Jurko Gospodnetiæ (jurko.gospodnetic_at_[hidden])
Date: 2008-04-12 22:44:18
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk