"""Graph topology optimization for S23DR 2026."""

import numpy as np
from typing import List, Tuple
from collections import defaultdict


def resolve_t_junctions(vertices, connections, threshold=0.3):
    if len(vertices) < 3 or len(connections) < 1: return vertices, connections
    edges_to_remove, edges_to_add = set(), set()
    for v_idx in range(len(vertices)):
        for e_idx, (a, b) in enumerate(connections):
            if v_idx == a or v_idx == b: continue
            p, p1, p2 = vertices[v_idx], vertices[a], vertices[b]
            edge_vec = p2 - p1; edge_len = np.linalg.norm(edge_vec)
            if edge_len < 1e-6: continue
            t = np.dot(p - p1, edge_vec / edge_len) / edge_len
            if 0.1 < t < 0.9:
                proj = p1 + t * edge_vec
                if np.linalg.norm(p - proj) < threshold:
                    edges_to_remove.add((min(a,b), max(a,b)))
                    edges_to_add.add((min(a, v_idx), max(a, v_idx)))
                    edges_to_add.add((min(v_idx, b), max(v_idx, b)))
    final = [(a, b) for a, b in connections if (min(a,b), max(a,b)) not in edges_to_remove]
    existing = set(tuple(sorted(c)) for c in final)
    for a, b in edges_to_add:
        if (a, b) not in existing: final.append((a, b)); existing.add((a, b))
    return vertices, final


def enforce_planarity(vertices, connections, face_vertex_groups=None):
    if face_vertex_groups is None: return vertices
    adjusted = vertices.copy()
    for group in face_vertex_groups:
        if len(group) < 3: continue
        pts = vertices[group]; centroid = pts.mean(axis=0)
        _, _, Vt = np.linalg.svd(pts - centroid); normal = Vt[-1]
        for local_idx, global_idx in enumerate(group):
            pt = vertices[global_idx]; adjusted[global_idx] = pt - np.dot(pt - centroid, normal) * normal
    return adjusted


def merge_close_vertices(vertices, connections, threshold=0.1):
    if len(vertices) < 2: return vertices, connections
    from scipy.spatial import KDTree
    tree = KDTree(vertices); parent = list(range(len(vertices)))
    def find(x):
        while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
        return x
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb: parent[ra] = rb
    for i, j in tree.query_pairs(r=threshold): union(i, j)
    groups = defaultdict(list)
    for i in range(len(vertices)): groups[find(i)].append(i)
    new_verts, old_to_new = [], {}
    for new_idx, (_, members) in enumerate(groups.items()):
        new_verts.append(vertices[members].mean(axis=0))
        for m in members: old_to_new[m] = new_idx
    new_verts = np.array(new_verts)
    new_conns = set()
    for a, b in connections:
        na, nb = old_to_new.get(a), old_to_new.get(b)
        if na is not None and nb is not None and na != nb: new_conns.add(tuple(sorted((na, nb))))
    return new_verts, list(new_conns)