CSR: Indexed properties maps are unstable

Open
#373 0 comments 0 reactions 0 assignees View on GitHub

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

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

data structure priority: medium

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

  1. whether a safer property-map derivation should be made the default (removing a tricky UB trap)
  2. whether other graph models can be reviewed for similar property-map invalidation
  3. 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.
Dominant language
C++
Stars
395
Forks
239
Avg merge
18h 50m
Merged PRs (30d)
20

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

More from boostorg/graph

All issues in boostorg/graph

Similar issues

More C++ issues

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.