boostorg / boostorg/graph

CSR: Indexed properties maps are unstable

未关闭
#373 0 条评论 0 个 reaction 已指派 0 人 在 GitHub 查看
data structure priority: medium
主要语言
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 还没有评估数据。

把新 issue 发到你的邮箱

精选适合新手参与的 GitHub issue 摘要。