Integration of a graph-generation library

[plc-dev]

Possible candidates:

• NetworkX

One exemplary use-case is the generation of randomized "Gozintographs" for practice-exercises in production planning regarding algorithms for BOM explosion:

The wrapper should expose an

• OpenAPI-Spec,
  • by virtue of that, a REST-API
  • and preferably a mirroring CLI,
• be distributed as a Docker-Image
• and - if required - state its minimal hardware requirements.

The code should be added as a subdirectory within the /services/-directory and should adhere to the defined contracts of the repository. Namely, the Makefile targets and the inclusion of a Github CI workflow.

As the above candidates are tested already, units regarding the functionality of the embedded library may be omitted.

[plc-dev]

AI-guided design process for documentation. Utilized harness is the Kilo-cli with version 7.3.46, in Code-mode and Auto-Frontier-models (Opus 4.8).

Prompt: Produce a search of available libraries for graph generation

I am trying to implement a containerized microservice that exposes a unified API for generating graphs. I want to embed existing libraries for graph generation and cover as many different graph generation algorithms as possible.
Provide a tabular overview of existing libraries - if required perform a web-search. The table should include the name of the library, the available graph generation algorithms alongside the function signatures for each algorithm (name, input parameters and return value - if possible with their type signatures), the programming language in which the library is implemented, a link to its public repository and a date of when it was last maintained (e.g. latest commit or published version).

For reusing this prompt for similar issues, just substitute "graph generation" for the name of the family of algorithms that should be compared (e.g. noise generation).

Result: Overview of available libraries for graph generation

Graph Generation Libraries — Comparison

Overview of existing libraries for embedding graph generation algorithms into a containerized microservice with a unified API. Compiled via web research; dates reflect the latest confirmed release/commit as of mid-2026.

Summary

Library	Language	Public repository	Latest release / maintained	Approx. # of generators
NetworkX	Python (pure)	https://github.com/networkx/networkx	v3.6.x (2026, actively maintained)	~60+ (largest catalog)
igraph (C core)	C	https://github.com/igraph/igraph	C core 1.0.0 (Oct 2025)	~40+
python-igraph	Python (C bindings)	https://github.com/igraph/python-igraph	v1.0.1 (Dec 26, 2025)	~40+
rigraph (R)	R (C bindings)	https://github.com/igraph/rigraph	v2.x (CRAN, Apr 2026)	~40+
graph-tool	C++/Python (Boost)	https://git.skewed.de/count0/graph-tool	v2.98 (2025)	~15
JGraphT	Java	https://github.com/jgrapht/jgrapht	v1.5.2 (updated Apr 2026)	~20 + many named graphs
NetworKit	C++/Python	https://github.com/networkit/networkit	v11.2.1 (Jan 9, 2026)	~15 (large-scale focus)
SNAP	C++ (+ Python snap.py)	https://github.com/snap-stanford/snap	v6.0 (maintenance)	~10
Boost Graph Library (BGL)	C++ (header-only)	https://github.com/boostorg/graph	Boost 1.8x (2025/26)	~5

Below are the per-library details with algorithm names, signatures, and types.

---

NetworkX (Python) — largest algorithm catalog

Repo: https://github.com/networkx/networkx · Latest: v3.6.x (2026) · Language: pure Python.

All generators return a networkx.Graph (or DiGraph/MultiGraph) object.

Random graphs (networkx.generators.random_graphs)

Algorithm	Signature	Returns
Erdős–Rényi G(n,p)	gnp_random_graph(n: int, p: float, seed=None, directed: bool=False) -> Graph	Graph
Fast G(n,p) (sparse)	fast_gnp_random_graph(n: int, p: float, seed=None, directed: bool=False) -> Graph	Graph
Erdős–Rényi G(n,m)	gnm_random_graph(n: int, m: int, seed=None, directed: bool=False) -> Graph	Graph
Dense G(n,m)	dense_gnm_random_graph(n: int, m: int, seed=None) -> Graph	Graph
Aliases	erdos_renyi_graph, binomial_graph (= gnp_random_graph)	Graph
Watts–Strogatz	watts_strogatz_graph(n: int, k: int, p: float, seed=None) -> Graph	Graph
Newman–Watts–Strogatz	newman_watts_strogatz_graph(n: int, k: int, p: float, seed=None) -> Graph	Graph
Connected Watts–Strogatz	connected_watts_strogatz_graph(n: int, k: int, p: float, tries: int=100, seed=None) -> Graph	Graph
Random regular	random_regular_graph(d: int, n: int, seed=None) -> Graph	Graph
Barabási–Albert	barabasi_albert_graph(n: int, m: int, seed=None, initial_graph: Graph=None) -> Graph	Graph
Dual Barabási–Albert	dual_barabasi_albert_graph(n: int, m1: int, m2: int, p: float, seed=None, initial_graph=None) -> Graph	Graph
Extended Barabási–Albert	extended_barabasi_albert_graph(n: int, m: int, p: float, q: float, seed=None) -> Graph	Graph
Holme–Kim power-law cluster	powerlaw_cluster_graph(n: int, m: int, p: float, seed=None) -> Graph	Graph
Random lobster	random_lobster(n: int, p1: float, p2: float, seed=None) -> Graph	Graph
Random shell	random_shell_graph(constructor, seed=None) -> Graph	Graph
Random power-law tree	random_powerlaw_tree(n: int, gamma: float=3, seed=None, tries: int=100) -> Graph	Graph
Random kernel graph	random_kernel_graph(n: int, kernel_integral, kernel_root=None, seed=None) -> Graph	Graph

Degree-sequence models (networkx.generators.degree_seq)

Algorithm	Signature	Returns
Configuration model	configuration_model(deg_sequence: list[int], create_using=None, seed=None) -> MultiGraph	MultiGraph
Directed config. model	directed_configuration_model(in_degree_sequence, out_degree_sequence, create_using=None, seed=None) -> MultiDiGraph	MultiDiGraph
Expected degree (Chung–Lu)	expected_degree_graph(w: list[float], seed=None, selfloops: bool=True) -> Graph	Graph
Havel–Hakimi	havel_hakimi_graph(deg_sequence: list[int], create_using=None) -> Graph	Graph
Degree sequence tree	degree_sequence_tree(deg_sequence, create_using=None) -> Graph	Graph
Random degree sequence	random_degree_sequence_graph(sequence, seed=None, tries: int=10) -> Graph	Graph

Community / clustered models (networkx.generators.community)

