In [76]:

    

import random, sys, math

class MinCut(object):
    def run(self):
        f = open("kargerMinCut.txt", "r")
        src = [[int(n)-1 for n in line.split()][1:] for line in f]
        n = len(src)
        for i in xrange(n):
            x = [0]*n
            for j in src[i]:
                x[j] += 1
            src[i] = x
        f.close()
        min_cut = sys.maxsize
        N = int(n*n*math.log(n))
        while N > 0:
            edges = [_[:] for _ in src]
            v = [_ for _ in xrange(n)]
            end = n-1
            while end > 1:
                i = random.randrange(0, end+1)
                p = v[i]
                v[0], v[i] = v[i], v[0]
                j = random.randrange(1, end+1)
                q = v[j]
                v[end], v[j] = v[j], v[end]
                for j in xrange(n):
                    edges[p][j] += edges[q][j]
                for i in xrange(end):
                    x = edges[v[i]]
                    x[p] += x[q]
                    x[q] = 0
                edges[p][p] = 0
                end -= 1
            res = sum(edges[v[0]])
            res2 = sum(edges[v[1]])
            assert res == res2
            if res < min_cut:
                min_cut = res
            if N%10000 == 0:
                print "min_cut=%d, N=%d"%(min_cut, N)
            N -= 1
        return min_cut


    

In [77]:

    

MinCut().run()


    

    




min_cut=20, N=210000
min_cut=20, N=200000
min_cut=20, N=190000
min_cut=20, N=180000
min_cut=20, N=170000
min_cut=20, N=160000
min_cut=20, N=150000
min_cut=20, N=140000
min_cut=20, N=130000
min_cut=20, N=120000
min_cut=20, N=110000
min_cut=20, N=100000
min_cut=20, N=90000
min_cut=20, N=80000
min_cut=20, N=70000
min_cut=20, N=60000
min_cut=20, N=50000
min_cut=20, N=40000
min_cut=20, N=30000
min_cut=20, N=20000
min_cut=20, N=10000






    
Out[77]:





20

In [ ]:

    




    

In [75]:

    

import copy
import random

def contraCut(mapD,edgeList):
    while len(mapD)>2:
        [u,v]=edgeList.pop(random.randrange(0,len(edgeList)-1))
        while([v,u] in edgeList):
            edgeList.remove([v,u])
        while([u,v] in edgeList):
            edgeList.remove([u,v])
        for ind in range(0,len(edgeList)):
            if edgeList[ind][0]==v:edgeList[ind][0]=u
            if edgeList[ind][1]==v:edgeList[ind][1]=u
        mapD[u]=mapD[u]-{v}
        mapD[v]=mapD[v]-{u}
        for [x,y] in mapD.items():
            if v in y:
                mapD[x]=(mapD[x]|{u})-{v}
        mapD[u]=mapD[u]|mapD[v]
        del mapD[v]

    return len(edgeList)/2

if __name__ == '__main__':
    f=open('kargerMinCut.txt','r')
    # f=open('testMinCut2.txt', 'r')
    mapDict={}
    for line in f.readlines():
        tmp=[int(x) for x in line.split()]
        mapDict[tmp[0]]=set(tmp[1:])
    f.close()
    
    edgeList=[]
    for [x,y] in mapDict.items():
        edgeList.extend([[x,v] for v in y])
    
    minNum = 2**100
    for i in range(200):
        cpmapDict=copy.deepcopy(mapDict)
        cpedgeList=copy.deepcopy(edgeList)
        
        num=contraCut(cpmapDict,cpedgeList)
        if num < minNum:
            minNum = num

    print("Result = " + str(minNum))


    

    




Result = 17

In [ ]:

    




    

In [ ]: