Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

CSR: Indexed properties maps are unstable #373

Open
sehe opened this issue May 3, 2024 · 0 comments
Open

CSR: Indexed properties maps are unstable #373

sehe opened this issue May 3, 2024 · 0 comments

Comments

@sehe
Copy link
Contributor

sehe commented May 3, 2024

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.
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant