1
\$\begingroup\$

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 = [0]*len(edges)
    tries2 = 1.0/tries
    trialCut = [0]*len(edges)
    nodeObjs = [0] + [ 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[0]))


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

\$\endgroup\$
  • \$\begingroup\$ Obligatory xkcd link: imgs.xkcd.com/comics/ineffective_sorts.png \$\endgroup\$ – Sumurai8 Sep 22 '16 at 15:47
  • \$\begingroup\$ @Sumurai8 Haven't seen that one before but it was pretty great! \$\endgroup\$ – MattTheSnake Sep 22 '16 at 15:52
  • \$\begingroup\$ @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? \$\endgroup\$ – Gareth Rees Sep 24 '16 at 8:29
  • \$\begingroup\$ @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.) \$\endgroup\$ – Gareth Rees Sep 26 '16 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.