You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
The unit test test_basic_csr_directed_graph has been there, but disabled ever since it was added in 2012 because it didn't work.
The corresponding version with external properties worked.
I analyzed it and it turns out that the property maps from indexed_properties that underlie the bundled property maps returns an iterator_property_map into the actual model storage collections. However, since CSR stores nodes and edges in vectors, they can become invalidated.
Due to the two-phase nature in which the parser builds the output CSR graph this happens by definition in read_graphviz.
This is what is allows us to restore the unit test with the workaround. This issue is created in order to investigate
whether a safer property-map derivation should be made the default (removing a tricky UB trap)
whether other graph models can be reviewed for similar property-map invalidation
whether the documentation of such graph models should state property-map validity guarantees in some way; this may seem like a lot of work, e.g. arguably adjacency_list might be worst due to its high container configurability. However, adjacency_list already has extensive (terse) documentation on iterator/descriptor invalidation. Arguably, that entire group of model instances might defer to those guarantees for applicable property maps.
The text was updated successfully, but these errors were encountered:
sehe
added a commit
to sehe/graph
that referenced
this issue
May 3, 2024
Works around invalidation of bundle property maps (see boostorg#373).
The `#if SEHE_UNSTABLE_PROPERTY_MAPS_FIXED` section is there to signal
my intent to investigate a generalized fix under that issue. It doubles
as literate documentation of the need for the workaround, so it's less
likely to bite the unwary.
The unit test
test_basic_csr_directed_graph
has been there, but disabled ever since it was added in 2012 because it didn't work.The corresponding version with external properties worked.
I analyzed it and it turns out that the property maps from
indexed_properties
that underlie the bundled property maps returns aniterator_property_map
into the actual model storage collections. However, since CSR stores nodes and edges in vectors, they can become invalidated.Due to the two-phase nature in which the parser builds the output CSR graph this happens by definition in
read_graphviz
.There is a workaround to replace the idiomatic:
With a custom property-map that does offer stability by indirecting via the graph model each time:
This is what is allows us to restore the unit test with the workaround. This issue is created in order to investigate
adjacency_list
might be worst due to its high container configurability. However,adjacency_list
already has extensive (terse) documentation on iterator/descriptor invalidation. Arguably, that entire group of model instances might defer to those guarantees for applicable property maps.The text was updated successfully, but these errors were encountered: