CSR: Indexed properties maps are unstable
- 主要语言
- C++
- 星标
- 392
- 派生
- 239
- 平均合并
- 1 天 11 分钟
- 30 天内合并 PR
- 20
描述
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:
```c++
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:
```c++
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)
1. whether other graph models can be reviewed for similar property-map invalidation
1. 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.
贡献指南
评估
这个 Issue 还没有评估数据。