# FindUnion data structure used to find the minimum cut of a graph

I am trying to find the bottleneck in my code for computing the minimum cut of a graph. Currently the program runs in about 40 minutes on the test data set linked below (200 nodes and ~2000 edges). I have tried to make it as fast as possible by removing a dictionary and replacing it with a list (nodeObjs) as well as resetting the values of the objects instead of creating new ones on each iteration.

Neither of these have lead to any real improvement in speed and I lost some of the generality by using a list instead of a dictionary to store my objects. I will likely get rid of the list later to make it more general. The number of trials required is large because the odds of success of an individual trial is approximately $\frac{1}{n^2}$ where $n$ is the number of nodes.

On the linked data set the solution is found early but I believe this is due to the structure of the graph.

import random
from math import log
from readGraphIn import readGraphIn
from unionfind import UnionFind
from time import clock

def randomMinCut(nodes,edges):

tries = int( (len(nodes)**2)*log(len(nodes),2))
minCut = *len(edges)
tries2 = 1.0/tries
trialCut = *len(edges)
nodeObjs =  + [ UnionFind(node) for node in nodes ]

for i in xrange(tries):
if not i % 100:
print 'Progress:', i*tries2*100,'Tries:', i, 'MinCut Length', len(minCut)
#random.shuffle(edges)
treeIndex = 0
cutIndex = 0

# reset object values without creating new values
for node in nodeObjs[1:]:
node.__init__(node.vertex)

for u,v in edges:
#first build two unconnected forests
if treeIndex >= len(nodes)-2:
if nodeObjs[u].find_root() != nodeObjs[v].find_root():
trialCut[cutIndex] = [u,v]
cutIndex += 1
if cutIndex > len(minCut):
break
elif nodeObjs[u].find_root() != nodeObjs[v].find_root():
treeIndex += 1
UnionFind.union(nodeObjs[u], nodeObjs[v])

if cutIndex < len(minCut):
minCut = trialCut[:cutIndex]

print minCut
return len(minCut)

nodes, edges = readGraphIn()
t0 = clock()
print randomMinCut(nodes, edges)
t1 = clock()
print 'Run Time: ', t1-t0
#print edgeContraction(edges, tuple(edges))

class UnionFind(object):
'''
Used to initialize the set and then holds the required functions to operate on them
'''

def __init__(self, vertex):
self.rank = 0
self.parent = self
self.vertex = vertex

def find_root(self):
if self != self.parent:
self.parent = self.parent.find_root()
return self.parent

@staticmethod
def union(x,y):
xroot = x.find_root()
yroot = y.find_root()

if xroot == yroot:
return

if xroot.rank > yroot.rank:
yroot.parent = xroot
else:
xroot.parent = yroot
if xroot.rank == yroot.rank:
yroot.rank += 1

return

def __str__(self):
return 'Me: %s, Parent: %s, rank: %s ' % ( str(self.vertex), str(self.parent.vertex), str(self.rank))


Test data set location

• Obligatory xkcd link: imgs.xkcd.com/comics/ineffective_sorts.png – Sumurai8 Sep 22 '16 at 15:47
• @Sumurai8 Haven't seen that one before but it was pretty great! – MattTheSnake Sep 22 '16 at 15:52
• @MattTheSnake: Your link for the test data is not working for me: I get "access denied". Also, can you show us the source code for the readGraphIn function, please? – Gareth Rees Sep 24 '16 at 8:29
• @MattTheSnake: Also, I notice that you've commented out the call to random.shuffle(edges). Doesn't this break things? (Since every try will be the same.) – Gareth Rees Sep 26 '16 at 9:35