1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #!/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"
|