benchmark.py

import time
import networkx as nx
import random
import matplotlib.pyplot as plt
from fvs.solver import iterative_compression


def generate_planted_fvs_graph(n, k, density=0.5):
    """Generates a graph with n nodes that has a FVS of size <= k

    Strategy:
    1. Create a set F (Forest) of n-k nodes and put a random tree on it
    2. Create a set S (Solution) of k nodes
    3. Add random edges between S and F, and inside S
    """
    if k >= n:
        raise ValueError("k must be smaller than n")

    G = nx.Graph()
    nodes = list(range(n))

    # Split the sets
    fvs_nodes = nodes[:k]
    forest_nodes = nodes[k:]

    # Create the forest structure (random tree here for complexity)
    if len(forest_nodes) > 0:
        T = nx.random_labeled_tree(len(forest_nodes))
        mapping = {i: forest_nodes[i] for i in range(len(forest_nodes))}
        T = nx.relabel_nodes(T, mapping)
        G.add_edges_from(T.edges())

    # Add random edges involving FVS nodes
    for u in fvs_nodes:
        for v in forest_nodes:
            if random.random() < density:
                G.add_edge(u, v)

    # Connections FVS <-> FVS
    for i, u in enumerate(fvs_nodes):
        for j in range(i + 1, len(fvs_nodes)):
            if random.random() < density:
                G.add_edge(fvs_nodes[i], fvs_nodes[j])

    return G


def benchmark_varying_k(fixed_n=50, max_k=12):
    """Tests impact of k on runtime (should be exponential)"""
    print(f"\n--- Test 1 : Varying k (n={fixed_n}) ---")
    print(f"{'k':<5} | {'Time (s)':<10} | {'FVS Size'}")
    print("-" * 35)

    times = []
    ks = list(range(1, max_k + 1))

    for k in ks:
        # Generate graph that has a solution of size k
        G = generate_planted_fvs_graph(n=fixed_n, k=k, density=0.3)

        start = time.perf_counter()
        # Look for solution of size at most k
        sol = iterative_compression(G, k)
        end = time.perf_counter()

        duration = end - start
        times.append(duration)

        sol_size = sol.number_of_nodes() if sol else "N/A"
        print(f"{k:<5} | {duration:<10.4f} | {sol_size}")

    return ks, times


def benchmark_varying_n(fixed_k=5, max_n=200, step=25):
    """Tests impact of n on runtime (should be polynomial)"""
    print(f"\n--- Test 2 : Varying n (k={fixed_k}) ---")
    print(f"{'n':<5} | {'Time (s)':<10} | {'FVS Size'}")
    print("-" * 35)

    times = []
    ns = list(range(fixed_k + 10, max_n + 1, step))

    for n in ns:
        G = generate_planted_fvs_graph(n=n, k=fixed_k, density=0.2)

        start = time.perf_counter()
        sol = iterative_compression(G, fixed_k)
        end = time.perf_counter()

        duration = end - start
        times.append(duration)

        sol_size = sol.number_of_nodes() if sol else "N/A"
        print(f"{n:<5} | {duration:<10.4f} | {sol_size}")

    return ns, times


def plot_results(k_data, n_data, fixed_k, fixed_n):
    """Plot curves for both benchmarks"""
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5), sharey=True)

    # Plot k
    ks, k_times = k_data
    ax1.plot(ks, k_times, "o-", color="red")
    ax1.set_title(f"Impact of k (n={fixed_n})")
    ax1.set_xlabel("FVS size (k)")
    ax1.set_ylabel("Time (seconds)")
    ax1.grid(True)
    # ax1.set_yscale('log')

    # Plot n
    ns, n_times = n_data
    ax2.plot(ns, n_times, "s-", color="blue")
    ax2.set_title(f"Impact of n (k={fixed_k})")
    ax2.set_xlabel("Num vertices (n)")
    ax2.set_ylabel("Time (seconds)")
    ax2.grid(True)

    plt.tight_layout()
    print("\nShowing plots...")
    plt.show()


if __name__ == "__main__":
    # Change these values depending on machine power
    MAX_K = 30
    FIXED_N_FOR_K = 200

    FIXED_K_FOR_N = 8
    MAX_N = 1000
    STEP_N = 30

    k_res = benchmark_varying_k(FIXED_N_FOR_K, MAX_K)
    n_res = benchmark_varying_n(FIXED_K_FOR_N, MAX_N, STEP_N)

    import json

    with open("benchmark_results.json", "w") as f:
        json.dump({"k_benchmark": k_res, "n_benchmark": n_res}, f)

    plot_results(k_res, n_res, FIXED_K_FOR_N, FIXED_N_FOR_K)