Karger's random contraction algorithm for finding a min cut of a graph

random_contraction_algorithm.py

import numpy as np
from copy import deepcopy

def random_contraction(graph, n_repeat=None):
    """
    graph: undirected graph as a dict of lists 
        (adjacency list representation)
    n_repeat: Number of repeated independent trials
    """
    if n_repeat is None:
        n_repeat = len(graph)
    
    min_cuts = []
    
    for iterr in range(n_repeat):
        graph_ = deepcopy(graph)
        n_vertices = len(graph_.keys())

        while n_vertices > 2:
            u = np.random.choice(list(graph_.keys()))
            v = np.random.choice(graph_[u])

            # need to contract

            graph_[v] = graph_[v] + graph_[u]
            for i in graph_[u]:
                # move edges from u to v
                graph_[i] = list(map(lambda x: x if x != u else v, graph_[i]))

            graph_[v] = [n for n in graph_[v] if n != v] # remove self-loops
            graph_.pop(u)

            n_vertices -= 1
        
        n_crossing_edges = len(graph_[list(graph_.keys())[0]])
        min_cuts.append(n_crossing_edges)
        
    return min(min_cuts)