Algorithm	Signature	Returns
Stochastic block model	stochastic_block_model(sizes: list[int], p: list[list[float]], nodelist=None, seed=None, directed=False, selfloops=False, sparse=True) -> Graph	Graph
Planted partition	planted_partition_graph(l: int, k: int, p_in: float, p_out: float, seed=None, directed=False) -> Graph	Graph
Gaussian random partition	gaussian_random_partition_graph(n, s, v, p_in, p_out, directed=False, seed=None) -> Graph	Graph
Relaxed caveman	relaxed_caveman_graph(l: int, k: int, p: float, seed=None) -> Graph	Graph
LFR benchmark	LFR_benchmark_graph(n, tau1, tau2, mu, ...) -> Graph	Graph
Windmill	windmill_graph(n: int, k: int) -> Graph	Graph

Geometric graphs (networkx.generators.geometric)

Algorithm	Signature	Returns
Random geometric	random_geometric_graph(n: int, radius: float, dim: int=2, pos=None, p: float=2, seed=None) -> Graph	Graph
Soft random geometric	soft_random_geometric_graph(n, radius, dim=2, pos=None, p=2, p_dist=None, seed=None) -> Graph	Graph
Geographical threshold	geographical_threshold_graph(n, theta, dim=2, pos=None, weight=None, ...) -> Graph	Graph
Waxman	waxman_graph(n, beta=0.4, alpha=0.1, L=None, domain=(0,0,1,1), ...) -> Graph	Graph
Navigable small world	navigable_small_world_graph(n, p=1, q=1, r=2, dim=2, seed=None) -> Graph	Graph
Thresholded RGG	thresholded_random_geometric_graph(n, radius, theta, dim=2, ...) -> Graph	Graph

Classic / deterministic (networkx.generators.classic, .small, .lattice)

Algorithm	Signature	Returns
Complete	complete_graph(n, create_using=None) -> Graph	Graph
Complete bipartite	complete_bipartite_graph(n1, n2, create_using=None) -> Graph	Graph
Cycle	cycle_graph(n, create_using=None) -> Graph	Graph
Path	path_graph(n, create_using=None) -> Graph	Graph
Star	star_graph(n, create_using=None) -> Graph	Graph
Wheel	wheel_graph(n, create_using=None) -> Graph	Graph
Balanced tree	balanced_tree(r, h, create_using=None) -> Graph	Graph
Grid 2D	grid_2d_graph(m, n, periodic=False, create_using=None) -> Graph	Graph
Grid n-D	grid_graph(dim, periodic=False) -> Graph	Graph
Hypercube	hypercube_graph(n) -> Graph	Graph
Named small graphs	petersen_graph(), karate_club_graph(), les_miserables_graph(), etc.	Graph

Also: directed scale-free (scale_free_graph), intersection graphs, internet AS graphs (random_internet_as_graph), trees (random_labeled_tree, random_unlabeled_tree), and RMAT-like duplication-divergence models.

---

igraph (C core + Python / R bindings)

C core repo: https://github.com/igraph/igraph (1.0.0, Oct 2025). Python: https://github.com/igraph/python-igraph (v1.0.1, Dec 2025). R: https://github.com/igraph/rigraph (CRAN v2.x, Apr 2026).

Python constructors are classmethods on igraph.Graph returning a Graph. Table below lists the Python signature and the R equivalent.

Algorithm	Python signature (igraph.Graph.…)	R equivalent	Returns
Erdős–Rényi	Erdos_Renyi(n, p=None, m=None, directed=False, loops=False)	sample_gnp(n, p), sample_gnm(n, m)	Graph
Barabási–Albert	Barabasi(n, m=1, outpref=False, directed=False, power=1, zero_appeal=1, ...)	sample_pa(n, power=1, m=NULL, ...)	Graph
Watts–Strogatz	Watts_Strogatz(dim, size, nei, p, loops=False, multiple=False)	sample_smallworld(dim, size, nei, p)	Graph
Stochastic block model	SBM(n, pref_matrix, block_sizes, directed=False, loops=False)	sample_sbm(n, pref.matrix, block.sizes)	Graph
Random tree	Tree_Game(n, directed=False, method="lerw")	sample_tree(n)	Graph
Forest fire	Forest_Fire(n, fw_prob, bw_factor=0.0, ambs=1, directed=False)	sample_forestfire(n, fw.prob, ...)	Graph
Geometric random	GRG(n, radius, torus=False)	sample_grg(n, radius)	Graph
Growing random	Growing_Random(n, m, directed=False, citation=False)	sample_growing(n, m)	Graph
Establishment	Establishment(n, types, k, type_dist, pref_matrix, directed=False)	—	Graph
Preference	Preference(n, type_dist, pref_matrix, attribute=None, directed=False, loops=False)	sample_pref(...)	Graph
Asymmetric preference	Asymmetric_Preference(n, type_dist_matrix, pref_matrix, ...)	—	Graph
Recent-degree	Recent_Degree(n, power, window, m, ...)	—	Graph
k-regular	K_Regular(n, k, directed=False, multiple=False)	sample_k_regular(n, k)	Graph
Static fitness	Static_Fitness(m, fitness_out, fitness_in=None, loops=False, multiple=False)	sample_fitness(...)	Graph
Static power law	Static_Power_Law(n, m, exponent_out, exponent_in=-1, ...)	sample_fitness_pl(...)	Graph
Degree sequence	Degree_Sequence(out, in_=None, method="configuration")	sample_degseq(out.deg, ...)	Graph
Random bipartite	Random_Bipartite(n1, n2, p=None, m=None, directed=False, ...)	sample_bipartite(n1, n2, ...)	Graph
LCF / named	LCF(n, shifts, repeats), plus Famous(name) (Petersen, Zachary, etc.)	graph_from_lcf(...), make_famous_graph(name)	Graph

---

graph-tool (C++/Python)

Repo: https://git.skewed.de/count0/graph-tool · Latest v2.98 (2025). Module: graph_tool.generation. Returns graph_tool.Graph.

Algorithm	Signature	Returns
Degree-based random graph	random_graph(N, deg_sampler, directed=True, parallel_edges=False, self_loops=False, block_membership=None, ..., n_iter=...) -> Graph (or (Graph, VertexPropertyMap))	Graph
In-place rewire	random_rewire(g, model="uncorrelated", n_iter=1, edge_sweep=True, ...) -> int	rejection count
Price / Barabási–Albert	price_network(N, m=1, c=None, gamma=1, directed=True, seed_graph=None) -> Graph	Graph
Stochastic block model	generate_sbm(b, probs, out_degs=None, in_degs=None, directed=False, ...) -> Graph	Graph
Max-entropy SBM	generate_maxent_sbm(b, mrs, out_degs=None, in_degs=None, directed=False) -> Graph	Graph
k-nearest-neighbor graph	generate_knn(points, k, dist=None, ...) -> (Graph, VertexPropertyMap)	Graph + weights
Triadic closure	generate_triadic_closure(g, t, ...) -> Graph	Graph
Geometric graph	geometric_graph(points, radius, ranges=None) -> (Graph, VertexPropertyMap)	Graph + pos
Lattice	lattice(shape, periodic=False) -> Graph	Graph
Complete	complete_graph(N, self_loops=False, directed=False) -> Graph	Graph
Circular	circular_graph(N, k=1, self_loops=False, directed=False) -> Graph	Graph
Triangulation	triangulation(points, type="simple", periodic=False) -> (Graph, VertexPropertyMap)	Graph + pos

