Topology · max_acyclic
Max Acyclic Graph
Maximum acyclic directed graph — all edges go from higher to lower numbered 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 · edges6 · 15
Closure |TC|15
Closure / edges1.0×
A small instance from the generator the benchmark runs with n from 100 upwards.
Definition
Symbol
T_n
Edges
\{(i,j) \mid i \in 1..n-1, j \in i+1..n\}
Generator
engine.data_generator.DataGenerator.generate_max_acyclic_graphgenerate_db.py
def generate_max_acyclic_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
"""Generate a max acyclic graph with n nodes."""
# self.E = {(a, b) for a in range(1, n + 1) for b in range(1, a) if a > b}
logging.info(f'Generating max acyclic graph for n={n}')
for a in range(1, n + 1):
for b in range(1, a):
if a > b:
yield (a, b)