Karger's min cut randomized contraction algorithm [implemented in Python]
<p>Here's my Python implementation for min cut algorithm-</p>

<pre><code>def findMinCut(dict):

replace_list = []
while len(dict.keys()) &gt; 2:   
    #uniformly pick 2 values
    a,b= random.sample(dict.keys(),2) 

    #keep record of all the replaced nodes
    replace_list.append(a)
    replace_list.append(b)
    if a in dict.keys() and b in dict.keys():   #always true if condition
        dict[a] += dict[b]
        while a in dict[a]:
            dict[a].remove(a)
        while b in dict[a]:
            dict[a].remove(b)
        del dict[b]

key = dict.keys()
l1 = dict[key[0]]
l2 = dict[key[1]]


for i in range(0,len(replace_list),2):
    for index_1 in range(0, len(l1)):
        if l1[index_1] == replace_list[i+1]:
            l1[index_1] = replace_list[i]
    for index_2 in range(0, len(l2)):
        if l2[index_2] == replace_list[i+1]:
            l2[index_2] = replace_list[i]

i = 0
j = 0
len_key1 = 0
len_key2 = 0

while i &lt; len(l1):
    if key[1] == l1[i]:
        len_key1 += 1
    i += 1
while j &lt; len(l2):
    if key[0] == l2[j]:
        len_key2 += 1
    j += 1

#deliberate check to make sure both lengths are always equal
if len_key1 == len_key2:
    return len_key1
else:
    print "unequal" + str(len_key2) + str(len_key1)

def main():
filename = sys.argv[1]
f = open(filename, 'rU')

dict = {}
for nums in f:
    nums = nums.split()
    dict[int(nums[0])] = map(int,nums[1:len(nums)])

N = (len(dict.keys()))
#N = N*N
#N = 1
N = int(math.ceil(N*N * math.log(N)))

true_min = findMinCut(dict)

for i in range(0,N):
    f = open(filename, 'rU')
    print i
    for nums in f:
        nums = nums.split()
        dict[int(nums[0])] = map(int, nums[1:len(nums)])
    min_cut = findMinCut(dict)
    if true_min &gt; min_cut:
        true_min = min_cut
print true_min
</code></pre>

<p>When I run this code of the following data set :</p>

<pre><code>1 2 3 4 7
2 1 3 4
3 1 2 4
4 1 2 3 5
5 4 6 7 8
6 5 7 8
7 1 5 6 8
8 5 6 7
</code></pre>

<p>I get the right min cut i.e., 2 but only after running for atleast N^2ln(N) times. However for larger data set, I'm not sure I get the right min cut value. </p>

<p>I have following questions:</p>

<ul>
<li><p>Is this the right implementation of algorithm?</p></li>
<li><p>Based on the results of above posted dataset and assuming the implementation is correct, how to determine the number of iterations after which the algorithm will compute the actual min cut?</p></li>
</ul>

<p>This is not for any college programming assignment. I'm trying to learn graph algorithms for knowledge purpose. Also, I'm new to Python, so any tips on the coding style  and how can they be improved will be highly appreciated. </p>

<p>You run the algorithm <strong>N^2ln(N)</strong> times because only after running the algorithm,
<strong>N^2ln(N)</strong> times, the <strong>probability of success is >= (N - 1)/(N).</strong></p>

<p>David Krager's algorithm cannot determine the number of iterations after which the right min-cut is found, becuase it is not deterministic.</p>

<p>The Key Idea is that you have to run the algorithm <strong>N^2ln(N)</strong> times to ensure high probability of success.</p>

<p>Its fairly simple to implement:</p>

<pre><code>Repeat the following N^2ln(N) times
{
 Start from a original graph.
 while there are more than 2 vertices
 {
   Pick a random edge with two vertices in different sets and contract it
 }

 X = The number of crossing edges
 Keep track of the minimum X found so far.     
}

Min Cut = Minimum X found.       
</code></pre>

python algorithm minimum