---

JGraphT (Java)

Repo: https://github.com/jgrapht/jgrapht · v1.5.2 (updated Apr 2026). Package org.jgrapht.generate. Generators implement GraphGenerator<V,E,T>; construct the generator, then call generateGraph(Graph<V,E> target, Map<String,T> resultMap) (void; populates the target graph).

Algorithm	Constructor signature	Notes
G(n,p) Erdős–Rényi	GnpRandomGraphGenerator(int n, double p, long seed, boolean createLoops) (+ overloads)	populates target
G(n,m) Erdős–Rényi	GnmRandomGraphGenerator(int n, int m, long seed, boolean loops, boolean multipleEdges)
Barabási–Albert graph	BarabasiAlbertGraphGenerator(int m0, int m, int n, long seed) (or Random rng)
Barabási–Albert forest	BarabasiAlbertForestGenerator(int t, int n, long seed)	trees/forests
Watts–Strogatz	WattsStrogatzGraphGenerator(int n, int k, double p, boolean addInsteadOfRewire, Random rng)
Scale-free	ScaleFreeGraphGenerator(int size, long seed)
Random regular	RandomRegularGraphGenerator(int n, int d, long seed)
Complete	CompleteGraphGenerator(int size)
Complete bipartite	CompleteBipartiteGraphGenerator(int partitionOne, int partitionTwo)
Grid	GridGraphGenerator(int rows, int cols)
Hyper-cube	HyperCubeGraphGenerator(int dim)
Ring	RingGraphGenerator(int size)
Star	StarGraphGenerator(int order)
Wheel	WheelGraphGenerator(int size)
Linear (path)	LinearGraphGenerator(int size)
Kleinberg small-world	KleinbergSmallWorldGraphGenerator(int n, int p, int q, int r, long seed)
Pruefer tree	PruferTreeGenerator(int n, long seed)	random labeled trees
Generalized Petersen	GeneralizedPetersenGraphGenerator(int n, int k)
Named graphs	NamedGraphGenerator → petersenGraph(), zacharyKarateClubGraph(), heawoodGraph(), chvatalGraph(), dodecahedronGraph(), … (dozens)	static factory methods

---

NetworKit (C++ core, Python API) — for very large graphs

Repo: https://github.com/networkit/networkit · v11.2.1 (Jan 9, 2026). Module networkit.generators. Pattern: instantiate a generator class, call .generate() → returns networkit.Graph.

Algorithm	Signature	Returns
Erdős–Rényi	ErdosRenyiGenerator(nNodes: int, prob: float, directed=False, selfLoops=False).generate()	Graph
Barabási–Albert	BarabasiAlbertGenerator(k: int, nMax: int, n0: int=0, batagelj=True).generate()	Graph
Watts–Strogatz	WattsStrogatzGenerator(nNodes: int, nNeighbors: int, p: float).generate()	Graph
Clustered random	ClusteredRandomGraphGenerator(n: int, k: int, pIntra: float, pInter: float).generate()	Graph
Stochastic block model	StochasticBlockmodel(n, nBlocks, membership, affinity).generate()	Graph
Chung–Lu	ChungLuGenerator(degreeSequence: list[int]).generate()	Graph
Havel–Hakimi	HavelHakimiGenerator(sequence: list[int], ignoreIfRealizable=True).generate()	Graph
Edge-switching config. model	EdgeSwitchingMarkovChainGenerator(degreeSequence, ignoreIfRealizable=False).generate()	Graph
Hyperbolic (RHG)	HyperbolicGenerator(n, k=6, gamma=3, T=0).generate()	Graph
Dorogovtsev–Mendes	DorogovtsevMendesGenerator(nNodes: int).generate()	Graph
R-MAT	RmatGenerator(scale: int, edgeFactor: int, a, b, c, d).generate()	Graph
Regular ring lattice	RegularRingLatticeGenerator(nNodes, nNeighbors).generate()	Graph
PubWeb	PubWebGenerator(numNodes, numberOfDenseAreas, neighborhoodRadius, maxNumberOfNeighbors).generate()	Graph
LFR benchmark	LFRGenerator(n) + .generatePowerlawDegreeSequence(...), .run()	Graph

---

SNAP (C++ core, snap.py Python bindings)

Repo: https://github.com/snap-stanford/snap · v6.0. Namespace TSnap. Returns PUNGraph/PNGraph (smart pointers to un/directed graphs).

Algorithm	C++ signature	Returns
G(n,m) random	GenRndGnm<PGraph>(const int& Nodes, const int& Edges, const bool& IsDir=true, TRnd& Rnd=TInt::Rnd)	PGraph
Preferential attachment (BA)	GenPrefAttach(const int& Nodes, const int& NodeOutDeg, TRnd& Rnd=TInt::Rnd)	PUNGraph
Geometric pref. attachment	GenGeoPrefAttach(const int& Nodes, const int& OutDeg, const double& Beta, TRnd& Rnd)	PUNGraph
Small-world (Watts–Strogatz)	GenSmallWorld(const int& Nodes, const int& NodeOutDeg, const double& RewireProb, TRnd& Rnd)	PUNGraph
Power-law degree	GenRndPowerLaw(const int& Nodes, const double& PowerExp, ...)	PUNGraph
Random k-regular	GenRndDegK(const int& Nodes, const int& Deg, ...)	PUNGraph
Random bipartite	GenRndBipart(const int& LeftNodes, const int& RightNodes, const int& Edges, TRnd& Rnd)	PUNGraph
Grid	GenGrid<PGraph>(const int& Rows, const int& Cols, const bool& IsDir=true)	PGraph
Full/complete	GenFull<PGraph>(const int& Nodes)	PGraph
Star	GenStar<PGraph>(const int& Nodes, const bool& IsDir=true)	PGraph
Circle	GenCircle<PGraph>(const int& Nodes, const int& OutDeg, const bool& IsDir=true)	PGraph
Forest Fire	TFfGGen class / GenForestFire(Nodes, FwdProb, BckProb)	PNGraph
Kronecker	TKronMtx + GenKronecker(...) (in kronecker.h)	PNGraph
Rewire	GenRewire(PUNGraph& Graph, const int& NSwitch, TRnd& Rnd)	PUNGraph

