# [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:

- 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.
- Understand which vertices comprise the two subgroupings representing the minimum cut. The functions implemented upon the "supervertices" dict achieve this.
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;
```

More Related questions

We use cookies to improve the performance of the site. By staying on our site, you agree to the terms of use of cookies.