Karger's algorithm

kargerMinCut.py

import random

smallest = 100000
for t in range(1, 1000):
    input_file = open("kargerMinCut.txt")
    dic = {}
    for line in input_file:
        l = line.split('\t')
        nums = list(map(lambda x: int(x), l[:len(l) - 1]))
        dic[nums[0]] = nums[1:]

    while len(dic.keys()) > 2:
        v1 = list(dic.keys())[random.randrange(len(dic.keys()))]
        l1 = dic[v1]
        v2 = l1[random.randrange(len(l1))]

        dic[v1] += dic[v2]
        dic.pop(v2)
        # print(str(v1)+" remove: "+str(v2))

        dic[v1] = [x for x in dic[v1] if x != v2 and x != v1]

        # remove v2
        for i in dic.keys():
            if i != v1:
                dic[i] = [v1 if x == v2 else x for x in dic[i]]

    cut = len(dic[list(dic.keys())[0]])
    if smallest > cut:
        smallest = cut

print(smallest)