Python (snap.py) mirrors these: snap.GenRndGnm(snap.PUNGraph, n, m), snap.GenPrefAttach(n, outdeg), snap.GenSmallWorld(n, outdeg, rewireprob), etc.

---

Boost Graph Library (C++, header-only)

Repo: https://github.com/boostorg/graph · Ships with Boost (1.8x, 2025/26). Generators are iterator classes that produce edge pairs consumed by a graph constructor; typically used with adjacency_list.

Algorithm	Signature	Returns
Erdős–Rényi G(n,p)	erdos_renyi_iterator<RandGen, Graph>(gen, n, p, allow_self_loops=false)	edge iterator
Sorted Erdős–Rényi	sorted_erdos_renyi_iterator<RandGen, Graph>(gen, n, p, allow_self_loops=false)	edge iterator
Small-world (Watts–Strogatz)	small_world_iterator<RandGen, Graph>(gen, n, k, prob, allow_self_loops=false)	edge iterator
Preferential attachment (BA)	plod_iterator<RandGen, Graph>(gen, n, alpha, beta, allow_self_loops=false) (power-law out-degree)	edge iterator
R-MAT	rmat_iterator<RandGen, Graph>(gen, n, m, a, b, c, d)	edge iterator
Mesh / grid	mesh_graph generator utilities in topology.hpp / examples	—

Typical usage: Graph g(er_begin, er_end, n);

---

Recommendations for a unified microservice

