karger min cut algorithm in python 2.7
algorithm, min, python
Solution
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.
Problem
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)]