'''
* 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
