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

Eggett

Answer 1

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.

Fado

So do you say my program is right except for the fact that I have to run it several times ?? – Eggett

Answer 2

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

Orectic

My understanding is that Karger's algorithm chooses an edge uniformly at random from the edges. This algorithm chooses a node uniformly at random and then chooses one of its edges uniformly at random. Thus an edge between two low degree nodes is more likely to be chosen than an edge between two high degree nodes. – Sapir

@Sapir and Oscar: thank you guys, this answer/comment was really helpful. I just wanted to share that I addressed Joels' comment and implemented Karger's algorithm with random edge choosing. You can see my answer below. – Spidery

Answer 3

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

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

This part of the code did not correctly eliminate the self loops. So I 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 was not needed. since the target node would be automatically changed to self loop and it would be removed.

edgelist.remove(target_edge)

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

Eggett

Answer 4

While looking at this post's answers, I came across Joel's comment. According to Karger's algorithm, the edge must be chosen uniformly at random. You can find my implementation which is based on Oscar's answer and Joel's 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

Spidery

Answer 5

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

Further iterating upon @sestus' helpful answer above, I wanted to address three 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 of times (in my case, 100 times) and keep track of the smallest min_cut and its related supervertices. That's what my outside function full_karger() achieves. I am not clever 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]))
   

Texture

"for edges in self.graph.values(): min_cut = len(edges)" looks wrong to me. What you'll end up with is the length of the last key's edge list. It seems like what you really want to return is the difference between the total number of edges before and after the cut. – Nepos

Answer 6

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

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

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

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

Mccarter