boostorg / boostorg/graph

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

Offen
#465 0 Kommentare 0 Reaktionen 1 zugewiesene Person Beansprucht von @Becheler Auf GitHub ansehen
data structure
Vorherrschende Sprache
C++
Sterne
392
Forks
239
Ø Merge
1 T. 11 Min.
Gemergte PRs (30 T.)
20

Beschreibung

## 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

Beitragsleitfaden

Beitragsleitfaden öffnen

Bewertung

Dieses Issue wurde noch nicht bewertet.

Neue Issues direkt in Ihr Postfach

Eine kurze Übersicht über anfängerfreundliche GitHub-Issues.