Minimum Cut(Karger’s algorithm)

Question

I am trying to implement Krager's Min. cut algorithm in python to solve the following problem. This problem is from the edx course by Stanford, "Algorithms: Design and Analysis, Part 1"

The file contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to. So for example, the 6th row looks like : "6 155 56 52 120 ......". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc

run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut.

It involves the following adjacency list: https://pastebin.pl/view/39b087f8

Here is what I have coded up in python - I know the implementation is naive but I just want to get it right before it is optimised.

import random
import copy
with open('Contraction hwk.txt') as f:  #Please input the correct file path
    proto = f.readlines()
proto2 = [(x.replace('\t',' ').strip('\n')).split() for x in proto]
adjl = [[int(x) for x in i] for i in proto2]

solnset = []
for x in range(1000):#Repeated a 100 times cause the algo is not always correct
    wadjl = copy.deepcopy(adjl)
    nodes = list(range(1,len(adjl)+1))
    while len(nodes) > 2:
        randnodeval = random.choice(nodes)  #Select a random node
        randnode = wadjl[randnodeval-1] #Assign the random node to a var --> randnode
        randedgeval = random.choice(randnode[1:]) # Picks another random node(edge node) that is adjacent to the initial this will contract with the original random node
        if randedgeval == randnodeval:
            continue
        for node in wadjl[randedgeval-1][1:]:#This loop will go to all nodes adjacent to the edge node and replace the value of the edge node with the random node
            if node == randnodeval:#If the node is the same as the random node it removes the node as an adjacent node (Deletion of edge node from random node)
                modnode = wadjl[node-1][1:]
                edgevalnode = modnode.index(randedgeval)
                wadjl[node-1].pop(edgevalnode+1)
                continue
            modnode = wadjl[node-1][1:]
            edgevalnode = modnode.index(randedgeval)
            wadjl[node-1][edgevalnode+1] = randnodeval 
        randnodeidx = wadjl[randedgeval-1][1:].index(randnodeval)#This yeilds the index of the random node in the adjaceny list of the edge node 
        wadjl[randedgeval-1].pop(randnodeidx+1)#The random node is removed from that list(Deletion of random node from edgenode)
        randnode.extend(wadjl[randedgeval-1][1:])#The adjacency list of the edge node is merged with that of the random node
        del wadjl[randedgeval-1][1:]#The edge node is deleted
        try:#repeates/edges to itself are removed from the random node
            repeats = [i for i,x in enumerate(randnode) if x == randnodeval]
            for repeate in repeats:
                randnode.pop(repeat)
        except:
            pass
        #Edge node is removed from the nodes list
        noderemove = nodes.index(randedgeval) 
        nodes.pop(noderemove)
    for entry in wadjl:
        if len(entry) > 1:
            minc = len(entry) - 1 #edges in min cut case
            solnset.append(minc) #append solution to solution set
            break
# print(solnset)
print(min(solnset))

Based on some internet searches the answer seems to be 17. I get an answer of 20, moreover I don't think my implementation of the algorithm is correct as the solution set is too varied. I believe if implemented correctly the solution should appear quite often in this set.

Answer 1

The code you posted doesn't choose an edge uniformly at random unless the contracted graph happens to have uniform degree (which is almost always not the case). By choosing a random node and then a random neighbor of that node, it overweights nodes with few neighbors, which causes the optimal cut edges to be contracted more often than they should, creating larger final cuts.

In theory Karger's algorithm also needs Θ(n choose 2) iterations to succeed with constant probability, and n choose 2 is 200 (200 - 1) / 2 = 19,900 here, but this graph isn't close to the worst case, as 100 iterations seems to be more than sufficient most of the time.

Here's my implementation:

import fileinput
import random


def find(parents, i):
    r = i
    while r in parents:
        r = parents[r]
    while i in parents:
        p = parents[i]
        parents[i] = r
        i = p
    return i


def unite(parents, i, j):
    parents[i] = j


def karger(n, edges):
    edges = list(edges)
    random.shuffle(edges)
    parents = {}
    for i, j in edges:
        if n <= 2:
            break
        i = find(parents, i)
        j = find(parents, j)
        if i == j:
            continue
        unite(parents, i, j)
        n -= 1
    return sum(find(parents, i) != find(parents, j) for (i, j) in edges)


def main():
    lines = list(fileinput.input())
    n = len(lines)
    edges = set()
    for line in lines:
        fields = iter(map(int, line.split()))
        u = next(fields)
        edges.update((min(u, v), max(u, v)) for v in fields)
    print(min(karger(n, edges) for k in range(1000)))


if __name__ == "__main__":
    main()