Graph generators for benchmarking and testing

[Becheler]

Story

Virtually any problem with graphs hits the same question: "does it scale?". Someone has to go find a real or synthetic graph, download it, parse it, and hope it's the right shape. BGL has very little built-in generators. NetworkX ships with Erdős–Rényi, Barabási–Albert, Watts–Strogatz, grid graphs, trees, and SNAP loaders as standard.

This gap makes it hard to write self-contained tests, benchmarks, or documentation examples.

Dream solution

A boost::graph::generators header covering standard synthetic families plus real datasets loaders for SNAP and GraphML. Used throughout BGL's own test suite.

Starting point

• BGL current generators
• NetworkX generators
• SNAP datasets

Intermediary objective (45 min)

• Identify the perimeter of actionable work items in 2026: matching NetworkX coverage is unlikely, but encouraging contributors submitting simple generators is easy.
• Identify the most critical gaps: generators that most of users need and that would be painful to implement themselves
• Identify risks: accessing online datasets in C++ is hard.
• Write an ideal API specification for a generator of your choice:
  • function signature,
  • return type,
  • template parameters,
  • complexity.
  • No implementation, just the interface contract. This turns "we should have generators" into a PR someone can open on Monday 😄

[sducomman]

I can be interess to have benchmarking of different algos for bgl.

First we can have the difference for algo of data structure : Adjacency list, matric CSR
And in second time, the comparaison of algorithm of the same family.

Melon (https://github.com/fhamonic/melon) the successor of Lemon (https://en.wikipedia.org/wiki/LEMON_(C%2B%2B_library)) has initiate benchmarking of Lemon, BGL and itself.
It parses some snap and some classical graphs from DIMACS and just the difference time between adjacency_list and CSR is interessting. Maybe to put in the graph structure of documentation.