karger min cut algorithm in python 2.7
Question: Here is my code for the karger min cut algorithm.. To the best of my knowledge
the algorithm i have implemented is right. But I don get the answer right. If
someone can check what's going wrong I would be grateful.

    
    
    import random
    from random import randint
    
    #loading data from the text file#
    with open('data.txt') as req_file:
        mincut_data = []
        for line in req_file:
            line = line.split()
            if line:
                line = [int(i) for i in line]
                mincut_data.append(line)
    
    #extracting edges from the data #            
    edgelist = []
    nodelist = []
    for every_list in mincut_data:
        nodelist.append(every_list[0])
        temp_list = []
        for temp in range(1,len(every_list)):
            temp_list = [every_list[0], every_list[temp]]
            flag = 0
            for ad in edgelist:
                if set(ad) == set(temp_list):
                    flag = 1
            if flag == 0 :
                edgelist.append([every_list[0],every_list[temp]])
    
    
    #karger min cut algorithm#
    while(len(nodelist) > 2):
        val = randint(0,(len(edgelist)-1))
        print val
        target_edge = edgelist[val]
        replace_with = target_edge[0]
        should_replace = target_edge[1]
        for edge in edgelist:
            if(edge[0] == should_replace):
                edge[0] = replace_with
            if(edge[1] == should_replace):
                edge[1] = replace_with
        edgelist.remove(target_edge)
        nodelist.remove(should_replace)
        for edge in edgelist:
            if edge[0] == edge[1]:
                edgelist.remove(edge)
    
    print ('edgelist remaining: ',edgelist)
    print ('nodelist remaining: ',nodelist)
    

The test case data is :

    
    
    1 2 3 4 7
    2 1 3 4
    3 1 2 4
    4 1 2 3 5
    5 4 6 7 8
    6 5 7 8
    7 1 5 6 8
    8 5 6 7
    

Please copy it in a text file and save it as "data.txt" and run the program

The answer should be : the number of min cuts is 2 and the cuts are at edges
[(1,7), (4,5)]


Answer: So Karger's algorithm is a `random alogorithm'. That is, each time you run it
it produces a solution which is in no way guaranteed to be best. The general
approach is to run it lots of times and keep the best solution. For lots of
configurations there will be many solutions which are best or approximately
best, so you heuristically find a good solution quickly.

As far as I can see, you are only running the algorithms once. Thus the
solution is unlikely to be the optimal one. Try running it 100 times in for
loop and holding onto the best solution.

