mincut

mincut.py

'''
Gabriel C. 2015
 
Karger's minimum-cut algorithm on a list of edges
(definitely not the best data structure choice)
'''

import random
        
def contract(edges, u, v, nodes):
   # print "Contracting %s of %s" % ((u, v), edges)
    
    for i in xrange(len(edges)):
        if edges[i][0] == v:
         #   print "Replacing %s with %s" % (edges[i], (u, edges[i][1]))
            edges[i] = (u, edges[i][1])
            
        if edges[i][1] == v:
          #  print "Replacing %s with %s" % (edges[i], (edges[i][0], u))
            edges[i] = (edges[i][0], u)

    return ([edge for edge in edges if edge != (u, u)], [node for node in nodes if node != v])
    
def min_cut(edges):
    nodes = []
	
    for edge in edges:
        for node in edge:
            if node not in nodes:
                nodes.append(node)
                
    while len(nodes) > 2:
        (u, v) = random.choice(edges)
        (edges, nodes) = contract(edges, u, v, nodes)

    #print edges
    return len(edges)

def get_min(edges, tries):
    minim = 1000
    for i in xrange(tries):
       result = min_cut(edges[:])
       if result < minim:
           minim = result

    return minim