Karger's min cut algorithm

kargers_min_cut_algorithm.rb

#######################
#
# While there are more than 2 vertices:
#   - pick a remaining edge (u, v) uniformly at random
#   - merge edge (u, v) into a single vertex
#   - remove self-loops

def deep_copy(original)
  Marshal.load Marshal.dump(original)
end

# Return edge [ u, v ]
def pick_edge(graph)
  u = v = nil

  while v.nil?
    u = graph.keys.sample  # Random vertex #1

    # Now cycle through the edge vertices, randomly, to find a good edge left
    v = graph[u].sort_by { rand }.detect { |v| graph.key?(v) }
  end
  [u, v]
end

# Merge edge [u, v]
def merge_edge(graph, edge)
  v1, v2    = edge
  graph[v1] += graph.delete(v2)
end

# Remove self looks
def remove_self_loops(graph, vertex)
  graph[vertex] - [vertex]
end

tmp_graph = {}
while line = gets
  nums = line.chomp.split
  tmp_graph[nums.shift] = nums
end
p tmp_graph

edges  = []
trials = 10_000
trials.times do |n|
  graph = deep_copy(tmp_graph)

  m = []
  while graph.keys.length > 2 do
    edge = pick_edge(graph)

    merge_edge(graph, edge)
    remove_self_loops(graph, edge.first)
  end
  edges += graph.values.map(&:length)
  min = edges.min
  edges = [min]
  puts "#{n}\tmin:\t #{min}"
end

p edges.min