karger.py

import networkx as nx
import matplotlib.pyplot as plt
import random
import matplotlib.animation as animation
import numpy as np

# Step 1: Create the graph
G = nx.MultiGraph()
edges = [
    (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6),
    (3, 7), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8), (5, 9), (6, 7), (6, 8), (6, 9), (6, 10), (7, 8), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10),
]
G.add_edges_from(edges)

# Initial position
pos = nx.spring_layout(G, seed=42)

# Step 2: Define Karger's Min-Cut algorithm with animation
fig, ax = plt.subplots()


def interpolate_positions(pos1, pos2, alpha):
    """Interpolates positions between pos1 and pos2 based on alpha."""
    return {
        node: (1 - alpha) * np.array(pos1[node]) + alpha * np.array(pos2[node])
        for node in pos1
    }


def generate_frames(G, pos):
    name = {i: i for i in G.nodes}

    def find(i):
        while i != name[i]:
            i = name[i]
        return i

    def union(i, j):
        i = find(i)
        j = find(j)
        name[i] = j

    frames = []
    while len(G.nodes) > 2:
        print("Edges:", sum(w for u, v, w in G.edges))
        u, v = random.choice([(u, v) for u, v, w, in G.edges for _ in range(1 + w)])
        # Contract edge and recompute the layout
        old_G = G.copy()
        G = nx.contracted_edge(G, (u, v), self_loops=False)
        new_pos = nx.spring_layout(G, pos=pos, fixed=G.nodes)

        union(v, u)
        for vv, uu in name.items():
            new_pos[vv] = new_pos[uu]

        for alpha in np.linspace(0, 1, 10):
            intermediate_pos = interpolate_positions(pos, new_pos, alpha)
            frames.append((old_G, intermediate_pos))

        pos = new_pos

    return frames


# Generate frames
frames = generate_frames(G.copy(), pos)


# Animation function
def update(num):
    ax.clear()
    G, pos = frames[num]
    # Draw the graph with edge multiplicity
    edge_labels = nx.get_edge_attributes(G, "weight")
    nx.draw(G, pos, with_labels=True, node_color="lightblue", ax=ax)
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, ax=ax)


# Create animation
ani = animation.FuncAnimation(fig, update, frames=len(frames), repeat=False)
name = "karger_min_cut_animation_with_contraction.mp4"
ani.save(name, writer="ffmpeg")
print(f"Animation saved as {name}")