• Primary engine: NetworkX + igraph. Together they cover the widest range of models (NetworkX for breadth and pure-Python simplicity; igraph's C core for performance and models NetworkX lacks, e.g. forest fire, establishment, static power-law).
• Add NetworKit or graph-tool if very large graphs (millions of nodes) are needed — both have C++ cores. graph-tool has the richest SBM tooling.
• JGraphT/SNAP/BGL are worth wrapping only if specific niche generators are required (JGraphT's large "named graphs" catalog; SNAP's Kronecker/RMAT at scale; BGL if the service is C++-native).

Design implication for the unified API

These libraries disagree on conventions:

• Return object vs. in-place populate vs. edge-iterator.
• Parameter naming (e.g. m meaning edges-per-node vs. total edges).
• Directedness defaults.

A normalization layer should map a canonical model name (e.g. erdos_renyi, barabasi_albert, watts_strogatz, sbm, configuration, rgg) and a canonical parameter set to each backend's specific signature, and standardize the output (e.g. export to a common format such as GraphML or an edge list) regardless of the underlying library.

Prompt: Selection libraries from the comparison overview - framed as an optimization problem

Utilize the information of that comparison table to select the minimal amount of libraries that cover the most amount of algorithms (ideally all), with the side condition of having a minimal overlap between the selected libraries. This is essentially an optimization problem. You may add weights that influence the selection for the compatibility of the exposed APIs for each library and the last maintenance date.

Result: Optimal selection

Optimal Library Selection for a Unified Graph-Generation Microservice

This document uses the data from graph-generation-libraries-comparison.md to solve a
weighted maximum-coverage / set-cover problem: select the smallest set of libraries
that covers the largest number of distinct graph-generation algorithm families, while
minimizing redundant overlap between the selected libraries, and while favoring
libraries that are actively maintained and expose an API style that is easy to unify
behind a single microservice interface.

---

1. Problem formalization

Let:

• A = {a_1, ..., a_26} — the universe of distinct algorithm families (canonical
  generator categories, not individual function signatures; e.g. "Barabási–Albert" is
  one category even though 6 libraries implement it with different signatures).
• L = {NetworkX, igraph, graph-tool, JGraphT, NetworKit, SNAP, BGL} — candidate
  libraries (rigraph is excluded a priori: it wraps the same C core as python-igraph
  and would only add coverage overlap plus a second runtime/language to embed).
• cover(l) ⊆ A — the set of algorithm families implemented by library l.
• Q(l) = freshness(l) × api_compat(l) — a quality weight in [0, 1] per library.

We want to choose S ⊆ L minimizing |S|, such that ⋃_{l∈S} cover(l) is as close to
A as possible, while maximizing:

score(S) = Σ_{l∈S} Q(l) × |new(l, S)|

where new(l, S) is the set of algorithm families l adds that were not already
covered by other libraries already chosen in S (this is what enforces "minimal
overlap" — each added library must justify its inclusion mainly through new
coverage, not duplicate coverage).

This is the classic weighted maximum coverage problem (NP-hard in general); we
solve it with the standard greedy approximation (pick, at each step, the library
maximizing Q(l) × |new(l, S)|), which is known to be within a (1 − 1/e) factor of
optimal.

---

2. Algorithm family universe

#	Algorithm family
1	Erdős–Rényi G(n,p)
2	Erdős–Rényi G(n,m)
3	Watts–Strogatz small-world
4	Barabási–Albert preferential attachment (incl. dual/extended variants)
5	Configuration model / degree-sequence (Havel–Hakimi, edge-switching)
6	Stochastic block model
7	Random k-regular graph
8	Random geometric graph (RGG)
9	Forest-fire model
10	Kronecker / R-MAT
11	Classic deterministic graphs (complete, star, wheel, path, cycle, grid, hypercube, lattice)
12	Named / famous graphs (Petersen, Zachary karate club, etc.)
13	Random tree generators (Prüfer, uniform random tree)
14	Random bipartite graph
15	Community / clustered models (planted partition, Gaussian RP, LFR, relaxed caveman)
16	Hyperbolic random graph
17	Chung–Lu / expected-degree graph
18	Static fitness / power-law fitness model
19	Growing random / establishment / preference (citation-style) models
20	Kleinberg navigable small-world
21	k-nearest-neighbor graph
22	Triangulation / Delaunay graph
23	Price network (dedicated directed citation-growth model)
24	Holme–Kim power-law cluster model
25	Waxman / geographic threshold graph
26	Duplication-divergence / internet AS model

---

3. Coverage matrix

✓ = implemented, – = not implemented (or only approximable via a generic/manual construction).

#	Family	NetworkX	igraph	graph-tool	JGraphT	NetworKit	SNAP	BGL
1	Erdős–Rényi G(n,p)	✓	✓	–	✓	✓	–	✓
2	Erdős–Rényi G(n,m)	✓	✓	–	✓	–	✓	–
3	Watts–Strogatz	✓	✓	–	✓	✓	✓	✓
4	Barabási–Albert (+variants)	✓	✓	–	✓	✓	✓	✓
5	Configuration / degree-seq.	✓	✓	–	–	✓	–	–
6	Stochastic block model	✓	✓	✓	–	✓	–	–
7	Random k-regular	✓	✓	–	✓	–	✓	–
8	Random geometric (RGG)	✓	✓	✓	–	–	–	–
9	Forest fire	–	✓	–	–	–	✓	–
10	Kronecker / R-MAT	–	–	–	–	✓	✓	✓
11	Classic deterministic	✓	✓	✓	✓	✓ (partial)	✓	–
12	Named / famous graphs	✓	✓	–	✓ (largest catalog)	–	–	–
13	Random trees	✓	✓	–	✓	–	–	–
14	Random bipartite	✓	✓	–	–	–	✓	–
15	Community / clustered	✓	–	–	–	✓	–	–
16	Hyperbolic random graph	–	–	–	–	✓	–	–
17	Chung–Lu / expected degree	✓	–	–	–	✓	–	–
18	Static fitness / power law	–	✓	–	–	–	–	–
19	Growing random / establishment / preference	–	✓	–	–	–	–	–
20	Kleinberg navigable small-world	✓	–	–	✓	–	–	–
21	k-nearest-neighbor graph	–	–	✓	–	–	–	–
22	Triangulation / Delaunay	–	–	✓	–	–	–	–
23	Price network (dedicated)	–	–	✓	–	–	–	–
24	Holme–Kim power-law cluster	✓	–	–	–	–	–	–
25	Waxman / geo-threshold	✓	–	–	–	–	–	–
26	Duplication-divergence / AS	✓	–	–	–	–	–	–
	Raw coverage count	18	15	6	10	9	7	4

---

4. Quality weights

Two independent factors are combined multiplicatively into Q(l) = freshness × api_compat.

4.1 Freshness (recency of maintenance, 0–1)

Library	Latest release	Freshness
NetworkX	v3.6.x, 2026, continuously released	1.00
NetworKit	v11.2.1, Jan 2026	0.95
python-igraph	v1.0.1, Dec 2025	0.95
graph-tool	v2.98, 2025	0.85
JGraphT	v1.5.2, updated Apr 2026 (but infrequent major releases — 2 years between 1.5.1 and 1.5.2)	0.70
BGL	ships with Boost 1.8x (stable, but generator set essentially frozen for years)	0.60
SNAP	v6.0 (core generator code largely unchanged for years; low commit velocity)	0.50

4.2 API compatibility (fit for a unified, containerized microservice, 0–1)

Criteria: native return-object vs. in-place/iterator paradigm, ease of pip/container
packaging, native-dependency footprint, language/runtime match with the rest of the
stack (assumed Python-first service).

Library	Paradigm	Packaging	api_compat
NetworkX	Returns Graph object, pure Python	Trivial (pip install networkx)	1.00
python-igraph	Returns Graph object, C extension	Easy (prebuilt wheels)	0.90
NetworKit	Returns Graph object, C++ core + Python bindings	Moderate (prebuilt wheels available, OpenMP dep)	0.80
graph-tool	Returns Graph/tuple, C++ (Boost) core	Hard — no PyPI wheels on most platforms; Boost/OpenMP/CGAL deps, officially recommends Conda/Docker	0.45
JGraphT	In-place generateGraph(target, resultMap), Java	Requires JVM sidecar or bindings (jpype/Py4J) inside the container	0.35
SNAP	Smart-pointer graph types (PUNGraph), C++/SWIG Python bindings	Older SWIG bindings, template-heavy API, inconsistent maintenance	0.35
BGL	Edge-iterator objects consumed by a graph constructor, header-only C++	No Python bindings at all — pure C++	0.20

4.3 Combined weight Q(l)

Library	Freshness	api_compat	Q(l)
NetworkX	1.00	1.00	1.000
python-igraph	0.95	0.90	0.855
NetworKit	0.95	0.80	0.760
graph-tool	0.85	0.45	0.383
JGraphT	0.70	0.35	0.245
SNAP	0.50	0.35	0.175
BGL	0.60	0.20	0.120

---

5. Greedy weighted maximum-coverage run

Step 1 — pick the library maximizing Q(l) × |cover(l)|:

Library	|cover(l)|	Q(l)	Score
NetworkX	18	1.000	18.00 ← selected
igraph	15	0.855	12.83
JGraphT	10	0.245	2.45
NetworKit	9	0.760	6.84
SNAP	7	0.175	1.23
graph-tool	6	0.383	2.30
BGL	4	0.120	0.48

→ Selected: NetworkX (covers families 1–8, 11–15, 17, 20, 24–26 → 18/26, 69%)

Step 2 — recompute new(l, S) against the 8 remaining families {9,10,16,18,19,21,22,23}:

Library	New families covered	|new|	Q(l)	Score
igraph	9, 18, 19	3	0.855	2.57 ← selected
NetworKit	10, 16	2	0.760	1.52
graph-tool	21, 22, 23	3	0.383	1.15
SNAP	9, 10	2	0.175	0.35
JGraphT	(none new — its unique contribution is depth within family 12, already covered)	0	0.245	0.00
BGL	10	1	0.120	0.12

→ Selected: igraph (adds forest-fire, static-fitness/power-law, growing-random/
establishment/preference → 21/26, 81%)

Step 3 — remaining uncovered families: {10, 16, 21, 22, 23}:

Library	New families covered	|new|	Q(l)	Score
NetworKit	10, 16	2	0.760	1.52 ← selected
graph-tool	21, 22, 23	3	0.383	1.15
SNAP	10	1	0.175	0.18
BGL	10	1	0.120	0.12

→ Selected: NetworKit (adds Kronecker/R-MAT, hyperbolic random graphs → 23/26, 88%)

Step 4 — remaining uncovered families: {21, 22, 23} — only graph-tool covers any
of them:

Library	New families covered	|new|	Q(l)	Score
graph-tool	21, 22, 23	3	0.383	1.15 ← only remaining contributor

→ Optional 4th pick: graph-tool (adds k-NN graphs, triangulation/Delaunay, dedicated
Price network → 26/26, 100%)

No further library adds coverage: JGraphT, SNAP, and BGL are now fully subsumed by the
chosen set (their remaining families are already covered), so the algorithm terminates.

---

6. Recommendation

Tier 1 — Minimal core set (recommended default)

Rank	Library	New families added	Cumulative coverage	Q(l)
1	NetworkX	18	18/26 (69%)	1.000
2	python-igraph	3 (forest fire, static fitness/power-law, growing/establishment/preference)	21/26 (81%)	0.855
3	NetworKit	2 (Kronecker/R-MAT, hyperbolic)	23/26 (88%)	0.760

This 3-library set reaches 88% coverage of all identified algorithm families with
very low mutual overlap (each library was selected specifically because it
contributed the most new families per unit of quality weight) and consists
exclusively of libraries that:

• expose a consistent Python object-return API (easy to wrap in one microservice
  interface / one Dockerfile, one language runtime),
• are actively maintained (all released or updated within the last ~12 months),
• have low native-dependency friction (NetworkX: none; igraph: prebuilt wheels;
  NetworKit: prebuilt wheels, OpenMP only).

Tier 2 — Complete-coverage extension

Rank	Library	New families added	Cumulative coverage	Q(l)
4	graph-tool	3 (k-NN graph, triangulation/Delaunay, dedicated Price network)	26/26 (100%)	0.383

Add graph-tool only if the k-NN / triangulation / dedicated Price-network generators
are actually required by your product. Its low api_compat score (0.45) is driven by
real operational cost: no portable PyPI wheels, a Boost/OpenMP/(optionally CGAL) native
toolchain, and a heavier, harder-to-reproduce container image (the project itself
recommends Conda or its own Docker image rather than pip install). If accepted, it
should be isolated in its own container/sidecar behind the unified API rather than
built into the same image as NetworkX/igraph/NetworKit, to avoid dependency conflicts.

Explicitly excluded

Library	Reason for exclusion
rigraph (R)	Same underlying C core and algorithm coverage as python-igraph; would only add a second language runtime (R) with zero net-new coverage.
JGraphT	After NetworkX + igraph are selected, contributes zero new algorithm families — its unique value (a very large catalog of specific named/deterministic graphs) is a depth-within-family gain, not a new family, and it would require embedding a JVM (or JVM sidecar) purely for that. Revisit only if the product specifically needs its extensive named-graph catalog.
SNAP	Its only unique-at-the-margin contribution (R-MAT/Kronecker) is already covered by NetworKit with a much higher quality weight (0.760 vs 0.175); SNAP's SWIG-based Python bindings and low maintenance velocity make it a poor fit.
BGL	No Python bindings, C++ header-only edge-iterator paradigm is the worst fit for a unified API, and its only unique contribution (R-MAT) is already covered by NetworKit.

---

7. Residual gaps

Even with the 4-library "complete" set, some fine-grained/niche generators noted in the
original comparison are not exactly duplicated (they are treated as depth within an
already-covered family, not a missing family):

• JGraphT's extensive catalog of specific named/deterministic graphs (Möbius–Kantor,
  Coxeter, Ellingham–Horton, etc.) beyond what NetworkX/igraph ship under "named/famous
  graphs".
