Reconcile `labeled_graph` and `named_graph` into a single documented component
- Dominant language
- C++
- Stars
- 392
- Forks
- 239
- Avg merge
- 1d 11m
- Merged PRs (30d)
- 20
Description
## 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
Contributor guide
Assessment
This issue has not been assessed yet.