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

Score: 11

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] = 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

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

Score: 9

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.

Score: 2

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 == edge:
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] == edgelist[i]:
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. :)

Score: 2

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] = 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
``````
Score: 1

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

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):

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
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
supervertices = out

for i in range(iterations):
graph = KargerMinCut('kargerMinCut.txt')
out = graph.find_min_cut()
if out < min_cut:
min_cut = out
supervertices = out
return min_cut, supervertices

out = full_karger(100)
print("min_cut: {}\nsupervertices: {}".format(out,out))
``````
Score: 0

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 == edge:
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 == edge:
newEdgeList.remove(edge);
edgeList = newEdgeList;
``````

More Related questions