#!/usr/bin/perl

# sigclust.pl v0.5 (c) Darxus@ChaosReigns.com
# http://www.chaosreigns.com/code/
#
# Displays a list of IDs in a keyring, grouped by cluster
# (Group of IDs indirectly linked by signatures)
#
# v0.5 Nov 26 17:39 1st one I got to process the entire list of signatures from
#                   ftp://ftp.es.net/pub/pgp-public-keys/keys/signature from Aug 11, 1999

$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) unless &keychild($id,$pub);
      push (@{$keys{$pub}},$id) unless &keychild($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 (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;
    next if $checked{$keys{$key}};
    $checked{$keys{$key}} = 1;
    push (@{$clusters[$clustnum]},$key);
    for $child ( @{$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++;
}

sub keychild
{
  $key = @_[0];
  $child = @_[1];
  for $member (@{$keys{$key}})
  {
     return 1 if ($member eq $child);
  }
  return 0;
}