tgen vs jngen — Feature Comparison

Comparison of non-trivial generation operations. See benchmarks below.

Graphs

Operation	jngen	tgen	Notes	Benchmark
Connected random graph	Yes `Graph::random(n, m).connected()` DocsNon‑uniform*O(n + m log n) time*	Yes `graph(n, m).get_connected()` DocsNon‑uniformO(n + m log^2 n) expected time	Same Prüfer tree + rejection edge add. Neither uniform over all connected labeled graphs.	jngen 1832 ms tgen 405 ms 0.22x n=10⁶, m=10⁶
Random graph with fixed n, m	Yes `Graph::random(n, m)` DocsNon‑uniform*O(n + m log n) time*	Yes `graph(n, m).gen()` DocsUniformO(n + m log^2 n) expected time	Rejection sampling with constraint machinery.	(m=n) jngen 901 ms tgen 425 ms 0.47x n=10⁶, m=10⁶ (m=2n) jngen 2287 ms tgen 971 ms 0.42x n=10⁶, m=2×10⁶
Skewed / stretched connected graph	Yes `Graph::randomStretched(n, m, elongation, spread)` DocsNon‑uniformO(n + m log n) time* if spread is *O(1)Omega(n m)** time* otherwise	Yes `graph::gen_skewed(n, m, elongation, spread)` DocsNon‑uniformO(n + m log n) time if spread is O(1)O(n log n + m log^2 n) expected time otherwise	Same high-level algorithm: skewed spanning tree, then ancestor-biased extra edges. Extra edges reject duplicates; jngen resets an attempt counter on success and throws after MAX_ATTEMPTS=1000 consecutive failures, while tgen uses its unique generation framework. For large spread, tgen uses binary lifting; jngen uses trivial parent-by-parent lifting.	(m=n) jngen 1204 ms tgen 426 ms 0.35x n=10⁶, m=10⁶, elongation=100, spread=2 (distinct worst) jngen FAILURE tgen 779 ms n=10⁶, m=2n-3, elongation=100, spread=2
Bipartite graph (random / complete)	Yes `Graph::randomBipartite(n1, n2, m), completeBipartite(n1, n2)` DocsUniform**O(n1 + n2 + m log(n1 n2))** time*	Yes `graph::gen_bipartite(n1, n2, m), K(n1, n2)` DocsUniformO(n1 + n2 + m log(n1 * n2)) expected time	tgen: Distinct edge-index sampling. jngen: Rejection sampling. Both support optional connected generation. jngen also supports allowMulti; tgen stores simple graphs only.	jngen 526 ms tgen 102 ms 0.19x n1=10³, n2=10³, m=5×10⁵
Directed random graph	Yes `Graph::random(n, m).directed().g()` DocsNon‑uniform*O(n + m log n) time*	Yes `graph(n, m, directed=true).gen()` DocsNon‑uniformO(n + m log^2 n) expected time	tgen: Rejection with constraint machinery. jngen: Rejection sampling.	(directed) jngen 1274 ms tgen 485 ms 0.38x n=10⁶, m=10⁶ (DAG) jngen 1488 ms tgen 629 ms 0.42x n=10⁶, m=10⁶
Directed acyclic random graph (DAG)	Yes `Graph::random(n, m).directed().acyclic().g()` DocsNon‑uniform*O(n + m log n) time*	Yes `graph(n, m, directed=true).get_acyclic()` DocsNon‑uniformO(n + m log^2 n) expected time	tgen: Randomized Kahn topological order, then rejection sampling. jngen: Rejection sampling + acyclic shuffle-orient.	jngen 1488 ms tgen 629 ms 0.42x n=10⁶, m=10⁶

* Uniformity or complexity is undocumented and is inferred by code inspection.

Trees

