26 Mar 2009
From Facebook's Job Puzzles page:
Cliques are sets of vertices in a graph that are complete, meaning there is an edge between every pair of the vertices in the clique. This Facebook puzzle is to find maximal cliques in presumably a large but sparse data set, since the problem is NP-complete (worst-case is when the graph is dense).
I will come back and cover this in broader detail at a later time.
The following solution in Ruby passed the Facebook puzzle robot:
#!/usr/bin/env ruby
# VROOM
# Kanwei Li, 2009
# Make sure input file exists and read from it
filename = ARGV[0]
unless filename && File.exist?(filename)
puts "error: must specify a valid input file"
exit
end
input = File.open(filename)
$build_matrix = {}
$adj_matrix = {}
while line = input.gets
line.strip!
next if line.empty?
splitted = line.split("\t")
a, b = splitted[1..2]
unless a == b
$build_matrix[a] ||= {}
$build_matrix[a][b] = true
if $build_matrix[b] && $build_matrix[b][a]
$adj_matrix[a] ||= []
$adj_matrix[a] << b
$adj_matrix[b] ||= []
$adj_matrix[b] << a
end
end
end
$cliques = []
def print_cliques(set, neighbors, seen)
if neighbors.empty? && seen.empty?
$cliques << set.sort.join(", ") if set.size > 2
else
possible_pivots = neighbors + seen
pivot = possible_pivots.inject(nil) do |best, p|
best.nil? || $adj_matrix[p].size > best.size ? best = p : best
end
neighbors.size.times do |i|
n = neighbors[i]
next if $adj_matrix[n].include?(pivot)
neighbors[i] = nil
print_cliques(set + [n], neighbors.compact & $adj_matrix[n], seen & $adj_matrix[n])
seen << n
end
end
end
print_cliques([], $adj_matrix.keys, [])
puts $cliques.sort.join("\n") << "\n"