boostorg / boostorg/graph

Reconcile `labeled_graph` and `named_graph` into a single documented component

未关闭
#465 0 条评论 0 个 reaction 已指派 1 人 已被 @Becheler 认领 在 GitHub 查看
data structure
主要语言
C++
星标
392
派生
239
平均合并
1 天 11 分钟
30 天内合并 PR
20

描述

## Problem

Boost.Graph has two overlapping mechanisms for label to vertex lookup:

- `labeled_graph` (Sutton, 2009): simple API, external adaptor, but undocumented, non-compilable example, and broken in multiple ways :
- #147
- #167
- #187
- `named_graph` (Gregor, 2007): sound internals (multi-index), but requires trait specialization, tightly coupled to `adjacency_list`, drags in Boost.MultiIndex unconditionally, which drags mp11 ... also undocumented. Friction to adoption due to boilerplate code is high.

Both are incomplete. Users end up maintaining their own `std::map` because both options are either broken or too cumbersome.

## Proposal

- keep `labeled_graph` external API (simpler one):
- `add_vertex(label, g)`
- `g.vertex(label)`
- `remove_vertex(label, g)`
- Replace `labeled_graph` internal `_map` with `named_graph` multi-index machinery. This would eliminate the entire set of map-sync bugs by construction.
- Decouple `named_graph` from `adjacency_list` so it can back any graph type
- Deprecate direct use of `named_graph traits` (`internal_vertex_name`, `internal_vertex_constructor`) as they become implementation details
- Drop `vecS` label storage that seems fundamentally broken and blocked by static_assert in #464)
- Reverse lookup (vertex to label)
- Eliminate the owning/pointer graph duplication from `labeled_graph`
- Write a documentation page + working examples

贡献指南

打开贡献指南

评估

这个 Issue 还没有评估数据。

把新 issue 发到你的邮箱

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