scripts/test.py

"""CPU-only verification test for Ramsey R(5,5) Simulated Annealing Search"""
print("Testing ramsey-r55-cuda...")

from itertools import combinations

def count_monochromatic_k5(n, adj_set):
    """Count monochromatic K_5 in 2-coloring. adj_set = set of edges colored red."""
    count = 0
    for combo in combinations(range(n), 5):
        edges = list(combinations(combo, 2))
        red = sum(1 for e in edges if e in adj_set)
        if red == 10 or red == 0:  # all red or all blue
            count += 1
    return count

# K_4: no K_5 subgraph possible, so count=0 for any coloring
print(f"  K_4 all-red: {count_monochromatic_k5(4, set(combinations(range(4),2)))} K_5 (expect 0)")
assert count_monochromatic_k5(4, set(combinations(range(4),2))) == 0

# K_5 all-red: exactly 1 monochromatic K_5
all_edges = set(combinations(range(5), 2))
print(f"  K_5 all-red: {count_monochromatic_k5(5, all_edges)} K_5 (expect 1)")
assert count_monochromatic_k5(5, all_edges) == 1

# K_6 all-red: C(6,5)=6 monochromatic K_5
all_edges_6 = set(combinations(range(6), 2))
print(f"  K_6 all-red: {count_monochromatic_k5(6, all_edges_6)} K_5 (expect 6)")
assert count_monochromatic_k5(6, all_edges_6) == 6

print(f"\n3/3 tests passed")