Skip to main content

Module gac

csp_solver::solver

Module gac 

Source
Expand description

Unified GAC all-different core (Régin 1994), sentinel-generic and incremental.

One propagator body serves both the plain all-different constraint and the sentinel-aware “all-different-except” variant. The distinction is a single Option<&D::Value> parameter:

  • sentinel = None — plain all-different. Every unassigned variable must be matched to a distinct value.
  • sentinel = Some(s) — the value s is an “escape valve” any number of variables may take; it is removed from the value side of the bipartite graph, and variables whose domain has narrowed to {s} drop out of the variable side.

The Régin pipeline (Hopcroft-Karp maximum matching → residual graph → Tarjan SCC → prune edges outside every maximum matching) is identical for both; only participant/value collection and free-vertex reachability seeding branch on the sentinel. The graph primitives live in [matching].

§Incrementality

Two costs the from-scratch predecessor paid on every revise() are gone:

  1. Per-call heap allocation. All working buffers (adjacency, matching, residual graph, Tarjan stacks) live in a thread-local [GacScratch] that is cleared — not freed — between calls. The value universe is the sole per-call Vec<V> the generic bound cannot pool.
  2. Cold Hopcroft-Karp. With a stable constraint id, the previous maximum matching is cached per constraint and warm-starts the next call: cached edges still valid against the live domains seed match_u/match_v, and Hopcroft-Karp only augments from the vertices left free — O(E) repair rather than O(E·√V) reconstruction. The cache is a pure hint: every seeded edge is validated against live domains, so a stale cache costs extra augmentation, never correctness.

Constants§

GAC_MIN_PARTICIPANTS
Below this live-participant count, GAC finds nothing singleton removal misses, so the caller’s cheaper path is preferred. Exposed so constraints gate consistently.

Statics§

GAC_IN_ALLDIFF_ENABLED
A/B measurement toggle for the plain AllDifferent GAC path (Sudoku, Futoshiki). Default on; flipping it off reverts AllDifferent to singleton-removal-only so the pruning-strength delta can be measured.

Functions§

next_gac_id
Allocate a fresh, process-unique constraint id for matching-cache keying.
propagate_gac_core
Run Régin GAC on scope, sentinel-generic and incremental.