#!/usr/bin/env python
# coding: utf-8

# # Wild edges in edge-colored graphs
# 
# **PI**: Aleyah Dawkins
# 
# 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.
# 
# 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.
# 
# **Formal Definition**
# 
# 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.
# 
# The wild number of an edge-colored graph, denoted $\mathrm{wld}(G)$, is the minimum size of a wild set.
# 
# **Theoretical Bounds**
# 
# Let $\kappa(G_i)$ denote the number of connected components in the monochromatic subgraph of color $i$.
# - Component Lower Bound (CLB): $\max_{i} (\kappa(G_i)) - 1 \le \mathrm{wld}(G)$
# - Component Upper Bound (CUB): $\mathrm{wld}(G) \le \sum_{i=1}^{\ell} \kappa(G_i) - \ell$
# - Ceiling Lower Bound: $\lceil \frac{\text{CUB}}{\ell - 1} \rceil \le \mathrm{wld}(G)$

# ## Imports & Setup

# In[10]:


from typing import Any, List, Tuple, Set, Dict, Optional, Generator
from itertools import combinations, cycle
from matplotlib.colors import is_color_like
import random
import math

random.seed(int(42))


# ## WildGraph Visualizer

# In[11]:


class WildGraphVisualizer:
    """
    Mixin class handling all rendering and plotting logic.
    Separates the display backend from the core combinatorial math.
    """

    @staticmethod
    def get_color_palette(num_colors: int) -> List[str]:
        """
        Centralized DRY color palette generator.
        Uses distinct named colors, scaling to continuous hex codes if needed.
        """
        named_colors = [
            'red', 'blue', 'green', 'purple', 'orange', 'brown', 'pink', 'gray',
            'olive', 'cyan', 'magenta', 'teal', 'navy', 'maroon', 'gold',
            'indigo', 'salmon', 'plum', 'turquoise', 'coral'
        ]
        if num_colors <= len(named_colors):
            return named_colors[:num_colors]

        import matplotlib.cm as cm
        import matplotlib.colors as mcolors
        return [mcolors.to_hex(cm.hsv(i / num_colors)) for i in range(num_colors)]

    def display_color(self, color: Any) -> str:
        """Fallback helper to ensure valid color compliance."""
        return color if isinstance(color, str) and is_color_like(color) else 'gray'

    def _render_layered_plot(self, edge_list: List[Tuple[Any, Any, Any]], wild_edges: List[Tuple[Any, ...]], title: Optional[str] = None) -> Any:
        """
        DRY Core Engine: Generates layout-pinned, multi-layered plots.
        Overlays solid color classes with dashed wild sets in their original colors.
        """
        wild_normalized = self.normalize_edges(wild_edges)

        # Layer 1: Spanning Subgraph of Base Color Classes (Solid lines)
        G_colored = Graph()
        G_colored.add_vertices(self.vertices)
        solid_colors = {} # eg., {'red': [(0, 1), (2, 3)], 'blue' : [(1, 4)]}

        for u, v, label in edge_list:
            if self.normalize_edge((u, v)) not in wild_normalized: # if wild, don't draw solid
                G_colored.add_edge(u, v)
                color_str = self.display_color(label)
                solid_colors.setdefault(color_str, []).append((u, v))

        p_colored = G_colored.plot(
            pos=self.pos, edge_colors=solid_colors, edge_style='solid',
            vertex_size=300, vertex_labels=True, title=title, axes=False
        )

        # Layer 2: Wild Edge Overlay (Thick Dashed lines matching their true color)
        if wild_normalized:
            G_wild = Graph()
            G_wild.add_vertices(self.vertices)
            dashed_colors = {}

            for edge in wild_edges:
                # Handle both (u, v) and (u, v, c) tuple formats robustly
                if len(edge) >= 3:
                    u, v, label = edge[0], edge[1], edge[2]
                else:
                    u, v = edge[0], edge[1]
                    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

                G_wild.add_edge(u, v)
                color_str = self.display_color(label)
                dashed_colors.setdefault(color_str, []).append((u, v))

            p_wild = G_wild.plot(
                pos=self.pos, edge_colors=dashed_colors, edge_style='dashed',
                edge_thickness=4, vertex_size=0, vertex_labels=False, axes=False
            )
            return p_colored + p_wild

        return p_colored

    # --- Public API Methods ---

    def plot_colored(self, title: Optional[str] = None, wild_edges: Optional[List[Tuple[Any, ...]]] = None, show: bool = False) -> Optional[Any]:
        wild_edges = [] if wild_edges == None else wild_edges
        p = self._render_layered_plot(self.edges, wild_edges, title=title)
        if show: p.show()
        else: return p

    def plot_monochromatic(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None, title: Optional[str] = None, show: bool = False) -> Optional[Any]:
        color_edges = [e for e in self.edges if e[2] == color]
        p = self._render_layered_plot(color_edges, wild_edges or [], title=title)
        if show: p.show()
        else: return p

    def plot_wild_topology_grid(self, wild_edges: List[Tuple[Any, ...]], cols: int = 4) -> None:
        plots = []
        plots.append(self._render_layered_plot([], wild_edges, title="Base Components\n(No Matching)"))

        for color in sorted(self.colors):
            color_edges = [e for e in self.edges if e[2] == color]

            W_color = self.make_graph(wild_edges)
            for u, v, _ in color_edges:
                W_color.add_edge(u, v)

            comp_count = W_color.connected_components_number()
            status = "Connected!" if comp_count == 1 else f"Disconnected ({comp_count})"

            plots.append(self._render_layered_plot(color_edges, wild_edges, title=f"Matching: {color}\nResult: {status}"))

        rows = math.ceil(len(plots) / cols)
        graphics_array(plots, ncols=cols).show(figsize=(cols * 5, rows * 5))

    def plot_wild_set(self, wild_edges: List[Tuple[Any, ...]]) -> None:
        p = self._render_layered_plot([], wild_edges, title="Wild Set")
        p.show()


# ## WildGraph

# ### Edge Valuations and Algorithmic Bounds
# 
# 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. 
# 
# Based on these edge valuations, we implement two critical bounds:
# 
# **1. The Dip Lower Bound (Proposition 5.6):**
# 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.
# 
# **2. The Greedy Upper Bound (Algorithm 5.10):**
# 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.

# In[12]:


