BFS with Augmented State, in depth: product graphs, time phases, automata, parity and dominance pruning

The product graph

Let the base graph have vertices V, and let the extra information take values in a finite set X. The augmented graph has vertex set V × X. There is an edge from (u, x) to (v, y) when the move u to v is allowed in context x and leaves context y. The start is (s, x₀), and the goal is any (t, y) whose y is acceptable.

Two facts make this useful. First, every edge of the augmented graph still costs one move, so BFS on it finds the fewest moves, by the same argument as plain BFS: the queue holds states in non-decreasing distance order and each state is labelled the first time it is reached. Second, a path in the augmented graph projects to a walk in the base graph by dropping the x component. The walk may revisit a vertex, which is the point: a cell visited at t mod 3 = 0 and again at t mod 3 = 1 is two different states, and the second visit can be necessary.

The cost is at most |V| × |X| states and |E| × |X| edges, so the size of X decides feasibility.

The design rule follows: X must contain everything the rules consult about the past, and nothing else. Missing information makes BFS merge states that have different futures and gives wrong answers. Extra information, such as the step count, makes equivalent states look different, and the state space grows without bound.

Kinds of extra state

Most augmented-state problems use one of a few kinds of extra dimension:

Budget and set dimensions are covered in BFS on implicit graphs. The phase, automaton and parity kinds follow, and then the budget kind returns to show dominance pruning. When a budget is a real-valued resource rather than a small counter, the problem becomes constrained shortest path, which is NP-hard in general.

Worked example: a corridor with timed gates

Take this grid. S is the start and G the goal; # is a wall. A digit k is a gate that is closed at every time t with t mod 3 = k. Each step you move to a neighbouring cell or, optionally, wait in place, and the cell you are in at time t must be open at time t.

S.0.1.G
.#####.
.......

Because the gates repeat with period 3, the time only matters modulo 3, so the state is (row, col, t mod 3). With 16 open cells that is at most 48 states. BFS with the wait move:

from collections import deque

GRID = ["S.0.1.G", ".#####.", "......."]
P = 3
R, C = len(GRID), len(GRID[0])

def open_at(r, c, t):
    ch = GRID[r][c]
    if ch == "#":
        return False
    return not (ch.isdigit() and t % P == int(ch))

def shortest(start, goal, allow_wait=True):
    moves = [(1, 0), (-1, 0), (0, 1), (0, -1)] + ([(0, 0)] if allow_wait else [])
    first = (start[0], start[1], 0)
    dist = {first: 0}                       # key: (row, col, t mod P)
    q = deque([first])
    while q:
        r, c, ph = q.popleft()
        t = dist[(r, c, ph)]
        if (r, c) == goal:
            return t, len(dist)
        for dr, dc in moves:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and open_at(nr, nc, t + 1):
                nxt = (nr, nc, (t + 1) % P)
                if nxt not in dist:
                    dist[nxt] = t + 1
                    q.append(nxt)
    return None, len(dist)

Running it from (0, 0) to (0, 6) returns 7 moves, having discovered 39 of the 48 states. The route runs along the top row, reaches column 3 at t = 3, and waits once, because stepping onto gate 1 at t = 4 is forbidden (4 mod 3 = 1). It crosses at t = 5 and arrives at t = 7.

Without the wait move the answer is 8: the route steps down to (1, 0) and back to S, shifting the phase by 2, a revisit plain BFS cannot make. A common bug is to key the visited set by cell only. With waiting allowed, that version returns 10, the long detour along the bottom row, because the state (0, 3) at phase 1 is rejected as already visited when it was only visited at phase 0. The wrong answer looks plausible, which is why this bug survives review.

Rules about the path: product with an automaton

Some rules are about the sequence of edges used. Suppose every edge is red or blue and a valid path must alternate colours. Write the rule as a small deterministic finite automaton (DFA) over edge labels; the state becomes (vertex, DFA state), and an edge is allowed only if the DFA has a transition on its label. Any rule a regular expression can express works this way: 'at most two consecutive toll roads', 'use the ferry exactly once', 'end with a blue edge'.

from collections import deque

def bfs_with_dfa(adj, src, dst, delta, q0, accepting):
    """adj[u]: list of (v, label). delta: dict (dfa_state, label) -> dfa_state.
    Returns the fewest edges from src to dst along a label sequence the DFA accepts."""
    start = (src, q0)
    dist = {start: 0}
    queue = deque([start])
    while queue:
        u, qs = queue.popleft()
        if u == dst and qs in accepting:
            return dist[(u, qs)]
        for v, label in adj[u]:
            nq = delta.get((qs, label))
            if nq is None:
                continue                      # the rule forbids this edge here
            if (v, nq) not in dist:
                dist[(v, nq)] = dist[(u, qs)] + 1
                queue.append((v, nq))
    return -1

