examples/debug_zero_spanning_trees.py

#!/usr/bin/env python3
"""
Debug the zero spanning tree cases - these shouldn't exist for 3-connected graphs!
"""

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

import json
import numpy as np
import networkx as nx
from ideal_poly_volume_toolkit.plantri_interface import find_plantri_executable
import subprocess

def get_triangulations_text(n_vertices: int, min_connectivity: int = 3) -> list:
    """Generate triangulations in ASCII format."""
    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)

    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

        # Convert adjacency to triangles
        triangles = []
        for v0 in range(n):
            for v1 in adj[v0]:
                if v1 <= v0:
                    continue
                for v2 in adj[v1]:
                    if v2 <= v1:
                        continue
                    if v2 in adj[v0]:
                        tri = tuple(sorted([v0, v1, v2]))
                        if tri not in triangles:
                            triangles.append(tri)

        if triangles:
            triangulations.append((n, adj, triangles))

    return triangulations


def remove_vertex_to_planar(triangles: list, vertex_to_remove: int) -> list:
    """Remove a vertex to create planar triangulation."""
    return [tri for tri in triangles if vertex_to_remove not in tri]


def triangles_to_graph(triangles: list) -> nx.Graph:
    """Convert triangle list to NetworkX graph."""
    G = nx.Graph()
    for tri in triangles:
        v0, v1, v2 = tri
        G.add_edge(v0, v1)
        G.add_edge(v1, v2)
        G.add_edge(v2, v0)
    return G


def count_spanning_trees_kirchhoff(G: nx.Graph) -> int:
    """Count spanning trees using Kirchhoff's matrix-tree theorem."""
    if len(G.nodes()) == 0:
        return 0
    if len(G.nodes()) == 1:
        return 1

    # Get Laplacian matrix
    L = nx.laplacian_matrix(G).toarray()

    # Remove first row and column (compute cofactor)
    L_reduced = L[1:, 1:]

    # Compute determinant (this is the number of spanning trees)
    det = np.linalg.det(L_reduced)

    # Round to nearest integer (should be exact integer, but floating point)
    return int(round(det))


def debug_zero_cases():
    """Debug cases with zero spanning trees."""

    print("="*70)
    print("DEBUGGING ZERO SPANNING TREE CASES")
    print("="*70)

    # Generate n=10 triangulations
    print("\nGenerating n=10 triangulations...")
    closed_tris = get_triangulations_text(10, min_connectivity=3)
    print(f"Generated {len(closed_tris)} closed triangulations")

    # Find first few zero cases
    zero_cases = []
    for idx, (n, adj, closed_tri) in enumerate(closed_tris):
        planar_tri = remove_vertex_to_planar(closed_tri, 0)
        G = triangles_to_graph(planar_tri)
        n_spanning = count_spanning_trees_kirchhoff(G)

        if n_spanning == 0:
            zero_cases.append((idx, n, adj, closed_tri, planar_tri, G))
            if len(zero_cases) >= 5:
                break

    print(f"\nFound {len(zero_cases)} zero-spanning-tree cases in first {idx+1} triangulations")

    # Analyze each zero case
    for case_num, (idx, n, adj, closed_tri, planar_tri, G) in enumerate(zero_cases, 1):
        print("\n" + "="*70)
        print(f"ZERO CASE #{case_num}: Triangulation index {idx}")
        print("="*70)

        # Original closed triangulation
        print(f"\nOriginal closed triangulation (n={n} vertices):")
        print(f"  Number of triangles: {len(closed_tri)}")
        print(f"  Triangles: {closed_tri[:10]}..." if len(closed_tri) > 10 else f"  Triangles: {closed_tri}")

        # Build graph from closed triangulation
        G_closed = nx.Graph()
        for v in range(n):
            for neighbor in adj[v]:
                G_closed.add_edge(v, neighbor)

        print(f"\nClosed graph properties:")
        print(f"  Nodes: {G_closed.number_of_nodes()}")
        print(f"  Edges: {G_closed.number_of_edges()}")
        print(f"  Connected: {nx.is_connected(G_closed)}")
        print(f"  Node connectivity: {nx.node_connectivity(G_closed)}")

        # Check degrees
        degrees = dict(G_closed.degree())
        print(f"  Degree sequence: {sorted(degrees.values())}")

        # Planar triangulation (after removing vertex 0)
        print(f"\nPlanar triangulation (after removing vertex 0):")
        print(f"  Number of triangles: {len(planar_tri)}")
        print(f"  Triangles: {planar_tri[:10]}..." if len(planar_tri) > 10 else f"  Triangles: {planar_tri}")

        # Planar graph
        print(f"\nPlanar graph properties:")
        print(f"  Nodes: {G.number_of_nodes()}")
        print(f"  Edges: {G.number_of_edges()}")
        print(f"  Connected: {nx.is_connected(G)}")

        if not nx.is_connected(G):
            components = list(nx.connected_components(G))
            print(f"  Number of components: {len(components)}")
            print(f"  Component sizes: {[len(c) for c in components]}")
            print(f"  Components: {components}")

        # Check which vertices appear in planar triangulation
        vertices_in_planar = set()
        for tri in planar_tri:
            vertices_in_planar.update(tri)

        print(f"\nVertices analysis:")
        print(f"  Vertices in planar triangulation: {sorted(vertices_in_planar)}")
        print(f"  Expected vertices (1 to {n-1}): {list(range(1, n))}")
        missing = set(range(1, n)) - vertices_in_planar
        if missing:
            print(f"  MISSING vertices: {sorted(missing)}")

        # Check Laplacian
        if G.number_of_nodes() > 0:
            L = nx.laplacian_matrix(G).toarray()
            print(f"\nLaplacian matrix rank: {np.linalg.matrix_rank(L)}")
            print(f"Expected rank for connected graph: {G.number_of_nodes() - 1}")

            eigenvalues = np.linalg.eigvalsh(L)
            print(f"Laplacian eigenvalues (sorted): {eigenvalues[:5]}...")
            print(f"Number of zero eigenvalues: {sum(abs(ev) < 1e-10 for ev in eigenvalues)}")


if __name__ == '__main__':
    debug_zero_cases()