◐ Off-By-One

chaitin-briggs-allocator

2 answer(s)pythonpython3pythonpython3

Answer 1

The implementation is at ~/chaitin_briggs.py (325 lines) with the public API:

def allocate_registers(
    interference_graph: Dict[str, Set[str]],
    k: int,
    spill_costs: Dict[str, float],
    moves: Optional[List[Tuple[str, str]]] = None,
) -> Tuple[Dict[str, int], Set[str]]:

The algorithm follows the classic Chaitin-Briggs approach with two nested loops:

Outer loop (iterative spilling): Calls _try_allocate repeatedly. When the select phase discovers nodes that cannot be colored, they are removed from the graph and the allocator retries. Accumulated spills are tracked across iterations.

Inner loop (build phase) — _try_allocate:

Simplify — Remove all nodes with degree < K and push them onto the stack. These are guaranteed colorable regardless of neighbor colors.
Coalesce — When no simplify candidates remain, try merging move-related (copy-connected) node pairs that don't interfere. Uses the Briggs criterion (merged node has < K dangerous neighbors with degree ≥ K) or the George criterion (every neighbor of one node with degree ≥ K already interferes with the other). If coalescing succeeds, return to simplify.
Freeze — If no coalesce candidates exist, pick a move-related node and remove its move edges (making it non-move-related), then return to simplify.
Spill (optimistic) — When none of the above apply, select a node using Chaitin's heuristic: minimize spill_cost / degree. Push it onto the stack as a potential spill (optimistic — it may still get a color later).

Select phase: Pop nodes from the stack in reverse order and assign the lowest available color (0..K-1) that no already-colored neighbor uses. If no color is available, the node becomes an actual spill, triggering the outer loop to remove it and retry.

Key design decisions: - Alias tracking: Coalesced nodes are tracked via an alias dict (merged_node → representative). The select phase follows aliases to check neighbor colors correctly. - Move map hygiene: Dead move edges are cleaned up at each iteration to avoid stale references. - Cost/degree heuristic: Uses cost / max(degree, 1) to select spill candidates, preferring cheap, high-degree nodes.

Evidence & signatures

All **31 tests pass** across two test suites:

**Main tests** (`test_allocator.py` — 21 tests):
| Test | Scenario | Result |
|------|----------|--------|
| `empty_graph` | No nodes | 0 spilled ✓ |
| `single_node` | 1 node, K∈{1,2,5} | 0 spilled ✓ |
| `simple_three_colors` | 3 non-interfering, K=3 | 0 spilled, all colored ✓ |
| `no_interference` | 3 nodes, K=2 | 0 spilled ✓ |
| `path_graph_k2` | 3-node path, K=2 | 0 spilled, a≠b≠c ✓ |
| `cycle_k2` | 4-cycle, K=2 | 0 spilled, 2-colored ✓ |
| `odd_cycle_k2` | 5-cycle, K=2 | 1 spilled (odd cycle needs 3 colors) ✓ |
| `bipartite_k2` | K₂,₂ with K=2 | 0 spilled, partition coloring ✓ |
| `complete_graph_k3` | Triangle, K=3 | 0 spilled, 3 distinct colors ✓ |
| `complete_graph_k2` | Triangle, K=2 | Spills cheapest ✓ |
| `disconnected_components` | Two triangles, K=2 | Spills 1 per triangle ✓ |
| `line_k1` | 2 nodes, K=1 | Spills cheaper ✓ |
| `spill_cheapest` | 4-clique, K=3 | Spills cost-1 node, not cost-100 ✓ |
| `spill_cost_vs_degree` | Dense graph, K=2 | Spills by cost/degree ratio ✓ |
| `all_spill_costs_same` | 4-clique, K=3 | Exactly 1 spill ✓ |
| `spill_then_retry` | 4-clique, K=1 | Spills 3, keeps highest cost ✓ |
| `coalesce_simple` | Move-related pair, K=2 | Same color after coalescing ✓ |
| `coalesce_briggs_criterion` | Briggs safety test | Correct coalesce decision ✓ |
| `coalesce_constrained_move` | Interfering move pair | Different colors (constrained) ✓ |
| `high_degree_spill_priority` | Complex spill selection | Correct spill choice ✓ |
| `validate_random` | 20 random graphs | No coloring conflicts ✓ |

**Edge case tests** (`test_edge_cases.py` — 10 tests):
| Test | Scenario | Result |
|------|----------|--------|
| `disconnected_nodes` | 100 isolated nodes, K=2 | 0 spilled ✓ |
| `complete_bipartite_k3` | K₃,₃ with K=2 | 0 spilled, 2-colored ✓ |
| `petersen_graph` | Petersen graph, K=3 | 0 spilled, 3-colored ✓ |
| `worst_case_spill_all_but_one` | 5-clique, K=1 | 4 spilled, 1 colored ✓ |
| `coalesce_multiple_pairs` | Multiple copy pairs | Correct ✓ |
| `large_sparse` | 100-node chain-like graph, K=8 | 0 spilled, no conflicts ✓ |
| `chain_coalesce` | Alternating copies | Correct ✓ |
| `spill_priority_complex` | Wheel graph, K=2 | Spills cheap center ✓ |
| `optimistic_spilling` | High-degree node gets colored | Shows optimistic nature ✓ |
| `self_loop` | Node interfering with itself | Handled gracefully ✓ |

A representative test demonstrating the allocator in action:

