#!/usr/bin/env ruby
# tom.luo@gmail.com
# 01/24/2010


=begin
Cliques: according to Bron and Kerbosch 1973, is complete subgraph of a graph: part of a graph in which all
nodes are connected to each other
    BronKerbosch2(R,P,X):
       if P and X are both empty:
           report R as a maximal clique
       choose a pivot vertex u in P ⋃ X
       for each vertex v in P \ N(u):
           BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}
=end

def bronkerbosch(r, p, x)
  if p.empty? && x.empty?
    # ["a@example.com, b@example.com, c@example.com", ...]
    return $cliques << r.sort.join(", ") if r.size >= 3
  else
    px = p + x
    pivot = nil
    px.each do |u| 
      if pivot.nil? or $adjacency_hash[u].size > pivot.size then
         pivot = u
      end 
    end
 
    p.size.times do |i|
      v = p[i]
      # for each vertex v in P \ N(u):
      if not $adjacency_hash[v].include?(pivot)
        p[i] = nil
        # BronKerbosch2(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
        # P := P \ {v}
        bronkerbosch(r + [v], p.compact & $adjacency_hash[v], x & $adjacency_hash[v])
        # & = ⋂
        # X := X ⋃ {v}
        x += [v]
      end
    end
  end
end

# Main
file_name=ARGV[0]

file=File.open(file_name,"r")
lines = file.readlines

$temp_hash = {}
$adjacency_hash = {}

lines.each do |line|
  line.strip!
  next if line.empty?
  emails=line.split("\t")
  # ignore date = emails[0]
  e1 = emails[1]
  e2 = emails[2]
  pair12 = [e1,e2]
  pair21 = pair12.reverse 

  if   e1 != e2 
       pair12 = [e1,e2]
       pair21 = [e2,e1]
       $temp_hash[pair12] = 1 

# http://en.wikipedia.org/wiki/Adjacency_matrix
#                  a@example.com  b@example.com  c@example.com
# a@example.com    0              1              1
# b@example.com    1              0              1
# c@example.com    1              1              0              

# if e1 -> e2 and e2 -> e1 
#  adjacency_hash[e1] = [...,e2] i.e. e1 => [...,e2] (e1 maps to an array of emails)
#  adjacency_hash[e2] = [...,e1] i.e. e2 => [...,e1] (e2 maps to an array of emails)

    if $temp_hash[pair21] == 1
      $adjacency_hash[e1] = [] if $adjacency_hash[e1].nil? 
      $adjacency_hash[e2] = [] if $adjacency_hash[e2].nil?
      $adjacency_hash[e1] << e2
      $adjacency_hash[e2] << e1
    end
  end
end


$cliques = []

bronkerbosch([], $adjacency_hash.keys, [])
puts $cliques.sort.join("\n") << "\n"