class WildGraph(WildGraphVisualizer):
    """
    Immutable representation of an edge-colored graph.
    Inherits plotting capabilities from WildGraphVisualizer.
    """
    def __init__(self, graph: Any):
        self.G = graph
        self.vertices: List[Any] = self.G.vertices(sort=True)
        self.edges: List[Tuple[Any, Any, Any]] = self.G.edges(labels=True, sort=True)
        self.colors: Set[Any] = set(color for _, _, color in self.edges)

        # pin the vertex layout coordinates permanently on initialization
        self.pos: Dict[Any, Tuple[float, float]] = self.G.layout_circular()

        # Cache base kappas (O(1) bounds lookups)
        self.base_kappas: Dict[Any, int] = {color: self.kappa(color) for color in self.colors}

    @classmethod
    def from_colored_edges(cls, G: Any, colored_edges: List[Tuple[Any, Any, Any]]) -> "WildGraph":
        H = Graph()
        H.add_vertices(G.vertices(sort=True))
        H.add_edges(colored_edges)
        return cls(H)

    # --- Structural Helpers ---

    @property
    def color_classes(self) -> Dict[str, List[Tuple[Any, Any]]]:
        """Returns a clean dictionary mapping each color string to its edges."""
        classes = {}
        for u, v, c in self.edges:
            color_str = self.display_color(c)
            classes.setdefault(color_str, []).append((u, v))
        return classes

    def display_coloring(self, plot: bool = False) -> Optional[Any]:
        """
        Prints a clean text breakdown of the color classes
        and optionally returns the visual plot representation.
        """
        print(f"Graph Coloring Breakdown ({len(self.colors)} colors):")
        for color, edges in self.color_classes.items():
            print(f"{color:<8}: {edges}")

        if plot:
            print("\nRendering visual plot...")
            return self.plot_colored()

    def normalize_edge(self, edge: Tuple[Any, ...]) -> Tuple[Any, Any]:
        return tuple(sorted(edge[:2]))

    def normalize_edges(self, edges: List[Tuple[Any, ...]]) -> Set[Tuple[Any, Any]]:
        return {self.normalize_edge(e) for e in edges}

    def make_graph(self, edges: List[Tuple[Any, ...]]) -> Any:
        H = Graph()
        H.add_vertices(self.vertices)
        H.add_edges(edges)
        return H

    def monochromatic_subgraph(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> Any:
        color_edges = [e for e in self.edges if e[2] == color]
        return self.make_graph(color_edges + list(wild_edges or []))

    # --- Graph Theory Metrics ---

    def kappa(self, color: Any, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> int:
        return self.monochromatic_subgraph(color, wild_edges).connected_components_number()

    def kappa_total(self, wild_edges: Optional[List[Tuple[Any, ...]]] = None) -> int:
        if not wild_edges: return sum(self.base_kappas.values())
        return sum(self.kappa(color, wild_edges) for color in self.colors)

    def is_color_connecting(self, wild_edges: List[Tuple[Any, ...]]) -> bool:
        return all(self.kappa(color, wild_edges) == 1 for color in self.colors)

    def dip_number(self, edge: Tuple[Any, ...], current_wild: Optional[List[Tuple[Any, ...]]] = None) -> int:
        current_wild = current_wild or []
        before = self.kappa_total(wild_edges=current_wild)
        after = self.kappa_total(wild_edges=current_wild + [edge])
        return before - after

    def get_all_dip_numbers(self) -> List[Tuple[int, Tuple[Any, ...]]]:
        """Returns all edges sorted descending by their initial dip number."""
        dips = [(self.dip_number(e), e) for e in self.edges]
        dips.sort(key=lambda x: x[0], reverse=True)
        return dips

    def contracted_dip_sequence(self, candidate_edge: Tuple[Any, ...], current_wild: List[Tuple[Any, ...]], available_edges: List[Tuple[Any, ...]]) -> Tuple[int, ...]:
        """
        Algorithm 5.10 Potential Function (Edge Contraction):
        Adding an edge to the wild set universally merges its endpoints across all colors.
        This is topologically identical to edge contraction (G / e).
        This method calculates the lexicographic dip sequence of the post-contraction graph.
        """
        hypothetical_wild = current_wild + [candidate_edge]
        remaining_edges = [e for e in available_edges if e != candidate_edge]

        # Calculate dips in the conceptually contracted graph and sort descending
        future_dips = [self.dip_number(e, hypothetical_wild) for e in remaining_edges]
        future_dips.sort(reverse=True)

        return tuple(future_dips)

    # --- Theoretical Bounds ---

    def component_bounds(self) -> Tuple[int, int]:
        clb = max(self.base_kappas.values()) - 1
        cub = sum(self.base_kappas.values()) - len(self.colors)
        return clb, cub

    def ceiling_lower_bound(self) -> int:
        _, cub = self.component_bounds()
        ell = len(self.colors)
        return 0 if ell <= 1 else math.ceil(cub / (ell - 1))

    def dip_lower_bound(self) -> int:
        _, cub = self.component_bounds()
        dips = [d for d, _ in self.get_all_dip_numbers()]
        total = 0
        for p, d in enumerate(dips, start=1):
            total += d
            if total >= cub:
                return p
        return len(dips)

    # --- Solvers & Algorithms ---

    def find_exact_wild_set(self, timeout: Optional[float] = None) -> List[Tuple[Any, ...]]:
        """Exact wild set by checking all subsets (Brute Force). O(2^m)."""
        import time
        start_time = time.time()

        start_k = max(self.dip_lower_bound(), self.ceiling_lower_bound())

        for k in range(start_k, len(self.edges) + 1):
            for wild_edges in combinations(self.edges, k):
                if timeout and (time.time() - start_time) > timeout:
                    return None

                if self.is_color_connecting(list(wild_edges)):
                    return list(wild_edges)
        raise ValueError("Graph cannot be connected.")

    def find_greedy_wild_set(self) -> List[Tuple[Any, ...]]:
        """
        Algorithm 5.10: Iteratively picks edges by dynamic dip number.
        Breaks ties using lexicographic potential (the sequence of dips after contraction).
        """
        current_wild = []
        available_edges = list(self.edges)

        while not self.is_color_connecting(current_wild):
            dips = [(self.dip_number(e, current_wild), e) for e in available_edges] #  = [(dip, (u, v, c)), ...]
            max_dip = max(dips, key=lambda x: x[0])[0]

            tied_edges = [e for d, e in dips if d == max_dip]

            if len(tied_edges) == 1:
                best_edge = tied_edges[0]
            else:
                # break ties using dip potential
                potentials = [(self.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges] # = [(dip_sequence, (u, v, c)), ...]
                potentials.sort(key=lambda x: x[0], reverse=True)
                best_edge = potentials[0][1]

            current_wild.append(best_edge)
            available_edges.remove(best_edge)

        return current_wild

    def find_milp_wild_set(self, upper_bound: Optional[int] = None) -> List[Tuple[Any, ...]]:
        """
        Solves for the exact wild number using MILP.
        """
        from sage.numerical.mip import MixedIntegerLinearProgram
        from itertools import combinations

        # upper bound to prune the search space
        fallback_wild_set = None
        if upper_bound is None:
            upper_bound, fallback_wild_set = self.wild_number(method="greedy")

        edges = self.G.edges(labels=False)
        edge_to_idx = {tuple(sorted(e)): i for i, e in enumerate(edges)} # link each edge to an index for MILP
        num_edges = len(edges)

        # initialize MILP solver
        milp = MixedIntegerLinearProgram(maximization=False, solver='GLPK')
        milp.solver_parameter("timelimit", 600)
        x = milp.new_variable(binary=True) # x[i] = 1 => x is wild

        # objective: minimize the total number of wild edges
        milp.set_objective(sum(x[i] for i in range(num_edges)))

        # constraint: prune the search tree
        milp.add_constraint(sum(x[i] for i in range(num_edges)) <= upper_bound)

        # constraints: for each color, W must connect the components of M_i
        for color in self.colors:
            M_i = self.monochromatic_subgraph(color)
            comps = M_i.connected_components() # eg., [[0, 1], [2, 3, 4], [5], [6, 7]]
            c = len(comps)

            if c <= 1:
                continue

            # map vertices to component IDs for O(1) lookup;s eg., {0:0, 1:1: 2:1, ...}
            comp_of = {v: idx for idx, comp in enumerate(comps) for v in comp}

            # pre-filter cross edges
            cross_edges = []
            for u, v in edges:
                cu = comp_of[u]
                cv = comp_of[v]
                if cu != cv:
                    cross_edges.append((edge_to_idx[tuple(sorted((u, v)))], cu, cv))

            comp_indices = list(range(c))

            # generate all valid cuts
            # need to ensure that for every way to partition the components into A and B, there is at least a wild crossing edge
            # iterate over all partitions of the components into two non-empty sets
            # fix component 0 to group A to avoid checking (A, B) and (B, A)
            for r in range(1, len(comp_indices)): # eg., r = |A|, eg., r = 2
                for subset in combinations(comp_indices[1:], r-1):
                    S = set(subset) | {0} # eg., A = {2} U {0} = {0, 2}

                    # cut edges
                    cut_edge_indices = [
                        idx for idx, cu, cv, in cross_edges
                        if (cu in S) != (cv in S)
                    ]

                    # W must contain at least one edge from this cut to ensure connectivity
                    if cut_edge_indices:
                        milp.add_constraint(sum(x[idx] for idx in cut_edge_indices) >= 1)

        # solve
        try:
            min_wld = milp.solve()
            x_values = milp.get_values(x)
            wild_set = [edges[i] for i in range(num_edges) if x_values[i] > 0.5]
            return wild_set
        except Exception as e:
            print(f"[Error] ILP Solver failed: {e}")
            return fallback_wild_set

    def wild_number(self, method: str = "auto") -> Tuple[int, List[Tuple[Any, ...]]]:
        """Intelligent dispatcher to find the Wild Number."""
        if len(self.colors) == 2:
            cub = self.component_bounds()[1]
            wild_set = self.find_greedy_wild_set()
            return cub, wild_set

        m = len(self.edges)
        if method == "exact" or (method == "auto" and m <= 38):
            wild_set = self.find_exact_wild_set()
        elif method == "milp" or (method == "auto" and m > 38):
            wild_set = self.find_milp_wild_set()
        else:
            wild_set = self.find_greedy_wild_set()

        return len(wild_set), wild_set


# ## Coloring Generators
# 
# A suite of tools to assign color classes strictly (Proper Edge Colorings), uniformly, or partitioned equitably. We generate structural variance via Line Graph conversions.

# ### Random Colorings

# In[13]:


def color_randomly(G: Any, num_colors: int) -> WildGraph:
    """Assigns random colors to edges using the true named palette."""
    assert num_colors <= G.size(), "More colors than edges requested."
    color_palette = WildGraphVisualizer.get_color_palette(num_colors)

    edges = G.edges(labels=False, sort=True)
    while True:
        colored_edges = [(u, v, random.choice(color_palette)) for u, v in edges]
        if len(set(c for _, _, c in colored_edges)) == num_colors:
            return WildGraph.from_colored_edges(G, colored_edges)


# ### Equitable Colorings

# In[480]:


def color_by_edge_partition(G: Any, num_colors: int) -> WildGraph:
    """Divides edges as evenly as possible among true named colors."""
    color_palette = WildGraphVisualizer.get_color_palette(num_colors)
    colored_edges = [
        (u, v, color_palette[i % num_colors])
        for i, (u, v, _) in enumerate(G.edges(labels=True, sort=True))
    ]
    return WildGraph.from_colored_edges(G, colored_edges)


# #### Proper Colorings

# In[14]:


def round_robin_proper_coloring(n: int) -> WildGraph:
    """Generates one structurally round-robin proper coloring of K_n."""
    if n < 2: raise ValueError("Complete graph must have at least 2 vertices.")

    ell = n if n % 2 != 0 else n - 1
    color_palette = WildGraphVisualizer.get_color_palette(ell)

    vertices = list(range(n))
    random.shuffle(vertices)
    colored_edges = []

    if n % 2 == 0:
        for i in range(n - 1):
            color = color_palette[i]
            for j in range(n // 2):
                v1 = vertices[(i + j) % (n - 1)]
                v2 = vertices[n - 1] if j == 0 else vertices[(i - j + n - 1) % (n - 1)]
                colored_edges.append((min(v1, v2), max(v1, v2), color))
    else:
        for i in range(n):
            color = color_palette[i]
            for j in range(1, (n // 2) + 1):
                v1 = vertices[(i + j) % n]
                v2 = vertices[(i - j + n) % n]
                colored_edges.append((min(v1, v2), max(v1, v2), color))

    return WildGraph.from_colored_edges(graphs.CompleteGraph(n), colored_edges)


# In[3]:


def _structural_fingerprint(WG: "WildGraph") -> Tuple[Tuple[int, ...], ...]:
    """
    Creates a color-agnostic, vertex-agnostic structural signature for a proper coloring.
    Calculates the cycle lengths of every isolated pair of colors.
    """
    colors = list(WG.colors)
    all_cycle_profiles = []

    # iterate over all pairs of colors
    for c1, c2 in combinations(colors, 2): # eg., ('red', 'blue')
        # isolate subgraph of just these two colors
        subgraph_edges = [(u, v) for u, v, c in WG.edges if c in (c1, c2)]
        H = Graph()
        H.add_edges(subgraph_edges)

        # get the lengths of the cycles/paths in this 2-colored world
        # eg., [8] or [4, 4]
        cycle_lengths = tuple(sorted([len(comp) for comp in H.connected_components()]))
        all_cycle_profiles.append(cycle_lengths)

    # sort the profiles to make it completely invariant to which color is which
    # eg., ((4, 4), (8,), (8,))
    return tuple(sorted(all_cycle_profiles))


def _factor_switch_move(WG: "WildGraph") -> "WildGraph":
    """
    Performs a single random Kempe chain swap on two color classes.
    This safely walks the graph across the mathematical space of 1-factorizations.
    """
    colors = list(WG.colors)
    if len(colors) < 2:
        return WG

    # pick two random colors to isolate
    c1, c2 = random.sample(colors, 2) # eg., ['red', 'blue']

    # build kempe graph
    subgraph_edges = [(u, v) for u, v, c in WG.edges if c in (c1, c2)]
    H = Graph()
    H.add_edges(subgraph_edges)

    comps = H.connected_components() # eg., [[0, 1, 2, 3], [4, 5, 6, 7]]

    # isolate loops large enough to meaningfully swap
    valid_comps = [comp for comp in comps if len(comp) >= 3]
    if not valid_comps:
        return WG

    # pick a random cycle and prepare to swap its edges
    target_comp = set(random.choice(valid_comps)) # eg., {0, 1, 2, 3}

    # perform kempe swap
    new_edges = []
    for u, v, c in WG.edges:
        # if the edge is in our target loop and is one of our two colors, swap it
        if c in (c1, c2) and u in target_comp and v in target_comp:
            new_color = c2 if c == c1 else c1
            new_edges.append((u, v, new_color))
        else:
            new_edges.append((u, v, c))

    return WildGraph.from_colored_edges(WG.G, new_edges)


def generate_diverse_proper_colorings(
    G: Any,
    num_colors: int,
    max_yields: int = 10,
    max_stagnation: int = 1_000
    ) -> Generator["WildGraph", None, None]:
    """
    Explores the space of proper colorings using Markov-chain Kempe swaps.
    Uses 2-factor structural fingerprints to perfectly detect diverse isomorphism classes.
    """
    # seed the markov chain with a valid starting factorization
    n = G.order()
    current_WG = round_robin_proper_coloring(n)

    accepted_graphs: List[WildGraph] = []
    seen_fingerprints = set()

    stagnation_counter = 0

    # save the base graph immediately so we don't lose the original round-robin class
    base_fingerprint = _structural_fingerprint(current_WG)
    seen_fingerprints.add(base_fingerprint)
    accepted_graphs.append(current_WG)
    yield current_WG

    while len(accepted_graphs) < max_yields and stagnation_counter < max_stagnation:
        stagnation_counter += 1

        # mutate the graph via a random walk of 20 factor switches
        for _ in range(20):
            current_WG = _factor_switch_move(current_WG)

        # check our color-agnostic structural invariant
        fingerprint = _structural_fingerprint(current_WG) # eg., ((4, 4), (8,), (8,))

        if fingerprint not in seen_fingerprints:
            seen_fingerprints.add(fingerprint)
            accepted_graphs.append(current_WG)
            stagnation_counter = 0
            yield current_WG

    if stagnation_counter >= max_stagnation:
        print(f"[Info] Search space exhausted. Halted at {len(accepted_graphs)} diverse colorings.")


# #### Product Coloring

# In[483]:


def make_product_graph_coloring(
    WG1: WildGraph,
    WG2: WildGraph,
    color_G: Optional[str] = None,
    color_H: Optional[str] = None,
) -> WildGraph:
    """Generates the Cartesian Product G □ H and inherits or overrides factor colorings."""
    G, H = WG1.G, WG2.G
    colored_edges = []

    for h in H.vertices(sort=True):
        for u, v, orig_color in G.edges(labels=True, sort=True):
            colored_edges.append(((u, h), (v, h), color_G or orig_color))

    for g in G.vertices(sort=True):
        for u, v, orig_color in H.edges(labels=True, sort=True):
            colored_edges.append(((g, u), (g, v), color_H or orig_color))

    P = Graph()
    P.add_vertices(
        [(g, h) for g in G.vertices(sort=True) for h in H.vertices(sort=True)]
    )
    return WildGraph.from_colored_edges(P, colored_edges)


# ## Experimental Scripts

# ### $\mathbb{E}[\mathrm{wld}(G)]$

# In[484]:


def expected_wld(G: Any, method: str = "auto", iterations: int = 50_000) -> float:
    """Calculates the expected wild number for an equitable 2-coloring of graph G."""
    edges = list(G.edges(labels=False, sort=True))
    m = len(edges)
    red_size = m // 2
    method = ("exact" if m <= 20 else "monte_carlo") if method == "auto" else method

    def cub_of(red_set: Set[Tuple[Any, ...]]) -> int:
        colored = [(u, v, "red" if (u, v) in red_set else "blue") for u, v in edges]
        return WildGraph.from_colored_edges(G, colored).component_bounds()[1]

    if method == "exact":
        samples = (set(c) for c in combinations(edges, red_size))
        total = binomial(m, red_size)
        return sum(cub_of(s) for s in samples) / float(total)

    acc = sum(cub_of(set(random.sample(edges, red_size))) for _ in range(iterations))
    return float(acc) / iterations


# ### Wild Set Robustness
# 
# 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?

# In[485]:


def test_wild_set_robustness(
    G: Any,
    wild_edges: List[Tuple[Any, ...]],
    num_colors: int,
    max_test_cases: int = 100
) -> List[WildGraph]:
    """Tests if a specific Wild Set 'W' survives against distinct proper colorings."""
    print(f"testing W against isomorphically distinct proper colorings...")
    successes = 0
    failing_graphs = []

    for WG_new in generate_diverse_proper_colorings(G, num_colors, max_yields=max_test_cases):
        if WG_new.is_color_connecting(wild_edges):
            successes += 1
        else:
            failing_graphs.append(WG_new)

    total_tested = successes + len(failing_graphs)
    if total_tested == 0:
        print("\n[Warning] No colorings were generated to test against.")
        return []

    win_rate = float(successes / total_tested) * 100

    print(f"\ntotal colorings tested: {successes + len(failing_graphs)}")
    print(f"W remained valid in: {successes} colorings")
    print(f"W failed in: {len(failing_graphs)} colorings")
    print(f"robustness score: {win_rate:.1f}%")

    return failing_graphs


# ### Proper Colorings of $K_n$

# In[486]:


def sample_proper_coloring_wild_sets(
    n: int,
    num_samples: Optional[int] = None,
    plot: bool = False,
    cols: Optional[int] = None
    ) -> None:
    """
    Samples structurally distinct proper colorings of K_n, computes their exact
    wild sets, prints the text-based edge lists, and optionally renders a visual grid.

    Args:
        n: The number of vertices for the complete graph K_n.
        num_samples: The maximum number of distinct proper colorings to evaluate.
        plot: If True, renders the visual graphics_array grid. If False, keeps it purely text-based.
        cols: Number of columns in the visualization grid.
    """
    print(f"Structural Analysis of {num_samples} Isomorphically Distinct Proper Colorings on K_{n}\n")

    num_samples = num_samples if num_samples is not None else n // 2
    cols = cols if cols is not None else n // 2

    G = graphs.CompleteGraph(n)
    ell = n if n % 2 != 0 else n - 1

    # Pull exclusively from our randomized, non-isomorphic generator
    colorings = list(generate_diverse_proper_colorings(G, ell, max_yields=num_samples))
    plots = []

    for i, WG in enumerate(colorings):
        # Calculate the exact optimal wild set
        wld, wild_edges = WG.wild_number(method="exact")

        print(f"Sample {i+1:02d} | wld = {wld} | W =  {wild_edges}")

        # Accumulate plots only if the user explicitly requests them
        if plot:
            title_str = f"Sample {i+1} | wld = {wld}"
            p = WG.plot_colored(title=title_str, wild_edges=wild_edges, show=False)
            plots.append(p)

    # Render the visualization suite only if the flag is True and colorings exist
    if plot and plots:
        print("\nRendering visual topologies...")
        rows = math.ceil(len(plots) / cols)
        grid = graphics_array(plots, ncols=cols)
        grid.show(figsize=(cols * 5, rows * 5))


# ## Execution Workspace

# ### Greedy vs Brute Force

# In[16]:


import time

header = f"{'n':>2} | {'Greedy':>6} | {'Exact':>5} | {'Gap':>3} | {'Greedy(s)':>9} | {'Exact(s)':>9} | {'Speedup':>8}"
print(header)
print("-" * len(header))

for n in range(3, 11):
    WG = round_robin_proper_coloring(n)

    start = time.time()
    greedy_wld, _ = WG.wild_number(method="greedy")
    greedy_time = time.time() - start

    start = time.time()
    exact_wld, _ = WG.wild_number(method="exact")
    brute_time = time.time() - start

    gap = abs(greedy_wld - exact_wld)
    speedup = brute_time / greedy_time if greedy_time > 0 else float("inf")

    print(
        f"{n:>2} | {greedy_wld:>6} | {exact_wld:>5} | {gap:>3} | {greedy_time:>9.4f} | {brute_time:>9.4f} | {speedup:>7.1f}x"
    )


# ### Bound Verification

# In[488]:


n = 8
WG = round_robin_proper_coloring(n)

clb, cub = WG.component_bounds()
dlb = WG.dip_lower_bound()
exact_wld, _ = WG.wild_number(method="exact")
greedy_wld, _ = WG.wild_number(method="greedy")

print(
    f"CLB ({clb}) <= DLB ({dlb}) <= WLD ({exact_wld}) <= Greedy ({greedy_wld}) <= CUB ({cub})"
)
assert clb <= dlb <= exact_wld <= greedy_wld <= cub, "Hierarchy violated!"


# **Q**: How tight is the greedy upper bound?

# ### Expected Equitable Wild Number

# In[489]:


for n in range(4, 9):
    G_test = graphs.CompleteGraph(n)
    ev = expected_wld(G_test, method="auto")
    print(f"E[wld(K_{n})] ≈ {ev:.4f}")


# ### $K_n$ Proper Edge Coloring

# In[ ]:


import time

n = 9
ell = n if (n % 2 == 1) else (n - 1)

G = graphs.CompleteGraph(n)
WG = round_robin_proper_coloring(n)

start = time.time()
wild_number, wild_edges = WG.wild_number()
clean_wild_edges = [(u, v) for u, v, _ in wild_edges]
wild_time = time.time() - start

print(f"K_{n} | ell = {ell} | wld = {wild_number}")
print(f"W = {wild_edges}")
print(f"time: {wild_time:.4f}s\n")

start = time.time()
failures = test_wild_set_robustness(G=G, wild_edges=clean_wild_edges, num_colors=ell)
robust_time = time.time() - start
print(f"time: {robust_time:.4f}s")


# In[ ]:


# if failures:
#     failures[0].plot_wild_topology_grid(clean_wild_edges, cols=ell//2 + 1)
# else:
#     print("W is robust")


# ### Greedy vs MILP

# In[ ]:


import time

header = f"{'n':>2} | {'ILP':>5} | {'Greedy':>6} | {'Gap':>5} | {'ILP(s)':>9} | {'Greedy(s)':>9}"
print(header)
print("-" * len(header))

for n in range(3, 17):
    WG = round_robin_proper_coloring(n)

    # 1. run greedy
    start = time.time()
    greedy_wld, _ = WG.wild_number(method="greedy")
    greedy_time = time.time() - start

    # 2. run ilp
    start = time.time()
    ilp_edges_raw = WG.find_milp_wild_set(upper_bound=greedy_wld)
    ilp_time = time.time() - start

    if ilp_edges_raw is not None:
        ilp_wld = len(ilp_edges_raw)
        ilp_str = f"{ilp_wld}"
    else:
        ilp_wld = greedy_wld # fallback for tracking
        ilp_str = "T/O"

    gap = greedy_wld - ilp_wld
    print(
        f"{n:>2} | {ilp_str:>5} | {greedy_wld:>6} | {gap:>5} | {ilp_time:>9.4f} | {greedy_time:>9.4f}"
    )


# In[ ]:


n = 13

WG = round_robin_proper_coloring(n)

# 1. get the ground truth from the ILP
print("solving ILP for ground truth...")
greedy_upper_bound, _ = WG.wild_number(method="greedy")
color_map = {WG.normalize_edge(e): e for e in WG.edges}
ilp_wild_set = WG.find_milp_wild_set(upper_bound=greedy_upper_bound)
ilp_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in ilp_wild_set])

print(f"ILP wld: {len(ilp_wild_set)}")
print(f"ILP wild set: {ilp_wild_set}\n")
WG.plot_wild_set(ilp_wild_set)

# 2. replay the greedy algorithm manually
current_wild = []
available_edges = list(WG.edges)
step = 1

print("--- greedy algorithm step-by-step ---")

while not WG.is_color_connecting(current_wild):
    # calculate dips for all remaining edges given the current wild set
    # eg., [(dip, (u, v, c)), ...]
    dips = [(WG.dip_number(e, current_wild), e) for e in available_edges]
    max_dip = max(dips, key=lambda x: x[0])[0]

    tied_edges = [e for d, e in dips if d == max_dip]

    if len(tied_edges) == 1:
        best_edge = tied_edges[0]
    else:
        # break ties using lexicographic potential (contracted dip sequence)
        # eg., [((4, 3, 1), (u, v, c)), ...]
        potentials = [(WG.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]
        potentials.sort(key=lambda x: x[0], reverse=True)
        best_edge = potentials[0][1]

    # check if this greedy choice exists anywhere in the optimal ILP set
    normalized_choice = WG.normalize_edge(best_edge)
    clean_ilp_wild_set = sorted({WG.normalize_edge(e) for e in ilp_wild_set})
    is_optimal = normalized_choice in clean_ilp_wild_set

    # visually flag divergence
    status = "matched" if is_optimal else "divergence"

    print(f"step {step:02d} | picked edge: {best_edge} | dip number : {max_dip} | ilp status : {status}")

    current_wild.append(best_edge)
    available_edges.remove(best_edge)
    step += 1

print(f"\nfinal greedy size: {len(current_wild)}")
print(f"greedy edges: {current_wild}")
WG.plot_wild_set(current_wild)
print(f"greedy gap: {len(current_wild) - len(ilp_wild_set)}")


# In[568]:


import time
import math

plots = []

for n in range(3, 24):
    ell = n if (n % 2 == 1) else (n - 1)
    print(f"=== K_{n} | ell = {ell} ===")

    WG = round_robin_proper_coloring(n)

    # 1. run greedy and time it
    start = time.time()
    greedy_upper_bound, _ = WG.wild_number(method="greedy")
    greedy_time = time.time() - start

    # 2. run ilp and time it
    start = time.time()
    ilp_edges_raw = WG.find_milp_wild_set(upper_bound=greedy_upper_bound)
    ilp_time = time.time() - start

    if ilp_edges_raw is None:
        print(f"[error] ILP failed or timed out. skipping K_{n}.\n")
        continue

    # map geometry back to color instantly for ILP
    color_map = {WG.normalize_edge(e): e for e in WG.edges}
    ilp_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in ilp_edges_raw])
    ilp_normalized = {WG.normalize_edge(e) for e in ilp_wild_set}

    # 3. run exact solver with the dynamic timeout
    exact_wild_set = []

    if n <= 10:
        allowed_exact_time = greedy_time + ilp_time + 60.0
        start = time.time()
        exact_edges_raw = WG.find_exact_wild_set(timeout=allowed_exact_time)
        exact_time = time.time() - start

        if exact_edges_raw is not None:
            exact_wild_set = sorted([color_map[WG.normalize_edge(e)] for e in exact_edges_raw])
            exact_title = f"K_{n} Exact (wld={len(exact_wild_set)})"
            print(f"exact  | wld: {len(exact_wild_set):02d} | W: {exact_wild_set}")
        else:
            exact_title = f"K_{n} Exact (T/O)"
            print(f"exact  | T/O (> {allowed_exact_time:.1f}s)")
    else:
        # Skip the exact solver for n > 10 to save time
        exact_title = f"K_{n} Exact (Skipped)"
        print(f"exact  | Skipped (n > 10)")

    # 4. replay the greedy algorithm manually
    current_wild = []
    available_edges = list(WG.edges)

    greedy_dips = []
    divergence_steps = []

    while not WG.is_color_connecting(current_wild):
        dips = [(WG.dip_number(e, current_wild), e) for e in available_edges]
        max_dip = max(dips, key=lambda x: x[0])[0]
        tied_edges = [e for d, e in dips if d == max_dip]

        if len(tied_edges) == 1:
            best_edge = tied_edges[0]
        else:
            potentials = [(WG.contracted_dip_sequence(e, current_wild, available_edges), e) for e in tied_edges]
            potentials.sort(key=lambda x: x[0], reverse=True)
            best_edge = potentials[0][1]

        # track if this was a trap using the ILP ground truth
        if WG.normalize_edge(best_edge) not in ilp_normalized:
            divergence_steps.append(len(current_wild) + 1)

        greedy_dips.append(max_dip)
        current_wild.append(best_edge)
        available_edges.remove(best_edge)

    gap = len(current_wild) - len(ilp_wild_set)

    # 5. condensed output
    print(f"ilp    | wld: {len(ilp_wild_set):02d} | W: {ilp_wild_set}")
    print(f"greedy | wld: {len(current_wild):02d} | W: {current_wild}")
    print(f"gap    | {gap}")

    if gap > 0:
        print(f"alert  | divergences occurred at steps: {divergence_steps}")
        print(f"alert  | greedy dip sequence: {greedy_dips}")
    print("")

    # 6. generate the plots for all three solvers
    p_exact = WG.plot_colored(title=exact_title, wild_edges=exact_wild_set, show=False)
    p_ilp = WG.plot_colored(title=f"K_{n} ILP (wld={len(ilp_wild_set)})", wild_edges=ilp_wild_set, show=False)
    p_greedy = WG.plot_colored(title=f"K_{n} Greedy (wld={len(current_wild)})", wild_edges=current_wild, show=False)

    # append the trio to the master list
    plots.extend([p_exact, p_ilp, p_greedy])


# In[575]:


if plots:
    print("rendering master topology grid (Exact | ILP | Greedy)...")
    grid = graphics_array(plots, ncols=6)
    grid.show(figsize=(48, 48))


# In[ ]:


num_samples = 5

for n in range(3, 16):
    ell = n if (n % 2 == 1) else (n - 1)
    G = graphs.CompleteGraph(n)
    wlds_found = set()

    print(f"\nK_{n} | ell={ell}")

    # generate structurally distinct proper colorings
    for i, WG in enumerate(generate_diverse_proper_colorings(G, ell, max_yields=num_samples)):
        wild_number, wild_edges = WG.wild_number()

        wlds_found.add(wild_number)

    print(f"found wlds = {wlds_found}")


# In[ ]:


n = 16
ell = n if (n % 2 == 1) else (n - 1)

WG = round_robin_proper_coloring(n)

wild_number, wild_edges = WG.wild_number()
WG.plot_colored(
    title=f"K_{n} | ell = {ell} | wld = {wild_number}",
    wild_edges=wild_edges,
    show=True
)


# In[ ]:


WG.plot_colored(wild_edges)


# In[ ]:


plots = []
for n in range(3, 20):
    ell = n if (n % 2 == 1) else (n - 1)
    WG = round_robin_proper_coloring(n)
    wild_number, wild_edges = WG.wild_number(method="milp")
    plots.append(WG.plot_colored(
        title=f"K_{n} | ell = {ell} | wld = {wild_number}",
        wild_edges=wild_edges,
        show=False)
    )

grid = graphics_array(plots, ncols=num_samples)
grid.show(figsize=(8, 8))


# In[ ]:


n = 16
ell = n if (n % 2 == 1) else (n - 1)
num_samples = 5

G = graphs.CompleteGraph(n)
colorings = generate_diverse_proper_colorings(G, ell, max_yields=num_samples)

plots = []
for i, WG in enumerate(colorings):
    wild_number, wild_edges = WG.wild_number()
    plots.append(WG.plot_colored(title=f"Sample {i+1:02d}: wld = {wild_number}", wild_edges=wild_edges, show=False))

grid = graphics_array(plots, ncols=num_samples)
grid.show(figsize=(num_samples * 5, num_samples * 5))


# ### Conjecture: $\mathrm{wld}\rho(K_n) = \left\lfloor \frac{4\lceil n/2 \rceil}{3}\right\rfloor$

# In[19]:


header = f"{'n':>2} | {'k':>2} | {'conj':>6} | {'wld':>6}"
print(header)
print("-" * len(header))

for n in range(3, 20):
    k = math.ceil(n / 2)
    conj = int(4 * k // 3)

    WG = round_robin_proper_coloring(n)
    greedy_wld, _ = WG.wild_number(method="greedy")
    ilp_edges = WG.find_milp_wild_set(upper_bound=greedy_wld)
    ilp_wld = len(ilp_edges)

    print(f"{n:>2} | {k:>2} | {conj:>6} | {ilp_wld:>6}")


# ### Coloring-Invariant Bounds

# In[ ]:


for n in range(3, 12):
    ell = n if n % 2 != 0 else n - 1
    G = graphs.CompleteGraph(n)
    WG = round_robin_proper_coloring(n)

    clb, cub = WG.component_bounds()
    ceil_lb = WG.ceiling_lower_bound()
    dip_lb = WG.dip_lower_bound()

    # predicted values
    kappa = (n+1)//2 if n % 2 != 0 else n//2
    pred_clb = kappa - 1
    pred_cub = ell * (kappa - 1)
    pred_ceil = math.ceil(n/2)

    match = (clb==pred_clb and cub==pred_cub and ceil_lb==pred_ceil and dip_lb==pred_ceil)
    print(f"K_{n}: clb={clb}(={pred_clb}), cub={cub}(={pred_cub}), "
          f"ceil={ceil_lb}(={pred_ceil}), dip={dip_lb} | match={match}")


# ### Uniform Dip Numbers

# In[ ]:


for n in range(3, 20):
    ell = n if n % 2 != 0 else n - 1
    G = graphs.CompleteGraph(n)
    WG = round_robin_proper_coloring(n)
    dips = set(d for d, _ in WG.get_all_dip_numbers())
    conj = dips == {ell-1}
    print(f"K_{n} | dip = {dips} | expected = {{{ell-1}}} | conj = {conj}")


# ### Structural Analysis of Wild Set

# In[543]:


def disjoint_star_wild_set(WG, n):
    """
    Attempt to build a wild set as disjoint stars.
    For odd n: place stars at every 3rd vertex, size 2 each,
    plus handle remainder.
    """
    k = math.ceil(n / 2)
    target = int(4 * k // 3)

    # find isolated vertex for each color
    isolated = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated[color] = v
                break

    # print(f"isolated vertices: {isolated}")
    # print(f"target wld: {target}")

    # each vertex v is isolated in exactly one color
    # verify this
    isolated_inv = {}  # vertex -> color it's isolated in
    for color, v in isolated.items():
        isolated_inv[v] = color

    print(f"each vertex isolated in one color: {len(isolated_inv) == n}")
    return isolated, isolated_inv

for n in range(3, 17, 2):
    print(f"K_{n} | ", end="")
    WG = round_robin_proper_coloring(n)
    iso, iso_inv = disjoint_star_wild_set(WG, n)


# In[535]:


def analyze_wild_set_structure(WG, wild_set):
    """Check if wild set forms a spanning forest of disjoint stars."""
    degree = {}
    for u, v in wild_set:
        degree[u] = degree.get(u, 0) + 1
        degree[v] = degree.get(v, 0) + 1

    # identify hubs (degree > 1) and leaves (degree 1)
    hubs  = {v: d for v, d in degree.items() if d > 1}
    leaves = {v: d for v, d in degree.items() if d == 1}

    # check vertex coverage
    covered = set(degree.keys())
    all_vertices = set(WG.vertices)

    # check it's a forest of stars (no vertex appears as both hub and leaf)
    is_star_forest = len(hubs.keys() & leaves.keys()) == 0

    print(f"  |W| = {len(wild_set)}")
    print(f"  hubs:     {dict(sorted(hubs.items()))}")
    print(f"  leaves:   {sorted(leaves.keys())}")
    print(f"  vertex cover: {len(covered)}/{len(all_vertices)}")
    print(f"  star forest: {is_star_forest}")
    print(f"  num stars: {len(hubs)}")

for n in range(5, 12):
    G = graphs.CompleteGraph(n)
    WG = round_robin_proper_coloring(n)
    greedy_ub, _ = WG.wild_number(method="greedy")
    wild_set = WG.find_milp_wild_set(upper_bound=greedy_ub)
    print(f"\nK_{n}:")
    analyze_wild_set_structure(WG, wild_set)


# In[549]:


def optimal_star_forest(n):
    """
    Build the optimal star forest for K_n.
    For odd n or n divisible by 3: span all n vertices.
    For even n not divisible by 3: span n-1 vertices.
    """
    if n % 2 == 1 or n % 3 == 0:
        v = n       # span all vertices
    else:
        v = n - 1   # leave one vertex out

    t = v // 3      # number of stars
    if t == 0:
        t = 1

    stars = []
    idx = 0
    for i in range(t):
        size = v // t + (1 if i < v % t else 0)
        stars.append(list(range(idx, idx + size)))
        idx += size

    edges = sum(len(s) - 1 for s in stars)
    print(f"K_{n}: {t} stars on {v} vertices, "
          f"sizes {[len(s) for s in stars]}, edges={edges}, "
          f"formula={int(4 * math.ceil(n/2) // 3)}, match={edges == int(4*math.ceil(n/2)//3)}")
    return stars


# In[550]:


for n in range(3, 16):
    optimal_star_forest(n)


# In[563]:


def test_optimal_forest_validity(n, num_colorings=20):
    """
    For several proper colorings of K_n, check whether
    the optimal_star_forest construction is color-connecting.
    """
    G = graphs.CompleteGraph(n)
    stars = optimal_star_forest(n)
    ell = n if n % 2 != 0 else n - 1
    valid_sets = []
    failed = []

    for i, WG in enumerate(generate_diverse_proper_colorings(
        G, ell, max_yields=num_colorings
    )):
        wild_set = []
        for star in stars:
            hub = star[0]
            for leaf in star[1:]:
                for u, v, c in WG.edges:
                    if set([u, v]) == set([hub, leaf]):
                        wild_set.append((u, v, c))
                        break

        valid = WG.is_color_connecting(wild_set)

        if valid:
            valid_sets.append(wild_set)
        else:
            failed.append((i, WG, wild_set))

    total = len(valid_sets) + len(failed)
    status = "✓ ALL VALID" if not failed else f"✗ {len(failed)} FAILURES"
    print(f"K_{n} | {status} | {len(valid_sets)}/{total} colorings")

    if failed:
        print(f"  first failure at coloring {failed[0][0] + 1}")

for n in range(3, 16, 2):
    test_optimal_forest_validity(n)


# In[562]:


def test_adapted_forest_validity(n, num_colorings=20):
    G = graphs.CompleteGraph(n)
    ell = n if n % 2 != 0 else n - 1
    t = n // 3
    valid_count = 0
    total = 0

    for WG in generate_diverse_proper_colorings(G, ell, max_yields=num_colorings):
        total += 1

        # find isolated vertex for each color
        isolated = {}
        for color in WG.colors:
            M = WG.monochromatic_subgraph(color)
            for v in WG.vertices:
                if M.degree(v) == 0:
                    isolated[color] = v
                    break

        # choose t colors deterministically, take their isolated vertices as hubs
        hub_colors = sorted(WG.colors)[:t]           # sort for determinism
        hub_list = [isolated[c] for c in hub_colors]
        hubs = set(hub_list)

        # assign remaining vertices to hubs as evenly as possible
        leaves = [v for v in sorted(WG.vertices) if v not in hubs]
        assignment = {h: [h] for h in hub_list}
        for i, leaf in enumerate(leaves):
            assignment[hub_list[i % t]].append(leaf)

        # build wild set
        wild_set = []
        for hub, star in assignment.items():
            for leaf in star[1:]:
                for u, v, c in WG.edges:
                    if set([u, v]) == set([hub, leaf]):
                        wild_set.append((u, v, c))
                        break

        valid = WG.is_color_connecting(wild_set)
        if valid:
            valid_count += 1
        else:
            print(f"  K_{n} coloring {total}: FAILS | hubs={hubs}")

    print(f"K_{n}: {valid_count}/{total} valid with adapted construction\n")

for n in range(3, 16, 2):
    test_adapted_forest_validity(n)


# In[564]:


def find_valid_hub_selection(WG, n, verbose=True):
    """
    Try ALL possible selections of floor(n/3) vertices as hubs.
    Tests all possible leaf assignments too.
    """
    from itertools import combinations, permutations

    t = n // 3

    # find isolated vertices
    isolated_by_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_by_color[color] = v
                break

    valid_hubs = []

    # try all possible hub vertex sets
    for hub_combo in combinations(range(n), t):
        hubs = set(hub_combo)
        hub_list = list(hub_combo)
        leaves = [v for v in sorted(WG.vertices) if v not in hubs]

        # try round-robin leaf assignment
        assignment = {h: [h] for h in hub_list}
        for i, leaf in enumerate(leaves):
            assignment[hub_list[i % t]].append(leaf)

        wild_set = []
        for hub, star in assignment.items():
            for leaf in star[1:]:
                for u, v, c in WG.edges:
                    if set([u, v]) == set([hub, leaf]):
                        wild_set.append((u, v, c))
                        break

        if WG.is_color_connecting(wild_set):
            valid_hubs.append(hub_combo)

    if verbose:
        print(f"  valid hub selections: {len(valid_hubs)} / {binomial(n,t)}")
        print(f"  isolated vertices:    {isolated_by_color}")
        if valid_hubs:
            print(f"  first valid hubs:     {valid_hubs[0]}")
        # check: do valid hubs always use isolated vertices?
        iso_verts = set(isolated_by_color.values())
        hub_from_iso = [h for h in valid_hubs if set(h).issubset(iso_verts)]
        print(f"  valid hubs that are isolated vertices: {len(hub_from_iso)}")

    return valid_hubs

# test on K_7 and K_9
for n in [7, 9, 11]:
    G = graphs.CompleteGraph(n)
    ell = n if n % 2 != 0 else n - 1
    print(f"\nK_{n}:")
    for WG in generate_diverse_proper_colorings(G, ell, max_yields=3):
        find_valid_hub_selection(WG, n)


# In[580]:


def search_color_connecting_partition_pruned(WG):
    # each vertex is isolated in exactly one color (Lemma bijection)
    isolated_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_color[v] = color
                break
    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}

    def is_good_triple(triple):
        # Lemma: {iso, a, b} is bad iff iso = v_c for some color c and rho(ab) = c
        x, y, z = triple
        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:
            c = isolated_color.get(iso)
            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:
                return False
        return True

    def to_wild(partition):
        wild = []
        for t in partition:
            tl = list(t)
            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:
                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))
        return wild

    def search(remaining, partition):
        if not remaining:
            return partition if WG.is_color_connecting(to_wild(partition)) else None
        first = min(remaining)
        for pair in combinations(sorted(remaining - {first}), 2):
            triple = (first,) + pair
            if not is_good_triple(triple):      # <-- the lemma, as a prune
                continue
            res = search(remaining - set(triple), partition + [triple])
            if res is not None:
                return res
        return None

    return search(set(WG.vertices), [])

for n in [9, 15, 21]:
    G = graphs.CompleteGraph(n)
    ok = total = 0
    for WG in generate_diverse_proper_colorings(G, n, max_yields=10):
        total += 1
        if search_color_connecting_partition_pruned(WG):
            ok += 1
    print(f"K_{n}: color-connecting partition found {ok}/{total}")


# In[581]:


def test_canonical_construction(n, num_colorings=15):
    """
    Place hubs at isolated vertices, attach remaining vertices as leaves,
    check whether THIS specific star forest is color-connecting.
    Reports failures and whether a different hub choice would have worked.
    """
    G = graphs.CompleteGraph(n)
    ell = n if n % 2 else n - 1
    t = n // 3
    valid = total = 0
    failures = []

    for WG in generate_diverse_proper_colorings(G, ell, max_yields=num_colorings):
        total += 1
        isolated = {}
        for color in WG.colors:
            M = WG.monochromatic_subgraph(color)
            for v in WG.vertices:
                if M.degree(v) == 0:
                    isolated[color] = v
                    break

        # canonical: pick t colors' isolated vertices as hubs
        hub_colors = sorted(WG.colors)[:t]
        hubs = [isolated[c] for c in hub_colors]
        leaves = [v for v in sorted(WG.vertices) if v not in set(hubs)]

        assignment = {h: [h] for h in hubs}
        for i, leaf in enumerate(leaves):
            assignment[hubs[i % t]].append(leaf)

        edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}
        wild = []
        for h, star in assignment.items():
            for leaf in star[1:]:
                wild.append((h, leaf, edge_color[WG.normalize_edge((h, leaf))]))

        if WG.is_color_connecting(wild):
            valid += 1
        else:
            failures.append(WG)

    status = "✓ all valid" if not failures else f"✗ {len(failures)} failures"
    print(f"K_{n}: {valid}/{total} {status}")
    return failures

for n in [9, 15, 21]:
    test_canonical_construction(n)


# In[582]:


def good_vs_connected(WG, max_good=300):
    isolated_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_color[v] = color
                break
    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}

    def is_good_triple(triple):
        x, y, z = triple
        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:
            c = isolated_color.get(iso)
            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:
                return False
        return True

    def to_wild(partition):
        wild = []
        for tr in partition:
            tl = list(tr)
            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:
                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))
        return wild

    counts = {"good": 0, "disconnected": 0}

    def search(remaining, partition):
        if counts["good"] >= max_good:
            return
        if not remaining:
            counts["good"] += 1
            if not WG.is_color_connecting(to_wild(partition)):
                counts["disconnected"] += 1
            return
        first = min(remaining)
        for pair in combinations(sorted(remaining - {first}), 2):
            triple = (first,) + pair
            if is_good_triple(triple):
                search(remaining - set(triple), partition + [triple])
                if counts["good"] >= max_good:
                    return

    search(set(WG.vertices), [])
    return counts["good"], counts["disconnected"]

