boostorg / boostorg/graph

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

Open
#465 0 comments 0 reactions 1 assignee Claimed by @Becheler View on GitHub
data structure
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.