Calling a randomized algorithm iteratively, receiving the same result each call

Question

I am attempting to implement Kargers min-cut algorithm. The algorithm is a randomized algorithm that you should run (n(logn))^2 times to be confident you've found the minimum cut. I've done a novice's job at implementing this algorithm in-place in Ruby:

def karger(graph)
#graph will be an array
#each element of graph is an array
#these subarrays are of the form [[4], 43, 23, 1, 67]
#where the zeroth element is the vertex label
#the other elements represent edges to other vertices.
  while graph.length > 2
    #u & v are the indices of two random vertices that will be merged together
    u = rand(0...graph.length)
    v = rand(0...graph.length)
    #while loop ensures u != v
    while v == u
      u = rand(0...graph.length)
      v = rand(0...graph.length)
    end
    #merge u & v into a single vertex, 
    graph[u] += graph[v][1...graph[v].length]
    graph[u][0].concat(graph[v][0])
    graph.delete_at(v)
  end
  #this nested block eliminates self loops on the two remaining superveticies
  graph.each do |z|
    z.each do |x|
      unless x.class == Array
        if z[0].include?(x)
          z.delete(x)
        end
      end
    end
  end
  return (graph[0].length)-1 #-1 since the first element of both subarrays is the vertex   label
end

My problem is that when I try to create a block or loop to run the algorithm the necessary (nlog(n))^2 times, every single cut is the same value. So if the first call of karger() produces a cut of 2, then every single call after that will return 2 as well. However, if I call karger() manually, just pressing cntrl R in textmate, I will get a variation in my results. The first time I run it on a certain input, I get a cut of 5, the next time, 2. Thus my attempt at generating a massive sample of karger() calls, and finding the minimum result does not work, because I will just have a massive sample of 2's or 5's or whatever. If I run the block that calls karger() (nlog(n))^2 times, I get different answers, depending on what the first call of karger() returns, since every other call returns the same result.

Hope that's clear.

Here's a sample graph:

testgraph1 = [[[1],2,2,3], [[2],1,1,3,4,5], [[3],1,2,4], [[4],2,3], [[5],2]]

EDIT:

I thought it might be helpful if I added the method I've used to iteratively call the function:

def kargeriterate(graph)
  n = graph.flatten.length
  min = graph.flatten.length
  ((n)*(Math.log(n)))**2.to_i.times do |z|
      a = karger(graph)
      puts a  #this puts is here just to see each output
      if a < min
        min = a
      end
    end
  return min
end

in the interest of full disclosure. Since you're a new user and this is your first question. Is this a homework problem? Not that that's necessarily an issue, but you might want to do that to avoid being voted down. — engineerDave, Jul 15 '12 at 20:29
depends on what you mean by homework. It is for a coursera class on algorithms. This is not homework in the sense that you are helping me receive a grade from a class i've paid tuition for, I am just interested in algorithms, and IMO this is the best way to learn it for free. — Nathaniel Gentile, Jul 15 '12 at 20:41

score 2 · Accepted Answer · answered Jul 15 '12 at 21:07

Methods like delete and delete_at modify their argument in place. Since everything is passed by value in ruby, this means that the second (and third, fourth, fifth etc) time you call karger you're doing so on the already processed graph, so the method doesn't do anything.

It looks like you modify the arrays nested inside graph as well as graph itself, so doing graph=graph.dup at the start of your karger method wouldn't be enough. There isn't a standard deep copy built-in to ruby, but an easy way to achieve this is to dump and deserialize your object:

def karger(graph)
  graph = Marshal.load(Marshal.dump(graph))
  ...
end

Calling a randomized algorithm iteratively, receiving the same result each call

1 Answers1