for n in [9, 15, 21]:
    G = graphs.CompleteGraph(n)
    tot_good = tot_disc = 0
    for WG in generate_diverse_proper_colorings(G, n, max_yields=8):
        g, d = good_vs_connected(WG, max_good=300)
        tot_good += g
        tot_disc += d
    print(f"K_{n}: good sampled={tot_good}, good-but-disconnected={tot_disc}")


# In[15]:


from collections import defaultdict

def internal_edge_diagnosis(WG, max_good=150):
    isolated_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_color[v] = color
                break
    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}

    def is_good_triple(triple):
        x, y, z = triple
        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:
            c = isolated_color.get(iso)
            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:
                return False
        return True

    stat = defaultdict(lambda: [0, 0])  # internal_count -> [connected, disconnected]
    counter = {"n": 0}

    def analyze(partition):
        comp_of = {v: i for i, tr in enumerate(partition) for v in tr}
        t = len(partition)
        for color in WG.colors:
            M = WG.monochromatic_subgraph(color)
            internal = 0
            Q = Graph(); Q.add_vertices(range(t))
            for u, v in M.edges(labels=False):
                cu, cv = comp_of[u], comp_of[v]
                if cu == cv:
                    internal += 1
                else:
                    Q.add_edge(cu, cv)
            connected = Q.connected_components_number() == 1
            stat[internal][0 if connected else 1] += 1

    def search(remaining, partition):
        if counter["n"] >= max_good:
            return
        if not remaining:
            counter["n"] += 1
            analyze(partition)
            return
        first = min(remaining)
        for pair in combinations(sorted(remaining - {first}), 2):
            triple = (first,) + pair
            if is_good_triple(triple):
                search(remaining - set(triple), partition + [triple])
                if counter["n"] >= max_good:
                    return

    search(set(WG.vertices), [])
    return stat

