examples/sample_random_triangulations.py

#!/usr/bin/env python3
"""
Sample random triangulations using edge flips.

Two strategies depending on size:
1. Small n (≤15): Start with plantri enumeration, then flip
2. Large n (>15): Start with Delaunay of random points, then flip many times

The flip graph is not an expander, so for uniform sampling we need
approximately O(n^2) flips for mixing (diameter is O(n^2)).
"""

import sys
from pathlib import Path
sys.path.insert(0, str(Path(__file__).parent.parent))

import numpy as np
from scipy.spatial import Delaunay
from ideal_poly_volume_toolkit.rivin_delaunay import random_edge_flips
from ideal_poly_volume_toolkit.plantri_interface import find_plantri_executable
from ideal_poly_volume_toolkit.planar_utils import extract_faces_from_planar_embedding
import subprocess


def sample_small_triangulation(n_vertices: int, n_flips: int, min_connectivity: int = 3, seed: int = 42):
    """
    Sample a random triangulation for small n using plantri + flips.

    Args:
        n_vertices: Number of vertices (recommend ≤15)
        n_flips: Number of random edge flips
        min_connectivity: Minimum connectivity (3 or 4)
        seed: Random seed

    Returns:
        List of triangles
    """
    print(f"Sampling small triangulation (n={n_vertices})...")
    print(f"  Strategy: plantri enumeration → pick one → flip {n_flips} times")

    # Get all triangulations from plantri
    plantri = find_plantri_executable()
    if plantri is None:
        raise RuntimeError("plantri not found")

    args = [plantri, f'-pc{min_connectivity}', '-a', str(n_vertices)]
    result = subprocess.run(args, capture_output=True, text=True)

    # Parse triangulations
    triangulations = []
    for line in result.stdout.split('\n'):
        line = line.strip()
        if not line or line.startswith('>'):
            continue

        parts = line.split(maxsplit=1)
        if len(parts) != 2:
            continue

        n = int(parts[0])
        adj_str = parts[1]

        # Build adjacency dict
        adj = {}
        vertex_lists = adj_str.split(',')
        for v_idx, neighbor_str in enumerate(vertex_lists):
            neighbors = []
            for letter in neighbor_str:
                neighbor_idx = ord(letter) - ord('a')
                neighbors.append(neighbor_idx)
            adj[v_idx] = neighbors

        # Extract faces properly
        triangles = extract_faces_from_planar_embedding(n, adj)

        if triangles:
            triangulations.append(triangles)

    print(f"  Found {len(triangulations)} triangulations from plantri")

    # Pick one randomly
    np.random.seed(seed)
    idx = np.random.randint(len(triangulations))
    closed_tri = triangulations[idx]

    # Remove vertex 0 to get planar triangulation
    planar_tri = [tri for tri in closed_tri if 0 not in tri]

    print(f"  Selected triangulation #{idx}")
    print(f"  Planar triangulation: {len(planar_tri)} triangles")

    # Apply random flips
    if n_flips > 0:
        flipped = random_edge_flips(planar_tri, n_flips=n_flips, seed=seed)
        print(f"  Applied {n_flips} random edge flips")
        return flipped
    else:
        return planar_tri


def sample_large_triangulation(n_vertices: int, n_flips: int, seed: int = 42):
    """
    Sample a random triangulation for large n using Delaunay + many flips.

    For uniform sampling, use n_flips ≈ 10 * n_vertices^2 (conservative estimate).

    Args:
        n_vertices: Number of vertices
        n_flips: Number of random edge flips (recommend ≥ 10*n^2 for mixing)
        seed: Random seed

    Returns:
        List of triangles
    """
    print(f"Sampling large triangulation (n={n_vertices})...")
    print(f"  Strategy: Delaunay(random points) → flip {n_flips} times")

    # Generate random points
    np.random.seed(seed)
    points = np.random.rand(n_vertices, 2)

    # Compute Delaunay triangulation
    tri = Delaunay(points)
    initial_triangles = [tuple(simplex) for simplex in tri.simplices]

    print(f"  Generated {n_vertices} random points")
    print(f"  Delaunay triangulation: {len(initial_triangles)} triangles")

    # Apply many random flips for mixing
    if n_flips > 0:
        flipped = random_edge_flips(initial_triangles, n_flips=n_flips, seed=seed)
        print(f"  Applied {n_flips} random edge flips")

        # Note on mixing
        diameter_estimate = n_vertices * n_vertices
        if n_flips < 10 * diameter_estimate:
            print(f"  WARNING: For uniform sampling, recommend ≥{10*diameter_estimate} flips")
            print(f"           (flip graph diameter ≈ n^2 = {diameter_estimate})")

        return flipped
    else:
        return initial_triangles


def sample_triangulation(n_vertices: int, n_flips: int = None, min_connectivity: int = 3, seed: int = 42):
    """
    Sample a random triangulation using the appropriate strategy for the size.

    Args:
        n_vertices: Number of vertices
        n_flips: Number of flips (if None, use default based on size)
        min_connectivity: Minimum connectivity for small n (3 or 4)
        seed: Random seed

    Returns:
        List of triangles
    """
    # Choose strategy and default flips based on size
    if n_vertices <= 15:
        # Small: Use plantri + moderate flips
        if n_flips is None:
            n_flips = 100 * n_vertices  # Conservative
        return sample_small_triangulation(n_vertices, n_flips, min_connectivity, seed)
    else:
        # Large: Use Delaunay + many flips
        if n_flips is None:
            # For mixing, need ~O(n^2) flips (flip graph diameter)
            # Use 10*n^2 to be conservative
            n_flips = 10 * n_vertices * n_vertices
        return sample_large_triangulation(n_vertices, n_flips, seed)


if __name__ == '__main__':
    import argparse

    parser = argparse.ArgumentParser(description='Sample random triangulations')
    parser.add_argument('--n', type=int, required=True, help='Number of vertices')
    parser.add_argument('--flips', type=int, help='Number of edge flips (auto if not specified)')
    parser.add_argument('--connectivity', type=int, default=3, choices=[3, 4],
                       help='Min connectivity for small n (3 or 4)')
    parser.add_argument('--seed', type=int, default=42, help='Random seed')
    parser.add_argument('--samples', type=int, default=1, help='Number of samples to generate')

    args = parser.parse_args()

    print("="*70)
    print("RANDOM TRIANGULATION SAMPLING VIA EDGE FLIPS")
    print("="*70)
    print()

    for i in range(args.samples):
        if args.samples > 1:
            print(f"\nSample {i+1}/{args.samples}:")
            print("-"*70)

        seed = args.seed + i if args.samples > 1 else args.seed
        triangles = sample_triangulation(
            n_vertices=args.n,
            n_flips=args.flips,
            min_connectivity=args.connectivity,
            seed=seed
        )

        print(f"\nResult: {len(triangles)} triangles")

        # Show a few triangles
        print(f"Sample triangles: {triangles[:5]}")

        # Could test realizability here
        # from ideal_poly_volume_toolkit.rivin_delaunay import check_delaunay_realizability
        # result = check_delaunay_realizability(triangles, verbose=False)
        # print(f"Realizable: {result['realizable']}")

    print()
    print("="*70)