Find MinCut of a Graph using networkx

'''
* Implemented by Arjun sunel.
'''
#Program to find min-cut of a graph using Karger's Algorithm having running time O(n*n*n*n*logn)
import networkx as nx, random, matplotlib.pyplot as plt
def main():
 G =nx.MultiGraph()     #defining graph
 G.add_edges_from([(1,2),(2,3),(3,4),(4,2),(4,5) , (6,7), ( 7,8) , ( 8,5) , (1,3) , (6,5) , (9, 10) , (10,1) , (9, 1), (5,1) , (5, 11) , (7,5) , (8, 6)  , (10 , 3) , (9, 3) , (11, 7)])  #adding edges
 min_cut(G)  #prints min cut of G        #K = nx.gnm_random_graph(10 , 40) ---> used for creating a random graph
 nx.draw(G)   #plots graph G
 plt.show()   #to show graph
 
def min_cut(G):  #min-cut function
 u= (G.order())**2 # number of iterations required to ensure that we will get a min-cut
 List=Cut(G)  #initialized List to a Cut of G
 while u>0:   #while loop starts
  if len(Cut(G))<len(List): #comparing current and previous cut's lengths to get minimum of them
   List=Cut(G) 
  u=u-1
 print "min_cut is :", List   #prints min cut
 
def Cut(G):   #function to find a cut of G
 H = nx.MultiGraph()  #declared H and I as multigraphs
 for a,b in G.edges_iter():  # "for loop" for assigning "edges" as "weights" to each edge
  H.add_edge(a,b,weight= (a,b)) 
  
 while H.order()>2: # while loop  until number of nodes becomes 2
  (a,b,d)=random.choice(H.edges(data=True)) #randomly selected edge    

  for e  in H.edges():
   if    e== ( a , b ) : H.remove_edge(a,b )   #removing randomly selected edge

  for i in H.neighbors(b):    #adding and deleting edges during combining two nodes
   j=len(H.get_edge_data(b,i))
   while j>0: 
    H.add_edge( a ,  i  ,  weight=  H.get_edge_data(b,i)[j-1]['weight']   )
    j=j-1
   H.remove_edge(b,i)
  H.remove_node(b)  #while loop ends
  
 cut=[]
 for e in H.edges(data = True):
  cut.append(e[2]['weight']) 
 return cut     #returns a cut of the graph
 
if __name__ == '__main__':
    main()      #calls the main function