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 n) time	Same Prüfer tree + rejection edge add. Neither uniform over all connected labeled graphs.	jngen 1366 ms tgen 315 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 n) time	Rejection sampling with constraint machinery.	(m=n) jngen 628 ms tgen 294 ms 0.47x n=10⁶, m=10⁶ (m=2n) jngen 1404 ms tgen 658 ms 0.47x 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) 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 757 ms tgen 253 ms 0.33x n=10⁶, m=10⁶, elongation=100, spread=2 (distinct worst) jngen FAILURE tgen 507 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)) time	tgen: Distinct edge-index sampling. jngen: Rejection sampling. Both support optional connected generation. jngen also supports allowMulti; tgen stores simple graphs only.	jngen 214 ms tgen 61 ms 0.29x 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 n) time	tgen: Rejection with constraint machinery. jngen: Rejection sampling.	(directed) jngen 688 ms tgen 294 ms 0.43x n=10⁶, m=10⁶ (DAG) jngen 689 ms tgen 394 ms 0.57x 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 n) time	tgen: Randomized Kahn topological order, then rejection sampling. jngen: Rejection sampling + acyclic shuffle-orient.	jngen 689 ms tgen 394 ms 0.57x 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 781 ms tgen 660 ms 0.84x 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 314 ms tgen 213 ms 0.68x 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 779 ms tgen 678 ms 0.87x 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 1967 ms tgen 981 ms 0.50x 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 92 ms tgen 62 ms 0.67x 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 142 ms tgen 152 ms 1.07x 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 659 ms tgen 335 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: 822 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: 1054 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 203 ms tgen 122 ms 0.60x n=10⁶, k=10⁶

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

Geometry

Operation	jngen	tgen	Notes	Benchmark
Random convex polygon	Yes `rndg.convexPolygon(n, min, max)` DocsNon‑uniform*O(n log n) time*	Yes `geometry::random_convex_polygon(n, min, max)` DocsNon‑uniformO(n log n) time	tgen: Valtr construction filling bounding box. jngen: Hull of 10n ellipse points, subsample n. Different shape distributions. Benchmark uses the same n and max for both (wide max so jngen hull subsampling succeeds at n=1e6).	jngen 2830 ms tgen 953 ms 0.34x n=10⁶, 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*	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 2010 ms tgen 11 ms <0.01x n=1800, min=0, max=3×10⁶ (n=1e6) jngen TIMEOUT tgen 203 ms n=10⁶, min=0, max=3×10⁶
Random simple polygon	No	Yes `geometry::random_simple_polygon(n, min, max)` DocsNon‑uniformO(n log n) expected time	Points + polygonization.	tgen: 1247 ms n=10⁶, min=0, max=3×10⁶
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: 1094 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 404 ms tgen 516 ms 1.28x 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(k log n) time for k distinct values	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)` 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)` DocsNon‑uniformO(n log n) expected time 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 dae9a10, 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 1366 ms tgen 315 ms	0.23x
`graph::get_connected (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 2036 ms tgen 678 ms	0.33x
`graph::gen (m=n)`Docs	n=10⁶, m=10⁶	jngen 628 ms tgen 294 ms	0.47x
`graph::gen (m=2n)`Docs	n=10⁶, m=2×10⁶	jngen 1404 ms tgen 658 ms	0.47x
`graph::gen_skewed (m=n)`Docs	n=10⁶, m=10⁶, elongation=100, spread=2	jngen 757 ms tgen 253 ms	0.33x
`graph::gen_skewed (m=2n)`Docs	n=10⁶, m=2×10⁶, elongation=100, spread=6	jngen 1836 ms tgen 617 ms	0.34x
`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 507 ms	—
`tree::gen`Docs	n=10⁶	jngen 781 ms tgen 660 ms	0.84x
`tree::gen_skewed`Docs	n=10⁶, elongation=100	jngen 314 ms tgen 213 ms	0.68x
`tree::gen_kruskal`Docs	n=10⁶	jngen 779 ms tgen 678 ms	0.87x
`list<int>::gen (all_different)`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 1967 ms tgen 981 ms	0.50x
`list<int>::gen`Docs	n=5×10⁶, value_left=1, value_right=10×10⁶	jngen 92 ms tgen 62 ms	0.67x
`geometry::random_convex_polygon`Docs	n=10⁶, min=0, max=3×10¹⁰	jngen 2830 ms tgen 953 ms	0.34x
`geometry::random_points_general_position (n=1800)`Docs	n=1800, min=0, max=3×10⁶	jngen 2010 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 203 ms	—
`permutation::gen`Docs	n=5×10⁶	jngen 142 ms tgen 152 ms	1.07x
`graph::gen_bipartite`Docs	n1=10³, n2=10³, m=5×10⁵	jngen 214 ms tgen 61 ms	0.29x
`graph::gen (directed)`Docs	n=10⁶, m=10⁶	jngen 688 ms tgen 294 ms	0.43x
`graph::get_acyclic (DAG)`Docs	n=10⁶, m=10⁶	jngen 689 ms tgen 394 ms	0.57x
`str::gen`Docs	pattern=(([1-9][0-9]{3}\|[A-F]{4})\|(ab\|cd){2}){r}, len=10⁷	jngen 404 ms tgen 516 ms	1.28x
`math::gen_partition_fixed_size_fast`Docs	n=10¹⁸, k=3×10⁶, part_left=0	jngen 659 ms tgen 335 ms	0.51x
`math::partition_elements`Docs	n=10⁶, k=10⁶	jngen 203 ms tgen 122 ms	0.60x

tgen-only timings

Operation	Parameters	tgen
`geometry::random_simple_polygon`Docs	n=10⁶, min=0, max=3×10⁶	1247 ms
`geometry::random_simple_polygon_through_points`Docs	n=10⁶	1094 ms
`math::gen_partition`Docs	n=4.8×10⁶	1054 ms
`math::gen_partition_fixed_size`Docs	n=5×10⁷, k=10, part_left=0	822 ms