SG19 Graph Library Standardization Meeting — July 2026

Attendees

Michael (chair). Guy Davidson (WG21 convener; departed mid-session) . Phil (co-author of the graph library proposal) . Vinnie Falco (Boost library author; presented on standardization criteria). Andrew (BGL original co-author). Oliver . Richard (professor, statistics library author)

Summary

This SG19 session featured a framework for evaluating whether library proposals belong in the standard was presented and debated, then applied to the long-running graph library proposal, resulting in informal consensus that the graph proposal should pursue an incubation path through Boost and/or the Beaman project before seeking advancement, with a concepts-first approach potentially replacing the current container-centric design. No formal polls were taken; a draft poll was read into the record but deferred.

Standardization Criteria Framework by Vinnie

A framework for evaluating standard library proposals was presented, arguing that the default answer to any library proposal should be "no" with the burden of proof on the paper, and that proposals should be measured against quantitative criteria including the complexity budget, the coordination problem solved, a GitHub test, a reach test, the standardization penalty, the interaction tax, and the return on complexity.

• The standard has grown from roughly 700 pages in C++98 to 2,700 pages; every page is an ongoing maintenance, editing, and bug-fixing liability

• The central question: does this component solve a coordination problem (allowing independently written code to interoperate) whose benefit exceeds the standardization penalty?

• The GitHub test: if a library is already freely available and the standard adds no value beyond what users can download, it should not be added

• The standardization penalty: every library immediately gets worse when standardized (std::regex became 75x slower; std::unordered_map ossified due to bucket-iterator ABI commitment); the penalty must be measured and justified

• The interaction tax grows quadratically: each new component must be considered against everything already in the standard

• Deployment evidence is essential: papers should read like research reports with field data, not just design documents; WG21 currently has no rule requiring a working implementation for library proposals

• The smallest standardizable piece is the best: maximize value per page of wording; for networking, this might mean standardizing only the coroutine awaitable/sender piece rather than the full socket layer

• People expressed support for these criteria and stated an intent to reduce the number of papers and raise the quality bar going forward

• A counter-point was raised that the GitHub test assumes universal access; government, military, and finance sectors often mandate standard-library-only code, and C++ lacks a standard package manager

Graph Library Proposal — Incubation Path

The graph library proposal, under development for five-plus years, was assessed against the framework and found to need incubation and deployment evidence before it can advance, with a concepts-first strategy emerging as the likely path forward.

• Informal consensus: the proposal needs community users and deployment evidence before advancing to LEWG; no one on the call disagreed

• Draft poll read by the chair (not voted): "SG19 encourages continued development of the graph library proposal and recommends that the authors pursue incubation through the Beaman project and/or Boost with the goal of obtaining deployment experience before seeking advancement to LEWG. SG19 will reevaluate the proposal's readiness for advancement once this evidence is available."

• It was argued the coordination problem for graphs is at the concept layer (shared vocabulary for traversal), not the container layer (specific data structures), because graph data structures are highly application-specific

• The M×N problem: without shared concepts, M algorithms times N graph representations requires M×N implementations; concepts reduce this to M+N

• The BGL original co-author argued that algorithms must come first and concepts must be derived from algorithmic requirements, not designed independently — starting from concepts risks putting the cart before the horse

• Agreement that concepts should be proven to model existing diversity: BGL adjacency list, CSR representations, implicit grid graphs, adjacency matrices, custom graphs — without forcing any to change

• Visitor callbacks were identified as a risk: they may freeze a specific implementation strategy (e.g., CLRS textbook BFS with color maps) into a public contract rather than expressing algorithmically inherent events

• The graph library co-author reported adding BGL adapters so standard graph algorithms can run against BGL's data structures, and expressed interest in partnering with BGL maintainers to position the work as "BGL 2," though engagement has been difficult

• Practical incubation advice from the Boost library author: search GitHub for users of existing graph libraries, recruit migration, measure conversion rate; submit to Boost rather than Beaman (Beaman libraries expire after two cycles, discouraging adoption; Boost libraries persist and ship with every Linux distribution)

• The SG19 naming issue was raised: graphs and basic statistics are far more elementary than machine learning, and a group evaluating graph proposals should reflect the breadth of graph applications (compilers, routers, dependency solvers, EDA, games, AI, bioinformatics), not imply an ML-only scope

• Concepts have no ABI, so the standardization penalty on implementation choices is minimized — the coordination benefit without the freeze

• Action: the graph authors to digest the framework and consider whether to reorient toward a concepts-and-algorithms-first strategy

• Action: the chair to arrange a private meeting for an AI tools demo with the graph and statistics authors