CSR: Indexed properties maps are unstable
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Bug
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- data, documentation, testing
Research direction
Start with the disabled test_basic_csr_directed_graph and trace read_graphviz, indexed_properties, and the bundled property maps it uses. Compare the unstable iterator_property_map behavior with the shown indirect property-map workaround. Done means determining whether safer defaults are appropriate, checking other graph models for similar invalidation, and documenting the relevant validity guarantees.
Written by the indexing model from the issue text.
Description
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.
There is a workaround to replace the idiomatic:
TEST_GRAPH(graph_t, sample, g, "node_id", "", //
get(&Models::VertexBundle::name, g), // FIXME
get(&Models::VertexBundle::mass, g), // FIXME
get(&Models::EdgeBundle::weight, g) // FIXME
);
With a custom property-map that does offer stability by indirecting via the graph model each time:
TEST_GRAPH(graph_t, sample, g, "node_id", "", //
boost::make_function_property_map< V >(
[&g](V v) -> std::string& { return g[v].name; }),
boost::make_function_property_map< V >(
[&g](V v) -> Mass& { return g[v].mass; }),
boost::make_function_property_map< E >(
[&g](E e) -> Weight& { return g[e].weight; })
);
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_listmight be worst due to its high container configurability. However,adjacency_listalready has extensive (terse) documentation on iterator/descriptor invalidation. Arguably, that entire group of model instances might defer to those guarantees for applicable property maps.
- Dominant language
- C++
- Stars
- 395
- Forks
- 239
- Avg merge
- 18h 50m
- Merged PRs (30d)
- 20
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from boostorg/graph
-
beginner friendly
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
algorithm beginner friendly priority: high
Difficulty 2/5 1-3 hours Newbie friendliness 68/100
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
priority: high warning
-
algorithm
boostorg/graph#493 · 22 comments · 1 reaction · 2 assignees ·
Similar issues
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
AXERA-TECH/ax-llm#77 ·
-
Difficulty 1/5 Under an hour Newbie friendliness 90/100
games-on-whales/wolf#509 ·
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
-
bug-unconfirmed
Difficulty 2/5 1-3 hours Newbie friendliness 76/100
-
Difficulty 2/5 1-3 hours Newbie friendliness 74/100
NVIDIA/cuda-samples#453 ·