Topology · cycle
Cycle Graph
A simple directed cycle of n nodes. TC is the complete graph on those nodes.
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 · edges10 · 10
Closure |TC|100
Closure / edges10.0×
A small instance from the generator the benchmark runs with n from 100 upwards.
Definition
Symbol
C_n
Edges
\{(i,i+1) \mid i \in 1..n-1\} \cup \{(n,1)\}
Generator
engine.data_generator.DataGenerator.generate_cycle_graphgenerate_db.py
def generate_cycle_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
"""Generate a cycle graph with n nodes."""
# E = {(i, i + 1) for i in range(1, n)} | {(n, 1)}
logging.info(f'Generating cycle graph for n={n}')
for i in range(1, n):
yield (i, i + 1)
yield (n, 1)