{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6a53722b",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "# Wild edges in edge-colored graphs\n",
    "\n",
    "**PI**: Aleyah Dawkins\n",
    "\n",
    "Consider a graph of your favorite city with vertices representing locations and edges representing routes between them. Suppose each route can currently only support one mode of transportation (corresponding to an edge color). Planners want citizens to have access to every location using entirely their preferred mode of transportation.\n",
    "\n",
    "We call an edge wild if any mode of transportation can use it (i.e., it belongs to every color class). We consider the minimum number of wild edges required to connect the graph for every color simultaneously.\n",
    "\n",
    "**Formal Definition**\n",
    "\n",
    "Let $G$ be a connected graph with an edge-coloring $c: E(G) \\to [\\ell]$. A subset of edges $W \\subseteq E(G)$ is a wild set if, for every color $i \\in [\\ell]$, the spanning subgraph $G_i^W$ with edge set $E_i \\cup W$ is connected.\n",
    "\n",
    "The wild number of an edge-colored graph, denoted $\\mathrm{wld}(G)$, is the minimum size of a wild set.\n",
    "\n",
    "**Theoretical Bounds**\n",
    "\n",
    "Let $\\kappa(G_i)$ denote the number of connected components in the monochromatic subgraph of color $i$.\n",
    "- Component Lower Bound (CLB): $\\max_{i} (\\kappa(G_i)) - 1 \\le \\mathrm{wld}(G)$\n",
    "- Component Upper Bound (CUB): $\\mathrm{wld}(G) \\le \\sum_{i=1}^{\\ell} \\kappa(G_i) - \\ell$\n",
    "- Ceiling Lower Bound: $\\lceil \\frac{\\text{CUB}}{\\ell - 1} \\rceil \\le \\mathrm{wld}(G)$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea72a9c6",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## Imports & Setup"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "id": "e06279db",
   "metadata": {},
   "outputs": [
    {
     "ename": "ModuleNotFoundError",
     "evalue": "No module named 'sage'",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mModuleNotFoundError\u001b[0m                       Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[17], line 6\u001b[0m\n\u001b[1;32m      4\u001b[0m \u001b[38;5;28;01mimport\u001b[39;00m \u001b[38;5;21;01mrandom\u001b[39;00m\n\u001b[1;32m      5\u001b[0m \u001b[38;5;28;01mimport\u001b[39;00m \u001b[38;5;21;01mmath\u001b[39;00m\n\u001b[0;32m----> 6\u001b[0m \u001b[38;5;28;01mfrom\u001b[39;00m \u001b[38;5;21;01msage\u001b[39;00m\u001b[38;5;21;01m.\u001b[39;00m\u001b[38;5;21;01mall\u001b[39;00m \u001b[38;5;28;01mimport\u001b[39;00m \u001b[38;5;241m*\u001b[39m\n\u001b[1;32m      8\u001b[0m random\u001b[38;5;241m.\u001b[39mseed(\u001b[38;5;28mint\u001b[39m(\u001b[38;5;241m42\u001b[39m))\n",
      "\u001b[0;31mModuleNotFoundError\u001b[0m: No module named 'sage'"
     ]
    }
   ],
   "source": [
    "from typing import Any, List, Tuple, Set, Dict, Optional, Generator\n",
    "from itertools import combinations, cycle\n",
    "from matplotlib.colors import is_color_like\n",
    "import random\n",
    "import math\n",
    "from sage.all import *\n",
    "\n",
    "random.seed(int(42))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d3709fa5",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## WildGraph Visualizer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "cf0c8375",
   "metadata": {},
   "outputs": [],
   "source": [
    "class WildGraphVisualizer:\n",
    "    \"\"\"\n",
    "    Mixin class handling all rendering and plotting logic.\n",
    "    Separates the display backend from the core combinatorial math.\n",
    "    \"\"\"\n",
    "\n",
    "    @staticmethod\n",
    "    def get_color_palette(num_colors: int) -> List[str]:\n",
    "        \"\"\"\n",
    "        Centralized DRY color palette generator.\n",
    "        Uses distinct named colors, scaling to continuous hex codes if needed.\n",
    "        \"\"\"\n",
    "        named_colors = [\n",
    "            'red', 'blue', 'green', 'purple', 'orange', 'brown', 'pink', 'gray',\n",
    "            'olive', 'cyan', 'magenta', 'teal', 'navy', 'maroon', 'gold',\n",
    "            'indigo', 'salmon', 'plum', 'turquoise', 'coral'\n",
    "        ]\n",
    "        if num_colors <= len(named_colors):\n",
    "            return named_colors[:num_colors]\n",
    "\n",
    "        import matplotlib.cm as cm\n",
    "        import matplotlib.colors as mcolors\n",
    "        return [mcolors.to_hex(cm.hsv(i / num_colors)) for i in range(num_colors)]\n",
    "\n",
    "    def display_color(self, color: Any) -> str:\n",
    "        \"\"\"Fallback helper to ensure valid color compliance.\"\"\"\n",
    "        return color if isinstance(color, str) and is_color_like(color) else 'gray'\n",
    "\n",
    "    def _render_layered_plot(self, edge_list: List[Tuple[Any, Any, Any]], wild_edges: List[Tuple[Any, ...]], title: Optional[str] = None) -> Any:\n",
    "        \"\"\"\n",
    "        DRY Core Engine: Generates layout-pinned, multi-layered plots.\n",
    "        Overlays solid color classes with dashed wild sets in their original colors.\n",
    "        \"\"\"\n",
    "        wild_normalized = self.normalize_edges(wild_edges)\n",
    "\n",
    "        # Layer 1: Spanning Subgraph of Base Color Classes (Solid lines)\n",
    "        G_colored = Graph()\n",
    "        G_colored.add_vertices(self.vertices)\n",
    "        solid_colors = {} # eg., {'red': [(0, 1), (2, 3)], 'blue' : [(1, 4)]}\n",
    "\n",
    "        for u, v, label in edge_list:\n",
    "            if self.normalize_edge((u, v)) not in wild_normalized: # if wild, don't draw solid\n",
    "                G_colored.add_edge(u, v)\n",
    "                color_str = self.display_color(label)\n",
    "                solid_colors.setdefault(color_str, []).append((u, v))\n",
    "\n",
    "        p_colored = G_colored.plot(\n",
    "            pos=self.pos, edge_colors=solid_colors, edge_style='solid',\n",
    "            vertex_size=300, vertex_labels=True, title=title, axes=False\n",
    "        )\n",
    "\n",
    "        # Layer 2: Wild Edge Overlay (Thick Dashed lines matching their true color)\n",
    "        if wild_normalized:\n",
    "            G_wild = Graph()\n",
    "            G_wild.add_vertices(self.vertices)\n",
    "            dashed_colors = {}\n",
    "\n",
    "            for edge in wild_edges:\n",
    "                # Handle both (u, v) and (u, v, c) tuple formats robustly\n",
    "                if len(edge) >= 3:\n",
    "                    u, v, label = edge[0], edge[1], edge[2]\n",
    "                else:\n",
    "                    u, v = edge[0], edge[1]\n",
    "                    label = next((c for x, y, c in self.edges if self.normalize_edge((u, v)) == self.normalize_edge((x, y))), 'black') # extract color, default black\n",
    "\n",
    "                G_wild.add_edge(u, v)\n",
    "                color_str = self.display_color(label)\n",
    "                dashed_colors.setdefault(color_str, []).append((u, v))\n",
    "\n",
    "            p_wild = G_wild.plot(\n",
    "                pos=self.pos, edge_colors=dashed_colors, edge_style='dashed',\n",
    "                edge_thickness=4, vertex_size=0, vertex_labels=False, axes=False\n",
    "            )\n",
    "            return p_colored + p_wild\n",
    "\n",
    "        return p_colored\n",
    "\n",
    "    # --- Public API Methods ---\n",
    "\n",
    "    def plot_colored(self, title: Optional[str] = None, wild_edges: Optional[List[Tuple[Any, ...]]] = None, show: bool = False) -> Optional[Any]:\n",
    "        wild_edges = [] if wild_edges == None else wild_edges\n",
    "        p = self._render_layered_plot(self.edges, wild_edges, title=title)\n",
    "        if show: p.show()\n",
    "        else: return p\n",
    "\n",
    "    def plot_monochromatic(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None, title: Optional[str] = None, show: bool = False) -> Optional[Any]:\n",
    "        color_edges = [e for e in self.edges if e[2] == color]\n",
    "        p = self._render_layered_plot(color_edges, wild_edges or [], title=title)\n",
    "        if show: p.show()\n",
    "        else: return p\n",
    "\n",
    "    def plot_wild_topology_grid(self, wild_edges: List[Tuple[Any, ...]], cols: int = 4) -> None:\n",
    "        plots = []\n",
    "        plots.append(self._render_layered_plot([], wild_edges, title=\"Base Components\\n(No Matching)\"))\n",
    "\n",
    "        for color in sorted(self.colors):\n",
    "            color_edges = [e for e in self.edges if e[2] == color]\n",
    "\n",
    "            W_color = self.make_graph(wild_edges)\n",
    "            for u, v, _ in color_edges:\n",
    "                W_color.add_edge(u, v)\n",
    "\n",
    "            comp_count = W_color.connected_components_number()\n",
    "            status = \"Connected!\" if comp_count == 1 else f\"Disconnected ({comp_count})\"\n",
    "\n",
    "            plots.append(self._render_layered_plot(color_edges, wild_edges, title=f\"Matching: {color}\\nResult: {status}\"))\n",
    "\n",
    "        rows = math.ceil(len(plots) / cols)\n",
    "        graphics_array(plots, ncols=cols).show(figsize=(cols * 5, rows * 5))\n",
    "\n",
    "    def plot_wild_set(self, wild_edges: List[Tuple[Any, ...]]) -> None:\n",
    "        p = self._render_layered_plot([], wild_edges, title=\"Wild Set\")\n",
    "        p.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "95408565",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## WildGraph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "c4e5ed86",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Edge Valuations and Algorithmic Bounds\n",
    "\n",
    "To compute the wild number efficiently, we must measure the \"value\" of an edge. We use the **Dip Number**, denoted $\\delta(e)$, which represents the total number of connected components an edge merges across all colors if it is made wild. \n",
    "\n",
    "Based on these edge valuations, we implement two critical bounds:\n",
    "\n",
    "**1. The Dip Lower Bound (Proposition 5.6):**\n",
    "This bound calculates the absolute minimum number of edges required to connect the graph, assuming \"perfect efficiency.\" It ranks all edges by their initial dip number $\\delta_1 \\ge \\delta_2 \\ge \\dots \\ge \\delta_m$ and finds the minimum $p$ such that the sum of these top $p$ dips exceeds the total number of connections required (the Component Upper Bound). Because it assumes no edge will ever be redundant, it acts as a strict mathematical floor.\n",
    "\n",
    "**2. The Greedy Upper Bound (Algorithm 5.10):**\n",
    "The wild number is the *minimum* possible size of a wild set. A greedy algorithm iteratively picks the edge with the highest dynamic dip number and adds it to the wild set. Because it dynamically recalculates dip numbers after every choice, it accounts for redundancy and is guaranteed to output a *valid* color-connecting set. Since any valid wild set's size is $\\ge \\mathrm{wld}(G)$, the size of the set produced by the Greedy Algorithm serves as a strict mathematical **Upper Bound**. However, because it makes myopic, local choices, it may not find the absolute minimum configuration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ca329356",
   "metadata": {},
   "outputs": [],
   "source": [
    "class WildGraph(WildGraphVisualizer):\n",
    "    \"\"\"\n",
    "    Immutable representation of an edge-colored graph.\n",
    "    Inherits plotting capabilities from WildGraphVisualizer.\n",
    "    \"\"\"\n",
    "    def __init__(self, graph: Any):\n",
    "        self.G = graph\n",
    "        self.vertices: List[Any] = self.G.vertices(sort=True)\n",
    "        self.edges: List[Tuple[Any, Any, Any]] = self.G.edges(labels=True, sort=True)\n",
    "        self.colors: Set[Any] = set(color for _, _, color in self.edges)\n",
    "\n",
    "        # pin the vertex layout coordinates permanently on initialization\n",
    "        self.pos: Dict[Any, Tuple[float, float]] = self.G.layout_circular()\n",
    "\n",
    "        # Cache base kappas (O(1) bounds lookups)\n",
    "        self.base_kappas: Dict[Any, int] = {color: self.kappa(color) for color in self.colors}\n",
    "\n",
    "    @classmethod\n",
    "    def from_colored_edges(cls, G: Any, colored_edges: List[Tuple[Any, Any, Any]]) -> \"WildGraph\":\n",
    "        H = Graph()\n",
    "        H.add_vertices(G.vertices(sort=True))\n",
    "        H.add_edges(colored_edges)\n",
    "        return cls(H)\n",
    "\n",
    "    # --- Structural Helpers ---\n",
    "\n",
    "    @property\n",
    "    def color_classes(self) -> Dict[str, List[Tuple[Any, Any]]]:\n",
    "        \"\"\"Returns a clean dictionary mapping each color string to its edges.\"\"\"\n",
    "        classes = {}\n",
    "        for u, v, c in self.edges:\n",
    "            color_str = self.display_color(c)\n",
    "            classes.setdefault(color_str, []).append((u, v))\n",
    "        return classes\n",
    "\n",
    "    def display_coloring(self, plot: bool = False) -> Optional[Any]:\n",
    "        \"\"\"\n",
    "        Prints a clean text breakdown of the color classes\n",
    "        and optionally returns the visual plot representation.\n",
    "        \"\"\"\n",
    "        print(f\"Graph Coloring Breakdown ({len(self.colors)} colors):\")\n",
    "        for color, edges in self.color_classes.items():\n",
    "            print(f\"{color:<8}: {edges}\")\n",
    "\n",
    "        if plot:\n",
    "            print(\"\\nRendering visual plot...\")\n",
    "            return self.plot_colored()\n",
    "\n",
    "    def normalize_edge(self, edge: Tuple[Any, ...]) -> Tuple[Any, Any]:\n",
    "        return tuple(sorted(edge[:2]))\n",
    "\n",
    "    def normalize_edges(self, edges: List[Tuple[Any, ...]]) -> Set[Tuple[Any, Any]]:\n",
    "        return {self.normalize_edge(e) for e in edges}\n",
    "\n",
    "    def make_graph(self, edges: List[Tuple[Any, ...]]) -> Any:\n",
    "        H = Graph()\n",
    "        H.add_vertices(self.vertices)\n",
    "        H.add_edges(edges)\n",
    "        return H\n",
    "\n",
    "    def monochromatic_subgraph(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> Any:\n",
    "        color_edges = [e for e in self.edges if e[2] == color]\n",
    "        return self.make_graph(color_edges + list(wild_edges or []))\n",
    "\n",
    "    # --- Graph Theory Metrics ---\n",
    "\n",
    "    def kappa(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> int:\n",
    "        return self.monochromatic_subgraph(color, wild_edges).connected_components_number()\n",
    "\n",
    "    def kappa_total(self, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> int:\n",
    "        if not wild_edges: return sum(self.base_kappas.values())\n",
    "        return sum(self.kappa(color, wild_edges) for color in self.colors)\n",
    "\n",
    "    def is_color_connecting(self, wild_edges: List[Tuple[Any, ...]]) -> bool:\n",
    "        return all(self.kappa(color, wild_edges) == 1 for color in self.colors)\n",
    "\n",
    "    def dip_number(self, edge: Tuple[Any, ...], current_wild: Optional[List[Tuple[Any, ...]]] = None) -> int:\n",
    "        current_wild = current_wild or []\n",
    "        before = self.kappa_total(wild_edges=current_wild)\n",
    "        after = self.kappa_total(wild_edges=current_wild + [edge])\n",
    "        return before - after\n",
    "\n",
    "    def get_all_dip_numbers(self) -> List[Tuple[int, Tuple[Any, ...]]]:\n",
    "        \"\"\"Returns all edges sorted descending by their initial dip number.\"\"\"\n",
    "        dips = [(self.dip_number(e), e) for e in self.edges]\n",
    "        dips.sort(key=lambda x: x[0], reverse=True)\n",
    "        return dips\n",
    "\n",
    "    def contracted_dip_sequence(self, candidate_edge: Tuple[Any, ...], current_wild: List[Tuple[Any, ...]], available_edges: List[Tuple[Any, ...]]) -> Tuple[int, ...]:\n",
    "        \"\"\"\n",
    "        Algorithm 5.10 Potential Function (Edge Contraction):\n",
    "        Adding an edge to the wild set universally merges its endpoints across all colors.\n",
    "        This is topologically identical to edge contraction (G / e).\n",
    "        This method calculates the lexicographic dip sequence of the post-contraction graph.\n",
    "        \"\"\"\n",
    "        hypothetical_wild = current_wild + [candidate_edge]\n",
    "        remaining_edges = [e for e in available_edges if e != candidate_edge]\n",
    "\n",
    "        # Calculate dips in the conceptually contracted graph and sort descending\n",
    "        future_dips = [self.dip_number(e, hypothetical_wild) for e in remaining_edges]\n",
    "        future_dips.sort(reverse=True)\n",
    "\n",
    "        return tuple(future_dips)\n",
    "\n",
    "    # --- Theoretical Bounds ---\n",
    "\n",
    "    def component_bounds(self) -> Tuple[int, int]:\n",
    "        clb = max(self.base_kappas.values()) - 1\n",
    "        cub = sum(self.base_kappas.values()) - len(self.colors)\n",
    "        return clb, cub\n",
    "\n",
    "    def ceiling_lower_bound(self) -> int:\n",
    "        _, cub = self.component_bounds()\n",
    "        ell = len(self.colors)\n",
    "        return 0 if ell <= 1 else math.ceil(cub / (ell - 1))\n",
    "\n",
    "    def dip_lower_bound(self) -> int:\n",
    "        _, cub = self.component_bounds()\n",
    "        dips = [d for d, _ in self.get_all_dip_numbers()]\n",
    "        total = 0\n",
    "        for p, d in enumerate(dips, start=1):\n",
    "            total += d\n",
    "            if total >= cub:\n",
    "                return p\n",
    "        return len(dips)\n",
    "\n",
    "    # --- Solvers & Algorithms ---\n",
    "\n",
    "    def find_exact_wild_set(self, timeout: Optional[float] = None) -> List[Tuple[Any, ...]]:\n",
    "        \"\"\"Exact wild set by checking all subsets (Brute Force). O(2^m).\"\"\"\n",
    "        import time\n",
    "        start_time = time.time()\n",
    "\n",
    "        start_k = max(self.dip_lower_bound(), self.ceiling_lower_bound())\n",
    "\n",
    "        for k in range(start_k, len(self.edges) + 1):\n",
    "            for wild_edges in combinations(self.edges, k):\n",
    "                if timeout and (time.time() - start_time) > timeout:\n",
    "                    return None\n",
    "\n",
    "                if self.is_color_connecting(list(wild_edges)):\n",
    "                    return list(wild_edges)\n",
    "        raise ValueError(\"Graph cannot be connected.\")\n",
    "\n",
    "    def find_greedy_wild_set(self) -> List[Tuple[Any, ...]]:\n",
    "        \"\"\"\n",
    "        Algorithm 5.10: Iteratively picks edges by dynamic dip number.\n",
    "        Breaks ties using lexicographic potential (the sequence of dips after contraction).\n",
    "        \"\"\"\n",
    "        current_wild = []\n",
    "        available_edges = list(self.edges)\n",
    "\n",
    "        while not self.is_color_connecting(current_wild):\n",
    "            dips = [(self.dip_number(e, current_wild), e) for e in available_edges] #  = [(dip, (u, v, c)), ...]\n",
    "            max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "\n",
    "            tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "            if len(tied_edges) == 1:\n",
    "                best_edge = tied_edges[0]\n",
    "            else:\n",
    "                # break ties using dip potential\n",
    "                potentials = [(self.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges] # = [(dip_sequence, (u, v, c)), ...]\n",
    "                potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "                best_edge = potentials[0][1]\n",
    "\n",
    "            current_wild.append(best_edge)\n",
    "            available_edges.remove(best_edge)\n",
    "\n",
    "        return current_wild\n",
    "\n",
    "    def find_greedy_wild_set_improved(self) -> List[Tuple[Any, ...]]:\n",
    "        \"\"\"\n",
    "        Algorithm 5.10 (Theory-Patched): Iteratively picks edges by dynamic dip number.\n",
    "        Uses theoretical structural bounds (Lemma 3.10) to avoid the Matching Trap.\n",
    "        \"\"\"\n",
    "        current_wild = []\n",
    "        available_edges = list(self.edges)\n",
    "\n",
    "        while not self.is_color_connecting(current_wild):\n",
    "            # 1. Base Score: Maximize immediate component merges\n",
    "            dips = [(self.dip_number(e, current_wild), e) for e in available_edges]\n",
    "            max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "            tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "            if len(tied_edges) == 1:\n",
    "                best_edge = tied_edges[0]\n",
    "            else:\n",
    "                # 2. THE THEORETICAL PATCH: Anti-Matching Tree Bias + Color Regularization\n",
    "                current_vertices = set(v for e in current_wild for v in e[:2])\n",
    "\n",
    "                # Count how many times each color has been used in the current wild set\n",
    "                from collections import Counter\n",
    "                color_counts = Counter(e[2] for e in current_wild)\n",
    "\n",
    "                def structural_score(edge):\n",
    "                    u, v, c = edge\n",
    "                    shared = (u in current_vertices) + (v in current_vertices)\n",
    "\n",
    "                    # Base structural score\n",
    "                    if shared == 1: score = 2  # Best: Expands an existing tree\n",
    "                    elif shared == 0: score = 1  # Okay: Starts a new tree\n",
    "                    else: score = 0              # Worst: Forms a cycle\n",
    "\n",
    "                    # The Color Penalty:\n",
    "                    # Subtract a fraction of a point for every time this color has been used.\n",
    "                    # This guarantees that if two edges have the same structural value,\n",
    "                    # the algorithm will strictly prefer the one from a less-used color class.\n",
    "                    penalty = color_counts[c] * 0.1\n",
    "\n",
    "                    return score - penalty\n",
    "\n",
    "                bias_scores = [(structural_score(e), e) for e in tied_edges]\n",
    "                max_bias = max(bias_scores, key=lambda x: x[0])[0]\n",
    "                bias_tied_edges = [e for b, e in bias_scores if b == max_bias]\n",
    "\n",
    "                if len(bias_tied_edges) == 1:\n",
    "                    best_edge = bias_tied_edges[0]\n",
    "                else:\n",
    "                    # 3. Fallback: Deep lookahead potential function\n",
    "                    potentials = [(self.contracted_dip_sequence(e, current_wild, available_edges), e) for e in bias_tied_edges]\n",
    "                    potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "                    best_edge = potentials[0][1]\n",
    "\n",
    "            current_wild.append(best_edge)\n",
    "            available_edges.remove(best_edge)\n",
    "\n",
    "        return current_wild\n",
    "\n",
    "    def find_greedy_wild_set_color_momentum(self) -> List[Tuple[Any, ...]]:\n",
    "        \"\"\"\n",
    "        Algorithm 5.10 (Color Momentum Test):\n",
    "        Iteratively picks edges by dynamic dip number.\n",
    "        At tie-breaking, forces the algorithm to prefer the color of the LAST chosen edge.\n",
    "        \"\"\"\n",
    "        current_wild = []\n",
    "        available_edges = list(self.edges)\n",
    "        last_color = None\n",
    "\n",
    "        while not self.is_color_connecting(current_wild):\n",
    "            # 1. Base Score: Maximize immediate component merges\n",
    "            dips = [(self.dip_number(e, current_wild), e) for e in available_edges]\n",
    "            max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "            tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "            if len(tied_edges) == 1:\n",
    "                best_edge = tied_edges[0]\n",
    "            else:\n",
    "                # 2. THE MOMENTUM PATCH: Prefer the last color taken\n",
    "                if last_color is not None:\n",
    "                    momentum_edges = [e for e in tied_edges if e[2] == last_color]\n",
    "                    if momentum_edges:\n",
    "                        # If edges of the last color exist in the tie, restrict our choices to ONLY those\n",
    "                        tied_edges = momentum_edges\n",
    "\n",
    "                # 3. Fallback: Deep lookahead potential function\n",
    "                if len(tied_edges) == 1:\n",
    "                    best_edge = tied_edges[0]\n",
    "                else:\n",
    "                    potentials = [(self.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]\n",
    "                    potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "                    best_edge = potentials[0][1]\n",
    "\n",
    "            current_wild.append(best_edge)\n",
    "            available_edges.remove(best_edge)\n",
    "            last_color = best_edge[2]  # Update momentum tracker\n",
    "\n",
    "        return current_wild\n",
    "\n",
    "    def find_milp_wild_set(self, upper_bound: Optional[int] = None) -> List[Tuple[Any, ...]]:\n",
    "        \"\"\"\n",
    "        Solves for the exact wild number using MILP.\n",
    "        \"\"\"\n",
    "        from sage.numerical.mip import MixedIntegerLinearProgram\n",
    "        from itertools import combinations\n",
    "\n",
    "        # upper bound to prune the search space\n",
    "        fallback_wild_set = None\n",
    "        if upper_bound is None:\n",
    "            upper_bound, fallback_wild_set = self.wild_number(method=\"greedy\")\n",
    "\n",
    "        edges = self.G.edges(labels=False)\n",
    "        edge_to_idx = {tuple(sorted(e)): i for i, e in enumerate(edges)} # link each edge to an index for MILP\n",
    "        num_edges = len(edges)\n",
    "\n",
    "        # initialize MILP solver\n",
    "        milp = MixedIntegerLinearProgram(maximization=False, solver='GLPK')\n",
    "        milp.solver_parameter(\"timelimit\", 600)\n",
    "        x = milp.new_variable(binary=True) # x[i] = 1 => x is wild\n",
    "\n",
    "        # objective: minimize the total number of wild edges\n",
    "        milp.set_objective(sum(x[i] for i in range(num_edges)))\n",
    "\n",
    "        # constraint: prune the search tree\n",
    "        milp.add_constraint(sum(x[i] for i in range(num_edges)) <= upper_bound)\n",
    "\n",
    "        # constraints: for each color, W must connect the components of M_i\n",
    "        for color in self.colors:\n",
    "            M_i = self.monochromatic_subgraph(color)\n",
    "            comps = M_i.connected_components() # eg., [[0, 1], [2, 3, 4], [5], [6, 7]]\n",
    "            c = len(comps)\n",
    "\n",
    "            if c <= 1:\n",
    "                continue\n",
    "\n",
    "            # map vertices to component IDs for O(1) lookup;s eg., {0:0, 1:1: 2:1, ...}\n",
    "            comp_of = {v: idx for idx, comp in enumerate(comps) for v in comp}\n",
    "\n",
    "            # pre-filter cross edges\n",
    "            cross_edges = []\n",
    "            for u, v in edges:\n",
    "                cu = comp_of[u]\n",
    "                cv = comp_of[v]\n",
    "                if cu != cv:\n",
    "                    cross_edges.append((edge_to_idx[tuple(sorted((u, v)))], cu, cv))\n",
    "\n",
    "            comp_indices = list(range(c))\n",
    "\n",
    "            # generate all valid cuts\n",
    "            # need to ensure that for every way to partition the components into A and B, there is at least a wild crossing edge\n",
    "            # iterate over all partitions of the components into two non-empty sets\n",
    "            # fix component 0 to group A to avoid checking (A, B) and (B, A)\n",
    "            for r in range(1, len(comp_indices)): # eg., r = |A|, eg., r = 2\n",
    "                for subset in combinations(comp_indices[1:], r-1):\n",
    "                    S = set(subset) | {0} # eg., A = {2} U {0} = {0, 2}\n",
    "\n",
    "                    # cut edges\n",
    "                    cut_edge_indices = [\n",
    "                        idx for idx, cu, cv, in cross_edges\n",
    "                        if (cu in S) != (cv in S)\n",
    "                    ]\n",
    "\n",
    "                    # W must contain at least one edge from this cut to ensure connectivity\n",
    "                    if cut_edge_indices:\n",
    "                        milp.add_constraint(sum(x[idx] for idx in cut_edge_indices) >= 1)\n",
    "\n",
    "        # solve\n",
    "        try:\n",
    "            min_wld = milp.solve()\n",
    "            x_values = milp.get_values(x)\n",
    "            wild_set = [edges[i] for i in range(num_edges) if x_values[i] > 0.5]\n",
    "            return wild_set\n",
    "        except Exception as e:\n",
    "            print(f\"[Error] ILP Solver failed: {e}\")\n",
    "            return fallback_wild_set\n",
    "\n",
    "    def wild_number(self, method: str = \"auto\") -> Tuple[int, List[Tuple[Any, ...]]]:\n",
    "        \"\"\"Intelligent dispatcher to find the Wild Number.\"\"\"\n",
    "        if len(self.colors) == 2:\n",
    "            cub = self.component_bounds()[1]\n",
    "            wild_set = self.find_greedy_wild_set()\n",
    "            return cub, wild_set\n",
    "\n",
    "        m = len(self.edges)\n",
    "        if method == \"exact\" or (method == \"auto\" and m <= 38):\n",
    "            wild_set = self.find_exact_wild_set()\n",
    "        elif method == \"milp\" or (method == \"auto\" and m > 38):\n",
    "            wild_set = self.find_milp_wild_set()\n",
    "        else:\n",
    "            wild_set = self.find_greedy_wild_set()\n",
    "\n",
    "        return len(wild_set), wild_set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fa938161",
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "from itertools import combinations\n",
    "from collections import defaultdict\n",
    "\n",
    "class AlgebraicTreePacker:\n",
    "    def __init__(self, wild_graph):\n",
    "        self.wg = wild_graph\n",
    "        self.vertices = set(wild_graph.vertices)\n",
    "        self.n = len(self.vertices)\n",
    "\n",
    "        # O(1) edge-color lookup (was O(E) linear scan per call)\n",
    "        self.color_of = {}\n",
    "        for u, v, c in wild_graph.edges:\n",
    "            self.color_of[(u, v)] = c\n",
    "            self.color_of[(v, u)] = c\n",
    "\n",
    "        # color -> its matching edges, for fast connectivity test\n",
    "        self.mono = defaultdict(list)\n",
    "        for u, v, c in wild_graph.edges:\n",
    "            self.mono[c].append((u, v))\n",
    "\n",
    "        self.colors = set(wild_graph.colors)\n",
    "        self.isolated_color_of = self._map_isolated_colors()\n",
    "        self.quad_trees_all = {}\n",
    "        self.triples_with = defaultdict(list)\n",
    "        self.quads_with = defaultdict(list)\n",
    "\n",
    "    def _map_isolated_colors(self):\n",
    "        missing = {}\n",
    "        for v in self.vertices:\n",
    "            incident = {self.color_of[(v, u)] for u in self.vertices\n",
    "                        if u != v}\n",
    "            missing[v] = (self.colors - incident).pop()\n",
    "        return missing\n",
    "\n",
    "    def get_edge_color(self, u, v):\n",
    "        return self.color_of.get((u, v))\n",
    "\n",
    "    # --- validity filters (O(1) color lookups now) ---\n",
    "    def is_valid_wild_triple(self, triple):\n",
    "        u, v, w = triple\n",
    "        iso = self.isolated_color_of\n",
    "        if self.color_of[(u, v)] == iso[w]: return False\n",
    "        if self.color_of[(v, w)] == iso[u]: return False\n",
    "        if self.color_of[(u, w)] == iso[v]: return False\n",
    "        return True\n",
    "\n",
    "    def get_all_valid_trees_for_quadruple(self, quad):\n",
    "        a, b, c, d = quad\n",
    "        forbidden = {self.isolated_color_of[x] for x in quad}\n",
    "        trees = [\n",
    "            [(a,b),(a,c),(a,d)], [(b,a),(b,c),(b,d)],\n",
    "            [(c,a),(c,b),(c,d)], [(d,a),(d,b),(d,c)],\n",
    "            [(a,b),(b,c),(c,d)], [(a,b),(b,d),(d,c)],\n",
    "            [(a,c),(c,b),(b,d)], [(a,c),(c,d),(d,b)],\n",
    "            [(a,d),(d,b),(b,c)], [(a,d),(d,c),(c,b)],\n",
    "            [(b,a),(a,c),(c,d)], [(b,a),(a,d),(d,c)],\n",
    "            [(b,c),(c,a),(a,d)], [(b,d),(d,a),(a,c)],\n",
    "            [(c,a),(a,b),(b,d)], [(c,b),(b,a),(a,d)],\n",
    "        ]\n",
    "        return [t for t in trees\n",
    "                if all(self.color_of[(x, y)] not in forbidden for x, y in t)]\n",
    "\n",
    "    # --- connectivity test: partition-only, union-find, no routings ---\n",
    "    def _partition_color_connecting(self, parts):\n",
    "        idx = {}\n",
    "        for i, part in enumerate(parts):\n",
    "            for v in part:\n",
    "                idx[v] = i\n",
    "        k = len(parts)\n",
    "        for medges in self.mono.values():\n",
    "            parent = list(range(k))\n",
    "            def find(x):\n",
    "                r = x\n",
    "                while parent[r] != r: r = parent[r]\n",
    "                while parent[x] != r:\n",
    "                    parent[x], x = r, parent[x]\n",
    "                return r\n",
    "            comps = k\n",
    "            for u, v in medges:\n",
    "                ru, rv = find(idx[u]), find(idx[v])\n",
    "                if ru != rv:\n",
    "                    parent[ru] = rv\n",
    "                    comps -= 1\n",
    "            if comps != 1:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def _canonical_edges(self, partition):\n",
    "        edges = []\n",
    "        for p_type, comp in partition:\n",
    "            if p_type == 'triple':\n",
    "                u, v, w = list(comp)\n",
    "                edges.append((u, v, self.get_edge_color(u, v)))\n",
    "                edges.append((v, w, self.get_edge_color(v, w)))\n",
    "            else:\n",
    "                tree = self.quad_trees_all[frozenset(comp)][0]\n",
    "                for x, y in tree:\n",
    "                    edges.append((x, y, self.get_edge_color(x, y)))\n",
    "        return edges\n",
    "\n",
    "    # --- exact cover (MRV via per-vertex index; no routing product) ---\n",
    "    def exact_cover(self, remaining, quads_needed, partition):\n",
    "        if not remaining:\n",
    "            parts = [comp for _, comp in partition]\n",
    "            if self._partition_color_connecting(parts):\n",
    "                return self._canonical_edges(partition)\n",
    "            return None\n",
    "\n",
    "        # MRV: remaining vertex in fewest still-available parts\n",
    "        pivot, best = None, None\n",
    "        for v in remaining:\n",
    "            cnt = sum(1 for t in self.triples_with[v] if t <= remaining)\n",
    "            if quads_needed > 0:\n",
    "                cnt += sum(1 for q in self.quads_with[v] if q <= remaining)\n",
    "            if best is None or cnt < best:\n",
    "                pivot, best = v, cnt\n",
    "                if cnt == 0:\n",
    "                    break\n",
    "        if best == 0:\n",
    "            return None\n",
    "\n",
    "        if quads_needed > 0:\n",
    "            cands = [q for q in self.quads_with[pivot] if q <= remaining]\n",
    "            random.shuffle(cands)\n",
    "            for quad in cands:\n",
    "                r = self.exact_cover(remaining - quad, quads_needed - 1,\n",
    "                                     partition + [('quad', quad)])\n",
    "                if r: return r\n",
    "\n",
    "        if len(remaining) - 3 >= 4 * quads_needed:\n",
    "            cands = [t for t in self.triples_with[pivot] if t <= remaining]\n",
    "            random.shuffle(cands)\n",
    "            for triple in cands:\n",
    "                r = self.exact_cover(remaining - triple, quads_needed,\n",
    "                                     partition + [('triple', triple)])\n",
    "                if r: return r\n",
    "        return None\n",
    "\n",
    "    def solve_perfect_graph(self):\n",
    "        quads_needed = self.n % 3\n",
    "\n",
    "        valid_triples = [frozenset(c) for c in combinations(self.vertices, 3)\n",
    "                         if self.is_valid_wild_triple(c)]\n",
    "        for t in valid_triples:\n",
    "            for v in t:\n",
    "                self.triples_with[v].append(t)\n",
    "\n",
    "        if quads_needed > 0:\n",
    "            for combo in combinations(self.vertices, 4):\n",
    "                trees = self.get_all_valid_trees_for_quadruple(combo)\n",
    "                if trees:\n",
    "                    fs = frozenset(combo)\n",
    "                    self.quad_trees_all[fs] = trees\n",
    "                    for v in fs:\n",
    "                        self.quads_with[v].append(fs)\n",
    "\n",
    "        result = self.exact_cover(self.vertices, quads_needed, [])\n",
    "        if not result:\n",
    "            raise ValueError(\"No valid color-connecting partition exists.\")\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "686a91d3",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## Coloring Generators\n",
    "\n",
    "A suite of tools to assign color classes strictly (Proper Edge Colorings), uniformly, or partitioned equitably. We generate structural variance via Line Graph conversions."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4782abda",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Random Colorings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0e3c96d3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def color_randomly(G: Any, num_colors: int) -> WildGraph:\n",
    "    \"\"\"Assigns random colors to edges using the true named palette.\"\"\"\n",
    "    assert num_colors <= G.size(), \"More colors than edges requested.\"\n",
    "    color_palette = WildGraphVisualizer.get_color_palette(num_colors)\n",
    "\n",
    "    edges = G.edges(labels=False, sort=True)\n",
    "    while True:\n",
    "        colored_edges = [(u, v, random.choice(color_palette)) for u, v in edges]\n",
    "        if len(set(c for _, _, c in colored_edges)) == num_colors:\n",
    "            return WildGraph.from_colored_edges(G, colored_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7580aed4",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Equitable Colorings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "35adb7df",
   "metadata": {},
   "outputs": [],
   "source": [
    "def color_by_edge_partition(G: Any, num_colors: int) -> WildGraph:\n",
    "    \"\"\"Divides edges as evenly as possible among true named colors.\"\"\"\n",
    "    color_palette = WildGraphVisualizer.get_color_palette(num_colors)\n",
    "    colored_edges = [\n",
    "        (u, v, color_palette[i % num_colors])\n",
    "        for i, (u, v, _) in enumerate(G.edges(labels=True, sort=True))\n",
    "    ]\n",
    "    return WildGraph.from_colored_edges(G, colored_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5b463b4e",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "#### Proper Colorings"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5a862f81",
   "metadata": {},
   "outputs": [],
   "source": [
    "def round_robin_proper_coloring(n: int) -> WildGraph:\n",
    "    \"\"\"Generates one structurally round-robin proper coloring of K_n.\"\"\"\n",
    "    if n < 2: raise ValueError(\"Complete graph must have at least 2 vertices.\")\n",
    "\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    color_palette = WildGraphVisualizer.get_color_palette(ell)\n",
    "\n",
    "    vertices = list(range(n))\n",
    "    random.shuffle(vertices)\n",
    "    colored_edges = []\n",
    "\n",
    "    if n % 2 == 0:\n",
    "        for i in range(n - 1):\n",
    "            color = color_palette[i]\n",
    "            for j in range(n // 2):\n",
    "                v1 = vertices[(i + j) % (n - 1)]\n",
    "                v2 = vertices[n - 1] if j == 0 else vertices[(i - j + n - 1) % (n - 1)]\n",
    "                colored_edges.append((min(v1, v2), max(v1, v2), color))\n",
    "    else:\n",
    "        for i in range(n):\n",
    "            color = color_palette[i]\n",
    "            for j in range(1, (n // 2) + 1):\n",
    "                v1 = vertices[(i + j) % n]\n",
    "                v2 = vertices[(i - j + n) % n]\n",
    "                colored_edges.append((min(v1, v2), max(v1, v2), color))\n",
    "\n",
    "    return WildGraph.from_colored_edges(graphs.CompleteGraph(n), colored_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0b27da78",
   "metadata": {},
   "outputs": [],
   "source": [
    "def _structural_fingerprint(WG: \"WildGraph\") -> Tuple[Tuple[int, ...], ...]:\n",
    "    \"\"\"\n",
    "    Creates a color-agnostic, vertex-agnostic structural signature for a proper coloring.\n",
    "    Calculates the cycle lengths of every isolated pair of colors.\n",
    "    \"\"\"\n",
    "    colors = list(WG.colors)\n",
    "    all_cycle_profiles = []\n",
    "\n",
    "    # iterate over all pairs of colors\n",
    "    for c1, c2 in combinations(colors, 2): # eg., ('red', 'blue')\n",
    "        # isolate subgraph of just these two colors\n",
    "        subgraph_edges = [(u, v) for u, v, c in WG.edges if c in (c1, c2)]\n",
    "        H = Graph()\n",
    "        H.add_edges(subgraph_edges)\n",
    "\n",
    "        # get the lengths of the cycles/paths in this 2-colored world\n",
    "        # eg., [8] or [4, 4]\n",
    "        cycle_lengths = tuple(sorted([len(comp) for comp in H.connected_components()]))\n",
    "        all_cycle_profiles.append(cycle_lengths)\n",
    "\n",
    "    # sort the profiles to make it completely invariant to which color is which\n",
    "    # eg., ((4, 4), (8,), (8,))\n",
    "    return tuple(sorted(all_cycle_profiles))\n",
    "\n",
    "\n",
    "def _factor_switch_move(WG: \"WildGraph\") -> \"WildGraph\":\n",
    "    \"\"\"\n",
    "    Performs a single random Kempe chain swap on two color classes.\n",
    "    This safely walks the graph across the mathematical space of 1-factorizations.\n",
    "    \"\"\"\n",
    "    colors = list(WG.colors)\n",
    "    if len(colors) < 2:\n",
    "        return WG\n",
    "\n",
    "    # pick two random colors to isolate\n",
    "    c1, c2 = random.sample(colors, 2) # eg., ['red', 'blue']\n",
    "\n",
    "    # build kempe graph\n",
    "    subgraph_edges = [(u, v) for u, v, c in WG.edges if c in (c1, c2)]\n",
    "    H = Graph()\n",
    "    H.add_edges(subgraph_edges)\n",
    "\n",
    "    comps = H.connected_components() # eg., [[0, 1, 2, 3], [4, 5, 6, 7]]\n",
    "\n",
    "    # isolate loops large enough to meaningfully swap\n",
    "    valid_comps = [comp for comp in comps if len(comp) >= 3]\n",
    "    if not valid_comps:\n",
    "        return WG\n",
    "\n",
    "    # pick a random cycle and prepare to swap its edges\n",
    "    target_comp = set(random.choice(valid_comps)) # eg., {0, 1, 2, 3}\n",
    "\n",
    "    # perform kempe swap\n",
    "    new_edges = []\n",
    "    for u, v, c in WG.edges:\n",
    "        # if the edge is in our target loop and is one of our two colors, swap it\n",
    "        if c in (c1, c2) and u in target_comp and v in target_comp:\n",
    "            new_color = c2 if c == c1 else c1\n",
    "            new_edges.append((u, v, new_color))\n",
    "        else:\n",
    "            new_edges.append((u, v, c))\n",
    "\n",
    "    return WildGraph.from_colored_edges(WG.G, new_edges)\n",
    "\n",
    "\n",
    "def generate_diverse_proper_colorings(\n",
    "    G: Any,\n",
    "    num_colors: int,\n",
    "    max_yields: int = 10,\n",
    "    max_stagnation: int = 1_000\n",
    "    ) -> Generator[\"WildGraph\", None, None]:\n",
    "    \"\"\"\n",
    "    Explores the space of proper colorings using Markov-chain Kempe swaps.\n",
    "    Uses 2-factor structural fingerprints to perfectly detect diverse isomorphism classes.\n",
    "    \"\"\"\n",
    "    # seed the markov chain with a valid starting factorization\n",
    "    n = G.order()\n",
    "    current_WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    accepted_graphs: List[WildGraph] = []\n",
    "    seen_fingerprints = set()\n",
    "\n",
    "    stagnation_counter = 0\n",
    "\n",
    "    # save the base graph immediately so we don't lose the original round-robin class\n",
    "    base_fingerprint = _structural_fingerprint(current_WG)\n",
    "    seen_fingerprints.add(base_fingerprint)\n",
    "    accepted_graphs.append(current_WG)\n",
    "    yield current_WG\n",
    "\n",
    "    while len(accepted_graphs) < max_yields and stagnation_counter < max_stagnation:\n",
    "        stagnation_counter += 1\n",
    "\n",
    "        # mutate the graph via a random walk of 20 factor switches\n",
    "        for _ in range(20):\n",
    "            current_WG = _factor_switch_move(current_WG)\n",
    "\n",
    "        # check our color-agnostic structural invariant\n",
    "        fingerprint = _structural_fingerprint(current_WG) # eg., ((4, 4), (8,), (8,))\n",
    "\n",
    "        if fingerprint not in seen_fingerprints:\n",
    "            seen_fingerprints.add(fingerprint)\n",
    "            accepted_graphs.append(current_WG)\n",
    "            stagnation_counter = 0\n",
    "            yield current_WG\n",
    "\n",
    "    if stagnation_counter >= max_stagnation:\n",
    "        print(f\"[Info] Search space exhausted. Halted at {len(accepted_graphs)} diverse colorings.\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1608a030",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "#### Product Coloring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d28863cb",
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_product_graph_coloring(\n",
    "    WG1: WildGraph,\n",
    "    WG2: WildGraph,\n",
    "    color_G: Optional[str] = None,\n",
    "    color_H: Optional[str] = None,\n",
    ") -> WildGraph:\n",
    "    \"\"\"Generates the Cartesian Product G □ H and inherits or overrides factor colorings.\"\"\"\n",
    "    G, H = WG1.G, WG2.G\n",
    "    colored_edges = []\n",
    "\n",
    "    for h in H.vertices(sort=True):\n",
    "        for u, v, orig_color in G.edges(labels=True, sort=True):\n",
    "            colored_edges.append(((u, h), (v, h), color_G or orig_color))\n",
    "\n",
    "    for g in G.vertices(sort=True):\n",
    "        for u, v, orig_color in H.edges(labels=True, sort=True):\n",
    "            colored_edges.append(((g, u), (g, v), color_H or orig_color))\n",
    "\n",
    "    P = Graph()\n",
    "    P.add_vertices(\n",
    "        [(g, h) for g in G.vertices(sort=True) for h in H.vertices(sort=True)]\n",
    "    )\n",
    "    return WildGraph.from_colored_edges(P, colored_edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "43b8785f",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## Experimental Scripts"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fdea3a44",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### $\\mathbb{E}[\\mathrm{wld}(G)]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "1ed3c521",
   "metadata": {},
   "outputs": [],
   "source": [
    "def expected_wld(G: Any, method: str = \"auto\", iterations: int = 50_000) -> float:\n",
    "    \"\"\"Calculates the expected wild number for an equitable 2-coloring of graph G.\"\"\"\n",
    "    edges = list(G.edges(labels=False, sort=True))\n",
    "    m = len(edges)\n",
    "    red_size = m // 2\n",
    "    method = (\"exact\" if m <= 20 else \"monte_carlo\") if method == \"auto\" else method\n",
    "\n",
    "    def cub_of(red_set: Set[Tuple[Any, ...]]) -> int:\n",
    "        colored = [(u, v, \"red\" if (u, v) in red_set else \"blue\") for u, v in edges]\n",
    "        return WildGraph.from_colored_edges(G, colored).component_bounds()[1]\n",
    "\n",
    "    if method == \"exact\":\n",
    "        samples = (set(c) for c in combinations(edges, red_size))\n",
    "        total = binomial(m, red_size)\n",
    "        return sum(cub_of(s) for s in samples) / float(total)\n",
    "\n",
    "    acc = sum(cub_of(set(random.sample(edges, red_size))) for _ in range(iterations))\n",
    "    return float(acc) / iterations"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "544a57fc",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Wild Set Robustness\n",
    "\n",
    "For a given graph $G$, is there any set $W$ of size $\\mathrm{wld}(G)$ that connects the graph for all possible proper colorings, or is every ideal wild set strictly coupled to the spatial geometry of a single coloring?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "aaa131d2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_wild_set_robustness(\n",
    "    G: Any,\n",
    "    wild_edges: List[Tuple[Any, ...]],\n",
    "    num_colors: int,\n",
    "    max_test_cases: int = 100\n",
    ") -> List[WildGraph]:\n",
    "    \"\"\"Tests if a specific Wild Set 'W' survives against distinct proper colorings.\"\"\"\n",
    "    print(f\"testing W against isomorphically distinct proper colorings...\")\n",
    "    successes = 0\n",
    "    failing_graphs = []\n",
    "\n",
    "    for WG_new in generate_diverse_proper_colorings(G, num_colors, max_yields=max_test_cases):\n",
    "        if WG_new.is_color_connecting(wild_edges):\n",
    "            successes += 1\n",
    "        else:\n",
    "            failing_graphs.append(WG_new)\n",
    "\n",
    "    total_tested = successes + len(failing_graphs)\n",
    "    if total_tested == 0:\n",
    "        print(\"\\n[Warning] No colorings were generated to test against.\")\n",
    "        return []\n",
    "\n",
    "    win_rate = float(successes / total_tested) * 100\n",
    "\n",
    "    print(f\"\\ntotal colorings tested: {successes + len(failing_graphs)}\")\n",
    "    print(f\"W remained valid in: {successes} colorings\")\n",
    "    print(f\"W failed in: {len(failing_graphs)} colorings\")\n",
    "    print(f\"robustness score: {win_rate:.1f}%\")\n",
    "\n",
    "    return failing_graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6ce1ce2",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Proper Colorings of $K_n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70962599",
   "metadata": {},
   "outputs": [],
   "source": [
    "def sample_proper_coloring_wild_sets(\n",
    "    n: int,\n",
    "    num_samples: Optional[int] = None,\n",
    "    plot: bool = False,\n",
    "    cols: Optional[int] = None\n",
    "    ) -> None:\n",
    "    \"\"\"\n",
    "    Samples structurally distinct proper colorings of K_n, computes their exact\n",
    "    wild sets, prints the text-based edge lists, and optionally renders a visual grid.\n",
    "\n",
    "    Args:\n",
    "        n: The number of vertices for the complete graph K_n.\n",
    "        num_samples: The maximum number of distinct proper colorings to evaluate.\n",
    "        plot: If True, renders the visual graphics_array grid. If False, keeps it purely text-based.\n",
    "        cols: Number of columns in the visualization grid.\n",
    "    \"\"\"\n",
    "    print(f\"Structural Analysis of {num_samples} Isomorphically Distinct Proper Colorings on K_{n}\\n\")\n",
    "\n",
    "    num_samples = num_samples if num_samples is not None else n // 2\n",
    "    cols = cols if cols is not None else n // 2\n",
    "\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "\n",
    "    # Pull exclusively from our randomized, non-isomorphic generator\n",
    "    colorings = list(generate_diverse_proper_colorings(G, ell, max_yields=num_samples))\n",
    "    plots = []\n",
    "\n",
    "    for i, WG in enumerate(colorings):\n",
    "        # Calculate the exact optimal wild set\n",
    "        wld, wild_edges = WG.wild_number(method=\"exact\")\n",
    "\n",
    "        print(f\"Sample {i+1:02d} | wld = {wld} | W =  {wild_edges}\")\n",
    "\n",
    "        # Accumulate plots only if the user explicitly requests them\n",
    "        if plot:\n",
    "            title_str = f\"Sample {i+1} | wld = {wld}\"\n",
    "            p = WG.plot_colored(title=title_str, wild_edges=wild_edges, show=False)\n",
    "            plots.append(p)\n",
    "\n",
    "    # Render the visualization suite only if the flag is True and colorings exist\n",
    "    if plot and plots:\n",
    "        print(\"\\nRendering visual topologies...\")\n",
    "        rows = math.ceil(len(plots) / cols)\n",
    "        grid = graphics_array(plots, ncols=cols)\n",
    "        grid.show(figsize=(cols * 5, rows * 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a402c1ab",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "## Execution Workspace"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b821b858",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Greedy vs Brute Force"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "75ff4b07",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " n | Greedy | Exact | Gap | Greedy(s) |  Exact(s) |  Speedup\n",
      "------------------------------------------------------------\n"
     ]
    },
    {
     "ename": "NameError",
     "evalue": "name 'graphs' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "Cell \u001b[0;32mIn[15], line 8\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[38;5;28mprint\u001b[39m(\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124m-\u001b[39m\u001b[38;5;124m\"\u001b[39m \u001b[38;5;241m*\u001b[39m \u001b[38;5;28mlen\u001b[39m(header))\n\u001b[1;32m      7\u001b[0m \u001b[38;5;28;01mfor\u001b[39;00m n \u001b[38;5;129;01min\u001b[39;00m \u001b[38;5;28mrange\u001b[39m(\u001b[38;5;241m3\u001b[39m, \u001b[38;5;241m11\u001b[39m):\n\u001b[0;32m----> 8\u001b[0m     WG \u001b[38;5;241m=\u001b[39m \u001b[43mround_robin_proper_coloring\u001b[49m\u001b[43m(\u001b[49m\u001b[43mn\u001b[49m\u001b[43m)\u001b[49m\n\u001b[1;32m     10\u001b[0m     start \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime()\n\u001b[1;32m     11\u001b[0m     greedy_wld, _ \u001b[38;5;241m=\u001b[39m WG\u001b[38;5;241m.\u001b[39mwild_number(method\u001b[38;5;241m=\u001b[39m\u001b[38;5;124m\"\u001b[39m\u001b[38;5;124mgreedy\u001b[39m\u001b[38;5;124m\"\u001b[39m)\n",
      "Cell \u001b[0;32mIn[9], line 27\u001b[0m, in \u001b[0;36mround_robin_proper_coloring\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m     24\u001b[0m             v2 \u001b[38;5;241m=\u001b[39m vertices[(i \u001b[38;5;241m-\u001b[39m j \u001b[38;5;241m+\u001b[39m n) \u001b[38;5;241m%\u001b[39m n]\n\u001b[1;32m     25\u001b[0m             colored_edges\u001b[38;5;241m.\u001b[39mappend((\u001b[38;5;28mmin\u001b[39m(v1, v2), \u001b[38;5;28mmax\u001b[39m(v1, v2), color))\n\u001b[0;32m---> 27\u001b[0m \u001b[38;5;28;01mreturn\u001b[39;00m WildGraph\u001b[38;5;241m.\u001b[39mfrom_colored_edges(\u001b[43mgraphs\u001b[49m\u001b[38;5;241m.\u001b[39mCompleteGraph(n), colored_edges)\n",
      "\u001b[0;31mNameError\u001b[0m: name 'graphs' is not defined"
     ]
    }
   ],
   "source": [
    "import time\n",
    "\n",
    "header = f\"{'n':>2} | {'Greedy':>6} | {'Exact':>5} | {'Gap':>3} | {'Greedy(s)':>9} | {'Exact(s)':>9} | {'Speedup':>8}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(3, 11):\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    start = time.time()\n",
    "    greedy_wld, _ = WG.wild_number(method=\"greedy\")\n",
    "    greedy_time = time.time() - start\n",
    "\n",
    "    start = time.time()\n",
    "    exact_wld, _ = WG.wild_number(method=\"exact\")\n",
    "    brute_time = time.time() - start\n",
    "\n",
    "    gap = abs(greedy_wld - exact_wld)\n",
    "    speedup = brute_time / greedy_time if greedy_time > 0 else float(\"inf\")\n",
    "\n",
    "    print(\n",
    "        f\"{n:>2} | {greedy_wld:>6} | {exact_wld:>5} | {gap:>3} | {greedy_time:>9.4f} | {brute_time:>9.4f} | {speedup:>7.1f}x\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "59251bfc",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Bound Verification"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3fac2a66",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 8\n",
    "WG = round_robin_proper_coloring(n)\n",
    "\n",
    "clb, cub = WG.component_bounds()\n",
    "dlb = WG.dip_lower_bound()\n",
    "exact_wld, _ = WG.wild_number(method=\"exact\")\n",
    "greedy_wld, _ = WG.wild_number(method=\"greedy\")\n",
    "\n",
    "print(\n",
    "    f\"CLB ({clb}) <= DLB ({dlb}) <= WLD ({exact_wld}) <= Greedy ({greedy_wld}) <= CUB ({cub})\"\n",
    ")\n",
    "assert clb <= dlb <= exact_wld <= greedy_wld <= cub, \"Hierarchy violated!\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "254608a2",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "**Q**: How tight is the greedy upper bound?"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "878d20d0",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Expected Equitable Wild Number"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "05974f3d",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(4, 9):\n",
    "    G_test = graphs.CompleteGraph(n)\n",
    "    ev = expected_wld(G_test, method=\"auto\")\n",
    "    print(f\"E[wld(K_{n})] ≈ {ev:.4f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0bb5217f",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### $K_n$ Proper Edge Coloring"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c9c2e1a2",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "n = 9\n",
    "ell = n if (n % 2 == 1) else (n - 1)\n",
    "\n",
    "G = graphs.CompleteGraph(n)\n",
    "WG = round_robin_proper_coloring(n)\n",
    "\n",
    "start = time.time()\n",
    "wild_number, wild_edges = WG.wild_number()\n",
    "clean_wild_edges = [(u, v) for u, v, _ in wild_edges]\n",
    "wild_time = time.time() - start\n",
    "\n",
    "print(f\"K_{n} | ell = {ell} | wld = {wild_number}\")\n",
    "print(f\"W = {wild_edges}\")\n",
    "print(f\"time: {wild_time:.4f}s\\n\")\n",
    "\n",
    "start = time.time()\n",
    "failures = test_wild_set_robustness(G=G, wild_edges=clean_wild_edges, num_colors=ell)\n",
    "robust_time = time.time() - start\n",
    "print(f\"time: {robust_time:.4f}s\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "3eb83815",
   "metadata": {},
   "outputs": [],
   "source": [
    "# if failures:\n",
    "#     failures[0].plot_wild_topology_grid(clean_wild_edges, cols=ell//2 + 1)\n",
    "# else:\n",
    "#     print(\"W is robust\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d039c8ce",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Greedy vs MILP"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "185fc369",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "header = f\"{'n':>2} | {'ILP':>5} | {'Greedy':>6} | {'Gap':>5} | {'ILP(s)':>9} | {'Greedy(s)':>9}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(3, 17):\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    # 1. run greedy\n",
    "    start = time.time()\n",
    "    greedy_wld, _ = WG.wild_number(method=\"greedy\")\n",
    "    greedy_time = time.time() - start\n",
    "\n",
    "    # 2. run ilp\n",
    "    start = time.time()\n",
    "    ilp_edges_raw = WG.find_milp_wild_set(upper_bound=greedy_wld)\n",
    "    ilp_time = time.time() - start\n",
    "\n",
    "    if ilp_edges_raw is not None:\n",
    "        ilp_wld = len(ilp_edges_raw)\n",
    "        ilp_str = f\"{ilp_wld}\"\n",
    "    else:\n",
    "        ilp_wld = greedy_wld # fallback for tracking\n",
    "        ilp_str = \"T/O\"\n",
    "\n",
    "    gap = greedy_wld - ilp_wld\n",
    "    print(\n",
    "        f\"{n:>2} | {ilp_str:>5} | {greedy_wld:>6} | {gap:>5} | {ilp_time:>9.4f} | {greedy_time:>9.4f}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ea278263",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Improved Greedy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ddfe7617",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import math\n",
    "\n",
    "header = f\"{'n':>2} | {'Formula':>7} | {'Greedy':>6} | {'Gap':>5} | {'Greedy(s)':>9}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(3, 30):\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    # 1. Run the Improved Greedy Algorithm\n",
    "    start = time.time()\n",
    "    greedy_wld = len(WG.find_greedy_wild_set_improved())\n",
    "    greedy_time = time.time() - start\n",
    "\n",
    "    # 2. Calculate the Theoretical Optimal (Conjecture 3.21)\n",
    "    # Formula: floor(4 * ceil(n / 2) / 3)\n",
    "    formula_wld = math.floor(4 * math.ceil(n / 2) / 3)\n",
    "\n",
    "    # 3. Calculate Gap\n",
    "    gap = greedy_wld - formula_wld\n",
    "\n",
    "    print(\n",
    "        f\"{n:>2} | {formula_wld:>7} | {greedy_wld:>6} | {gap:>5} | {greedy_time:>9.4f}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "30806151",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Worst Case Greedy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "70784bad",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " n | Formula | Greedy |   Gap | Greedy(s)\n",
      "-----------------------------------------\n",
      " 3 |       2 |      2 |     0 |    0.0014\n",
      " 4 |       2 |      2 |     0 |    0.0055\n",
      " 5 |       4 |      4 |     0 |    0.0288\n",
      " 6 |       4 |      4 |     0 |    0.1018\n",
      " 7 |       5 |      6 |     1 |    0.2820\n",
      " 8 |       5 |      6 |     1 |    0.6285\n",
      " 9 |       6 |      7 |     1 |    0.9598\n",
      "10 |       6 |      7 |     1 |    1.7438\n",
      "11 |       8 |     10 |     2 |    5.8791\n",
      "12 |       8 |     10 |     2 |    9.2172\n",
      "13 |       9 |     12 |     3 |   17.7956\n",
      "14 |       9 |     12 |     3 |   33.0720\n",
      "15 |      10 |     13 |     3 |   29.8003\n",
      "16 |      10 |     12 |     2 |   37.8619\n",
      "17 |      12 |     16 |     4 |  117.5548\n",
      "18 |      12 |     16 |     4 | 1749.5253\n",
      "19 |      13 |     18 |     5 |  267.8314\n",
      "20 |      13 |     18 |     5 | 1251.9841\n",
      "21 |      14 |     17 |     3 |  330.8515\n",
      "22 |      14 |     18 |     4 |  510.3249\n",
      "23 |      16 |     22 |     6 |  921.2856\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[31m---------------------------------------------------------------------------\u001b[39m",
      "\u001b[31mKeyboardInterrupt\u001b[39m                         Traceback (most recent call last)",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[12]\u001b[39m\u001b[32m, line 13\u001b[39m\n\u001b[32m      9\u001b[39m     WG = round_robin_proper_coloring(n)\n\u001b[32m     10\u001b[39m \n\u001b[32m     11\u001b[39m     \u001b[38;5;66;03m# 1. Run the Improved Greedy Algorithm\u001b[39;00m\n\u001b[32m     12\u001b[39m     start = time.time()\n\u001b[32m---> \u001b[39m\u001b[32m13\u001b[39m     greedy_wld = len(WG.find_greedy_wild_set_color_momentum())\n\u001b[32m     14\u001b[39m     greedy_time = time.time() - start\n\u001b[32m     15\u001b[39m \n\u001b[32m     16\u001b[39m     \u001b[38;5;66;03m# 2. Calculate the Theoretical Optimal (Conjecture 3.21)\u001b[39;00m\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 260\u001b[39m, in \u001b[36mWildGraph.find_greedy_wild_set_color_momentum\u001b[39m\u001b[34m(self)\u001b[39m\n\u001b[32m    256\u001b[39m                 \u001b[38;5;66;03m# 3. Fallback: Deep lookahead potential function\u001b[39;00m\n\u001b[32m    257\u001b[39m                 \u001b[38;5;28;01mif\u001b[39;00m len(tied_edges) == Integer(\u001b[32m1\u001b[39m):\n\u001b[32m    258\u001b[39m                     best_edge = tied_edges[Integer(\u001b[32m0\u001b[39m)]\n\u001b[32m    259\u001b[39m                 \u001b[38;5;28;01melse\u001b[39;00m:\n\u001b[32m--> \u001b[39m\u001b[32m260\u001b[39m                     potentials = [(self.contracted_dip_sequence(e, current_wild, available_edges), e) \u001b[38;5;28;01mfor\u001b[39;00m e \u001b[38;5;28;01min\u001b[39;00m tied_edges]\n\u001b[32m    261\u001b[39m                     potentials.sort(key=\u001b[38;5;28;01mlambda\u001b[39;00m x: x[Integer(\u001b[32m0\u001b[39m)], reverse=\u001b[38;5;28;01mTrue\u001b[39;00m)\n\u001b[32m    262\u001b[39m                     best_edge = potentials[Integer(\u001b[32m0\u001b[39m)][Integer(\u001b[32m1\u001b[39m)]\n\u001b[32m    263\u001b[39m \n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 100\u001b[39m, in \u001b[36mWildGraph.contracted_dip_sequence\u001b[39m\u001b[34m(self, candidate_edge, current_wild, available_edges)\u001b[39m\n\u001b[32m     96\u001b[39m         hypothetical_wild = current_wild + [candidate_edge]\n\u001b[32m     97\u001b[39m         remaining_edges = [e \u001b[38;5;28;01mfor\u001b[39;00m e \u001b[38;5;28;01min\u001b[39;00m available_edges \u001b[38;5;28;01mif\u001b[39;00m e != candidate_edge]\n\u001b[32m     98\u001b[39m \n\u001b[32m     99\u001b[39m         \u001b[38;5;66;03m# Calculate dips in the conceptually contracted graph and sort descending\u001b[39;00m\n\u001b[32m--> \u001b[39m\u001b[32m100\u001b[39m         future_dips = [self.dip_number(e, hypothetical_wild) \u001b[38;5;28;01mfor\u001b[39;00m e \u001b[38;5;28;01min\u001b[39;00m remaining_edges]\n\u001b[32m    101\u001b[39m         future_dips.sort(reverse=\u001b[38;5;28;01mTrue\u001b[39;00m)\n\u001b[32m    102\u001b[39m \n\u001b[32m    103\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m tuple(future_dips)\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 79\u001b[39m, in \u001b[36mWildGraph.dip_number\u001b[39m\u001b[34m(self, edge, current_wild)\u001b[39m\n\u001b[32m     77\u001b[39m     \u001b[38;5;28;01mdef\u001b[39;00m dip_number(self, edge: Tuple[Any, Ellipsis], current_wild: Optional[List[Tuple[Any, Ellipsis]]] = \u001b[38;5;28;01mNone\u001b[39;00m) -> int:\n\u001b[32m     78\u001b[39m         current_wild = current_wild \u001b[38;5;28;01mor\u001b[39;00m []\n\u001b[32m---> \u001b[39m\u001b[32m79\u001b[39m         before = self.kappa_total(wild_edges=current_wild)\n\u001b[32m     80\u001b[39m         after = self.kappa_total(wild_edges=current_wild + [edge])\n\u001b[32m     81\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m before - after\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 72\u001b[39m, in \u001b[36mWildGraph.kappa_total\u001b[39m\u001b[34m(self, wild_edges)\u001b[39m\n\u001b[32m     70\u001b[39m     \u001b[38;5;28;01mdef\u001b[39;00m kappa_total(self, wild_edges: Optional[List[Tuple[Any, Ellipsis]]] = \u001b[38;5;28;01mNone\u001b[39;00m) -> int:\n\u001b[32m     71\u001b[39m         \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28;01mnot\u001b[39;00m wild_edges: \u001b[38;5;28;01mreturn\u001b[39;00m sum(self.base_kappas.values())\n\u001b[32m---> \u001b[39m\u001b[32m72\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m sum(self.kappa(color, wild_edges) \u001b[38;5;28;01mfor\u001b[39;00m color \u001b[38;5;28;01min\u001b[39;00m self.colors)\n",
      "\u001b[36mFile \u001b[39m\u001b[32m/var/tmp/sage-10.9-current/local/lib/python3.14/site-packages/sage/misc/functional.py:587\u001b[39m, in \u001b[36msymbolic_sum\u001b[39m\u001b[34m(expression, *args, **kwds)\u001b[39m\n\u001b[32m    585\u001b[39m     \u001b[38;5;28;01mreturn\u001b[39;00m expression.sum(*args, **kwds)\n\u001b[32m    586\u001b[39m \u001b[38;5;28;01mif\u001b[39;00m \u001b[38;5;28mmax\u001b[39m(\u001b[38;5;28mlen\u001b[39m(args), \u001b[38;5;28mlen\u001b[39m(kwds)) <= \u001b[32m1\u001b[39m:\n\u001b[32m--> \u001b[39m\u001b[32m587\u001b[39m     \u001b[38;5;28;01mreturn\u001b[39;00m \u001b[30;43msum\u001b[39;49m\u001b[30;43m(\u001b[39;49m\u001b[30;43mexpression\u001b[39;49m\u001b[30;43m,\u001b[39;49m\u001b[30;43m \u001b[39;49m\u001b[30;43m*\u001b[39;49m\u001b[30;43margs\u001b[39;49m\u001b[30;43m,\u001b[39;49m\u001b[30;43m \u001b[39;49m\u001b[30;43m*\u001b[39;49m\u001b[30;43m*\u001b[39;49m\u001b[30;43mkwds\u001b[39;49m\u001b[30;43m)\u001b[39;49m\n\u001b[32m    588\u001b[39m \u001b[38;5;28;01mfrom\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[34;01msage\u001b[39;00m\u001b[34;01m.\u001b[39;00m\u001b[34;01msymbolic\u001b[39;00m\u001b[34;01m.\u001b[39;00m\u001b[34;01mring\u001b[39;00m\u001b[38;5;250m \u001b[39m\u001b[38;5;28;01mimport\u001b[39;00m SR\n\u001b[32m    589\u001b[39m \u001b[38;5;28;01mreturn\u001b[39;00m SR(expression).sum(*args, **kwds)\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 72\u001b[39m, in \u001b[36mWildGraph.kappa_total.<locals>.<genexpr>\u001b[39m\u001b[34m(.0)\u001b[39m\n\u001b[32m---> \u001b[39m\u001b[32m72\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m sum(self.kappa(color, wild_edges) \u001b[38;5;28;01mfor\u001b[39;00m color \u001b[38;5;28;01min\u001b[39;00m self.colors)\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 68\u001b[39m, in \u001b[36mWildGraph.kappa\u001b[39m\u001b[34m(self, color, wild_edges)\u001b[39m\n\u001b[32m     67\u001b[39m     \u001b[38;5;28;01mdef\u001b[39;00m kappa(self, color: Any, wild_edges: Optional[List[Tuple[Any, Ellipsis]]] = \u001b[38;5;28;01mNone\u001b[39;00m) -> int:\n\u001b[32m---> \u001b[39m\u001b[32m68\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m self.monochromatic_subgraph(color, wild_edges).connected_components_number()\n",
      "\u001b[36mCell\u001b[39m\u001b[36m \u001b[39m\u001b[32mIn[11]\u001b[39m\u001b[32m, line 62\u001b[39m, in \u001b[36mWildGraph.monochromatic_subgraph\u001b[39m\u001b[34m(self, color, wild_edges)\u001b[39m\n\u001b[32m     61\u001b[39m     \u001b[38;5;28;01mdef\u001b[39;00m monochromatic_subgraph(self, color: Any, wild_edges: Optional[List[Tuple[Any, Ellipsis]]] = \u001b[38;5;28;01mNone\u001b[39;00m) -> Any:\n\u001b[32m---> \u001b[39m\u001b[32m62\u001b[39m         color_edges = [e \u001b[38;5;28;01mfor\u001b[39;00m e \u001b[38;5;28;01min\u001b[39;00m self.edges \u001b[38;5;28;01mif\u001b[39;00m e[Integer(\u001b[32m2\u001b[39m)] == color]\n\u001b[32m     63\u001b[39m         \u001b[38;5;28;01mreturn\u001b[39;00m self.make_graph(color_edges + list(wild_edges \u001b[38;5;28;01mor\u001b[39;00m []))\n",
      "\u001b[36mFile \u001b[39m\u001b[32mcysignals/signals.pyx:357\u001b[39m, in \u001b[36mcysignals.signals.python_check_interrupt\u001b[39m\u001b[34m()\u001b[39m\n\u001b[32m--> \u001b[39m\u001b[32m357\u001b[39m \u001b[33m'Could not get source, probably due dynamically evaluated source code.'\u001b[39m\n",
      "\u001b[31mKeyboardInterrupt\u001b[39m: "
     ]
    }
   ],
   "source": [
    "import time\n",
    "import math\n",
    "\n",
    "header = f\"{'n':>2} | {'Formula':>7} | {'Greedy':>6} | {'Gap':>5} | {'Greedy(s)':>9}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(3, 30):\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    # 1. Run the Improved Greedy Algorithm\n",
    "    start = time.time()\n",
    "    greedy_wld = len(WG.find_greedy_wild_set_color_momentum())\n",
    "    greedy_time = time.time() - start\n",
    "\n",
    "    # 2. Calculate the Theoretical Optimal (Conjecture 3.21)\n",
    "    # Formula: floor(4 * ceil(n / 2) / 3)\n",
    "    formula_wld = math.floor(4 * math.ceil(n / 2) / 3)\n",
    "\n",
    "    # 3. Calculate Gap\n",
    "    gap = greedy_wld - formula_wld\n",
    "\n",
    "    print(\n",
    "        f\"{n:>2} | {formula_wld:>7} | {greedy_wld:>6} | {gap:>5} | {greedy_time:>9.4f}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bae1b0f2",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Algebraic Tree Packing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a2b284ad",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import math\n",
    "\n",
    "header = f\"{'n':>2} | {'Formula':>7} | {'Optimal':>6} | {'Gap':>5} | {'Optimal(s)':>9}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(9, 30, 2):\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    # 1. Run the Tree Packing Algorithm\n",
    "    start = time.time()\n",
    "    packer = AlgebraicTreePacker(WG)\n",
    "    optimal_edges = packer.solve_perfect_graph()\n",
    "    optimal_time = time.time() - start\n",
    "\n",
    "    # FIX: Define the wild number from the solver's output\n",
    "    optimal_wld = len(optimal_edges)\n",
    "\n",
    "    # 2. Calculate the Theoretical Optimal (Conjecture 3.21)\n",
    "    formula_wld = math.floor(4 * math.ceil(n / 2) / 3)\n",
    "\n",
    "    # 3. Calculate Gap\n",
    "    gap = optimal_wld - formula_wld\n",
    "\n",
    "    print(\n",
    "        f\"{n:>2} | {formula_wld:>7} | {optimal_wld:>6} | {gap:>5} | {optimal_time:>9.4f}\"\n",
    "    )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "49c23b0a",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 13\n",
    "\n",
    "WG = round_robin_proper_coloring(n)\n",
    "\n",
    "# 1. get the ground truth from the ILP\n",
    "print(\"solving ILP for ground truth...\")\n",
    "greedy_upper_bound = len(WG.find_greedy_wild_set_improved())\n",
    "color_map = {WG.normalize_edge(e): e for e in WG.edges}\n",
    "ilp_wild_set = WG.find_milp_wild_set(upper_bound=greedy_upper_bound)\n",
    "ilp_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in ilp_wild_set])\n",
    "\n",
    "print(f\"ILP wld: {len(ilp_wild_set)}\")\n",
    "print(f\"ILP wild set: {ilp_wild_set}\\n\")\n",
    "WG.plot_wild_set(ilp_wild_set)\n",
    "\n",
    "# 2. replay the greedy algorithm manually\n",
    "current_wild = []\n",
    "available_edges = list(WG.edges)\n",
    "step = 1\n",
    "\n",
    "print(\"--- greedy algorithm step-by-step ---\")\n",
    "\n",
    "while not WG.is_color_connecting(current_wild):\n",
    "    # calculate dips for all remaining edges given the current wild set\n",
    "    # eg., [(dip, (u, v, c)), ...]\n",
    "    dips = [(WG.dip_number(e, current_wild), e) for e in available_edges]\n",
    "    max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "\n",
    "    tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "    if len(tied_edges) == 1:\n",
    "        best_edge = tied_edges[0]\n",
    "    else:\n",
    "        # break ties using lexicographic potential (contracted dip sequence)\n",
    "        # eg., [((4, 3, 1), (u, v, c)), ...]\n",
    "        potentials = [(WG.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]\n",
    "        potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "        best_edge = potentials[0][1]\n",
    "\n",
    "    # check if this greedy choice exists anywhere in the optimal ILP set\n",
    "    normalized_choice = WG.normalize_edge(best_edge)\n",
    "    clean_ilp_wild_set = sorted({WG.normalize_edge(e) for e in ilp_wild_set})\n",
    "    is_optimal = normalized_choice in clean_ilp_wild_set\n",
    "\n",
    "    # visually flag divergence\n",
    "    status = \"matched\" if is_optimal else \"divergence\"\n",
    "\n",
    "    print(f\"step {step:02d} | picked edge: {best_edge} | dip number : {max_dip} | ilp status : {status}\")\n",
    "\n",
    "    current_wild.append(best_edge)\n",
    "    available_edges.remove(best_edge)\n",
    "    step += 1\n",
    "\n",
    "print(f\"\\nfinal greedy size: {len(current_wild)}\")\n",
    "print(f\"greedy edges: {current_wild}\")\n",
    "WG.plot_wild_set(current_wild)\n",
    "print(f\"greedy gap: {len(current_wild) - len(ilp_wild_set)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "ed7d2df8",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 13\n",
    "\n",
    "WG = round_robin_proper_coloring(n)\n",
    "\n",
    "# 1. get the ground truth from the ILP\n",
    "print(\"solving ILP for ground truth...\")\n",
    "greedy_upper_bound, _ = WG.wild_number(method=\"greedy\")\n",
    "color_map = {WG.normalize_edge(e): e for e in WG.edges}\n",
    "ilp_wild_set = WG.find_milp_wild_set(upper_bound=greedy_upper_bound)\n",
    "ilp_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in ilp_wild_set])\n",
    "\n",
    "print(f\"ILP wld: {len(ilp_wild_set)}\")\n",
    "print(f\"ILP wild set: {ilp_wild_set}\\n\")\n",
    "WG.plot_wild_set(ilp_wild_set)\n",
    "\n",
    "# 2. replay the greedy algorithm manually\n",
    "current_wild = []\n",
    "available_edges = list(WG.edges)\n",
    "step = 1\n",
    "\n",
    "print(\"--- greedy algorithm step-by-step ---\")\n",
    "\n",
    "while not WG.is_color_connecting(current_wild):\n",
    "    # calculate dips for all remaining edges given the current wild set\n",
    "    # eg., [(dip, (u, v, c)), ...]\n",
    "    dips = [(WG.dip_number(e, current_wild), e) for e in available_edges]\n",
    "    max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "\n",
    "    tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "    if len(tied_edges) == 1:\n",
    "        best_edge = tied_edges[0]\n",
    "    else:\n",
    "        # break ties using lexicographic potential (contracted dip sequence)\n",
    "        # eg., [((4, 3, 1), (u, v, c)), ...]\n",
    "        potentials = [(WG.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]\n",
    "        potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "        best_edge = potentials[0][1]\n",
    "\n",
    "    # check if this greedy choice exists anywhere in the optimal ILP set\n",
    "    normalized_choice = WG.normalize_edge(best_edge)\n",
    "    clean_ilp_wild_set = sorted({WG.normalize_edge(e) for e in ilp_wild_set})\n",
    "    is_optimal = normalized_choice in clean_ilp_wild_set\n",
    "\n",
    "    # visually flag divergence\n",
    "    status = \"matched\" if is_optimal else \"divergence\"\n",
    "\n",
    "    print(f\"step {step:02d} | picked edge: {best_edge} | dip number : {max_dip} | ilp status : {status}\")\n",
    "\n",
    "    current_wild.append(best_edge)\n",
    "    available_edges.remove(best_edge)\n",
    "    step += 1\n",
    "\n",
    "print(f\"\\nfinal greedy size: {len(current_wild)}\")\n",
    "print(f\"greedy edges: {current_wild}\")\n",
    "WG.plot_wild_set(current_wild)\n",
    "print(f\"greedy gap: {len(current_wild) - len(ilp_wild_set)}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c60d3dcd",
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "import math\n",
    "\n",
    "plots = []\n",
    "\n",
    "for n in range(3, 24):\n",
    "    ell = n if (n % 2 == 1) else (n - 1)\n",
    "    print(f\"=== K_{n} | ell = {ell} ===\")\n",
    "\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    # 1. run greedy and time it\n",
    "    start = time.time()\n",
    "    greedy_upper_bound, _ = WG.wild_number(method=\"greedy\")\n",
    "    greedy_time = time.time() - start\n",
    "\n",
    "    # 2. run ilp and time it\n",
    "    start = time.time()\n",
    "    ilp_edges_raw = WG.find_milp_wild_set(upper_bound=greedy_upper_bound)\n",
    "    ilp_time = time.time() - start\n",
    "\n",
    "    if ilp_edges_raw is None:\n",
    "        print(f\"[error] ILP failed or timed out. skipping K_{n}.\\n\")\n",
    "        continue\n",
    "\n",
    "    # map geometry back to color instantly for ILP\n",
    "    color_map = {WG.normalize_edge(e): e for e in WG.edges}\n",
    "    ilp_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in ilp_edges_raw])\n",
    "    ilp_normalized = {WG.normalize_edge(e) for e in ilp_wild_set}\n",
    "\n",
    "    # 3. run exact solver with the dynamic timeout\n",
    "    exact_wild_set = []\n",
    "\n",
    "    if n <= 10:\n",
    "        allowed_exact_time = greedy_time + ilp_time + 60.0\n",
    "        start = time.time()\n",
    "        exact_edges_raw = WG.find_exact_wild_set(timeout=allowed_exact_time)\n",
    "        exact_time = time.time() - start\n",
    "\n",
    "        if exact_edges_raw is not None:\n",
    "            exact_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in exact_edges_raw])\n",
    "            exact_title = f\"K_{n} Exact (wld={len(exact_wild_set)})\"\n",
    "            print(f\"exact  | wld: {len(exact_wild_set):02d} | W: {exact_wild_set}\")\n",
    "        else:\n",
    "            exact_title = f\"K_{n} Exact (T/O)\"\n",
    "            print(f\"exact  | T/O (> {allowed_exact_time:.1f}s)\")\n",
    "    else:\n",
    "        # Skip the exact solver for n > 10 to save time\n",
    "        exact_title = f\"K_{n} Exact (Skipped)\"\n",
    "        print(f\"exact  | Skipped (n > 10)\")\n",
    "\n",
    "    # 4. replay the greedy algorithm manually\n",
    "    current_wild = []\n",
    "    available_edges = list(WG.edges)\n",
    "\n",
    "    greedy_dips = []\n",
    "    divergence_steps = []\n",
    "\n",
    "    while not WG.is_color_connecting(current_wild):\n",
    "        dips = [(WG.dip_number(e, current_wild), e) for e in available_edges]\n",
    "        max_dip = max(dips, key=lambda x: x[0])[0]\n",
    "        tied_edges = [e for d, e in dips if d == max_dip]\n",
    "\n",
    "        if len(tied_edges) == 1:\n",
    "            best_edge = tied_edges[0]\n",
    "        else:\n",
    "            potentials = [(WG.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]\n",
    "            potentials.sort(key=lambda x: x[0], reverse=True)\n",
    "            best_edge = potentials[0][1]\n",
    "\n",
    "        # track if this was a trap using the ILP ground truth\n",
    "        if WG.normalize_edge(best_edge) not in ilp_normalized:\n",
    "            divergence_steps.append(len(current_wild) + 1)\n",
    "\n",
    "        greedy_dips.append(max_dip)\n",
    "        current_wild.append(best_edge)\n",
    "        available_edges.remove(best_edge)\n",
    "\n",
    "    gap = len(current_wild) - len(ilp_wild_set)\n",
    "\n",
    "    # 5. condensed output\n",
    "    print(f\"ilp    | wld: {len(ilp_wild_set):02d} | W: {ilp_wild_set}\")\n",
    "    print(f\"greedy | wld: {len(current_wild):02d} | W: {current_wild}\")\n",
    "    print(f\"gap    | {gap}\")\n",
    "\n",
    "    if gap > 0:\n",
    "        print(f\"alert  | divergences occurred at steps: {divergence_steps}\")\n",
    "        print(f\"alert  | greedy dip sequence: {greedy_dips}\")\n",
    "    print(\"\")\n",
    "\n",
    "    # 6. generate the plots for all three solvers\n",
    "    p_exact = WG.plot_colored(title=exact_title, wild_edges=exact_wild_set, show=False)\n",
    "    p_ilp = WG.plot_colored(title=f\"K_{n} ILP (wld={len(ilp_wild_set)})\", wild_edges=ilp_wild_set, show=False)\n",
    "    p_greedy = WG.plot_colored(title=f\"K_{n} Greedy (wld={len(current_wild)})\", wild_edges=current_wild, show=False)\n",
    "\n",
    "    # append the trio to the master list\n",
    "    plots.extend([p_exact, p_ilp, p_greedy])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "657547ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "if plots:\n",
    "    print(\"rendering master topology grid (Exact | ILP | Greedy)...\")\n",
    "    grid = graphics_array(plots, ncols=6)\n",
    "    grid.show(figsize=(48, 48))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c71f2554",
   "metadata": {},
   "outputs": [],
   "source": [
    "num_samples = 5\n",
    "\n",
    "for n in range(3, 16):\n",
    "    ell = n if (n % 2 == 1) else (n - 1)\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    wlds_found = set()\n",
    "\n",
    "    print(f\"\\nK_{n} | ell={ell}\")\n",
    "\n",
    "    # generate structurally distinct proper colorings\n",
    "    for i, WG in enumerate(generate_diverse_proper_colorings(G, ell, max_yields=num_samples)):\n",
    "        wild_number, wild_edges = WG.wild_number()\n",
    "\n",
    "        wlds_found.add(wild_number)\n",
    "\n",
    "    print(f\"found wlds = {wlds_found}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4f315385",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 16\n",
    "ell = n if (n % 2 == 1) else (n - 1)\n",
    "\n",
    "WG = round_robin_proper_coloring(n)\n",
    "\n",
    "wild_number, wild_edges = WG.wild_number()\n",
    "WG.plot_colored(\n",
    "    title=f\"K_{n} | ell = {ell} | wld = {wild_number}\",\n",
    "    wild_edges=wild_edges,\n",
    "    show=True\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c13d55a7",
   "metadata": {},
   "outputs": [],
   "source": [
    "WG.plot_colored(wild_edges)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "b3f6a02b",
   "metadata": {},
   "outputs": [],
   "source": [
    "plots = []\n",
    "for n in range(3, 20):\n",
    "    ell = n if (n % 2 == 1) else (n - 1)\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    wild_number, wild_edges = WG.wild_number(method=\"milp\")\n",
    "    plots.append(WG.plot_colored(\n",
    "        title=f\"K_{n} | ell = {ell} | wld = {wild_number}\",\n",
    "        wild_edges=wild_edges,\n",
    "        show=False)\n",
    "    )\n",
    "\n",
    "grid = graphics_array(plots, ncols=num_samples)\n",
    "grid.show(figsize=(8, 8))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "adbc5667",
   "metadata": {},
   "outputs": [],
   "source": [
    "n = 16\n",
    "ell = n if (n % 2 == 1) else (n - 1)\n",
    "num_samples = 5\n",
    "\n",
    "G = graphs.CompleteGraph(n)\n",
    "colorings = generate_diverse_proper_colorings(G, ell, max_yields=num_samples)\n",
    "\n",
    "plots = []\n",
    "for i, WG in enumerate(colorings):\n",
    "    wild_number, wild_edges = WG.wild_number()\n",
    "    plots.append(WG.plot_colored(title=f\"Sample {i+1:02d}: wld = {wild_number}\", wild_edges=wild_edges, show=False))\n",
    "\n",
    "grid = graphics_array(plots, ncols=num_samples)\n",
    "grid.show(figsize=(num_samples * 5, num_samples * 5))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e51da5d5",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Conjecture: $\\mathrm{wld}\\rho(K_n) = \\left\\lfloor \\frac{4\\lceil n/2 \\rceil}{3}\\right\\rfloor$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "678887b0",
   "metadata": {},
   "outputs": [],
   "source": [
    "header = f\"{'n':>2} | {'k':>2} | {'conj':>6} | {'wld':>6}\"\n",
    "print(header)\n",
    "print(\"-\" * len(header))\n",
    "\n",
    "for n in range(3, 20):\n",
    "    k = math.ceil(n / 2)\n",
    "    conj = int(4 * k // 3)\n",
    "\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    greedy_wld, _ = WG.wild_number(method=\"greedy\")\n",
    "    ilp_edges = WG.find_milp_wild_set(upper_bound=greedy_wld)\n",
    "    ilp_wld = len(ilp_edges)\n",
    "\n",
    "    print(f\"{n:>2} | {k:>2} | {conj:>6} | {ilp_wld:>6}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8712ad0c",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Coloring-Invariant Bounds"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "40bd894e",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(3, 12):\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "\n",
    "    clb, cub = WG.component_bounds()\n",
    "    ceil_lb = WG.ceiling_lower_bound()\n",
    "    dip_lb = WG.dip_lower_bound()\n",
    "\n",
    "    # predicted values\n",
    "    kappa = (n+1)//2 if n % 2 != 0 else n//2\n",
    "    pred_clb = kappa - 1\n",
    "    pred_cub = ell * (kappa - 1)\n",
    "    pred_ceil = math.ceil(n/2)\n",
    "\n",
    "    match = (clb==pred_clb and cub==pred_cub and ceil_lb==pred_ceil and dip_lb==pred_ceil)\n",
    "    print(f\"K_{n}: clb={clb}(={pred_clb}), cub={cub}(={pred_cub}), \"\n",
    "          f\"ceil={ceil_lb}(={pred_ceil}), dip={dip_lb} | match={match}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9c9be829",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Uniform Dip Numbers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7b75892f",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(3, 20):\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    dips = set(d for d, _ in WG.get_all_dip_numbers())\n",
    "    conj = dips == {ell-1}\n",
    "    print(f\"K_{n} | dip = {dips} | expected = {{{ell-1}}} | conj = {conj}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "66c0dd82",
   "metadata": {
    "vscode": {
     "languageId": "python"
    }
   },
   "source": [
    "### Structural Analysis of Wild Set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "95ea42df",
   "metadata": {},
   "outputs": [],
   "source": [
    "def disjoint_star_wild_set(WG, n):\n",
    "    \"\"\"\n",
    "    Attempt to build a wild set as disjoint stars.\n",
    "    For odd n: place stars at every 3rd vertex, size 2 each,\n",
    "    plus handle remainder.\n",
    "    \"\"\"\n",
    "    k = math.ceil(n / 2)\n",
    "    target = int(4 * k // 3)\n",
    "\n",
    "    # find isolated vertex for each color\n",
    "    isolated = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated[color] = v\n",
    "                break\n",
    "\n",
    "    # print(f\"isolated vertices: {isolated}\")\n",
    "    # print(f\"target wld: {target}\")\n",
    "\n",
    "    # each vertex v is isolated in exactly one color\n",
    "    # verify this\n",
    "    isolated_inv = {}  # vertex -> color it's isolated in\n",
    "    for color, v in isolated.items():\n",
    "        isolated_inv[v] = color\n",
    "\n",
    "    print(f\"each vertex isolated in one color: {len(isolated_inv) == n}\")\n",
    "    return isolated, isolated_inv\n",
    "\n",
    "for n in range(3, 17, 2):\n",
    "    print(f\"K_{n} | \", end=\"\")\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    iso, iso_inv = disjoint_star_wild_set(WG, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "021c37f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "def analyze_wild_set_structure(WG, wild_set):\n",
    "    \"\"\"Check if wild set forms a spanning forest of disjoint stars.\"\"\"\n",
    "    degree = {}\n",
    "    for u, v in wild_set:\n",
    "        degree[u] = degree.get(u, 0) + 1\n",
    "        degree[v] = degree.get(v, 0) + 1\n",
    "\n",
    "    # identify hubs (degree > 1) and leaves (degree 1)\n",
    "    hubs  = {v: d for v, d in degree.items() if d > 1}\n",
    "    leaves = {v: d for v, d in degree.items() if d == 1}\n",
    "\n",
    "    # check vertex coverage\n",
    "    covered = set(degree.keys())\n",
    "    all_vertices = set(WG.vertices)\n",
    "\n",
    "    # check it's a forest of stars (no vertex appears as both hub and leaf)\n",
    "    is_star_forest = len(hubs.keys() & leaves.keys()) == 0\n",
    "\n",
    "    print(f\"  |W| = {len(wild_set)}\")\n",
    "    print(f\"  hubs:     {dict(sorted(hubs.items()))}\")\n",
    "    print(f\"  leaves:   {sorted(leaves.keys())}\")\n",
    "    print(f\"  vertex cover: {len(covered)}/{len(all_vertices)}\")\n",
    "    print(f\"  star forest: {is_star_forest}\")\n",
    "    print(f\"  num stars: {len(hubs)}\")\n",
    "\n",
    "for n in range(5, 12):\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    greedy_ub, _ = WG.wild_number(method=\"greedy\")\n",
    "    wild_set = WG.find_milp_wild_set(upper_bound=greedy_ub)\n",
    "    print(f\"\\nK_{n}:\")\n",
    "    analyze_wild_set_structure(WG, wild_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e58c9cc8",
   "metadata": {},
   "outputs": [],
   "source": [
    "def optimal_star_forest(n):\n",
    "    \"\"\"\n",
    "    Build the optimal star forest for K_n.\n",
    "    For odd n or n divisible by 3: span all n vertices.\n",
    "    For even n not divisible by 3: span n-1 vertices.\n",
    "    \"\"\"\n",
    "    if n % 2 == 1 or n % 3 == 0:\n",
    "        v = n       # span all vertices\n",
    "    else:\n",
    "        v = n - 1   # leave one vertex out\n",
    "\n",
    "    t = v // 3      # number of stars\n",
    "    if t == 0:\n",
    "        t = 1\n",
    "\n",
    "    stars = []\n",
    "    idx = 0\n",
    "    for i in range(t):\n",
    "        size = v // t + (1 if i < v % t else 0)\n",
    "        stars.append(list(range(idx, idx + size)))\n",
    "        idx += size\n",
    "\n",
    "    edges = sum(len(s) - 1 for s in stars)\n",
    "    print(f\"K_{n}: {t} stars on {v} vertices, \"\n",
    "          f\"sizes {[len(s) for s in stars]}, edges={edges}, \"\n",
    "          f\"formula={int(4 * math.ceil(n/2) // 3)}, match={edges == int(4*math.ceil(n/2)//3)}\")\n",
    "    return stars"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "020fb983",
   "metadata": {},
   "outputs": [],
   "source": [
    "for n in range(3, 16):\n",
    "    optimal_star_forest(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fc97426f",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_optimal_forest_validity(n, num_colorings=20):\n",
    "    \"\"\"\n",
    "    For several proper colorings of K_n, check whether\n",
    "    the optimal_star_forest construction is color-connecting.\n",
    "    \"\"\"\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    stars = optimal_star_forest(n)\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    valid_sets = []\n",
    "    failed = []\n",
    "\n",
    "    for i, WG in enumerate(generate_diverse_proper_colorings(\n",
    "        G, ell, max_yields=num_colorings\n",
    "    )):\n",
    "        wild_set = []\n",
    "        for star in stars:\n",
    "            hub = star[0]\n",
    "            for leaf in star[1:]:\n",
    "                for u, v, c in WG.edges:\n",
    "                    if set([u, v]) == set([hub, leaf]):\n",
    "                        wild_set.append((u, v, c))\n",
    "                        break\n",
    "\n",
    "        valid = WG.is_color_connecting(wild_set)\n",
    "\n",
    "        if valid:\n",
    "            valid_sets.append(wild_set)\n",
    "        else:\n",
    "            failed.append((i, WG, wild_set))\n",
    "\n",
    "    total = len(valid_sets) + len(failed)\n",
    "    status = \"✓ ALL VALID\" if not failed else f\"✗ {len(failed)} FAILURES\"\n",
    "    print(f\"K_{n} | {status} | {len(valid_sets)}/{total} colorings\")\n",
    "\n",
    "    if failed:\n",
    "        print(f\"  first failure at coloring {failed[0][0] + 1}\")\n",
    "\n",
    "for n in range(3, 16, 2):\n",
    "    test_optimal_forest_validity(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "278b91b7",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_adapted_forest_validity(n, num_colorings=20):\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    t = n // 3\n",
    "    valid_count = 0\n",
    "    total = 0\n",
    "\n",
    "    for WG in generate_diverse_proper_colorings(G, ell, max_yields=num_colorings):\n",
    "        total += 1\n",
    "\n",
    "        # find isolated vertex for each color\n",
    "        isolated = {}\n",
    "        for color in WG.colors:\n",
    "            M = WG.monochromatic_subgraph(color)\n",
    "            for v in WG.vertices:\n",
    "                if M.degree(v) == 0:\n",
    "                    isolated[color] = v\n",
    "                    break\n",
    "\n",
    "        # choose t colors deterministically, take their isolated vertices as hubs\n",
    "        hub_colors = sorted(WG.colors)[:t]           # sort for determinism\n",
    "        hub_list = [isolated[c] for c in hub_colors]\n",
    "        hubs = set(hub_list)\n",
    "\n",
    "        # assign remaining vertices to hubs as evenly as possible\n",
    "        leaves = [v for v in sorted(WG.vertices) if v not in hubs]\n",
    "        assignment = {h: [h] for h in hub_list}\n",
    "        for i, leaf in enumerate(leaves):\n",
    "            assignment[hub_list[i % t]].append(leaf)\n",
    "\n",
    "        # build wild set\n",
    "        wild_set = []\n",
    "        for hub, star in assignment.items():\n",
    "            for leaf in star[1:]:\n",
    "                for u, v, c in WG.edges:\n",
    "                    if set([u, v]) == set([hub, leaf]):\n",
    "                        wild_set.append((u, v, c))\n",
    "                        break\n",
    "\n",
    "        valid = WG.is_color_connecting(wild_set)\n",
    "        if valid:\n",
    "            valid_count += 1\n",
    "        else:\n",
    "            print(f\"  K_{n} coloring {total}: FAILS | hubs={hubs}\")\n",
    "\n",
    "    print(f\"K_{n}: {valid_count}/{total} valid with adapted construction\\n\")\n",
    "\n",
    "for n in range(3, 16, 2):\n",
    "    test_adapted_forest_validity(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8bbc27c6",
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_valid_hub_selection(WG, n, verbose=True):\n",
    "    \"\"\"\n",
    "    Try ALL possible selections of floor(n/3) vertices as hubs.\n",
    "    Tests all possible leaf assignments too.\n",
    "    \"\"\"\n",
    "    from itertools import combinations, permutations\n",
    "\n",
    "    t = n // 3\n",
    "\n",
    "    # find isolated vertices\n",
    "    isolated_by_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_by_color[color] = v\n",
    "                break\n",
    "\n",
    "    valid_hubs = []\n",
    "\n",
    "    # try all possible hub vertex sets\n",
    "    for hub_combo in combinations(range(n), t):\n",
    "        hubs = set(hub_combo)\n",
    "        hub_list = list(hub_combo)\n",
    "        leaves = [v for v in sorted(WG.vertices) if v not in hubs]\n",
    "\n",
    "        # try round-robin leaf assignment\n",
    "        assignment = {h: [h] for h in hub_list}\n",
    "        for i, leaf in enumerate(leaves):\n",
    "            assignment[hub_list[i % t]].append(leaf)\n",
    "\n",
    "        wild_set = []\n",
    "        for hub, star in assignment.items():\n",
    "            for leaf in star[1:]:\n",
    "                for u, v, c in WG.edges:\n",
    "                    if set([u, v]) == set([hub, leaf]):\n",
    "                        wild_set.append((u, v, c))\n",
    "                        break\n",
    "\n",
    "        if WG.is_color_connecting(wild_set):\n",
    "            valid_hubs.append(hub_combo)\n",
    "\n",
    "    if verbose:\n",
    "        print(f\"  valid hub selections: {len(valid_hubs)} / {binomial(n,t)}\")\n",
    "        print(f\"  isolated vertices:    {isolated_by_color}\")\n",
    "        if valid_hubs:\n",
    "            print(f\"  first valid hubs:     {valid_hubs[0]}\")\n",
    "        # check: do valid hubs always use isolated vertices?\n",
    "        iso_verts = set(isolated_by_color.values())\n",
    "        hub_from_iso = [h for h in valid_hubs if set(h).issubset(iso_verts)]\n",
    "        print(f\"  valid hubs that are isolated vertices: {len(hub_from_iso)}\")\n",
    "\n",
    "    return valid_hubs\n",
    "\n",
    "# test on K_7 and K_9\n",
    "for n in [7, 9, 11]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "    print(f\"\\nK_{n}:\")\n",
    "    for WG in generate_diverse_proper_colorings(G, ell, max_yields=3):\n",
    "        find_valid_hub_selection(WG, n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "e849d3da",
   "metadata": {},
   "outputs": [],
   "source": [
    "def search_color_connecting_partition_pruned(WG):\n",
    "    # each vertex is isolated in exactly one color (Lemma bijection)\n",
    "    isolated_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_color[v] = color\n",
    "                break\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    def is_good_triple(triple):\n",
    "        # Lemma: {iso, a, b} is bad iff iso = v_c for some color c and rho(ab) = c\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def to_wild(partition):\n",
    "        wild = []\n",
    "        for t in partition:\n",
    "            tl = list(t)\n",
    "            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:\n",
    "                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))\n",
    "        return wild\n",
    "\n",
    "    def search(remaining, partition):\n",
    "        if not remaining:\n",
    "            return partition if WG.is_color_connecting(to_wild(partition)) else None\n",
    "        first = min(remaining)\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if not is_good_triple(triple):      # <-- the lemma, as a prune\n",
    "                continue\n",
    "            res = search(remaining - set(triple), partition + [triple])\n",
    "            if res is not None:\n",
    "                return res\n",
    "        return None\n",
    "\n",
    "    return search(set(WG.vertices), [])\n",
    "\n",
    "for n in [9, 15, 21]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ok = total = 0\n",
    "    for WG in generate_diverse_proper_colorings(G, n, max_yields=10):\n",
    "        total += 1\n",
    "        if search_color_connecting_partition_pruned(WG):\n",
    "            ok += 1\n",
    "    print(f\"K_{n}: color-connecting partition found {ok}/{total}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "0a02c284",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_canonical_construction(n, num_colorings=15):\n",
    "    \"\"\"\n",
    "    Place hubs at isolated vertices, attach remaining vertices as leaves,\n",
    "    check whether THIS specific star forest is color-connecting.\n",
    "    Reports failures and whether a different hub choice would have worked.\n",
    "    \"\"\"\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ell = n if n % 2 else n - 1\n",
    "    t = n // 3\n",
    "    valid = total = 0\n",
    "    failures = []\n",
    "\n",
    "    for WG in generate_diverse_proper_colorings(G, ell, max_yields=num_colorings):\n",
    "        total += 1\n",
    "        isolated = {}\n",
    "        for color in WG.colors:\n",
    "            M = WG.monochromatic_subgraph(color)\n",
    "            for v in WG.vertices:\n",
    "                if M.degree(v) == 0:\n",
    "                    isolated[color] = v\n",
    "                    break\n",
    "\n",
    "        # canonical: pick t colors' isolated vertices as hubs\n",
    "        hub_colors = sorted(WG.colors)[:t]\n",
    "        hubs = [isolated[c] for c in hub_colors]\n",
    "        leaves = [v for v in sorted(WG.vertices) if v not in set(hubs)]\n",
    "\n",
    "        assignment = {h: [h] for h in hubs}\n",
    "        for i, leaf in enumerate(leaves):\n",
    "            assignment[hubs[i % t]].append(leaf)\n",
    "\n",
    "        edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "        wild = []\n",
    "        for h, star in assignment.items():\n",
    "            for leaf in star[1:]:\n",
    "                wild.append((h, leaf, edge_color[WG.normalize_edge((h, leaf))]))\n",
    "\n",
    "        if WG.is_color_connecting(wild):\n",
    "            valid += 1\n",
    "        else:\n",
    "            failures.append(WG)\n",
    "\n",
    "    status = \"✓ all valid\" if not failures else f\"✗ {len(failures)} failures\"\n",
    "    print(f\"K_{n}: {valid}/{total} {status}\")\n",
    "    return failures\n",
    "\n",
    "for n in [9, 15, 21]:\n",
    "    test_canonical_construction(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7454dc16",
   "metadata": {},
   "outputs": [],
   "source": [
    "def good_vs_connected(WG, max_good=300):\n",
    "    isolated_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_color[v] = color\n",
    "                break\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    def is_good_triple(triple):\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def to_wild(partition):\n",
    "        wild = []\n",
    "        for tr in partition:\n",
    "            tl = list(tr)\n",
    "            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:\n",
    "                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))\n",
    "        return wild\n",
    "\n",
    "    counts = {\"good\": 0, \"disconnected\": 0}\n",
    "\n",
    "    def search(remaining, partition):\n",
    "        if counts[\"good\"] >= max_good:\n",
    "            return\n",
    "        if not remaining:\n",
    "            counts[\"good\"] += 1\n",
    "            if not WG.is_color_connecting(to_wild(partition)):\n",
    "                counts[\"disconnected\"] += 1\n",
    "            return\n",
    "        first = min(remaining)\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if is_good_triple(triple):\n",
    "                search(remaining - set(triple), partition + [triple])\n",
    "                if counts[\"good\"] >= max_good:\n",
    "                    return\n",
    "\n",
    "    search(set(WG.vertices), [])\n",
    "    return counts[\"good\"], counts[\"disconnected\"]\n",
    "\n",
    "for n in [9, 15, 21]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    tot_good = tot_disc = 0\n",
    "    for WG in generate_diverse_proper_colorings(G, n, max_yields=8):\n",
    "        g, d = good_vs_connected(WG, max_good=300)\n",
    "        tot_good += g\n",
    "        tot_disc += d\n",
    "    print(f\"K_{n}: good sampled={tot_good}, good-but-disconnected={tot_disc}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "47f712f5",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def internal_edge_diagnosis(WG, max_good=150):\n",
    "    isolated_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_color[v] = color\n",
    "                break\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    def is_good_triple(triple):\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    stat = defaultdict(lambda: [0, 0])  # internal_count -> [connected, disconnected]\n",
    "    counter = {\"n\": 0}\n",
    "\n",
    "    def analyze(partition):\n",
    "        comp_of = {v: i for i, tr in enumerate(partition) for v in tr}\n",
    "        t = len(partition)\n",
    "        for color in WG.colors:\n",
    "            M = WG.monochromatic_subgraph(color)\n",
    "            internal = 0\n",
    "            Q = Graph(); Q.add_vertices(range(t))\n",
    "            for u, v in M.edges(labels=False):\n",
    "                cu, cv = comp_of[u], comp_of[v]\n",
    "                if cu == cv:\n",
    "                    internal += 1\n",
    "                else:\n",
    "                    Q.add_edge(cu, cv)\n",
    "            connected = Q.connected_components_number() == 1\n",
    "            stat[internal][0 if connected else 1] += 1\n",
    "\n",
    "    def search(remaining, partition):\n",
    "        if counter[\"n\"] >= max_good:\n",
    "            return\n",
    "        if not remaining:\n",
    "            counter[\"n\"] += 1\n",
    "            analyze(partition)\n",
    "            return\n",
    "        first = min(remaining)\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if is_good_triple(triple):\n",
    "                search(remaining - set(triple), partition + [triple])\n",
    "                if counter[\"n\"] >= max_good:\n",
    "                    return\n",
    "\n",
    "    search(set(WG.vertices), [])\n",
    "    return stat\n",
    "\n",
    "for n in [15, 21]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    agg = defaultdict(lambda: [0, 0])\n",
    "    for WG in generate_diverse_proper_colorings(G, n, max_yields=6):\n",
    "        s = internal_edge_diagnosis(WG)\n",
    "        for k, (c, d) in s.items():\n",
    "            agg[k][0] += c; agg[k][1] += d\n",
    "    print(f\"K_{n}: internal_edges -> [connected, disconnected]\")\n",
    "    for k in sorted(agg):\n",
    "        c, d = agg[k]\n",
    "        print(f\"  {k}: connected={c}, disconnected={d}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f7c4c616",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from itertools import combinations\n",
    "\n",
    "def all_color_connecting_partitions(WG, cap=3000):\n",
    "    isolated_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_color[v] = color\n",
    "                break\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    def is_good_triple(triple):\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def to_wild(partition):\n",
    "        wild = []\n",
    "        for tr in partition:\n",
    "            tl = list(tr)\n",
    "            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:\n",
    "                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))\n",
    "        return wild\n",
    "\n",
    "    sols = []\n",
    "    def search(remaining, partition):\n",
    "        if len(sols) >= cap:\n",
    "            return\n",
    "        if not remaining:\n",
    "            if WG.is_color_connecting(to_wild(partition)):\n",
    "                sols.append(frozenset(frozenset(t) for t in partition))\n",
    "            return\n",
    "        first = min(remaining)\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if is_good_triple(triple):\n",
    "                search(remaining - set(triple), partition + [triple])\n",
    "                if len(sols) >= cap:\n",
    "                    return\n",
    "    search(set(WG.vertices), [])\n",
    "    return sols\n",
    "\n",
    "def within_coloring_invariants(WG):\n",
    "    sols = all_color_connecting_partitions(WG)\n",
    "    total = len(sols)\n",
    "    pair_count = Counter()\n",
    "    for P in sols:\n",
    "        for triple in P:\n",
    "            for a, b in combinations(sorted(triple), 2):\n",
    "                pair_count[(a, b)] += 1\n",
    "    always = [p for p, c in pair_count.items() if c == total]\n",
    "    never  = [(a, b) for a in WG.vertices for b in WG.vertices\n",
    "              if a < b and (a, b) not in pair_count]\n",
    "    print(f\"  solutions: {total} | forced-together pairs: {len(always)} \"\n",
    "          f\"| forbidden pairs: {len(never)}\")\n",
    "    # relate forced pairs to color structure\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "    if always:\n",
    "        forced_colors = Counter(edge_color[WG.normalize_edge(p)] for p in always)\n",
    "        print(f\"  forced pairs by edge color: {dict(forced_colors)}\")\n",
    "    return sols\n",
    "\n",
    "for n in [9, 15, 21]:\n",
    "    print(f\"K_{n}:\")\n",
    "    WG = round_robin_proper_coloring(n)\n",
    "    within_coloring_invariants(WG)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "818ce66d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def study(n, num_colorings=4, num_random=200):\n",
    "    \"\"\"\n",
    "    For a single n: compare the optimal wild set's worst-color internal load\n",
    "    against random size-matched partitions, to see if internal load separates\n",
    "    'connects' from 'disconnects'.\n",
    "    \"\"\"\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    ell = n if n % 2 else n - 1        # colors in a minimal proper coloring\n",
    "    v, sizes = forest_spec(n)\n",
    "    target = int(4 * math.ceil(n / 2) // 3)   # conjectured wild number\n",
    "    print(f\"K_{n}: spans {v} verts, sizes={sizes}, |W|={v - len(sizes)} (target {target})\")\n",
    "\n",
    "    # diverse colorings (Kempe-swap walk), NOT just round-robin\n",
    "    for idx, WG in enumerate(generate_diverse_proper_colorings(G, ell, max_yields=num_colorings)):\n",
    "\n",
    "        # optimal solution's worst-color internal load\n",
    "        og = optimal_groups(WG)\n",
    "        if og is None:\n",
    "            print(f\"  c{idx+1}: MILP T/O\")     # solver timed out; skip\n",
    "            continue\n",
    "        opt_max = max(color_loads(WG, og).values())\n",
    "\n",
    "        # random size-matched partitions for contrast\n",
    "        verts = list(WG.vertices)\n",
    "        good_max, bad_max, succ = [], [], 0\n",
    "        for _ in range(num_random):\n",
    "            random.shuffle(verts)\n",
    "            spanned = verts[:v]                # even n: last vertex dropped\n",
    "            groups, j = [], 0\n",
    "            for s in sizes:                    # carve into prescribed sizes\n",
    "                groups.append(spanned[j:j + s])\n",
    "                j += s\n",
    "            m = max(color_loads(WG, groups).values())   # this partition's worst load\n",
    "            if WG.is_color_connecting(groups_to_wild(groups)):\n",
    "                succ += 1\n",
    "                good_max.append(m)             # connected\n",
    "            else:\n",
    "                bad_max.append(m)              # disconnected\n",
    "\n",
    "        mean = lambda xs: f\"{float(sum(xs)) / len(xs):.2f}\" if xs else \"--\"\n",
    "        pct  = float(100 * succ) / num_random\n",
    "\n",
    "        print(f\"  c{idx+1}: opt max-load={opt_max} | \"\n",
    "              f\"random valid={pct:4.1f}% | \"\n",
    "              f\"max-load: valid={mean(good_max)} invalid={mean(bad_max)}\")\n",
    "\n",
    "for n in range(6, 17):\n",
    "    study(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "58d5f3bc",
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "from itertools import combinations\n",
    "\n",
    "def binding_constraint_orders(WG, max_good=400):\n",
    "    \"\"\"\n",
    "    Among GOOD triple partitions that still DISCONNECT, record the size (in # of\n",
    "    triples) of the smallest closed union for each disconnected color.\n",
    "\n",
    "    A disconnected color = a proper union U of triples closed under M_i.\n",
    "    The size of the SMALLEST such U is the 'order' of the binding constraint:\n",
    "        order 1 -> single triple closed   (= the goodness lemma; pruned out below)\n",
    "        order 2 -> a closed PAIR of triples (the first new local constraint)\n",
    "        order k -> k triples jointly closed\n",
    "    Low orders dominating => a few local rules nearly suffice.\n",
    "    High orders needed   => connectivity is irreducibly global.\n",
    "    \"\"\"\n",
    "    # vertex -> unique color it is isolated in (bijection, odd n)\n",
    "    isolated_color = {}\n",
    "    for color in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(color)\n",
    "        for v in WG.vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                isolated_color[v] = color\n",
    "                break\n",
    "\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    def is_good_triple(triple):\n",
    "        # the k=1 constraint: a triple {v_i, a, b} is bad iff rho(ab) = c_i\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    order_hist = Counter()      # binding order -> count\n",
    "\n",
    "    def analyze(partition):\n",
    "        comp_of = {v: i for i, tr in enumerate(partition) for v in tr}  # vertex -> super-node\n",
    "        t = len(partition)\n",
    "        for color in WG.colors:\n",
    "            M = WG.monochromatic_subgraph(color)\n",
    "            Q = Graph(); Q.add_vertices(range(t))           # quotient on super-nodes\n",
    "            for u, v in M.edges(labels=False):\n",
    "                a, b = comp_of[u], comp_of[v]\n",
    "                if a != b:\n",
    "                    Q.add_edge(a, b)                        # a crossing M_i-edge\n",
    "            comps = Q.connected_components()\n",
    "            if len(comps) > 1:                              # color disconnects\n",
    "                order_hist[min(len(c) for c in comps)] += 1 # smallest closed union\n",
    "\n",
    "    # DFS over GOOD partitions only (k=1 used as a prune), as in your earlier search\n",
    "    counter = {\"n\": 0}\n",
    "    def search(remaining, partition):\n",
    "        if counter[\"n\"] >= max_good:\n",
    "            return\n",
    "        if not remaining:\n",
    "            counter[\"n\"] += 1\n",
    "            analyze(partition)\n",
    "            return\n",
    "        first = min(remaining)\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if is_good_triple(triple):\n",
    "                search(remaining - set(triple), partition + [triple])\n",
    "                if counter[\"n\"] >= max_good:\n",
    "                    return\n",
    "\n",
    "    search(set(WG.vertices), [])\n",
    "    return order_hist\n",
    "\n",
    "for n in [9, 15, 21]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    agg = Counter()\n",
    "    for WG in generate_diverse_proper_colorings(G, n, max_yields=6):\n",
    "        agg += binding_constraint_orders(WG)\n",
    "    tot = sum(agg.values()) or 1\n",
    "    print(f\"K_{n}: binding-constraint order across disconnections\")\n",
    "    for k in sorted(agg):\n",
    "        print(f\"  order {k}: {agg[k]} ({100.0*agg[k]/tot:.1f}%)\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c96229ab",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Sage notebook cell. Assumes WildGraph, round_robin_proper_coloring, and\n",
    "# generate_diverse_proper_colorings are already defined in the session, and\n",
    "# that `graphs` / `Graph` are the usual Sage globals.\n",
    "#\n",
    "# Extends binding_constraint_orders into a PRUNE: during the triple-partition\n",
    "# DFS we reject any partial partition whose completed triples already contain a\n",
    "# union of 2 (or 3) triples that is \"sealed\" under some color -- i.e. no edge of\n",
    "# that color leaves the union. Such a union can never be repaired by later\n",
    "# choices (the color's matching is fixed; any still-free vertex lands outside\n",
    "# the union, so an absent crossing edge stays absent), so the branch cannot\n",
    "# yield a color-connecting partition. The prune is therefore lossless: it only\n",
    "# discards already-doomed branches. The point of the experiment is to see what\n",
    "# is LEFT once orders 1, 2, 3 are all pruned.\n",
    "\n",
    "from itertools import combinations\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "def count_disconnects_with_seal_prune(WG, max_seal_order=3, max_complete=2000):\n",
    "    \"\"\"\n",
    "    Enumerate triple-partitions of K_n with the goodness (order-1) prune AND a\n",
    "    general order-2/3 seal prune, then measure how many SURVIVING complete\n",
    "    partitions still fail to be color-connecting.\n",
    "\n",
    "    Returns\n",
    "    -------\n",
    "    connected     : # surviving complete partitions that ARE color-connecting\n",
    "    disconnected  : # surviving complete partitions that still disconnect\n",
    "    order_hist    : Counter mapping seal-order -> number of (color, partition)\n",
    "                    disconnections whose smallest closed union had that many\n",
    "                    triples. With orders 1..max_seal_order pruned, every key\n",
    "                    here should be >= max_seal_order + 1; anything <= max_seal_order\n",
    "                    would signal a bug in the prune.\n",
    "    cap_hit       : True if we stopped at max_complete survivors, meaning the\n",
    "                    counts are a DFS-ordered SAMPLE rather than a full census.\n",
    "\n",
    "    Assumes n is divisible by 3 (the clean odd case n = 3t), which all of\n",
    "    n = 9, 15, 21, 27 satisfy, so every partition is into triples.\n",
    "    \"\"\"\n",
    "\n",
    "    # ----- precompute the per-coloring data ONCE (no graph rebuilds in the DFS)\n",
    "\n",
    "    # partner[c][x] = the vertex matched to x by color c. Color c's single\n",
    "    # unpaired (isolated) vertex never becomes a key, so partner[c].get(iso) is\n",
    "    # None and it contributes no \"leaving\" edge -- exactly what we want.\n",
    "    partner = {c: {} for c in WG.colors}\n",
    "    # cedges[c] = list of c-colored edges, used to build the quotient in analyze.\n",
    "    cedges = {c: [] for c in WG.colors}\n",
    "    for u, v, c in WG.edges:\n",
    "        partner[c][u] = v\n",
    "        partner[c][v] = u\n",
    "        cedges[c].append((u, v))\n",
    "\n",
    "    # vertex -> the unique color in which it is isolated (the bijection lemma).\n",
    "    # Used only by the cheap order-1 prune below.\n",
    "    isolated_color = {}\n",
    "    for c in WG.colors:\n",
    "        paired = partner[c]\n",
    "        for v in WG.vertices:\n",
    "            if v not in paired:          # no c-edge at v  => v is c's isolated vertex\n",
    "                isolated_color[v] = c\n",
    "                break\n",
    "\n",
    "    # color of each edge, keyed by normalized (sorted) endpoint pair.\n",
    "    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}\n",
    "\n",
    "    colors = list(WG.colors)\n",
    "\n",
    "    # ----- order-1 prune (goodness), unchanged from the prior search ----------\n",
    "    def is_good_triple(triple):\n",
    "        # {iso, a, b} is BAD (a sealed single triple) iff iso is the isolated\n",
    "        # vertex of some color c AND edge ab is also color c. Then no c-edge\n",
    "        # leaves the triple, so the triple is an order-1 seal.\n",
    "        x, y, z = triple\n",
    "        for iso, a, b in ((x, y, z), (y, x, z), (z, x, y)):\n",
    "            c = isolated_color.get(iso)\n",
    "            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    # ----- general seal test --------------------------------------------------\n",
    "    def sealing_color(U):\n",
    "        # U is a set of vertices (a union of completed triples). Return the first\n",
    "        # color under which U is sealed (every vertex keeps its partner inside U),\n",
    "        # else None. We break out of a color the instant we find one edge leaving.\n",
    "        for c in colors:\n",
    "            pc = partner[c]\n",
    "            leaves = False\n",
    "            for x in U:\n",
    "                y = pc.get(x)\n",
    "                if y is not None and y not in U:   # a c-edge crosses out of U\n",
    "                    leaves = True\n",
    "                    break\n",
    "            if not leaves:\n",
    "                return c                            # U closed under c  => sealed\n",
    "        return None\n",
    "\n",
    "    # A seal must be a PROPER subset of the vertices: the whole vertex set is\n",
    "    # trivially closed under every color but is NOT a disconnection. (This bites\n",
    "    # only when a union happens to span everything, e.g. the order-3 union at\n",
    "    # K_9, where 3 triples = all 9 vertices.)\n",
    "    n_total = len(WG.vertices)\n",
    "\n",
    "    # ----- order-2 / order-3 prune -------------------------------------------\n",
    "    def creates_sealed_union(new_triple, clusters):\n",
    "        # Only test unions that CONTAIN the new triple. Unions among older\n",
    "        # clusters were checked when their last member was placed, and sealing is\n",
    "        # monotone (a union that's open when fully formed never becomes sealed),\n",
    "        # so this incremental check loses nothing.\n",
    "        new_set = set(new_triple)\n",
    "\n",
    "        # order 2: new triple + one existing cluster (6 vertices)\n",
    "        for A in clusters:\n",
    "            U = new_set | set(A)\n",
    "            if len(U) < n_total and sealing_color(U) is not None:\n",
    "                return True\n",
    "\n",
    "        # order 3: new triple + two existing clusters (9 vertices)\n",
    "        if max_seal_order >= 3:\n",
    "            for A, B in combinations(clusters, 2):\n",
    "                U = new_set | set(A) | set(B)\n",
    "                if len(U) < n_total and sealing_color(U) is not None:\n",
    "                    return True\n",
    "\n",
    "        return False\n",
    "\n",
    "    # ----- measurement on a COMPLETE surviving partition ----------------------\n",
    "    order_hist = Counter()\n",
    "    tally = {\"connected\": 0, \"disconnected\": 0, \"cap_hit\": False}\n",
    "\n",
    "    def analyze(partition):\n",
    "        comp_of = {v: i for i, tr in enumerate(partition) for v in tr}  # vertex -> super-node\n",
    "        t = len(partition)\n",
    "        partition_disconnects = False\n",
    "\n",
    "        for c in colors:\n",
    "            # quotient graph on the t triples; an edge a--b means some c-edge\n",
    "            # crosses between triple a and triple b.\n",
    "            Q = Graph()\n",
    "            Q.add_vertices(range(t))\n",
    "            for u, v in cedges[c]:\n",
    "                a, b = comp_of[u], comp_of[v]\n",
    "                if a != b:\n",
    "                    Q.add_edge(a, b)\n",
    "            comps = Q.connected_components()\n",
    "            if len(comps) > 1:                       # this color disconnects\n",
    "                partition_disconnects = True\n",
    "                # a quotient component is itself a closed union, and any sealed\n",
    "                # union is a union of whole components, so the smallest component\n",
    "                # size IS the smallest seal order for this color.\n",
    "                order_hist[min(len(cc) for cc in comps)] += 1\n",
    "\n",
    "        if partition_disconnects:\n",
    "            tally[\"disconnected\"] += 1\n",
    "        else:\n",
    "            tally[\"connected\"] += 1\n",
    "\n",
    "    # ----- the pruned DFS, same skeleton as binding_constraint_orders ---------\n",
    "    def search(remaining, partition):\n",
    "        if tally[\"connected\"] + tally[\"disconnected\"] >= max_complete:\n",
    "            tally[\"cap_hit\"] = True\n",
    "            return\n",
    "        if not remaining:\n",
    "            analyze(partition)\n",
    "            return\n",
    "        first = min(remaining)                       # canonical: pin smallest free vertex\n",
    "        for pair in combinations(sorted(remaining - {first}), 2):\n",
    "            triple = (first,) + pair\n",
    "            if not is_good_triple(triple):           # order-1 prune\n",
    "                continue\n",
    "            if creates_sealed_union(triple, partition):   # order-2/3 prune\n",
    "                continue\n",
    "            search(remaining - set(triple), partition + [triple])\n",
    "            if tally[\"connected\"] + tally[\"disconnected\"] >= max_complete:\n",
    "                tally[\"cap_hit\"] = True\n",
    "                return\n",
    "\n",
    "    search(set(WG.vertices), [])\n",
    "    return tally[\"connected\"], tally[\"disconnected\"], order_hist, tally[\"cap_hit\"]\n",
    "\n",
    "\n",
    "# ----- run across diverse colorings at the clean odd sizes n = 3t -------------\n",
    "# Note: `disconnected` counts PARTITIONS that fail; order_hist counts per-COLOR\n",
    "# disconnections, so a single failing partition can add several entries to the\n",
    "# histogram (one per disconnected color).\n",
    "for n in [9, 15, 21, 27]:\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    conn = disc = 0\n",
    "    agg_orders = Counter()\n",
    "    any_cap = False\n",
    "\n",
    "    # structurally distinct colorings via the Kempe-swap walk, NOT just round-robin\n",
    "    for WG in generate_diverse_proper_colorings(G, n, max_yields=6):\n",
    "        c, d, hist, cap = count_disconnects_with_seal_prune(\n",
    "            WG, max_seal_order=3, max_complete=2000\n",
    "        )\n",
    "        conn += c\n",
    "        disc += d\n",
    "        agg_orders += hist\n",
    "        any_cap = any_cap or cap\n",
    "\n",
    "    total = conn + disc\n",
    "    # float() so the Sage Rational from int/int formats cleanly with :.2f\n",
    "    rate = float(100.0 * disc / total) if total else 0.0\n",
    "\n",
    "    census = \"sampled (cap hit)\" if any_cap else \"exhaustive under cap\"\n",
    "    print(f\"K_{n}: surviving complete partitions = {total} ({census})\")\n",
    "    print(f\"   color-connecting: {conn} | still disconnected: {disc} \"\n",
    "          f\"| residual disconnect rate = {rate:.2f}%\")\n",
    "    if agg_orders:\n",
    "        for k in sorted(agg_orders):\n",
    "            warn = \"   <-- WARNING: order <= prune limit, prune has a bug\" if k <= 3 else \"\"\n",
    "            print(f\"   residual seal order {k}: {agg_orders[k]}{warn}\")\n",
    "    else:\n",
    "        print(\"   no residual seals -> every surviving partition is color-connecting\")\n",
    "    print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "5615ef10",
   "metadata": {},
   "outputs": [],
   "source": [
    "def has_valid_partition(WG):\n",
    "    \"\"\"\n",
    "    Checks if there exists a partition of V(K_9) into 3 product-free triples.\n",
    "    \"\"\"\n",
    "    vertices = WG.vertices\n",
    "\n",
    "    # 1. Map each vertex to the color it is isolated in\n",
    "    v_to_c = {}\n",
    "    for c in WG.colors:\n",
    "        M = WG.monochromatic_subgraph(c)\n",
    "        for v in vertices:\n",
    "            if M.degree(v) == 0:\n",
    "                v_to_c[v] = c\n",
    "                break\n",
    "\n",
    "    # 2. Map each edge to its color\n",
    "    edge_c = {}\n",
    "    for u, v, c in WG.edges:\n",
    "        edge_c[frozenset([u,v])] = c\n",
    "\n",
    "    # 3. Check all partitions of 9 vertices into 3 triples\n",
    "    # To avoid duplicates, fix vertices[0] in the first triple\n",
    "    from itertools import combinations\n",
    "\n",
    "    for t1 in combinations(vertices[1:], 2):\n",
    "        t1 = (vertices[0], t1[0], t1[1])\n",
    "        rem1 = [v for v in vertices if v not in t1]\n",
    "\n",
    "        for t2 in combinations(rem1[1:], 2):\n",
    "            t2 = (rem1[0], t2[0], t2[1])\n",
    "            t3 = tuple(v for v in rem1 if v not in t2)\n",
    "\n",
    "            # Check if t1, t2, t3 are ALL product-free (good)\n",
    "            all_good = True\n",
    "            for t in (t1, t2, t3):\n",
    "                a, b, c = t\n",
    "                # A triple is bad if the edge color matches the isolated color of the third\n",
    "                if edge_c[frozenset([a,b])] == v_to_c[c]:\n",
    "                    all_good = False; break\n",
    "                if edge_c[frozenset([a,c])] == v_to_c[b]:\n",
    "                    all_good = False; break\n",
    "                if edge_c[frozenset([b,c])] == v_to_c[a]:\n",
    "                    all_good = False; break\n",
    "\n",
    "            if all_good:\n",
    "                return True # Found a valid partition!\n",
    "    return False\n",
    "\n",
    "# --- Run the exhaustive check ---\n",
    "n = 9\n",
    "ell = 9\n",
    "G = graphs.CompleteGraph(n)\n",
    "\n",
    "valid_count = 0\n",
    "total_checked = 0\n",
    "\n",
    "# Check 500 structurally diverse proper colorings\n",
    "for WG in generate_diverse_proper_colorings(G, ell, max_yields=500, max_stagnation=5000):\n",
    "    total_checked += 1\n",
    "    if has_valid_partition(WG):\n",
    "        valid_count += 1\n",
    "    else:\n",
    "        print(f\"FAILED on coloring {total_checked}!\")\n",
    "        break\n",
    "\n",
    "print(f\"Result: {valid_count}/{total_checked} colorings have a valid partition.\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "f323161a",
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import combinations\n",
    "import random\n",
    "\n",
    "N = 9  # order of the quasigroup = number of vertices of K_9\n",
    "\n",
    "# ----------------------------------------------------------------------\n",
    "# A proper edge coloring of K_9 is the same object as a commutative\n",
    "# idempotent quasigroup on 9 elements, stored as a 9x9 table L:\n",
    "#     L[i][j] = i*j  = the color of edge {i,j}.\n",
    "# Requirements:\n",
    "#     symmetric:   L[i][j] == L[j][i]        (commutative / undirected edge)\n",
    "#     idempotent:  L[i][i] == i              (vertex i misses color i)\n",
    "#     Latin:       every row is a permutation of 0..8 (proper coloring)\n",
    "# Dictionary: the vertex that MISSES the color of edge {i,j} is L[i][j]\n",
    "# itself, so the BAD triple created by edge {i,j} is exactly {i,j,L[i][j]}.\n",
    "# ----------------------------------------------------------------------\n",
    "\n",
    "def is_valid_ciq(L):\n",
    "    \"\"\"Verify L really is a commutative idempotent quasigroup.\"\"\"\n",
    "    n = len(L)\n",
    "    for i in range(n):\n",
    "        if L[i][i] != i:                       # idempotent diagonal\n",
    "            return False\n",
    "        if sorted(L[i]) != list(range(n)):     # row is a permutation\n",
    "            return False\n",
    "        for j in range(n):\n",
    "            if L[i][j] != L[j][i]:             # symmetric\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "def product_free(L, triple):\n",
    "    \"\"\"A triple {a,b,c} is GOOD (product-free) iff no element is the\n",
    "    product of the other two:  c!=a*b, b!=a*c, a!=b*c.\n",
    "    (This is exactly 'the group of three traps no color'.)\"\"\"\n",
    "    a, b, c = triple\n",
    "    return L[a][b] != c and L[a][c] != b and L[b][c] != a\n",
    "\n",
    "def count_good_partitions(L, n=N):\n",
    "    \"\"\"Count partitions of {0..n-1} into 3 product-free triples.\n",
    "    Each partition is counted once (we fix vertex 0 in the first triple\n",
    "    and the smallest leftover vertex in the second).\"\"\"\n",
    "    rest = list(range(1, n))\n",
    "    count = 0\n",
    "    example = None\n",
    "    for pair in combinations(rest, 2):              # first triple = {0} U pair\n",
    "        T1 = (0,) + pair\n",
    "        if not product_free(L, T1):\n",
    "            continue\n",
    "        remaining = [v for v in rest if v not in pair]   # 6 left\n",
    "        r0, others = remaining[0], remaining[1:]\n",
    "        for pair2 in combinations(others, 2):\n",
    "            T2 = (r0,) + pair2\n",
    "            T3 = tuple(v for v in others if v not in pair2)\n",
    "            if product_free(L, T2) and product_free(L, T3):\n",
    "                count += 1\n",
    "                if example is None:\n",
    "                    example = (T1, T2, T3)\n",
    "    return count, example\n",
    "\n",
    "# ---------- structured quasigroups ----------\n",
    "def cyclic_ciq(n=N):\n",
    "    \"\"\"x*y = (x+y)/2 mod n  (n odd); /2 is multiplication by (n+1)/2.\"\"\"\n",
    "    half = (n + 1) // 2\n",
    "    return [[(half * (i + j)) % n for j in range(n)] for i in range(n)]\n",
    "\n",
    "def ag23_steiner():\n",
    "    \"\"\"Affine plane AG(2,3) Steiner quasigroup on F_3 x F_3, point (a,b)\n",
    "    labeled 3a+b.  x*y = -x-y (the third collinear point); its product-\n",
    "    triples are exactly the 12 lines of AG(2,3).\"\"\"\n",
    "    enc = lambda a, b: 3 * a + b\n",
    "    L = [[0] * 9 for _ in range(9)]\n",
    "    for a in range(3):\n",
    "        for b in range(3):\n",
    "            for c in range(3):\n",
    "                for d in range(3):\n",
    "                    L[enc(a, b)][enc(c, d)] = enc((-a - c) % 3, (-b - d) % 3)\n",
    "    return L\n",
    "\n",
    "# ---------- random quasigroups ----------\n",
    "def random_ciq(n=N):\n",
    "    \"\"\"Randomly build one by backtracking-filling a symmetric Latin square\n",
    "    with fixed idempotent diagonal.  Cell (i,j), i<j, gets a symbol unused\n",
    "    in rows i and j; the mirror cell (j,i) gets the same symbol.\"\"\"\n",
    "    L = [[None] * n for _ in range(n)]\n",
    "    for i in range(n):\n",
    "        L[i][i] = i\n",
    "    rowused = [set([i]) for i in range(n)]\n",
    "    cells = [(i, j) for i in range(n) for j in range(i + 1, n)]\n",
    "\n",
    "    def backtrack(k):\n",
    "        if k == len(cells):\n",
    "            return True\n",
    "        i, j = cells[k]\n",
    "        cands = [s for s in range(n) if s not in rowused[i] and s not in rowused[j]]\n",
    "        random.shuffle(cands)\n",
    "        for s in cands:\n",
    "            L[i][j] = L[j][i] = s\n",
    "            rowused[i].add(s); rowused[j].add(s)\n",
    "            if backtrack(k + 1):\n",
    "                return True\n",
    "            L[i][j] = L[j][i] = None\n",
    "            rowused[i].discard(s); rowused[j].discard(s)\n",
    "        return False\n",
    "\n",
    "    return L if backtrack(0) else None\n",
    "\n",
    "# ====================== run ======================\n",
    "print(\"structured cases:\")\n",
    "for name, L in [(\"cyclic        \", cyclic_ciq()),\n",
    "                (\"AG(2,3) Steiner\", ag23_steiner())]:\n",
    "    assert is_valid_ciq(L), name + \" is not a valid quasigroup!\"\n",
    "    cnt, ex = count_good_partitions(L)\n",
    "    print(f\"  {name}: {cnt:3d} good splits   e.g. {ex}\")\n",
    "\n",
    "print(\"\\nrandom cases:\")\n",
    "random.seed(int(2026))\n",
    "counts = []\n",
    "trials = 2000\n",
    "for _ in range(trials):\n",
    "    L = random_ciq()\n",
    "    if L is None:\n",
    "        continue\n",
    "    assert is_valid_ciq(L)\n",
    "    c, _ = count_good_partitions(L)\n",
    "    counts.append(c)\n",
    "\n",
    "zeros = sum(1 for c in counts if c == 0)\n",
    "print(f\"  tested {len(counts)} random quasigroups\")\n",
    "print(f\"  minimum number of good splits over all tested = {min(counts)}\")\n",
    "print(f\"  maximum = {max(counts)}\")\n",
    "print(f\"  how many had ZERO good splits = {zeros}\")\n",
    "print(f\"  distinct good-split counts seen (an isomorphism invariant) = \"\n",
    "      f\"{sorted(set(counts))}\")\n",
    "\n",
    "# ----------------------------------------------------------------------\n",
    "# KEY STRUCTURAL QUANTITY.\n",
    "# Pick a uniformly random partition of the 9 vertices into 3 triples\n",
    "# (280 of them).  A fixed triple is a block with probability 10/280.\n",
    "# By linearity, the EXPECTED number of bad blocks is\n",
    "#       E = (number of DISTINCT bad triples) * 10 / 280\n",
    "#         = (number of distinct bad triples) / 28.\n",
    "# If E < 1 then some partition has 0 bad blocks -> a good split EXISTS.\n",
    "# So: D <= 27  ==>  a good split exists, by first moment.  Let's see how\n",
    "# big D (distinct bad triples) actually gets.\n",
    "# ----------------------------------------------------------------------\n",
    "\n",
    "def distinct_bad_triples(L, n=N):\n",
    "    \"\"\"The set of 3-sets {a,b,a*b}, one per edge, de-duplicated.\"\"\"\n",
    "    s = set()\n",
    "    for a in range(n):\n",
    "        for b in range(a + 1, n):\n",
    "            s.add(frozenset((a, b, L[a][b])))\n",
    "    return s\n",
    "\n",
    "print(\"\\n--- distinct bad-triple counts D (first moment works iff D<=27) ---\")\n",
    "for name, L in [(\"cyclic        \", cyclic_ciq()),\n",
    "                (\"AG(2,3) Steiner\", ag23_steiner())]:\n",
    "    D = len(distinct_bad_triples(L))\n",
    "    print(f\"  {name}: D = {D:2d}   E[bad blocks] = {float(D/28):.3f}\")\n",
    "\n",
    "random.seed(int(2026))\n",
    "Ds, goods = [], []\n",
    "for _ in range(4000):\n",
    "    L = random_ciq()\n",
    "    if L is None:\n",
    "        continue\n",
    "    D = len(distinct_bad_triples(L))\n",
    "    g, _ = count_good_partitions(L)\n",
    "    Ds.append(D); goods.append(g)\n",
    "\n",
    "print(f\"\\n  over {len(Ds)} random quasigroups:\")\n",
    "print(f\"    distinct-bad-triple count D: min={min(Ds)}, max={max(Ds)}\")\n",
    "print(f\"    how many have D <= 27 (first moment alone closes it) = \"\n",
    "      f\"{sum(1 for d in Ds if d<=27)}/{len(Ds)}\")\n",
    "print(f\"    how many have D >= 28 (first moment alone fails)     = \"\n",
    "      f\"{sum(1 for d in Ds if d>=28)}/{len(Ds)}\")\n",
    "# For the D>=28 cases, do they still always have a good split?\n",
    "bad_cases = [(d,g) for d,g in zip(Ds,goods) if d>=28]\n",
    "if bad_cases:\n",
    "    print(f\"    among the D>=28 cases: min good splits = {min(g for _,g in bad_cases)}, \"\n",
    "          f\"any with 0 = {sum(1 for _,g in bad_cases if g==0)}\")\n",
    "# multiplicity view: sum over distinct bad triples of (generating edges) = 36 always\n",
    "print(f\"    D distribution: {sorted(set(Ds))}\")\n",
    "\n",
    "# ----------------------------------------------------------------------\n",
    "# Characterize the bad-triple hypergraph: how many bad triples pass\n",
    "# through a single vertex (degree) and through a pair (codegree).\n",
    "# Low degree would let a matching/greedy argument finish cleanly.\n",
    "# ----------------------------------------------------------------------\n",
    "def hypergraph_stats(L, n=N):\n",
    "    B = distinct_bad_triples(L)\n",
    "    deg = [0]*n\n",
    "    for tri in B:\n",
    "        for v in tri:\n",
    "            deg[v] += 1\n",
    "    # does a simple greedy always finish? try: every good T1 must leave\n",
    "    # the other 6 vertices splittable into two good triples.\n",
    "    rest_all = list(range(n))\n",
    "    greedy_ok = True\n",
    "    for pair in combinations(range(1, n), 2):\n",
    "        T1 = (0,)+pair\n",
    "        if not product_free(L, T1):\n",
    "            continue\n",
    "        rem = [v for v in range(n) if v not in T1]\n",
    "        ok = False\n",
    "        r0, oth = rem[0], rem[1:]\n",
    "        for p2 in combinations(oth, 2):\n",
    "            T2 = (r0,)+p2; T3 = tuple(v for v in oth if v not in p2)\n",
    "            if product_free(L,T2) and product_free(L,T3):\n",
    "                ok = True; break\n",
    "        if not ok:\n",
    "            greedy_ok = False; break\n",
    "    return len(B), max(deg), greedy_ok\n",
    "\n",
    "random.seed(int(7))\n",
    "maxdeg = 0\n",
    "greedy_always = True\n",
    "worst_D = 0\n",
    "for _ in range(3000):\n",
    "    L = random_ciq()\n",
    "    if L is None: continue\n",
    "    D, md, gok = hypergraph_stats(L)\n",
    "    maxdeg = max(maxdeg, md)\n",
    "    worst_D = max(worst_D, D)\n",
    "    if not gok:\n",
    "        greedy_always = False\n",
    "\n",
    "print(\"\\n--- bad-triple hypergraph over 3000 random quasigroups ---\")\n",
    "print(f\"  max bad-triples through a single vertex (degree) = {maxdeg}  (out of 28 triples/vertex)\")\n",
    "print(f\"  largest D seen = {worst_D}\")\n",
    "print(f\"  'every good first triple extends to a full good split': always true? {greedy_always}\")\n",
    "\n",
    "# ----------------------------------------------------------------------\n",
    "# For the structural proof: remove a good first triple T1.  Among the\n",
    "# remaining 6 vertices there are 10 ways to split into two triples; the\n",
    "# split fails only if one half is bad.  Each bad triple inside the 6\n",
    "# kills exactly one split, so if the 6-set holds <= 9 bad triples, a good\n",
    "# 2-split survives.  Measure: max over good T1 of (#bad triples inside the\n",
    "# complementary 6-set).  If this is always <= 9, \"greedy extends\" is a\n",
    "# theorem-in-waiting.\n",
    "# ----------------------------------------------------------------------\n",
    "def max_bad_in_leftover(L, n=N):\n",
    "    B = distinct_bad_triples(L)\n",
    "    worst = 0\n",
    "    for T1 in combinations(range(n), 3):\n",
    "        if not product_free(L, T1):\n",
    "            continue\n",
    "        six = set(range(n)) - set(T1)\n",
    "        m = sum(1 for tri in B if tri <= six)   # bad triples fully inside the 6\n",
    "        worst = max(worst, m)\n",
    "    return worst\n",
    "\n",
    "print(\"\\n--- max bad triples surviving in the leftover 6 (need <= 9) ---\")\n",
    "for name, L in [(\"cyclic        \", cyclic_ciq()),\n",
    "                (\"AG(2,3) Steiner\", ag23_steiner())]:\n",
    "    print(f\"  {name}: {max_bad_in_leftover(L)}\")\n",
    "\n",
    "random.seed(int(99))\n",
    "overall = 0\n",
    "hist = {}\n",
    "for _ in range(4000):\n",
    "    L = random_ciq()\n",
    "    if L is None: continue\n",
    "    m = max_bad_in_leftover(L)\n",
    "    overall = max(overall, m)\n",
    "    hist[m] = hist.get(m, 0) + 1\n",
    "print(f\"  random (4000): worst case over all good first triples = {overall}\")\n",
    "print(f\"  distribution of that worst case: {dict(sorted(hist.items()))}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "16ebcd8d",
   "metadata": {},
   "outputs": [],
   "source": [
    "def test_canonical_forest(n, num_colorings=50):\n",
    "    \"\"\"\n",
    "    Tests if the canonical star forest (sizes as balanced as possible)\n",
    "    is a valid wild set for diverse proper colorings of K_n.\n",
    "    \"\"\"\n",
    "    G = graphs.CompleteGraph(n)\n",
    "    t = n // 3\n",
    "    remainder = n % 3\n",
    "\n",
    "    # build the canonical star sizes (e.g., [4, 4, 3] for n=11)\n",
    "    sizes = [n // t] * t\n",
    "    for i in range(remainder):\n",
    "        sizes[i] += 1\n",
    "\n",
    "    print(f\"Testing K_{n}: {t} stars of sizes {sizes}\")\n",
    "\n",
    "    valid_count = 0\n",
    "    ell = n if n % 2 != 0 else n - 1\n",
    "\n",
    "    for i, WG in enumerate(generate_diverse_proper_colorings(G, ell, max_yields=num_colorings)):\n",
    "        # build the wild set using arbitrary hubs (star[0])\n",
    "        wild_set = []\n",
    "        idx = 0\n",
    "        for size in sizes:\n",
    "            hub = idx\n",
    "            for leaf in range(idx + 1, idx + size):\n",
    "                for u, v, c in WG.edges:\n",
    "                    if set([u, v]) == set([hub, leaf]):\n",
    "                        wild_set.append((u, v, c))\n",
    "                        break\n",
    "            idx += size\n",
    "\n",
    "        if WG.is_color_connecting(wild_set):\n",
    "            valid_count += 1\n",
    "        else:\n",
    "            print(f\"  FAILED on coloring {i+1}\")\n",
    "            break\n",
    "\n",
    "    print(f\"Result: {valid_count}/{num_colorings} colorings have a valid canonical forest.\\n\")\n",
    "    return valid_count == num_colorings\n",
    "\n",
    "# Run for n=11 and n=13\n",
    "test_canonical_forest(11, num_colorings=50)\n",
    "test_canonical_forest(13, num_colorings=50)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