for n in [15, 21]:
    G = graphs.CompleteGraph(n)
    agg = defaultdict(lambda: [0, 0])
    for WG in generate_diverse_proper_colorings(G, n, max_yields=6):
        s = internal_edge_diagnosis(WG)
        for k, (c, d) in s.items():
            agg[k][0] += c; agg[k][1] += d
    print(f"K_{n}: internal_edges -> [connected, disconnected]")
    for k in sorted(agg):
        c, d = agg[k]
        print(f"  {k}: connected={c}, disconnected={d}")


# In[20]:


from collections import Counter
from itertools import combinations

def all_color_connecting_partitions(WG, cap=3000):
    isolated_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_color[v] = color
                break
    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}

    def is_good_triple(triple):
        x, y, z = triple
        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:
            c = isolated_color.get(iso)
            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:
                return False
        return True

    def to_wild(partition):
        wild = []
        for tr in partition:
            tl = list(tr)
            for a, b in [(tl[0], tl[1]), (tl[1], tl[2])]:
                wild.append((a, b, edge_color[WG.normalize_edge((a, b))]))
        return wild

    sols = []
    def search(remaining, partition):
        if len(sols) >= cap:
            return
        if not remaining:
            if WG.is_color_connecting(to_wild(partition)):
                sols.append(frozenset(frozenset(t) for t in partition))
            return
        first = min(remaining)
        for pair in combinations(sorted(remaining - {first}), 2):
            triple = (first,) + pair
            if is_good_triple(triple):
                search(remaining - set(triple), partition + [triple])
                if len(sols) >= cap:
                    return
    search(set(WG.vertices), [])
    return sols

