import random
import math
import sys

def min_cut(g):
    """
    Return a min cut with probability of failure 1/n.

    :param dict g: graph represented as an adjacency list.
    :returns: int representing min cut.
    """
    n = len(g)
    # repeat n choose 2 * ln n times
    runs = int((n * (n - 1) / 2) * math.log(n))
    min = sys.maxint
    for i in range(0, runs):
        temp_g = g
        res = random_contraction(temp_g)
        if res < min:
            min = res

    return min

def random_contraction(g):
    """
    Return a potential minimum cut from a graph.

    :param dict g: graph we are contracting represented as an adjacency list.
    :returns: int representing a potential min cut.
    """
    edges = get_edgelist(g)

    while len(g) > 2:
        rand = random.randrange(0, len(edges))
        (u,v) = edges.pop(rand)
        g[u] = g[u] + g[v] # contract u and v
        g[u] = [adj for adj in g[u] if adj not in [u, v]] # remove self loops from nodes
        del g[v]

        # update occurrences of v to u
        for i, edge in enumerate(edges):
            if v in edge:
                edge = tuple([node if node != v else u for node in edge])
                edges[i] = edge

        # remove self loops from edges
        edges = [(x,y) for (x,y) in edges if x != y]

    return len(edges)

def get_edgelist(g):
    """
    Return a list of edges from a graph represented as an adjacency list.

    :param dict g: graph represented as an adjacency list.
    :returns: list of tuples.
    """
    edges = set([])
    for node in g:
        for adj in g[node]:
            # sort to deduplicate
            sorted_tuple = tuple(sorted((node, adj)))
            edges.add(sorted_tuple)

    return list(edges)


# TODO: since min_cut does not succeed all the time, determine how to write unit test

# model this graph:
# 'a'---'b'---'c'---'d'
# |   X  |     |  X  |
# 'e'---'f'---'g'---'h'

g = {
    'a': ['b','e','f'],
    'b': ['a','e','f','c'],
    'c': ['b','g','h','d'],
    'd': ['c','g','h'],
    'h': ['g','c','d'],
    'g': ['f','c','d','h'],
    'f': ['e','a','b','g'],
    'e': ['a','b','f']
}

print min_cut(g)
@@ -1,12 +1,52 @@
+from typing import Mapping, List, Tuple%0A
 import rando
@@ -71,16 +71,17 @@
 rt sys%0A%0A
+%0A
 def min_
@@ -85,17 +85,49 @@
 in_cut(g
-)
+: Mapping%5Bstr, List%5Bstr%5D%5D) -%3E int
 :%0A    %22%22
@@ -585,17 +585,49 @@
 action(g
-)
+: Mapping%5Bstr, List%5Bstr%5D%5D) -%3E int
 :%0A    %22%22
@@ -1446,17 +1446,67 @@
 gelist(g
-)
+: Mapping%5Bstr, List%5Bstr%5D%5D) -%3E List%5BTuple%5Bstr, str%5D%5D
 :%0A    %22%22

add type hints