Operation	jngen	tgen	Notes	Benchmark
Random labeled tree	Yes `Tree::random(n)` DocsUniformO(n) time*	Yes `tree(n).gen()` DocsUniformO(n) time	Prüfer sequence.	jngen 1234 ms tgen 900 ms 0.73x n=10⁶
Skewed tree (wnext / Prim-like)	Yes `Tree::randomPrim(n, elongation)` DocsNon‑uniform*O(n) time*	Yes `tree::gen_skewed(n, elongation)` DocsNon‑uniformO(n) time	Uses parent(i) = wnext(i, elongation).	jngen 577 ms tgen 324 ms 0.56x n=10⁶, elongation=100
Random tree (Kruskal-like)	Yes `Tree::randomKruskal(n)` DocsNon‑uniform*O(n log(n) alpha(n)) expected time*	Yes `tree::gen_kruskal(n)` DocsNon‑uniformO(n log(n) alpha(n)) expected time	Kruskal-like edge add until connected.	jngen 1315 ms tgen 941 ms 0.72x n=10⁶

* Uniformity or complexity is undocumented and is inferred by code inspection.

Lists and sequences

Operation	jngen	tgen	Notes	Benchmark
Distinct values in range	Yes `Array::randomUnique(k, lo, hi)` DocsUniform*O(k log k) expected time*	Yes `list<int>(k, lo, hi).all_different().gen()` DocsUniformO(k log k) time	tgen: Fisher–Yates + forbidden-value map. jngen: Hash-set rejection.	jngen 2806 ms tgen 2227 ms 0.79x n=5×10⁶, value_left=1, value_right=10×10⁶
Random integer list (duplicates allowed)	Yes `Array::random(k, lo, hi)` DocsUniform*O(k) time*	Yes `list<int>(k, lo, hi).gen()` DocsUniformO(k) time	Independent uniform draws.	jngen 162 ms tgen 132 ms 0.81x n=5×10⁶, value_left=1, value_right=10×10⁶
Uniform random permutation	Yes `Array::id(n).shuffled()` DocsUniform*O(n) time*	Yes `permutation(n).gen()` DocsUniformO(n) time	—	jngen 314 ms tgen 303 ms 0.97x n=5×10⁶
Declarative constraints (palindrome, cycles)	No	Yes `list/str/permutation/pair with .palindrome(), .cycles()...` Docs	Constraint-based uniform sampling.	—

* Uniformity or complexity is undocumented and is inferred by code inspection.

Math

Operation	jngen	tgen	Notes	Benchmark
Partition into k parts (fast)	Yes `rndm.partition(n, numParts, minSize, maxSize)` DocsNon‑uniform*O(k log k) time*	Yes `math::gen_partition_fixed_size_fast(n, k, part_left, part_right)` DocsNon‑uniformO(k log k) time	Same high-level approach: random delimiters, sort, gap recovery. jngen also sorts parts in non-increasing order and shuffles; tgen fast omits reordering. Not uniformly random; Optimized for speed.	jngen 982 ms tgen 506 ms 0.51x n=10¹⁸, k=3×10⁶, part_left=0
Uniform ordered partition into k parts (composition)	No	Yes `math::gen_partition_fixed_size(n, k, part_left, part_right)` DocsUniformO(n) time if unbounded part_rightO(n·k) time otherwise	Stars-and-bars or DP in log space. Uniform over ordered compositions.	tgen: 1305 ms n=5×10⁷, k=10, part_left=0
Uniform ordered partition, variable number of parts	No	Yes `math::gen_partition(n, part_left, part_right)` DocsUniformO(n) time	DP in log space.	tgen: 2102 ms n=4.8×10⁶
Random integer with congruence constraints	No	Yes `math::gen_congruent(l, r, rems, mods)` DocsUniformO(\|mods\| + log r) time	—	—
Partition array into k groups	Yes `rndm.partition(elements, numParts, minSize, maxSize)` DocsNon‑uniform*O(n + k log k) time*	Yes `math::partition_elements(elements, k, min_size, max_size)` DocsUniform if unbounded max_sizeNon‑uniform otherwiseO(n) time if unbounded max_sizeO(n + k log k) time otherwise	—	jngen 455 ms tgen 183 ms 0.40x n=10⁶, k=10⁶

