Karger's Min Cut Implementation in python 2.7 not giving the correct cuts

Question

 from random import randint
 from collections import defaultdict

 ######################

 def getGraph(filename):
 '''
 The function takes a txt file as input and returns
 the Graph with 1st element of each row as a vertex.
 '''
     with open(filename, 'r') as f_in:
         G = defaultdict(list)
         for row in f_in:
             row = row.split()
             G[row[0]] = row[1 : ]
     return G

 ######################

 def getVEPair(range):
 '''
 The function takes the range as input and returns a
 pair of random integers.
 '''
     v = randint(1, range)
     e = randint(1, range)
     return v, e

 ######################

 def removeVEPair(G, V, E):
 '''
 The function takes Graph, Vertex  and  Edge as input
 and removes this pair from the Graph. The function then
 returns the resulting Graph.
 '''
     while E in G[V]:
         G[V].remove(E)
     return G

 ######################

 def contractNodes(G, V, E):
 '''
 The function takes a Graph, vertex and edge as the input
 and contracts the two nodes which the edge connects. The
 function then returns the resulting Graph.
 '''
     edges = G[E]
     for edge in edges:

         if edge != V:
             G[V].append(edge)
     return G

 ######################

 def removeNode(G, V, E):
 '''
 The function intakes the graph and the node to be deleted.
 The function deletes the node and updates all instances of
 the deleted node in the Graph.
 The function then returns the resulting Graph.
 '''
     del G[E]
     for Vertex in G:
         while E in G[Vertex]:
             G[Vertex].remove(E)
             if V != Vertex:
                 G[Vertex].append(V)
     return G

 ######################

 def kargerMinCut():
 '''
 The function takes a graph as input and returns the min cut
 of the graph.
 '''
     minCut = []
     for i in range(0, 100):
         G = getGraph('dataGraph.txt')
         while(len(G) > 2):
             v, e = getVEPair(8)
             V = str(v)
             E = str(e)
             keys = G.keys()
             if V in keys and E != V:
                 if E in G[V]:
                     G = removeVEPair(G, V, E)
                     G = contractNodes(G, V, E)
                     G = removeNode(G, V, E)
                 else:
                     continue
         print G
         for v in G:
             minCut.append(len(G[v]))
             break
     return minCut
 ######################

 minCut = kargerMinCut()
 print '######################'
 print minCut
 print min(minCut)

I executed the code above by saving the data below in the dataGraph.txt file. The number i.e min cut is 1 and the correct cut is (4,5), but I am getting (1,7), (3,6), (8,4), (1,5), (3,7), (4,5) also as min cut pairs in separate iterations of the algorithm.

So my problem is that though the minCut i.e 1 is correct, but why am I getting these other pairs as minCuts?

In the data below, the first element of each row represents a node and the rest elements of the row denote the nodes to which the first element is connected. e.g 1 is connected to 3, 4 and 2.

1 3 4 2
2 1 4 3
3 1 2 4
4 5 3 2 1
5 4 8 6 7
6 8 7 5
7 5 8 6
8 5 7 6

Answer 1

I don't think it's correct to say "the correct cut is (4,5)".

I think it would be more correct to say "the correct cut is the two sets {1, 2, 3, 4} and {5, 6, 7, 8}". A cut is a partition of graph vertices into two, and the cutset (which is what you seem to be referring to) is the set of edges that connects these two sets. In the case of your graph the cutset corresponding to the minimum cut is {(4, 5)}.

Why do you get 'incorrect' results such as (1, 5)? This is because when you contract an edge and merge two nodes into one, you don't relabel the merged node. The merged node keeps the name of one of the two nodes. When you get to the end and the algorithm happens to find a cut of size 1, the labels of the two surviving nodes are those of the nodes from each side of the minimum cut that happened not to get deleted along the way. As I said, the correct cut is ({1, 2, 3, 4}, {5, 6, 7, 8}): the values 1 and 5 are just representatives for the two sides of the cut.

You will need to adapt your code so that adjusts node labels when it contracts an edge and merges two nodes into one. At the end, you can then read the cut from the labels of the two surviving nodes, and the cutset from the edges that connect the two sets of nodes.