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 1306 ms tgen 305 ms 0.23x 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 728 ms tgen 324 ms 0.44x n=10⁶, m=10⁶ (m=2n) jngen 1460 ms tgen 668 ms 0.46x 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 794 ms tgen 284 ms 0.36x n=10⁶, m=10⁶, elongation=100, spread=2 (distinct worst) jngen FAILURE tgen 560 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 243 ms tgen 61 ms 0.25x 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 650 ms tgen 275 ms 0.42x n=10⁶, m=10⁶ (DAG) jngen 690 ms tgen 366 ms 0.53x 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 690 ms tgen 366 ms 0.53x 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 772 ms tgen 638 ms 0.83x 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 376 ms tgen 243 ms 0.65x 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 802 ms tgen 659 ms 0.82x 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 1902 ms tgen 1225 ms 0.64x 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 102 ms tgen 81 ms 0.80x 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 152 ms tgen 142 ms 0.93x 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 712 ms tgen 346 ms 0.49x 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: 914 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: 1156 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 234 ms tgen 132 ms 0.57x 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: 967 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 3441 ms tgen 995 ms 0.29x 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.	(n=1800) jngen 2225 ms tgen 11 ms <0.01x n=1800, min=0, max=3×10⁶ (n=1e6) jngen TIMEOUT tgen 243 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: 1476 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: 697 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: 1145 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 466 ms tgen 568 ms 1.22x 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 05c6ea7, 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 1306 ms tgen 305 ms	0.23x
`graph::get_connected (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 2066 ms tgen 649 ms	0.31x
`graph::gen (m=n)`Docs	n=10⁶, m=10⁶	jngen 728 ms tgen 324 ms	0.44x
`graph::gen (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 1460 ms tgen 668 ms	0.46x
`graph::gen_skewed (m=n)`Docs	n=10⁶, m=10⁶, elongation=100, spread=2	jngen 794 ms tgen 284 ms	0.36x
`graph::gen_skewed (m=2n)`Docs	n=10⁶, m=2×10⁶, elongation=100, spread=6	jngen 1742 ms tgen 691 ms	0.40x
`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 560 ms	—
`tree::gen`Docs	n=10⁶	jngen 772 ms tgen 638 ms	0.83x
`tree::gen_skewed`Docs	n=10⁶, elongation=100	jngen 376 ms tgen 243 ms	0.65x
`tree::gen_kruskal`Docs	n=10⁶	jngen 802 ms tgen 659 ms	0.82x
`list<int>::gen (all_different)`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 1902 ms tgen 1225 ms	0.64x
`list<int>::gen`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 102 ms tgen 81 ms	0.80x
`geometry::random_convex_polygon (strict)`Docs	n=10⁶, min=0, max=10¹², strict=true	jngen 3441 ms tgen 995 ms	0.29x
`geometry::random_points_general_position (n=1800)`Docs	n=1800, min=0, max=3×10⁶	jngen 2225 ms tgen 11 ms	<0.01x
`geometry::random_points_general_position (n=1e6)`Docs	n=10⁶, min=0, max=3×10⁶	jngen TIMEOUT single run exceeded 5000 ms limit tgen 243 ms	—
`permutation::gen`Docs	n=5×10⁶	jngen 152 ms tgen 142 ms	0.93x
`graph::gen_bipartite`Docs	n1=10³, n2=10³, m=5×10⁵	jngen 243 ms tgen 61 ms	0.25x
`graph::gen (directed)`Docs	n=10⁶, m=10⁶	jngen 650 ms tgen 275 ms	0.42x
`graph::get_acyclic (DAG)`Docs	n=10⁶, m=10⁶	jngen 690 ms tgen 366 ms	0.53x
`str::gen`Docs	pattern=(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}, len=10⁷	jngen 466 ms tgen 568 ms	1.22x
`math::gen_partition_fixed_size_fast`Docs	n=10¹⁸, k=3×10⁶, part_left=0	jngen 712 ms tgen 346 ms	0.49x
`math::partition_elements`Docs	n=10⁶, k=10⁶	jngen 234 ms tgen 132 ms	0.57x

tgen-only timings

Operation	Parameters	tgen
`geometry::random_convex_polygon (non strict)`Docs	n=10⁶, min=0, max=3×10¹⁰, strict=false	967 ms
`geometry::random_simple_polygon`Docs	n=10⁶, min=0, max=3×10⁶, strict=false	1476 ms
`geometry::random_orthogonal_polygon`Docs	n=10⁶, min=0, max=3×10⁶, strict=false	697 ms
`geometry::random_simple_polygon_through_points`Docs	n=10⁶	1145 ms
`math::gen_partition`Docs	n=4.8×10⁶	1156 ms
`math::gen_partition_fixed_size`Docs	n=5×10⁷, k=10, part_left=0	914 ms