* Uniformity or complexity is undocumented and is inferred by code inspection.

Geometry

Operation	jngen	tgen	Notes	Benchmark
Random convex polygon (non strict)	No	Yes `geometry::random_convex_polygon(n, min, max, strict=false)` DocsNon‑uniformO(n log n) time	Valtr lattice walk; Collinear boundary vertices allowed.	tgen: 2213 ms n=10⁶, min=0, max=3×10¹⁰, strict=false
Random convex polygon	Yes `rndg.convexPolygon(n, min, max)` DocsNon‑uniform*O(n log n) time*	Yes `geometry::random_convex_polygon(n, min, max, strict=true)` DocsNon‑uniformO(n log n) time	Both sample extra vertices then subsample to n: jngen hull of 10n ellipse points; tgen Valtr walk on n + max(100, n/1000) grid lines, collinear removal, subsample.	jngen TIMEOUT tgen 2702 ms n=10⁶, min=0, max=10¹², strict=true
Points in general position (no three collinear)	Yes `rndg.pointsInGeneralPosition(n, min, max)` DocsNon‑uniform*O(n² log n) expected time*	Yes `geometry::random_points_general_position(n, min, max)` DocsNon‑uniformO(n) time	tgen: Algebraic construction over F_p. jngen: Rejection until no collinearity.	jngen TIMEOUT tgen 496 ms n=10⁶, min=0, max=3×10⁶
Random simple polygon	No	Yes `geometry::random_simple_polygon(n, min, max, strict=false)` DocsNon‑uniformO(n log n) expected time	Default (strict=false) samples distinct grid points, then polygonizes; Strict=true uses general-position vertices (v1.0.0 behavior). Collinear triples may appear on the boundary when strict=false.	tgen: 3172 ms n=10⁶, min=0, max=3×10⁶, strict=false
Random orthogonal polygon	No	Yes `geometry::random_orthogonal_polygon(n, min, max, strict=false)` DocsNon‑uniformO(n²) time for n <= 1000O(n) time otherwise	Axis-aligned simple polygon grown by local boundary edits. With strict=true, every vertex is a 90-degree turn.	tgen: 51 ms n=10⁶, min=0, max=3×10⁶, strict=false
Simple polygon through given points	No	Yes `geometry::random_simple_polygon_through_points(pts)` DocsNon‑uniformO(n log n) expected time	Randomized divide-and-conquer Hamiltonian path.	tgen: 2303 ms n=10⁶

* Uniformity or complexity is undocumented and is inferred by code inspection.

Strings

Operation	jngen	tgen	Notes	Benchmark
Regex / pattern strings	Yes `rnds.random("(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}")` DocsNon‑uniformO(output length) time*	Yes `str("(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}").gen()` DocsUniformO(output length) expected time	Same testlib-style regex syntax. tgen samples uniformly among matches (documented); jngen explicitly does not: e.g. Rnd.next("[1-9][0-9]{1,2}") does not yield uniform digit strings. Benchmark measures generation throughput at fixed pattern length, not distributional fairness.	jngen 798 ms tgen 788 ms 0.99x pattern=(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}, len=10⁷

* Uniformity or complexity is undocumented and is inferred by code inspection.

Hacks

