Kargers Min Cut algorithm.....

kargers_min_cut_algorithm.rb

# Input should be whitespace separated input where the first column is the vertex, and the remaining input is a list of vertices # it shares edges with.
# 1 2 3 4    vertex 1 shares an edge with 2, 3 and 4
# 2 1 4      vertex 2 shares an edit with 1, 4

trials = (ENV["T"] || 1).to_i

#######################
#
# 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(foo)
  Marshal.load Marshal.dump(foo)
end

# Return edge [ u, v ]
def pick_edge(graph)
  u = graph.keys.sample
  v = graph[u].sample
  [u, v]
end

# Merge edge [u, v], uniqify
def merge_edge(graph, edge)
  v1, v2 = edge

  graph[v1] += graph[v2]

  # report neighbors to merging vertext
  graph[v2].each do |n| 
    graph[n].map! { |i| i == v2 ? v1 : i }
  end

  graph.delete(v2)
end

# Remove self looks
def remove_self_loops(graph, edge)
  v1, _ = edge
  graph[v1] -= [v1]
end

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

edges = []
trials.times do |n|
  graph = deep_copy(original_graph)

  while graph.keys.length > 2 do
    edge = pick_edge(graph)
    merge_edge(graph, edge)
    remove_self_loops(graph, edge)
  end

  edges += graph.values.map &:length
  edges = edges.min
  edges = [min]
  puts "#{n}\tmin:\t #{min}"
end

p edges.min