# Alternating colours: DFA states are "start", "R" (last edge red) and "B" (last edge blue).
ALT = {("start", "red"): "R", ("start", "blue"): "B", ("R", "blue"): "B", ("B", "red"): "R"}

For alternating colours, call it with delta=ALT, q0="start", accepting={"start", "R", "B"}. On a graph with edges 0→1 red, 1→2 red, 1→2 blue and 0→2 red, the shortest alternating path to 2 is the direct red edge, length 1; delete it and the answer is 2 via red then blue, never red then red. Here a DFA state is the 'last edge colour', the same thing as the 'last move direction' state used for turn-counting puzzles.

Parity layers and the double cover

The smallest automaton has two states, even and odd. Pairing each vertex with the parity of the steps taken builds the bipartite double cover: every edge u—v becomes (u, even)—(v, odd) and (u, odd)—(v, even). BFS on it answers questions plain BFS cannot: the shortest odd walk from s to t, or whether a closed walk of odd length through s exists. In an undirected graph, s lies on an odd closed walk exactly when (s, odd) is reachable from (s, even), which ties this to bipartite checking with BFS: a connected graph is bipartite exactly when no vertex can reach its own odd copy.

Parity also answers exact-length questions in undirected graphs: if the shortest walk from s to t with the parity of L has length at most L, a walk of length exactly L exists, padded by crossing one edge back and forth.

Dominance pruning for budgets

With a budget, having more left is never worse: in the wall-breaking problem (cell, r) can do everything (cell, r') can if r ≥ r'. With BFS order that allows a smaller visited structure: keep, per cell, the largest remaining budget seen, and discard a new state unless it beats it.

from collections import deque

def fewest_steps_with_breaks(grid, k):
    """grid: list of lists of 0 (open) / 1 (wall). Up to k walls may be broken."""
    n, m = len(grid), len(grid[0])
    best = [[-1] * m for _ in range(n)]       # most budget left on arrival so far
    best[0][0] = k
    q = deque([(0, 0, k, 0)])
    while q:
        r, c, rem, d = q.popleft()
        if (r, c) == (n - 1, m - 1):
            return d
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < m:
                nrem = rem - grid[nr][nc]
                if nrem > best[nr][nc]:        # dominance: only strictly more budget helps
                    best[nr][nc] = nrem
                    q.append((nr, nc, nrem, d + 1))
    return -1

Why is this safe? BFS assigns distances in non-decreasing order. When a state (cell, r') arrives and a state (cell, r) with r ≥ r' was pushed earlier, the earlier one has distance no greater and at least as much budget, so every continuation of the new state is available to the old one at no greater cost. The new state cannot lead to a better answer.

Measured on a 40 by 40 random grid with 512 walls, using the scratch model behind this page: with k = 1, both the full (cell, r) search and the dominance version find 116 steps; with k = 3, 80 steps; with k = 10, 78, the Manhattan lower bound. The time saving is modest: at k = 10 the dominance version pops 13,298 states against 14,672, about 9 percent fewer. The bigger win is memory: 1,600 integers instead of a 14,702-entry visited set.

The argument needs two conditions, and breaking either gives wrong answers. The search order must be by distance: under DFS, or with weighted edges processed in FIFO order, an early arrival can have a larger distance. And the extra dimension must be ordered by usefulness. A phase t mod P is not: arriving at phase 0 is neither better nor worse than phase 2, so phase states must all be kept.

Weights, sizing and failure modes

When moves stop costing the same. If some augmented edges are free, such as changing direction without moving, or breaking a wall costs more than stepping, the product graph has 0/1 or general weights. Use 0-1 BFS for 0/1 weights and Dijkstra otherwise, on the same augmented states. The state design does not change, only the queue.

Sizing. A 1,000 by 1,000 grid with period 12 is 12 million states: fine as a flat int32 array (48 MB), heavy as a Python dict of tuples. Encode (r, c, x) as (r * C + c) * |X| + x.

Failure modes.

• A visited set keyed on position only: plausible but wrong answers, as in the corridor example.
• Checking the goal on the wrong layer: if the goal requires an accepting DFA state or zero remaining items, test the full state, not the position.
• Phase computed from the wrong time: the cell entered at t + 1 must be open at t + 1, not at t. Off-by-one here shifts every gate.
• Dominance applied to an unordered dimension, or with a non-FIFO queue.
• A period that is really the least common multiple of several: gates with periods 4 and 6 need t mod 12.

What to do next

1. Run the corridor code and confirm 7 with waiting and 8 without; then change the visited key to (r, c) and watch it return 10.
2. For your next search problem, write down every fact the move rules consult about the past. That list is X.
3. Compute |V| × |X| and choose a dict or a flat array before coding.
4. If a rule is about the sequence of edges, write it as a DFA first; the code above handles any DFA.
5. If X is a budget, add dominance pruning, and keep a test that compares it with the full search on random small grids.
6. If any augmented move costs differently, switch the queue to 0-1 BFS or Dijkstra and keep the state.