Operation	jngen	tgen	Notes	Benchmark
Polynomial hash collision strings (signed mod)	Yes `rnds.antiHash({{mod, base}, ...}, alphabet, len)` DocsO(√mod log mod) time*	Yes `hack::polynomial_hash(alphabet, base, mod)` DocsO(√mod log mod) time	Deterministic collision construction, not random sampling. Both generate colliding strings for rolling hash.	—
Polynomial hash collision (unsigned / power-of-two mod)	No	Yes `hack::unsigned_polynomial_hash()` DocsO(1) time	Thue–Morse construction.	—
std::unordered_set collision inputs	Yes `rnda.antiUnorderedSet(n, maxLoadFactor, reserve)` UndocumentedO(n) time*	Yes `hack::std_unordered(size)` DocsO(n) time	Overlap in purpose; Different APIs and compiler support. jngen: GCC 4.x only; Tuned load factor/reserve. tgen: GCC multiplier-based collision keys.	—
std::set collision strings	No	Yes `hack::string_set_worst_case(size)` DocsO(size log size) time	Distinct strings with equal std::set ordering keys.	—
Max-flow worst case (Dinitz / Edmonds-Karp)	No	Yes `hack::dinitz_worst_case(k, l)` DocsO(l + k²) time	Zadeh network.	—
Mo's algorithm worst-case queries	No	Yes `hack::mo_worst_case(n, q)` DocsO(n log n + q) time	—	—
SPFA TLE graph	No	Yes `hack::spfa(n)` DocsO(n) time	Graph with n vertices and edges; Forces Ω(n²) relaxations.	—
Stale-heap Dijkstra bug graph	No	Yes `hack::stale_heap_dijkstra_bug(n)` DocsO(n) time	Forces Ω(n²) without stale-heap skip.	—
Non-strict relaxation Dijkstra bug graph	No	Yes `hack::non_strict_relaxation_dijkstra_bug(n)` DocsO(n) time	Forces Ω(2^{n/2}) with non-strict relaxation.	—
MT19937 XOR-hash collision mask	No	Yes `hack::mt19937_xor_hash<T>()` DocsO(1) time	Bitmask for int or long long outputs.	—
Segment-tree-beats worst case	No	Yes `hack::segment_tree_beats_worst_case(k, q)` DocsO(n + q) time	—	—
Rotating calipers bug polygon	No	Yes `hack::naive_rotating_calipers_max_dist_bug()` DocsO(1) time	Fixed 6-vertex convex polygon.	—

* Uniformity or complexity is undocumented and is inferred by code inspection.

Other

Operation	jngen	tgen	Notes	Benchmark
Distinct generation	No	Yes `distinct<Func, Args>` DocsUniformO(T log k + log^2 k) time amortized expected per call when generating k values and next() runs in O(T)	Composable constraint machinery.	—
Testlib integration	Yes `registerGen, global rnd/rndm/rndg, testlib-compatible patterns` Docs	No	jngen is built on testlib. tgen is a standalone header with register_gen and its own constraint API.	—
Built-in SVG visualization	Yes `Drawer d ; d.polygon(...) ; d.dumpSvg("out.svg")` Docs	No	jngen Drawer for points, segments, circles, polygons; Outputs SVG.	—
Accelerated build guide	Yes `JNGEN_DECLARE_ONLY (precompiled static library)` Docs	No	Compile jngen.h once into a static lib; Link with JNGEN_DECLARE_ONLY for faster rebuilds.	—

Samples

Geometry

Operation	jngen	tgen
Random convex polygon	Yes `rndg.convexPolygon(n, min, max)` DocsNon‑uniform*O(n log n) time* n=80, min=0, max=1000 n=15000, min=0, max=3×10⁹	Yes `geometry::random_convex_polygon(n, min, max, strict=true)` DocsNon‑uniformO(n log n) time n=80, min=0, max=1000 n=15000, min=0, max=3×10⁹
Points in general position (no three collinear)	Yes `rndg.pointsInGeneralPosition(n, min, max)` DocsNon‑uniform*O(n² log n) expected time* n=2000, min=0, max=3×10⁶	Yes `geometry::random_points_general_position(n, min, max)` DocsNon‑uniformO(n) time n=2000, min=0, max=3×10⁶
Random simple polygon	No	Yes `geometry::random_simple_polygon(n, min, max, strict=false)` DocsNon‑uniformO(n log n) expected time n=80, min=0, max=1000
Random orthogonal polygon	No	Yes `geometry::random_orthogonal_polygon(n, min, max, strict=false)` DocsNon‑uniformO(n²) time for n <= 1000 n=80, min=0, max=1000
Simple polygon through given points	No	Yes `geometry::random_simple_polygon_through_points(pts)` DocsNon‑uniformO(n log n) expected time 10×10 input grid, min=0, max=1000

* Uniformity or complexity is undocumented and is inferred by code inspection.

