#!/usr/bin/perl

$clustnum = 0;
$lasttime = time;

while ($line = <STDIN>)
{
  if ($line =~ m#([^ ]+) +([^ ]+)#)
  {
    $type = $1;
    $id = $2;
    if ($type eq "pub")
    {
      $pubs++;
      print STDERR "Keys loaded:$pubs\n" if ($pubs % 1000 == 0);
      $id = (split('/',$id))[1];
      $pub = $id;
    } elsif ($type eq "sig")
    {
      $sigs++;
      next if ($id eq $pub);
      push (@{$keys{$id}},$pub);
      push (@{$keys{$pub}},$id);
    } 
  } else {
  }
}


print STDERR "$pubs keys with $sigs signatures loaded in ". scalar(time - $lasttime) ." seconds, tracing....\n";
print "$pubs keys with $sigs signatures loaded in ". scalar(time - $lasttime) ." seconds, tracing....\n";
$lasttime = time;


for $key (keys %keys)
{
  undef %saw;
  @saw{@{$keys{$key}}} = ();
  @{$keys{$key}} = keys %saw;
}
undef %saw;

print STDERR "Duplicate children removed.\n";


for $key (sort keys %keys)
{
  unless ($checked{$keys{$key}})
  {
    #print "clusters:$clustnum\n";
    &tracekey($key);
    $clustnum++;
  }
}

sub tracekey
{
  @queue = @_;
  
  while (@queue)
  {
    #print "@queue\n";
    $key = shift @queue;
    $checked{$keys{$key}} = 1;
    push (@{$clusters[$clustnum]},$key);
    for $child ( @{$keys{$key}} , @{$keys{$key}} )
    {
      #print "parent:$key:child:$child:\n";
      push (@queue,$child) unless $checked{$keys{$child}};
    }
  }
}

print "$clustnum clusters processed in ". scalar(time - $lasttime) ." seconds:\n";
$clustnum = 0;
for $key (@clusters)
{
  print "cluster $clustnum, ". scalar(@{$key}) ." nodes:@{$key}\n";
  $clustnum++;
}