• SNAP's/BGL's specific R-MAT parameterizations differ slightly from NetworKit's
  RmatGenerator (same family, different parameter surface).
• graph-tool's random_graph() with an arbitrary custom degree/correlation sampler is
  more general than the specific configuration-model/Chung-Lu implementations in
  NetworkX/NetworKit, but is categorized under the same family (feat: init graph-comparator-service #5/Revert "Add noise generation service" #17) since it can
  reproduce their behavior with a custom sampler function.

These are considered acceptable trade-offs given the goal of minimizing the number of
embedded libraries.

---

8. Final answer

Recommended library set: NetworkX + python-igraph + NetworKit (88% family
coverage, minimal overlap, highest aggregate quality weight per family covered).

If 100% coverage is a hard requirement: add graph-tool as a fourth, isolated
component (100% family coverage, at the cost of a heavier/harder-to-containerize
dependency and a slightly worse API-compatibility profile).

Prompt: API spec suggestion

Provide a suggestion for a unified (REST-)API-specification for the suggested selection of libraries. Suggest a minimal amount of distinct API-endpoints and map the respective algorithms of each library to that particular endpoint. Use discriminated unions or similar data structures to help streamline the API, while maintaining the fidelity and flexibility required by the underlying different algorithms and/or libraries.
As there were two different suggestions of library selections, provide two API-specification - one for each suggested library selection.

Adjust the amount of different API-specs to suggest based on the output of the previous step.

Result: API-specs

Unified REST API Specification for the Graph-Generation Microservice

This document defines a unified REST API for embedding the selected graph-generation
libraries behind a single interface, using discriminated unions to keep the number
of distinct endpoints minimal while preserving full parameter fidelity per algorithm
and per backend implementation.

Two variants are provided, matching the two library selections from
graph-generation-libraries-selection.md:

• Spec A — Tier 1 core set: NetworkX + python-igraph + NetworKit (23/26 families).
• Spec B — Tier 2 complete set: Tier 1 + graph-tool (26/26 families).

Both specs share the same 4 endpoints and the same envelope structure — only the
discriminated-union catalog of algorithm/backend combinations differs.

---

1. Design principles

1. One generation endpoint, not one endpoint per algorithm. All ~20+ generator
   families are exposed through a single POST /v1/graphs call whose body is a
   discriminated union, keyed first by algorithm (the canonical family, as
   catalogued previously) and, where more than one backend implements that family,
   keyed second by backend. This avoids a combinatorial explosion of endpoints
   (algorithm × backend × language) while still exposing each backend's exact,
   strongly-typed parameter set.
2. Backend is a first-class, explicit field, not hidden — different backends
   produce statistically different graphs even for the "same" model (e.g. NetworkX's
   barabasi_albert_graph vs. igraph's Barabasi(power=…, zero_appeal=…) vs.
   NetworKit's BarabasiAlbertGenerator(batagelj=…)). Hiding this would silently
   change results between calls. A backend can be omitted, in which case the service
   auto-selects a sensible default (documented per algorithm).
3. Discovery endpoint (GET /v1/algorithms) exposes the full catalog and JSON
   Schemas of the discriminated union at runtime, so clients (and OpenAPI/JSON Schema
   tooling, code generators, form builders) never need to hardcode the union.
4. Generation is decoupled from result retrieval. POST /v1/graphs returns a
   graph resource (potentially generated asynchronously for large n); the actual
   payload (nodes/edges) is fetched/streamed via GET /v1/graphs/{id} with content
   negotiation, so the generation contract stays independent of serialization format
   (edge list, GraphML, adjacency matrix, GML, graph6, …) and independent of size.
5. Uniform error/validation semantics. Because every algorithm variant is a member
   of one JSON Schema union, standard 400 validation errors
   (RFC 9457 application/problem+json) apply identically regardless of backend.

---

2. Shared endpoint set (identical for Spec A and Spec B)

#	Method & path	Purpose
1	GET /v1/algorithms	Discovery: list all algorithm/backend combinations, each with its JSON Schema, canonical family, and metadata (complexity, directedness support, deterministic vs. stochastic).
2	POST /v1/graphs	Generate a graph. Body = discriminated union (algorithm [+ backend] + params + output options). Returns 202 Accepted (async, with Location) for large/slow generators, or 201 Created with the graph inline for small/fast ones — both cases return a Graph resource envelope.
3	GET /v1/graphs/{graphId}	Retrieve a previously generated graph's metadata and (via Accept header / ?format=) its payload in the requested serialization (edge_list, graphml, adjacency, gml, graph6). Supports pagination/streaming for large edge lists.
4	DELETE /v1/graphs/{graphId}	Release a stored graph resource.

Optional, non-essential convenience routes (not counted against the "minimal
endpoint" goal, purely additive sugar; can be omitted):
GET /v1/graphs/{graphId}/stats (degree distribution, density, etc.) and
GET /v1/algorithms/{algorithm} (schema for one family only).

---

3. Shared envelope & discriminated-union pattern

3.1 Request envelope (POST /v1/graphs)

{
  "algorithm": "barabasi_albert",     // discriminator level 1 (canonical family)
  "backend": "networkit",             // discriminator level 2 (implementation) — optional
  "params": {                          // shape depends on (algorithm, backend)
    "n": 10000,
    "k": 4,
    "n0": 4,
    "batagelj": true,
    "seed": 42
  },
  "output": {                          // shared across all algorithms
    "format": "edge_list",             // edge_list | adjacency | graphml | gml | graph6
    "directed": false,
    "labels": "index"                  // index | uuid
  }
}

3.2 JSON Schema discriminated union (OpenAPI 3.1 style)

GenerateGraphRequest:
  oneOf:
    - $ref: '#/components/schemas/ErdosRenyiGnpRequest'
    - $ref: '#/components/schemas/ErdosRenyiGnmRequest'
    - $ref: '#/components/schemas/WattsStrogatzRequest'
    - $ref: '#/components/schemas/BarabasiAlbertRequest'
    - $ref: '#/components/schemas/StochasticBlockModelRequest'
    # ... one member per canonical algorithm family
  discriminator:
    propertyName: algorithm
    mapping:
      erdos_renyi_gnp: '#/components/schemas/ErdosRenyiGnpRequest'
      erdos_renyi_gnm: '#/components/schemas/ErdosRenyiGnmRequest'
      watts_strogatz: '#/components/schemas/WattsStrogatzRequest'
      barabasi_albert: '#/components/schemas/BarabasiAlbertRequest'
      stochastic_block_model: '#/components/schemas/StochasticBlockModelRequest'
      # ...

# Second-level union, only for families with >1 backend:
BarabasiAlbertRequest:
  type: object
  required: [algorithm, backend, params]
  properties:
    algorithm: { const: barabasi_albert }
    backend: { enum: [networkx, igraph, networkit] }
    params:
      oneOf:
        - $ref: '#/components/schemas/BarabasiAlbertNetworkXParams'
        - $ref: '#/components/schemas/BarabasiAlbertIgraphParams'
        - $ref: '#/components/schemas/BarabasiAlbertNetworKitParams'
      discriminator:
        propertyName: backend    # resolved via sibling `backend` field

3.3 Response envelope (Graph resource)

{
  "id": "grf_9f1c2e...",
  "status": "completed",            // pending | completed | failed
  "algorithm": "barabasi_albert",
  "backend": "networkit",
  "params": { "...": "echoed request params" },
  "metadata": {
    "numNodes": 10000,
    "numEdges": 39984,
    "directed": false,
    "createdAt": "2026-07-12T10:00:00Z",
    "generationTimeMs": 184
  },
  "_links": {
    "self": "/v1/graphs/grf_9f1c2e...",
    "export": "/v1/graphs/grf_9f1c2e...?format=graphml"
  }
}

Errors use application/problem+json (RFC 9457) with an additional
invalidParams: [{ name, reason }] array, so a single schema serves every backend.

---

4. Spec A — Tier 1 (NetworkX + python-igraph + NetworKit)

4.1 Algorithm catalog → endpoint → backend/function mapping

All rows use POST /v1/graphs with the given algorithm (+ backend) discriminator;
retrieval is always via GET /v1/graphs/{graphId}.

algorithm tag	Canonical family	backend options	Underlying function
erdos_renyi_gnp	Erdős–Rényi G(n,p)	networkx (default)	gnp_random_graph(n, p, seed, directed)
		igraph	Graph.Erdos_Renyi(n, p=p, directed=..., loops=...)
		networkit	ErdosRenyiGenerator(n, p, directed, selfLoops).generate()
erdos_renyi_gnm	Erdős–Rényi G(n,m)	networkx (default)	gnm_random_graph(n, m, seed, directed)
		igraph	Graph.Erdos_Renyi(n, m=m, directed=...)
watts_strogatz	Watts–Strogatz small-world	networkx (default)	watts_strogatz_graph(n, k, p, seed) / connected_watts_strogatz_graph(...) (variant sub-field)
		igraph	Graph.Watts_Strogatz(dim, size, nei, p)
		networkit	WattsStrogatzGenerator(n, nNeighbors, p).generate()
barabasi_albert	Barabási–Albert preferential attachment	networkx (default)	barabasi_albert_graph(n, m, seed, initial_graph) / dual_barabasi_albert_graph / extended_barabasi_albert_graph (variant sub-field)
		igraph	Graph.Barabasi(n, m, outpref, power, zero_appeal, directed)
		networkit	BarabasiAlbertGenerator(k, nMax, n0, batagelj).generate()
configuration_model	Degree-sequence / configuration model	networkx (default)	configuration_model(sequence) / havel_hakimi_graph(sequence) / expected_degree_graph(w) (variant sub-field)
		igraph	Graph.Degree_Sequence(out, in_, method)
		networkit	HavelHakimiGenerator(seq) / EdgeSwitchingMarkovChainGenerator(seq) (variant sub-field)
stochastic_block_model	Stochastic block model	networkx (default)	stochastic_block_model(sizes, p, directed, selfloops)
		igraph	Graph.SBM(n, pref_matrix, block_sizes, directed)
		networkit	StochasticBlockmodel(n, nBlocks, membership, affinity).generate()
random_regular	Random k-regular graph	networkx (default)	random_regular_graph(d, n, seed)
		igraph	Graph.K_Regular(n, k, directed, multiple)
random_geometric	Random geometric graph (RGG)	networkx (default)	random_geometric_graph(n, radius, dim, p, seed) / soft_random_geometric_graph (variant sub-field)
		igraph	Graph.GRG(n, radius, torus)
forest_fire	Forest-fire growth model	igraph (only)	Graph.Forest_Fire(n, fw_prob, bw_factor, ambs, directed)
kronecker_rmat	Kronecker / R-MAT	networkit (only)	RmatGenerator(scale, edgeFactor, a, b, c, d).generate()
classic_deterministic	Classic/deterministic graphs (complete, star, wheel, path, cycle, grid, hypercube, lattice)	networkx (default)	complete_graph, star_graph, wheel_graph, path_graph, cycle_graph, grid_graph, hypercube_graph (selected via shape sub-field)
		igraph	Graph.Full, Graph.Star, Graph.Wheel, Graph.Ring, Graph.Lattice, Graph.Hypercube
named_graph	Named / famous graphs	networkx (default)	petersen_graph(), karate_club_graph(), etc. (selected via name enum sub-field)
		igraph	Graph.Famous(name)
random_tree	Random tree generators	networkx (default)	random_labeled_tree(n, seed) / random_powerlaw_tree(n, gamma, seed) (variant sub-field)
		igraph	Graph.Tree_Game(n, method)
random_bipartite	Random bipartite graph	networkx (default)	bipartite.random_graph(n, m, p, seed, directed)
		igraph	Graph.Random_Bipartite(n1, n2, p, m, directed)
community_clustered	Community/clustered models	networkx (only)	planted_partition_graph / gaussian_random_partition_graph / LFR_benchmark_graph / relaxed_caveman_graph (variant sub-field)
		networkit	ClusteredRandomGraphGenerator(n, k, pIntra, pInter).generate() / LFRGenerator(n) (variant sub-field)
hyperbolic	Hyperbolic random graph	networkit (only)	HyperbolicGenerator(n, k, gamma, T).generate()
chung_lu	Chung–Lu / expected-degree graph	networkx (default)	expected_degree_graph(w, seed, selfloops)
		networkit	ChungLuGenerator(degreeSequence).generate()
static_fitness	Static fitness / power-law fitness model	igraph (only)	Graph.Static_Fitness(...) / Graph.Static_Power_Law(...) (variant sub-field)
growing_attachment	Growing random / establishment / preference (citation-style)	igraph (only)	Graph.Growing_Random, Graph.Establishment, Graph.Preference, Graph.Asymmetric_Preference, Graph.Recent_Degree (selected via variant sub-field)
kleinberg_small_world	Kleinberg navigable small-world	networkx (only)	navigable_small_world_graph(n, p, q, r, dim, seed)
powerlaw_cluster	Holme–Kim power-law cluster model	networkx (only)	powerlaw_cluster_graph(n, m, p, seed)
geometric_threshold	Waxman / geographic-threshold graph	networkx (only)	waxman_graph(...) / geographical_threshold_graph(...) (variant sub-field)
duplication_divergence	Duplication-divergence / internet-AS model	networkx (only)	random_internet_as_graph(n)

21 algorithm tags cover the 23 families of Tier 1 (some families are folded
together as a variant sub-discriminator inside one tag, e.g. classic_deterministic,
named_graph, community_clustered, growing_attachment, static_fitness,
geometric_threshold) — matching the "minimal number of distinct endpoints" goal
while still routing every underlying function 1:1 via (algorithm, backend, variant).

4.2 Example: multi-backend discriminated union for barabasi_albert

// backend = networkx
{
  "algorithm": "barabasi_albert",
  "backend": "networkx",
  "params": { "n": 500, "m": 3, "seed": 1, "variant": "standard" }
}

// backend = igraph (different parameter surface, same family)
{
  "algorithm": "barabasi_albert",
  "backend": "igraph",
  "params": { "n": 500, "m": 3, "power": 1.0, "zero_appeal": 1.0, "directed": false }
}

// backend = networkit (different parameter surface again)
{
  "algorithm": "barabasi_albert",
  "backend": "networkit",
  "params": { "k": 3, "nMax": 500, "n0": 4, "batagelj": true }
}

All three validate against the same top-level algorithm: barabasi_albert union
member but resolve to distinct params schemas via the nested backend
discriminator — this is what preserves full fidelity to each library's native
signature instead of forcing a lossy lowest-common-denominator parameter set.

---

5. Spec B — Tier 2 (Tier 1 + graph-tool)

Spec B reuses all 4 endpoints and all 21 tags from Spec A unchanged, and adds:

• 3 new algorithm tags exclusive to graph-tool (families not covered by Tier 1),
• graph-tool as an additional backend option on 2 existing tags where it offers a
  generalized/alternative implementation.

5.1 New tags (graph-tool exclusive)

algorithm tag	Canonical family	backend	Underlying function
knn_graph	k-nearest-neighbor graph	graph_tool (only)	generate_knn(points, k, dist)
triangulation	Triangulation / Delaunay graph	graph_tool (only)	triangulation(points, type, periodic)
price_network	Dedicated directed citation-growth (Price) model	graph_tool (only)	price_network(N, m, c, gamma, directed, seed_graph)

Because knn_graph and triangulation require spatial input, their params schema
includes a points: number[][] field (or a pointGenerator sub-object to have the
service sample random points), instead of a scalar n.

5.2 Backend extension on existing tags

algorithm tag	Added backend	Underlying function	Rationale
stochastic_block_model	graph_tool	generate_sbm(b, probs, out_degs, in_degs, directed) / generate_maxent_sbm(...) (variant sub-field)	graph-tool's SBM implementation supports degree-corrected and max-entropy variants not available in NetworkX/igraph/NetworKit.
configuration_model	graph_tool	random_graph(N, deg_sampler, directed, parallel_edges, self_loops, block_membership)	graph-tool's generic degree-sampler callback can reproduce configuration-model, Chung–Lu, and correlated-degree graphs with one generalized function; exposed here as an extra backend rather than a new tag to avoid duplicating the family.

5.3 Discovery endpoint delta

GET /v1/algorithms for Spec B returns the same 21 entries as Spec A plus the 3
new tags above, and the 2 extended backend enums — the discriminated union schema
is a strict superset, so any client written against Spec A remains valid against
Spec B (backward-compatible extension).

5.4 Deployment note

Because graph-tool has materially worse container/dependency ergonomics than the
Tier 1 libraries (see graph-generation-libraries-selection.md, §6), Spec B's
implementation should isolate the graph_tool backend in its own service/sidecar
behind the same POST /v1/graphs contract (e.g. routed internally by the API gateway
based on backend == "graph_tool"), rather than bundling it into the primary
NetworkX/igraph/NetworKit image. The public API surface is unaffected either way.

---

6. Summary

	Spec A (Tier 1)	Spec B (Tier 2)
Endpoints	4 (GET /v1/algorithms, POST /v1/graphs, GET /v1/graphs/{id}, DELETE /v1/graphs/{id})	Same 4
Backends	networkx, igraph, networkit	+ graph_tool
algorithm tags	21	24
Family coverage	23/26 (88%)	26/26 (100%)
Deployment	Single container	Primary container + isolated graph_tool sidecar

[lakshay6666]

Thanks for sharing the full Kilo-CLI log and design process. Having the exact API specs (especially the discriminated union structure for Spec A) gives me a perfect blueprint.

I am kicking off the ImplementationPhase now. As agreed, my first step is generating the Integration Test Suite for POST /v1/graphs (Spec A). I will generate the baseline, review and refine the routing/validation logic on my end to ensure we aren't testing upstream math, and will ping you once I have a solid, self-reviewed draft ready.