Topology · cycle_with_shortcuts
Cycle with Shortcuts
A cycle graph augmented with k shortcut edges per node for faster reachability.
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 · edges12 · 120
Closure |TC|144
Closure / edges1.2×
A small instance from the generator the benchmark runs with n from 100 upwards.
Definition
Symbol
S_{n,k}
Edges
\{(i, (i-1 + t \cdot n/(k+1)) \bmod n + 1) \mid i \in 1..n, t \in 1..k\} \cup C_n
Generator
engine.data_generator.DataGenerator.generate_cycle_with_shortcuts_graphgenerate_db.py
def generate_cycle_with_shortcuts_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
"""Generate a cycle with shortcuts graph with n nodes."""
logging.info(f'Generating cycle with shortcuts graph for n={n}')
skip = n // (self.k + 1) # Number of vertices to skip for shortcuts
for i in range(1, n):
yield (i, i + 1)
yield (n, 1)
for i in range(1, n + 1):
for t in range(1, self.k + 1):
yield (i, 1 + (i - 1 + skip * t) % n)