Randomized MinCut Algorithm

mincut.py

# -*- coding: utf-8 -*-
"""
Created on Sun Feb 15 18:35:50 2015

@author: mwoods
"""
import random

toy_graph = {1: [2, 4],
             2: [1, 4, 3],
             3: [2, 4],
             4: [1, 3, 2]}
             
    
def edge_ct(graph):
    return sum([len(v) for v in graph.values()])//2

def node_ct(graph):
    return len(graph)


def cut(graph, edge):
    node1, node2 = edge
    #collapse node1 into node2
    node1_endpoints = graph.pop(node1)
    
    
    #Move the edges terminating at node1 to node2    
    for n in node1_endpoints:
        graph[n] = [node2 if m == node1 else m for m in graph[n]]
    
    graph[node2] += node1_endpoints
    
    #Elimiate self loops
    graph[node2] = [n for n in graph[node2] if n != node2]
    
def MinCut(graph, n_trials = 1000):
        
    results = []
    min_value = float('inf')
    
    print("Starting Program: this may take a while....")
    for i in range(n_trials):
        graph_tmp = graph.copy()
        #print graph_tmp
        while len(graph_tmp) > 2:
            #find random edge
            left_node = random.choice(graph_tmp.keys())
            right_node = random.choice(graph_tmp[left_node])
            
            rand_edge = (left_node, right_node)
            cut(graph_tmp, rand_edge)
        
        min_cut = edge_ct(graph_tmp)
        results.append(min_cut)
        if min_cut < min_value:
            min_value = min_cut
        if (i % 10) == 0:
            print 'Iteration: %d, MinCut: %d, MinCut so far: %d'%(i, min_cut, min_value) 
    return results