Polynomial time vortex solver

import networkx as nx

# Generate a random graph
def generate_graph(num_nodes, num_edges):
    G = nx.gnm_random_graph(num_nodes, num_edges)
    return G

# Layering approach for Vertex Cover
def vertex_cover_layered(G, k, layer_size):
    edges = list(G.edges())
    layers = [edges[i:i + layer_size] for i in range(0, len(edges), layer_size)]
    cover = set()

    for layer in layers:
        for u, v in layer:
            if u not in cover and v not in cover:
                cover.add(u)
                cover.add(v)
                if len(cover) > k:
                    return False
    return True

# Measure time complexity for Vertex Cover using layering
def measure_vertex_cover_time(num_nodes, num_edges, k, layer_size):
    G = generate_graph(num_nodes, num_edges)
    start_solve_time = time.time()
    solvable = vertex_cover_layered(G, k, layer_size)
    end_solve_time = time.time()
    total_solve_time = end_solve_time - start_solve_time
    return total_solve_time, solvable

# Testing parameters for Vertex Cover
num_nodes_steps = [50, 100, 200, 400, 800]  # Larger instances of nodes
num_edges_factor = 2  # Number of edges will be num_nodes * num_edges_factor
k = 20  # Vertex cover size
layer_size = 50  # Size of each layer

results_vertex_cover = []

# Perform tests and collect results
for num_nodes in tqdm(num_nodes_steps, desc="Benchmarking Vertex Cover"):
    num_edges = num_nodes * num_edges_factor
    total_solve_time, solvable = measure_vertex_cover_time(num_nodes, num_edges, k, layer_size)
    results_vertex_cover.append((num_nodes, num_edges, total_solve_time, solvable))
    print(f"Nodes: {num_nodes}, Edges: {num_edges}, Solving Time: {total_solve_time:.2f}s, Solvable: {solvable}")

# Visualization for Vertex Cover
num_nodes, num_edges, solve_times, solvables = zip(*results_vertex_cover)

fig, ax = plt.subplots(figsize=(12, 8))
ax.plot(num_nodes, solve_times, marker='o', linestyle='-', color='b', label='Solving Time')
ax.set_xlabel('Number of Nodes')
ax.set_ylabel('Time (seconds)')
ax.set_title('Empirical Analysis of Layering Approach for Vertex Cover')
ax.legend()
ax.grid(True)

# Fit a polynomial curve to the data
coefficients = np.polyfit(num_nodes, solve_times, 2)  # Quadratic fit
polynomial = np.poly1d(coefficients)
x_fit = np.linspace(min(num_nodes), max(num_nodes), 100)
y_fit = polynomial(x_fit)
ax.plot(x_fit, y_fit, linestyle='--', color='r', label=f'Polynomial Fit: {polynomial}')
ax.legend()

plt.show()