Topology · grid

Grid Graph

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

Benchmark this topology

Evaluation

Linear · T ∘ E–iterations (left / right recursion)

Doubling · T ∘ T–iterations (double recursion)

1 / 1

iteration 1new pairs per iteration

Nodes · edges16 · 24

Closure |TC|84

Closure / edges3.5×

Size n16

A small instance from the generator the benchmark runs with n from 100 upwards.

Definition

Symbol

G_{n imes n}

Edges

\{(j, j+1) \mid i \in 1..n, j \in (i-1)n+1..in-1\} \cup \{(j, j+n) \mid i \in 1..n-1, j \in (i-1)n+1..in\}

Generator

engine.data_generator.DataGenerator.generate_grid_graph

generate_db.py

    def generate_grid_graph(self, n: int) -> Generator[tuple[int, int], None, None]:
        """Generate a grid graph with n nodes."""
        logging.info(f'Generating grid graph for n={n}')

        n = int(math.sqrt(n))

        # Generate edges (j, j+1) for rows
        for i in range(1, n + 1):
            for j in range((i - 1) * n + 1, (i - 1) * n + n):
                yield (j, j + 1)

        # Generate edges (j, j+n) for columns
        for i in range(1, n):
            for j in range((i - 1) * n + 1, (i - 1) * n + n + 1):
                yield (j, j + n)