def within_coloring_invariants(WG):
    sols = all_color_connecting_partitions(WG)
    total = len(sols)
    pair_count = Counter()
    for P in sols:
        for triple in P:
            for a, b in combinations(sorted(triple), 2):
                pair_count[(a, b)] += 1
    always = [p for p, c in pair_count.items() if c == total]
    never  = [(a, b) for a in WG.vertices for b in WG.vertices
              if a < b and (a, b) not in pair_count]
    print(f"  solutions: {total} | forced-together pairs: {len(always)} "
          f"| forbidden pairs: {len(never)}")
    # relate forced pairs to color structure
    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}
    if always:
        forced_colors = Counter(edge_color[WG.normalize_edge(p)] for p in always)
        print(f"  forced pairs by edge color: {dict(forced_colors)}")
    return sols

for n in [9, 15, 21]:
    print(f"K_{n}:")
    WG = round_robin_proper_coloring(n)
    within_coloring_invariants(WG)


# In[29]:


def study(n, num_colorings=4, num_random=200):
    """
    For a single n: compare the optimal wild set's worst-color internal load
    against random size-matched partitions, to see if internal load separates
    'connects' from 'disconnects'.
    """
    G = graphs.CompleteGraph(n)
    ell = n if n % 2 else n - 1        # colors in a minimal proper coloring
    v, sizes = forest_spec(n)
    target = int(4 * math.ceil(n / 2) // 3)   # conjectured wild number
    print(f"K_{n}: spans {v} verts, sizes={sizes}, |W|={v - len(sizes)} (target {target})")

    # diverse colorings (Kempe-swap walk), NOT just round-robin
    for idx, WG in enumerate(generate_diverse_proper_colorings(G, ell, max_yields=num_colorings)):

        # optimal solution's worst-color internal load
        og = optimal_groups(WG)
        if og is None:
            print(f"  c{idx+1}: MILP T/O")     # solver timed out; skip
            continue
        opt_max = max(color_loads(WG, og).values())

        # random size-matched partitions for contrast
        verts = list(WG.vertices)
        good_max, bad_max, succ = [], [], 0
        for _ in range(num_random):
            random.shuffle(verts)
            spanned = verts[:v]                # even n: last vertex dropped
            groups, j = [], 0
            for s in sizes:                    # carve into prescribed sizes
                groups.append(spanned[j:j + s])
                j += s
            m = max(color_loads(WG, groups).values())   # this partition's worst load
            if WG.is_color_connecting(groups_to_wild(groups)):
                succ += 1
                good_max.append(m)             # connected
            else:
                bad_max.append(m)              # disconnected

        mean = lambda xs: f"{float(sum(xs)) / len(xs):.2f}" if xs else "--"
        pct  = float(100 * succ) / num_random

        print(f"  c{idx+1}: opt max-load={opt_max} | "
              f"random valid={pct:4.1f}% | "
              f"max-load: valid={mean(good_max)} invalid={mean(bad_max)}")

for n in range(6, 17):
    study(n)


# In[30]:


from collections import Counter
from itertools import combinations

def binding_constraint_orders(WG, max_good=400):
    """
    Among GOOD triple partitions that still DISCONNECT, record the size (in # of
    triples) of the smallest closed union for each disconnected color.

    A disconnected color = a proper union U of triples closed under M_i.
    The size of the SMALLEST such U is the 'order' of the binding constraint:
        order 1 -> single triple closed   (= the goodness lemma; pruned out below)
        order 2 -> a closed PAIR of triples (the first new local constraint)
        order k -> k triples jointly closed
    Low orders dominating => a few local rules nearly suffice.
    High orders needed   => connectivity is irreducibly global.
    """
    # vertex -> unique color it is isolated in (bijection, odd n)
    isolated_color = {}
    for color in WG.colors:
        M = WG.monochromatic_subgraph(color)
        for v in WG.vertices:
            if M.degree(v) == 0:
                isolated_color[v] = color
                break

    edge_color = {WG.normalize_edge((u, v)): c for u, v, c in WG.edges}

    def is_good_triple(triple):
        # the k=1 constraint: a triple {v_i, a, b} is bad iff rho(ab) = c_i
        x, y, z = triple
        for iso, a, b in [(x, y, z), (y, x, z), (z, x, y)]:
            c = isolated_color.get(iso)
            if c is not None and edge_color.get(WG.normalize_edge((a, b))) == c:
                return False
        return True

    order_hist = Counter()      # binding order -> count

    def analyze(partition):
        comp_of = {v: i for i, tr in enumerate(partition) for v in tr}  # vertex -> super-node
        t = len(partition)
        for color in WG.colors:
            M = WG.monochromatic_subgraph(color)
            Q = Graph(); Q.add_vertices(range(t))           # quotient on super-nodes
            for u, v in M.edges(labels=False):
                a, b = comp_of[u], comp_of[v]
                if a != b:
                    Q.add_edge(a, b)                        # a crossing M_i-edge
            comps = Q.connected_components()
            if len(comps) > 1:                              # color disconnects
                order_hist[min(len(c) for c in comps)] += 1 # smallest closed union

    # DFS over GOOD partitions only (k=1 used as a prune), as in your earlier search
    counter = {"n": 0}
    def search(remaining, partition):
        if counter["n"] >= max_good:
            return
        if not remaining:
            counter["n"] += 1
            analyze(partition)
            return
        first = min(remaining)
        for pair in combinations(sorted(remaining - {first}), 2):
            triple = (first,) + pair
            if is_good_triple(triple):
                search(remaining - set(triple), partition + [triple])
                if counter["n"] >= max_good:
                    return

    search(set(WG.vertices), [])
    return order_hist

for n in [9, 15, 21]:
    G = graphs.CompleteGraph(n)
    agg = Counter()
    for WG in generate_diverse_proper_colorings(G, n, max_yields=6):
        agg += binding_constraint_orders(WG)
    tot = sum(agg.values()) or 1
    print(f"K_{n}: binding-constraint order across disconnections")
    for k in sorted(agg):
        print(f"  order {k}: {agg[k]} ({100.0*agg[k]/tot:.1f}%)")