tgen vs jngen — Benchmarks

Compiler: GCC 15.2.0
Flags: -std=c++17 -O2
Host: bruno-inspiron14
Vendor commits: tgen e598767, jngen 8d1e33b

Timing comparison

Bar length is relative to the slower library per operation (jngen vs tgen). Ratio is colored by the faster library.

Operation	Parameters	Comparison	Ratio (tgen/jngen)
`graph::get_connected (m=n)`Docs	n=10⁶, m=10⁶	jngen 1832 ms tgen 405 ms	0.22x
`graph::get_connected (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 2841 ms tgen 1073 ms	0.38x
`graph::gen (m=n)`Docs	n=10⁶, m=10⁶	jngen 901 ms tgen 425 ms	0.47x
`graph::gen (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 2287 ms tgen 971 ms	0.42x
`graph::gen_skewed (m=n)`Docs	n=10⁶, m=10⁶, elongation=100, spread=2	jngen 1204 ms tgen 426 ms	0.35x
`graph::gen_skewed (m=2n)`Docs	n=10⁶, m=2×10⁶, elongation=100, spread=6	jngen 2620 ms tgen 1072 ms	0.41x
`graph::gen_skewed (distinct worst)`Docs	n=10⁶, m=2n-3, elongation=100, spread=2	jngen FAILURE Cannot generate random stretched graph with parameters 1000000, 1999997, 100, 2 (assertion `false' failed). tgen 779 ms	—
`tree::gen`Docs	n=10⁶	jngen 1234 ms tgen 900 ms	0.73x
`tree::gen_skewed`Docs	n=10⁶, elongation=100	jngen 577 ms tgen 324 ms	0.56x
`tree::gen_kruskal`Docs	n=10⁶	jngen 1315 ms tgen 941 ms	0.72x
`list<int>::gen (all_different)`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 2806 ms tgen 2227 ms	0.79x
`list<int>::gen`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 162 ms tgen 132 ms	0.81x
`geometry::random_convex_polygon (strict)`Docs	n=10⁶, min=0, max=10¹², strict=true	jngen TIMEOUT single run exceeded 5000 ms limit tgen 2702 ms	—
`geometry::random_points_general_position`Docs	n=10⁶, min=0, max=3×10⁶	jngen TIMEOUT single run exceeded 5000 ms limit tgen 496 ms	—
`permutation::gen`Docs	n=5×10⁶	jngen 314 ms tgen 303 ms	0.97x
`graph::gen_bipartite`Docs	n1=10³, n2=10³, m=5×10⁵	jngen 526 ms tgen 102 ms	0.19x
`graph::gen (directed)`Docs	n=10⁶, m=10⁶	jngen 1274 ms tgen 485 ms	0.38x
`graph::get_acyclic (DAG)`Docs	n=10⁶, m=10⁶	jngen 1488 ms tgen 629 ms	0.42x
`str::gen`Docs	pattern=(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}, len=10⁷	jngen 798 ms tgen 788 ms	0.99x
`math::gen_partition_fixed_size_fast`Docs	n=10¹⁸, k=3×10⁶, part_left=0	jngen 982 ms tgen 506 ms	0.51x
`math::partition_elements`Docs	n=10⁶, k=10⁶	jngen 455 ms tgen 183 ms	0.40x

tgen-only timings

Operation	Parameters	tgen
`geometry::random_convex_polygon (non strict)`Docs	n=10⁶, min=0, max=3×10¹⁰, strict=false	2213 ms
`geometry::random_simple_polygon`Docs	n=10⁶, min=0, max=3×10⁶, strict=false	3172 ms
`geometry::random_orthogonal_polygon`Docs	n=10⁶, min=0, max=3×10⁶, strict=false	51 ms
`geometry::random_simple_polygon_through_points`Docs	n=10⁶	2303 ms
`math::gen_partition`Docs	n=4.8×10⁶	2102 ms
`math::gen_partition_fixed_size`Docs	n=5×10⁷, k=10, part_left=0	1305 ms