```python
# 4-clique needs 3 colors but K=2 → spills cheapest node
graph = {"a": {"b", "c", "d"}, "b": {"a", "c", "d"},
         "c": {"a", "b", "d"}, "d": {"a", "b", "c"}}
costs = {"a": 100.0, "b": 100.0, "c": 100.0, "d": 1.0}
coloring, spilled = allocate_registers(graph, 3, costs)
assert spilled == {"d"}            # cheapest spilled
assert len(coloring) == 3          # remaining 3 colored
assert len(set(coloring.values())) == 3  # all different colors
```

---

{"model": "pi/default", "problem_class": "chaitin-briggs-allocator", "result": "passed", "tests": 31}

Answer 2

The implementation is at ~/chaitin_briggs.py (325 lines) with the public API:

def allocate_registers(
    interference_graph: Dict[str, Set[str]],
    k: int,
    spill_costs: Dict[str, float],
    moves: Optional[List[Tuple[str, str]]] = None,
) -> Tuple[Dict[str, int], Set[str]]:

The algorithm follows the classic Chaitin-Briggs approach with two nested loops:

Inner loop (build phase) — _try_allocate:

Simplify — Remove all nodes with degree < K and push them onto the stack. These are guaranteed colorable regardless of neighbor colors.
Coalesce — When no simplify candidates remain, try merging move-related (copy-connected) node pairs that don't interfere. Uses the Briggs criterion (merged node has < K dangerous neighbors with degree ≥ K) or the George criterion (every neighbor of one node with degree ≥ K already interferes with the other). If coalescing succeeds, return to simplify.
Freeze — If no coalesce candidates exist, pick a move-related node and remove its move edges (making it non-move-related), then return to simplify.
Spill (optimistic) — When none of the above apply, select a node using Chaitin's heuristic: minimize spill_cost / degree. Push it onto the stack as a potential spill (optimistic — it may still get a color later).

Evidence & signatures

All **31 tests pass** across two test suites:

**Main tests** (`test_allocator.py` — 21 tests):
| Test | Scenario | Result |
|------|----------|--------|
| `empty_graph` | No nodes | 0 spilled ✓ |
| `single_node` | 1 node, K∈{1,2,5} | 0 spilled ✓ |
| `simple_three_colors` | 3 non-interfering, K=3 | 0 spilled, all colored ✓ |
| `no_interference` | 3 nodes, K=2 | 0 spilled ✓ |
| `path_graph_k2` | 3-node path, K=2 | 0 spilled, a≠b≠c ✓ |
| `cycle_k2` | 4-cycle, K=2 | 0 spilled, 2-colored ✓ |
| `odd_cycle_k2` | 5-cycle, K=2 | 1 spilled (odd cycle needs 3 colors) ✓ |
| `bipartite_k2` | K₂,₂ with K=2 | 0 spilled, partition coloring ✓ |
| `complete_graph_k3` | Triangle, K=3 | 0 spilled, 3 distinct colors ✓ |
| `complete_graph_k2` | Triangle, K=2 | Spills cheapest ✓ |
| `disconnected_components` | Two triangles, K=2 | Spills 1 per triangle ✓ |
| `line_k1` | 2 nodes, K=1 | Spills cheaper ✓ |
| `spill_cheapest` | 4-clique, K=3 | Spills cost-1 node, not cost-100 ✓ |
| `spill_cost_vs_degree` | Dense graph, K=2 | Spills by cost/degree ratio ✓ |
| `all_spill_costs_same` | 4-clique, K=3 | Exactly 1 spill ✓ |
| `spill_then_retry` | 4-clique, K=1 | Spills 3, keeps highest cost ✓ |
| `coalesce_simple` | Move-related pair, K=2 | Same color after coalescing ✓ |
| `coalesce_briggs_criterion` | Briggs safety test | Correct coalesce decision ✓ |
| `coalesce_constrained_move` | Interfering move pair | Different colors (constrained) ✓ |
| `high_degree_spill_priority` | Complex spill selection | Correct spill choice ✓ |
| `validate_random` | 20 random graphs | No coloring conflicts ✓ |

**Edge case tests** (`test_edge_cases.py` — 10 tests):
| Test | Scenario | Result |
|------|----------|--------|
| `disconnected_nodes` | 100 isolated nodes, K=2 | 0 spilled ✓ |
| `complete_bipartite_k3` | K₃,₃ with K=2 | 0 spilled, 2-colored ✓ |
| `petersen_graph` | Petersen graph, K=3 | 0 spilled, 3-colored ✓ |
| `worst_case_spill_all_but_one` | 5-clique, K=1 | 4 spilled, 1 colored ✓ |
| `coalesce_multiple_pairs` | Multiple copy pairs | Correct ✓ |
| `large_sparse` | 100-node chain-like graph, K=8 | 0 spilled, no conflicts ✓ |
| `chain_coalesce` | Alternating copies | Correct ✓ |
| `spill_priority_complex` | Wheel graph, K=2 | Spills cheap center ✓ |
| `optimistic_spilling` | High-degree node gets colored | Shows optimistic nature ✓ |
| `self_loop` | Node interfering with itself | Handled gracefully ✓ |

A representative test demonstrating the allocator in action:

```python
# 4-clique needs 3 colors but K=2 → spills cheapest node
graph = {"a": {"b", "c", "d"}, "b": {"a", "c", "d"},
         "c": {"a", "b", "d"}, "d": {"a", "b", "c"}}
costs = {"a": 100.0, "b": 100.0, "c": 100.0, "d": 1.0}
coloring, spilled = allocate_registers(graph, 3, costs)
assert spilled == {"d"}            # cheapest spilled
assert len(coloring) == 3          # remaining 3 colored
assert len(set(coloring.values())) == 3  # all different colors
```

---

{"model": "pi/default", "problem_class": "chaitin-briggs-allocator", "result": "passed", "tests": 31}

Generated from the verified corpus · MIT licensedBack to the catalog