GRASP Algorithm

grasp.py

def grasp_max_clique(
    graph: dict[int, set[int]], iterations: int = 100, alpha: float = 0.2
) -> set[int]:
    """
    GRASP (Greedy Randomized Adaptive Search Procedure) for maximum clique.
    Combines randomized greedy construction with local search.

    Args:
        graph: Dictionary representing adjacency list
        iterations: Number of GRASP iterations
        alpha: Randomization parameter (0=pure greedy, 1=pure random)

    Returns:
        Best clique found
    """
    import random

    best_clique = set()

    for _ in range(iterations):
        # Construction phase: build a clique greedily with randomization
        clique = set()
        candidates = set(graph.keys())

        while candidates:
            # Calculate degrees in remaining candidate set
            degrees = []
            for node in candidates:
                # Count how many candidates this node is connected to
                degree = sum(1 for neighbor in graph[node] if neighbor in candidates)
                degrees.append((degree, node))

            if not degrees:
                break

            degrees.sort(reverse=True)

            # RCL (Restricted Candidate List): top alpha% of candidates
            rcl_size = max(1, int(len(degrees) * alpha))
            rcl = [node for _, node in degrees[:rcl_size]]

            # Randomly select from RCL
            selected = random.choice(rcl)
            clique.add(selected)

            # Update candidates: only nodes connected to all nodes in clique
            candidates = candidates & graph[selected]

        # Local search phase: try to improve
        clique = local_search(graph, clique)

        if len(clique) > len(best_clique):
            best_clique = clique

    return best_clique


def local_search(graph: dict[int, set[int]], initial_clique: set[int]) -> set[int]:
    """
    Local search to improve a clique by swapping nodes.

    Args:
        graph: Dictionary representing adjacency list
        initial_clique: Starting clique

    Returns:
        Improved clique
    """
    clique = initial_clique.copy()
    improved = True

    while improved:
        improved = False
        clique_list = list(clique)

        # Try 1-1 swaps: remove one node, add one node
        for node_out in clique_list:
            # Find nodes that could replace node_out
            remaining = clique - {node_out}
            candidates = set(graph.keys()) - clique

            for node_in in candidates:
                # Check if node_in is connected to all remaining nodes
                if all(neighbor in graph[node_in] for neighbor in remaining):
                    # Found a valid swap - check if it leads to expansion
                    new_clique = remaining | {node_in}

                    # Try to add more nodes
                    expanded = new_clique.copy()
                    for extra in candidates - {node_in}:
                        if all(neighbor in graph[extra] for neighbor in expanded):
                            expanded.add(extra)

                    if len(expanded) > len(clique):
                        clique = expanded
                        improved = True
                        break

            if improved:
                break

    return clique