[ACCEPTED]-karger min cut algorithm in python 2.7-min

This code also works.

import random, copy
data = open("***.txt","r")
G = {}
for line in data:
    lst = [int(s) for s in line.split()]
    G[lst[0]] = lst[1:]   

def choose_random_key(G):
    v1 = random.choice(list(G.keys()))
    v2 = random.choice(list(G[v1]))
    return v1, v2

def karger(G):
    length = []
    while len(G) > 2:
        v1, v2 = choose_random_key(G)
        G[v1].extend(G[v2])
        for x in G[v2]:
            G[x].remove(v2)
            G[x].append(v1) 
        while v1 in G[v1]:
            G[v1].remove(v1)
        del G[v2]
    for key in G.keys():
        length.append(len(G[key]))
    return length[0]

def operation(n):
    i = 0
    count = 10000   
    while i < n:
        data = copy.deepcopy(G)
        min_cut = karger(data)
        if min_cut < count:
            count = min_cut
        i = i + 1
    return count


print(operation(100))

0

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

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

As stated by Phil, I had to run my program 9 100 times. And one more correction in the 8 code was :

for edge in edgelist:
        if edge[0] == edge[1]:
            edgelist.remove(edge)

This part of the code did not 7 correctly eliminate the self loops. So I 6 had to change the code like :

for i in range((len(edgelist)-1),-1,-1):
        if edgelist[i][0] == edgelist[i][1]:
            edgelist.remove(edgelist[i])

And this line 5 was not needed. since the target node would 4 be automatically changed to self loop and 3 it would be removed.

edgelist.remove(target_edge)

Then as said earlier, the 2 program was looped for 100 times, and I 1 got the minimum cut by randomization. :)

While looking at this post's answers, I 5 came across Joel's comment. According to 4 Karger's algorithm, the edge must be chosen 3 uniformly at random. You can find my implementation 2 which is based on Oscar's answer and Joel's 1 comment below:

class KargerMinCutter:
def __init__(self, graph_file):
    self._graph = {}
    self._total_edges = 0
    with open(graph_file) as file:
        for index, line in enumerate(file):
            numbers = [int(number) for number in line.split()]
            self._graph[numbers[0]] = numbers[1:]
            self._total_edges += len(numbers[1:])

def find_min_cut(self):
    min_cut = 0
    while len(self._graph) > 2:
        v1, v2 = self._pick_random_edge()
        self._total_edges -= len(self._graph[v1])
        self._total_edges -= len(self._graph[v2])
        self._graph[v1].extend(self._graph[v2])
        for vertex in self._graph[v2]:
            self._graph[vertex].remove(v2)
            self._graph[vertex].append(v1)
        self._graph[v1] = list(filter(lambda v: v != v1, self._graph[v1]))
        self._total_edges += len(self._graph[v1])
        self._graph.pop(v2)
    for edges in self._graph.values():
        min_cut = len(edges)
    return min_cut

def _pick_random_edge(self):
    rand_edge = randint(0, self._total_edges - 1)
    for vertex, vertex_edges in self._graph.items():
        if len(vertex_edges) <= rand_edge:
            rand_edge -= len(vertex_edges)
        else:
            from_vertex = vertex
            to_vertex = vertex_edges[rand_edge]
            return from_vertex, to_vertex

Note, my response is in Python3 as it has 9 been a few years since this post last received 8 a response.

Further iterating upon @sestus' helpful 7 answer above, I wanted to address three 6 features:

1. Within the _pick_random_edge method of the class KarmgerMinCut(), rand_edge will ultimately match the length of vertex_edges. I adjusted the code to subtract 1 from rand_edge so rand_edge does not attempt to grab an element at a location 1 greater than the array length.
2. Understand which vertices comprise the two subgroupings representing the minimum cut. The functions implemented upon the "supervertices" dict achieve this.

3. Run this algorithm a large number 5 of times (in my case, 100 times) and keep 4 track of the smallest min_cut and its related 3 supervertices. That's what my outside function 2 full_karger() achieves. I am not clever 1 enough to implement this as an internal

   from random import randint
   from math import log
   
   class KargerMinCut():
   
       # 0: Initialize graph
       def __init__(self, graph_file):
   
           # 0.1: Load graph file
           self.graph = {}
           self.total_edges = 0
           self.vertex_count = 0
           with open(graph_file, "r") as file:
               for line in file:
                   numbers = [int(x) for x in line.split('\t') if x!='\n']
                   vertex = numbers[0]
                   vertex_edges = numbers[1:]
                   self.graph[vertex] = vertex_edges
                   self.total_edges+=len(vertex_edges)
                   self.vertex_count+=1            
           self.supervertices = {}
           for key in self.graph:
               self.supervertices[key] = [key]
   
       # 1: Find the minimum cut
       def find_min_cut(self):
           min_cut = 0
           while len(self.graph)>2:
               # 1.1: Pick a random edge
               v1, v2 = self.pick_random_edge()
               self.total_edges -= len(self.graph[v1])
               self.total_edges -= len(self.graph[v2])
               # 1.2: Merge the edges
               self.graph[v1].extend(self.graph[v2])
               # 1.3: Update all references to v2 to point to v1
               for vertex in self.graph[v2]:
                   self.graph[vertex].remove(v2)
                   self.graph[vertex].append(v1)
               # 1.4: Remove self loops
               self.graph[v1] = [x for x in self.graph[v1] if x != v1]
               # 1.5: Update total edges
               self.total_edges += len(self.graph[v1])
               self.graph.pop(v2)
               # 1.6: Update cut groupings
               self.supervertices[v1].extend(self.supervertices.pop(v2))
           # 1.7: Calc min cut
           for edges in self.graph.values():
               min_cut = len(edges)
           # 1.8: Return min cut and the two supervertices
           return min_cut, self.supervertices      
   
       # 2: Pick a truly random edge:
       def pick_random_edge(self):
           rand_edge = randint(0, self.total_edges-1)
           for vertex, vertex_edges in self.graph.items():
               if len(vertex_edges) < rand_edge:
                   rand_edge -= len(vertex_edges)
               else:
                   from_vertex = vertex
                   to_vertex = vertex_edges[rand_edge-1]
                   return from_vertex, to_vertex
   
       # H.1: Helpful young man who prints our graph
       def print_graph(self):
           for key in self.graph:
               print("{}: {}".format(key, self.graph[key]))
   
   graph = KargerMinCut('kargerMinCut.txt')
   
   def full_karger(iterations):
       graph = KargerMinCut('kargerMinCut.txt')
       out = graph.find_min_cut()
       min_cut = out[0]
       supervertices = out[1]
   
       for i in range(iterations):
           graph = KargerMinCut('kargerMinCut.txt')
           out = graph.find_min_cut()
           if out[0] < min_cut:
               min_cut = out[0]
               supervertices = out[1]
       return min_cut, supervertices
   
   out = full_karger(100)
   print("min_cut: {}\nsupervertices: {}".format(out[0],out[1]))
   

I totally agree with the above answers. But 8 when I run your code with Python 3.x, it 7 turns out to produce Code 1. This code sometimes 6 works, but sometimes fails. In fact, as 5 @user_3317704 mentioned above, there is 4 a mistake in your code:

for edge in edgelist:
    if edge[0] == edge[1]:
        edgelist.remove(edge)

You should not change 3 the items of the list when you do a for-do. It 2 raises mistakes. For your reference, it 1 could be

newEdgeList = edgeList.copy();
for edge in edgeList:
    if edge[0] == edge[1]:
        newEdgeList.remove(edge);
edgeList = newEdgeList;