Topology · y
Y Graph
All n nodes converge to a central hub, then fan out along a k-length path.
Evaluation
Linear · T ∘ E–iterations (left / right recursion)
Doubling · T ∘ T–iterations (double recursion)
iteration 1new pairs per iteration
Point at a node (or tab to the drawing and use the arrow keys) to see every node it reaches, wave by wave. Those pairs are its rows of the closure.
Nodes · edges15 · 14
Closure |TC|95
Closure / edges6.8×
A small instance from the generator the benchmark runs with n from 100 upwards.
Definition
Symbol
Y_{n,k}
Edges
\{(i, n+1) \mid i \in 1..n\} \cup \{(i, i+1) \mid i \in n+1..n+k-1\}
Generator
engine.data_generator.DataGenerator.generate_y_graphgenerate_db.py
def generate_y_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
"""Generate a Y graph with n nodes."""
logging.info(f'Generating Y graph for n={n}')
for i in range(1, n + 1):
yield (i, n + 1)
for i in range(n + 2, n + self.k + 1):
yield (i - 1, i)