constraint-theory-core 2.1.0

Deterministic manifold snapping with O(log n) KD-tree indexing — maps continuous vectors to exact Pythagorean coordinates
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#!/usr/bin/env python3
"""Rigidity Percolation Simulation — validates Laman threshold = 12
Run on Forgemaster's RTX 4050. No GPU required for this version (CPU reference).

Generates random geometric graphs and measures:
- Rigidity (Laman condition check)
- Coordination success rate
- Phase transition at k=12
"""
import random, json, time
from collections import defaultdict

def generate_random_geometric_graph(n_agents, k_neighbors, radius=1.0):
    """Generate a random geometric graph with n agents, each tracking ~k neighbors."""
    positions = [(random.random() * radius, random.random() * radius) for _ in range(n_agents)]
    edges = set()
    for i in range(n_agents):
        dists = [(j, (positions[i][0]-positions[j][0])**2 + (positions[i][1]-positions[j][1])**2) 
                 for j in range(n_agents) if j != i]
        dists.sort(key=lambda x: x[1])
        for j, _ in dists[:k_neighbors]:
            edges.add((min(i,j), max(i,j)))
    return edges

def check_laman_condition(n, edges):
    """Check if graph satisfies Laman's condition for minimal rigidity.
    For 2D: |E| = 2n - 3 and every subset of n' vertices spans <= 2n' - 3 edges.
    Simplified check: just verify edge count and connectivity."""
    if len(edges) < 2 * n - 3:
        return False
    # Union-find for connectivity
    parent = list(range(n))
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    def union(a, b): parent[find(a)] = find(b)
    for a, b in edges: union(a, b)
    roots = set(find(i) for i in range(n))
    return len(roots) == 1  # Connected

def simulate_coordination(n_agents, k_neighbors, steps=100):
    """Simulate swarm coordination with k-neighbor constraint.
    Returns success rate (agents maintaining formation)."""
    success = 0
    for _ in range(steps):
        # Each agent tries to match average neighbor position
        positions = [random.gauss(0, 1) for _ in range(n_agents)]
        neighbors = defaultdict(list)
        for i in range(n_agents):
            others = list(range(n_agents))
            random.shuffle(others)
            neighbors[i] = others[:k_neighbors]
        
        # Simulate convergence
        converged = True
        target = sum(positions) / n_agents
        for i in range(n_agents):
            local_avg = sum(positions[j] for j in neighbors[i]) / len(neighbors[i])
            if abs(local_avg - target) > 0.5:
                converged = False
                break
        if converged:
            success += 1
    return success / steps

# Run experiments
print("Rigidity Percolation + Coordination Simulation")
print("="*50)
print(f"{'k':>4} {'Rigid%':>8} {'Coord%':>8} {'Edges':>8}")
print("-"*50)

results = []
for k in range(4, 21):
    n = 128
    trials = 100
    rigid_count = sum(1 for _ in range(trials) if check_laman_condition(n, generate_random_geometric_graph(n, k)))
    coord_rate = simulate_coordination(n, k, steps=50)
    edge_count = n * k // 2
    rigid_pct = rigid_count / trials * 100
    coord_pct = coord_rate * 100
    marker = " ◄◄◄ PHASE TRANSITION" if 10 <= k <= 14 and abs(rigid_pct - 50) < 30 else ""
    print(f"{k:>4} {rigid_pct:>7.1f}% {coord_pct:>7.1f}% {edge_count:>8}{marker}")
    results.append({"k": k, "rigid_pct": rigid_pct, "coord_pct": coord_pct})

# Save results
with open("rigidity_results.json", "w") as f:
    json.dump(results, f, indent=2)
print("\nResults saved to rigidity_results.json")
print("\nExpected: sharp phase transition at k=12")