import numpy as np
import networkx as nx
import random
from typing import List, Tuple, Optional

class LowWeightMatchingSolver:
    """
    Implementation of the core logic for finding Low Weight Perfect Matchings.
    
    This class implements a heuristic search based on the 'local switching' 
    (edge-swapping) technique to find a perfect matching with sum 0.
    """

    def __init__(self, n: int):
        self.n = n
        self.num_vertices = 4 * n
        self.adj_matrix = np.zeros((self.num_vertices, self.num_vertices), dtype=int)

    def generate_balanced_labeling(self):
        """Generates a labeling sigma: E(K_{4n}) -> {-1, 1} such that sigma(E) = 0."""
        num_edges = (self.num_vertices * (self.num_vertices - 1)) // 2
        if num_edges % 2 != 0:
            raise ValueError("Total edges must be even to have a zero-sum labeling.")

        edges = []
        for i in range(self.num_vertices):
            for j in range(i + 1, self.num_vertices):
                edges.append((i, j))

        random.shuffle(edges)
        half = num_edges // 2
        
        for i, (u, v) in enumerate(edges):
            val = 1 if i < half else -1
            self.adj_matrix[u][v] = self.adj_matrix[v][u] = val
        
        print(f"Generated K_{self.num_vertices} with {half} (+1) and {half} (-1) edges.")

    def get_matching_weight(self, matching: List[Tuple[int, int]]) -> int:
        return sum(self.adj_matrix[u][v] for u, v in matching)

    def find_initial_perfect_matching(self) -> List[Tuple[int, int]]:
        nodes = list(range(self.num_vertices))
        random.shuffle(nodes)
        return [(nodes[i], nodes[i+1]) for i in range(0, self.num_vertices, 2)]

    def local_search_zero_sum(self, max_iter: int = 1000) -> Optional[List[Tuple[int, int]]]:
        """Implements the local switching strategy to reduce |sigma(M)|."""
        current_m = self.find_initial_perfect_matching()
        current_weight = self.get_matching_weight(current_m)
        
        for iteration in range(max_iter):
            if current_weight == 0:
                return current_m
            
            improved = False
            indices = list(range(len(current_m)))
            random.shuffle(indices)
            
            for i in range(len(indices)):
                for j in range(i + 1, len(indices)):
                    e1, e2 = current_m[indices[i]], current_m[indices[j]]
                    u1, u2 = e1
                    v1, v2 = e2
                    
                    # Try two possible swap configurations
                    swaps = [
                        ((u1, v1), (u2, v2)),
                        ((u1, v2), (u2, v1))
                    ]
                    
                    for s1, s2 in swaps:
                        w_new = (current_weight 
                                 - self.adj_matrix[u1][u2] - self.adj_matrix[v1][v2] 
                                 + self.adj_matrix[s1[0]][s1[1]] + self.adj_matrix[s2[0]][s2[1]])
                        
                        if abs(w_new) < abs(current_weight):
                            current_m[indices[i]], current_m[indices[j]] = s1, s2
                            current_weight = w_new
                            improved = True
                            break
                    if improved: break
                if improved: break
            
            if not improved:
                # Restart to escape local minima
                current_m = self.find_initial_perfect_matching()
                current_weight = self.get_matching_weight(current_m)

        return None

if __name__ == '__main__':
    N_VAL = 2 # K_8
    solver = LowWeightMatchingSolver(N_VAL)
    solver.generate_balanced_labeling()
    
    print(f"Searching for zero-sum perfect matching in K_{4*N_VAL}...")
    result = solver.local_search_zero_sum()
    
    if result:
        print(f"\nSuccess! Matching found: {result}")
        print(f"Final Weight: {solver.get_matching_weight(result)}")
    else:
        print("\nFailed to find a zero-sum matching.")