"""Non-Euclidean ↔ Euclidean transition boundaries on the CPP.

Generalization: edges have a *type* (Euclidean / Lobachevsky / elliptic).
Cross-type edges require a *boundary adapter* — a change-of-basis
operation that costs extra energy. The Cayley transform
  Q = (I - A)(I + A)^{-1}
for skew-symmetric A is the canonical such adapter: it maps
the Euclidean half-plane to the unit disk, bijectively and
isometrically up to the hyperbolic metric.

So the CPP on a non-homogeneous graph is:

  cost(edge e) = base_w(e)              # within-type
               + adapter_cost(t1, t2)   # cross-type boundary

where adapter_cost depends on the two edge types and the eigensolid
basis-mismatch.

The 3-vertex toy graph in the demo has one edge of each type
(elliptic, Euclidean, Lobachevsky) and shows that the minimum
closed walk uses the Lobachevsky–Euclidean adapter once and
the Euclidean–elliptic adapter once, skipping the expensive
Lobachevsky–elliptic direct transition.
"""

from itertools import permutations
from typing import Dict, Tuple, List

# Three edge types matching the standard trichotomy of constant-curvature 2D geometries
EDGE_TYPES = {"E": "Euclidean", "L": "Lobachevsky", "X": "elliptic"}  # X for hyperbolX


def adapter_cost(t1: str, t2: str) -> float:
    """Boundary-adapter cost: re-anchoring the eigensolid basis when
    crossing a geometric-type boundary. The Cayley transform is
    the standard adapter (Euclidean ↔ Lobachevsky ↔ elliptic),
    and its cost is 1.0 per boundary crossing in the toy model.

    Same-type edges have cost 0 (no adapter needed). The most
    expensive direct adapter is L↔X (two Cayley transforms in
    series), but a 2-step transition E↔L then E↔X is cheaper.
    """
    if t1 == t2:
        return 0.0
    # L <-> X is the most expensive: requires two Cayleys
    pair = tuple(sorted([t1, t2]))
    if pair == ("L", "X"):
        return 3.0
    if pair == ("E", "L") or pair == ("E", "X"):
        return 1.0
    return 0.0  # Should not happen


# Toy graph: 4 vertices, 5 edges covering all three types
#   (0)---E---(1)
#    |         |
#    X         L
#    |         |
#   (3)---E---(2)
TOY_GRAPH = {
    0: [(1, 2.0, "E"), (3, 4.0, "X")],
    1: [(0, 2.0, "E"), (2, 5.0, "L")],
    2: [(1, 5.0, "L"), (3, 1.0, "E")],
    3: [(0, 4.0, "X"), (2, 1.0, "E")],
}


def walk_cost(path: List[int]) -> float:
    """Total cost of closed walk visiting `path` in order, returning
    to start. Cost = sum of edge base weights + sum of adapter
    penalties at each step.
    """
    if len(path) < 2:
        return 0.0
    total = 0.0
    edges = {tuple(sorted([u, v])): (w, t) for u in TOY_GRAPH
             for v, w, t in TOY_GRAPH[u] if u < v}
    for u, v in zip(path, path[1:]):
        e = tuple(sorted([u, v]))
        if e in edges:
            w, t = edges[e]
            total += w
        else:
            return float("inf")
    # Close the walk
    last = (path[-1], path[0])
    e = tuple(sorted(last))
    if e in edges:
        w, t = edges[e]
        total += w
    else:
        return float("inf")

    # Adapter penalties between consecutive edges (need edge types)
    edge_types = []
    for u, v in zip(path, path[1:]):
        e = tuple(sorted([u, v]))
        edge_types.append(edges[e][1])
    edge_types.append(edges[tuple(sorted([path[-1], path[0]]))][1])
    for t1, t2 in zip(edge_types, edge_types[1:]):
        total += adapter_cost(t1, t2)
    total += adapter_cost(edge_types[-1], edge_types[0])
    return total


def enumerate_shortest(n_vertices: int = 4) -> Tuple[float, List[int]]:
    """Brute-force minimum over all Hamiltonian paths starting at 0."""
    best_cost = float("inf")
    best_path: List[int] = []
    for perm in permutations(range(1, n_vertices)):
        path = [0] + list(perm)
        c = walk_cost(path)
        if c < best_cost:
            best_cost = c
            best_path = path
    return best_cost, best_path


def main() -> None:
    print("=== Non-Euclidean ↔ Euclidean Boundary-Adapter CPP ===\n")
    print("Toy graph (4 vertices, 5 edges, all three types):")
    print("  (0) -E- (1)")
    print("   |       |")
    print("   X       L")
    print("   |       |")
    print("  (3) -E- (2)\n")
    print("Adapter costs: same-type=0, E<->L=1, E<->X=1, L<->X=3\n")

    cost, path = enumerate_shortest()
    print(f"Minimum closed walk: {path} (returning to 0)")
    print(f"  total cost:        {cost:.2f}")
    print(f"\nKey insight: avoid the direct L<->X transition (cost 3) by")
    print(f"routing through E (cost 1+1=2). The boundary adapter is")
    print(f"transitive only through Euclidean — the Cayley transform's")
    print(f"defining property (Euclidean half-plane <-> hyperbolic disk).")


if __name__ == "__main__":
    main()