Last active
August 29, 2015 14:26
-
-
Save mykoweb/7e8d740064d86a3959d4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# With this algorithm, we merge/contract the head into the tail | |
# vertex, i.e., copy edges of head vertex into the tail vertex | |
# and then delete the head vertex. | |
adj_list = {} | |
file = File.read('./kargerMinCut.txt');nil | |
file.each_line do |line| | |
line_array = line.strip.split | |
vertex = line_array.shift | |
adj_list[vertex.to_s] = line_array | |
end | |
def randomized_contraction(adjacency_list) | |
adj_list = adjacency_list.dup | |
# The contraction hash key is the old vertex and its value is the | |
# value of the vertex that it was merged into. | |
contraction_hash = {} | |
# The deleted hash key is a vertex and its value is an array of vertices | |
# that were deleted and merged into the current vertex. | |
deleted_hash = {} | |
while adj_list.size > 2 | |
tail_vertex = adj_list.keys.sample | |
adj_row = adj_list[tail_vertex] | |
head_vertex = adj_row.sample | |
# Head vertices may be contracted into tail vertices | |
# multiple times. The following while loop will find | |
# the last remaining tail vertex in such chains. | |
while contraction_hash[head_vertex] | |
head_vertex = contraction_hash[head_vertex] | |
end | |
adj_list[tail_vertex] = adj_list[tail_vertex].concat Array(adj_list[head_vertex]) | |
adj_list.delete head_vertex | |
contraction_hash[head_vertex] = tail_vertex | |
if deleted_hash[tail_vertex].nil? | |
deleted_hash[tail_vertex] = Array(head_vertex) | |
else | |
deleted_hash[tail_vertex].concat Array(head_vertex) | |
end | |
if deleted_hash[head_vertex] | |
deleted_hash[tail_vertex].concat deleted_hash[head_vertex] | |
deleted_hash.delete head_vertex | |
end | |
adj_list[tail_vertex].delete(tail_vertex) | |
deleted_hash[tail_vertex].each do |v| | |
adj_list[tail_vertex].delete v | |
end | |
end | |
adj_list[adj_list.keys.first].count | |
end | |
file = File.open('./result.txt', 'a') | |
file.write " #{randomized_contraction(adj_list)} " | |
file.close |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment