kargerMinCut.py

#!/usr/bin/env python

from random import randint
from copy import deepcopy

def find_mincut(n, e):
    mincut = len(e)
    N = 2000
    for x in range(N):
        nodes = deepcopy(n)
        edges = deepcopy(e)
        m = karger_mincut(nodes, edges)
        if m < mincut:
            mincut = m
    print mincut

def karger_mincut(nodes, edges):
    while len(nodes) > 2:
        rand_edge = edges[randint(0, len(edges)-1)]
        edges = collapse_edge(edges, rand_edge)
        nodes.pop()
    return len(edges)

def collapse_edge(edges, rand_edge):
    new_edges = []
    for edge in edges:
        if edge[0] == rand_edge[0] or edge[1] == rand_edge[0]:
            if edge != rand_edge:
                new_edges.append((rand_edge[1], edge[0] if \
                                  edge[0] != rand_edge[0] else \
                                  edge[1]))
        else:
            new_edges.append(edge)
    for edge in new_edges:
        if edge[0] == edge[1]:
            new_edges.remove(edge)
    edges = new_edges
    return edges

#test cases
n1 = [0, 1, 2, 3]
e1 = [(0,1), (0,3), (1,2), (1,3), (2,3)]
#find_mincut(n1, e1)

lines = []
e = []
n = []
f = open("kargerMinCut.txt")
for line in f:
    lines.append([int(x) for x in line.split()])
for line in lines:
    n.append(line[0])
    for x in xrange(1, len(line)):
        if ((line[0], line[x]) not in e) and \
                ((line[x], line[0]) not in e):
            e.append((line[0], line[x]))
find_mincut(n, e)