Read-only copy. This public copy of trans-bench is read-only: it shows the published campaigns. Clone the repository to run benchmarks or to edit systems. github.com/Sirneij/trans-bench, branch verified-rerun-2026
Configure

Topologies

The graph families the suite generates. Each drawing is a small instance from the same generator the benchmark uses; open one to change its size and see what the transitive closure adds.

Add a topology New experiment

Barabási-Albert (Scale-Free)BA_{n,m}

Real-world scale-free model via preferential attachment (m=2). Mathematically guarantees that smaller graphs are subsets of larger ones, preventing zig-zagging curves.

22 nodes40 edges|TC| 74

Binary TreeB_h

A complete binary tree of depth floor(log2(n)). Edges go parent to child.

15 nodes14 edges|TC| 34

Complete GraphK_n

Every node has edges to every other node. Transitive closure is the graph itself.

6 nodes36 edges|TC| 36

Cycle GraphC_n

A simple directed cycle of n nodes. TC is the complete graph on those nodes.

10 nodes10 edges|TC| 100

Cycle with ShortcutsS_{n,k}

A cycle graph augmented with k shortcut edges per node for faster reachability.

12 nodes120 edges|TC| 144

Grid GraphG_{n imes n}

A 2D grid graph of sqrt(n) x sqrt(n) nodes with right and down edges.

16 nodes24 edges|TC| 84

Max Acyclic GraphT_n

Maximum acyclic directed graph — all edges go from higher to lower numbered nodes.

6 nodes15 edges|TC| 15

Multi-Path GraphM_{n,k}

k parallel paths, stress-testing multi-path transitive closure.

40 nodes30 edges|TC| 60

Path GraphP_n

A simple directed path 1→2→3→...→n. TC is a dense upper-triangular graph.

7 nodes6 edges|TC| 21

Reverse Binary TreeV_h

Binary tree with edges reversed — children point to parent.

15 nodes14 edges|TC| 34

Scale-Free DirectedSF_n

NetworkX scale_free_graph — directed scale-free graph with configurable alpha/beta/gamma.

22 nodes29 edges|TC| 55

Star GraphS_n

All nodes point to a single hub node. TC is sparse.

9 nodes8 edges|TC| 8

W GraphW_{n,k}

Each node in the first half connects to k nodes in the second half (circular).

10 nodes25 edges|TC| 25

X GraphX_{n,k}

All n nodes point to a hub, which fans out to k leaf nodes.

16 nodes15 edges|TC| 65

Y GraphY_{n,k}

All n nodes converge to a central hub, then fan out along a k-length path.

15 nodes14 edges|TC| 95