#!/usr/bin/perl -w

# springgraph v0.44, (c) 2002 Darxus@ChaosReigns.com, released under the GPL
#
# ALPHA SOFTWARE
# I *WILL* BREAK BACKWARDS COMPATIBILITY
#
# This program attempts to render .dot files in a fasion similar to neato,
# which is part of graphviz:  http://www.research.att.com/sw/tools/graphviz/.
# I have never looked at any of the code in graphviz.
#
# Example useage:
#
# cat test.dot | ./springgraph.pl > springgraph.png

# v0.26 May 06 16:12:30 2002 
# v0.27 May 06 18:15:38 2002 cleanup
# v0.44 May 06 23:56:45 2002 

use GD;
use strict;
use vars qw(
$push
$pull
%node
$im
$source
$dest
$nodenum
$blue
$black
$white
$dist
$wantdist
$iter
$maxiter
$percent
$xdist
$ydist
$wantxdist
$wantydist
$newdist2
$xmove
$ymove
$movecount
$rate
$nodes
%link
$continue
$done
$pullmove
$pushmove
$line
@nodelist
%saw
$name
$label
$margin
$minx
$miny
$maxx
$maxy
$scale
$nodesize
$powderblue
$darkgrey
$h
$s
$v
$r
$g
$b
$color
$maxxlength
$minxlength
);

$push = 2000;
$pull = .1;
$maxiter = 400;
$rate = 2;
$nodes = 5;
$done = 0.1;
$margin = 20;
$nodesize = 40;

srand 1;

if (defined $ARGV[0])
{
  $scale = $ARGV[0];
} else {
  $scale = 1;
}

while ($line = <STDIN>)
{
  undef $name;
  next if ($line =~ m#^//#);
  chomp $line;
  if ($line =~ m#^(.*)->(.*)#)
  {
    $source = $1;
    $dest = $2;
    $source =~ s/^\W*//;
    $source =~ s/\W*$//;
    $dest =~ s/^\W*//;
    $dest =~ s/\W*$//;
    $link{$source}{$dest} = 1;
    push (@nodelist,$source,$dest);
  } else {
    if ($line =~ m#^edge# or $line =~ m#^node#)
    {
      print STDERR "Skipping: $line\n";
      next;
    }
    if ($line =~ m#^(\S+).*\[.*\]#)
    {
      $name = $1;
      $name =~ tr/"//d;
      print STDERR "name:$name:\n";
    }
    if ($line =~ m#\[.*label=([^,\]]*).*\]#)
    {
      $label = $1;
      $label =~ tr/"//d;
      $node{$name}{'label'} = $label;
      print STDERR "label:$label:\n";
    }
    if ($line =~ m#\[.*fillcolor="([\d\.]+),([\d\.]+),([\d\.]+).*\]#)
    {
      $h = $1;
      $s = $2;
      $v = $3;
      print STDERR "hsv:$h:$s:$v:\n";
      $h = $h * 360;
      ($r,$g,$b) = &hsv2rgb($h,$s,$v);
      $node{$name}{r} = $r;
      $node{$name}{g} = $g;
      $node{$name}{b} = $b;
      print STDERR "rgb:$r:$g:$b:\n";
    }
  }
}

undef %saw;
@saw{@nodelist} = ();
@nodelist = sort keys %saw;  # remove sort if undesired
undef %saw;

for $nodenum (@nodelist)
{
  $node{$nodenum}{x}=rand;# $maxx;
  $node{$nodenum}{y}=rand;# $maxy;
  unless(defined $node{$nodenum}{'label'})
  {
    $node{$nodenum}{'label'} = $nodenum;
  }
}

&draw;
$continue = 1;
$iter = 0;
while($continue)
{
  $continue = 0;
  $iter++;
  for $nodenum (@nodelist)
  {
    $node{$nodenum}{oldx} = $node{$nodenum}{x};
    $node{$nodenum}{oldy} = $node{$nodenum}{y};
    $xmove = 0;
    $ymove = 0;
  }
  for $source (@nodelist)
  {
    $movecount = 0;
    for $dest (@nodelist)
    {
      next if ($source eq $dest);
      $xdist = $node{$source}{oldx} - $node{$dest}{oldx};
      $ydist = $node{$source}{oldy} - $node{$dest}{oldy};
      $dist = sqrt(abs($xdist)**2 + abs($ydist)**2);
      $wantdist = $dist;
      $wantdist = $wantdist + ($push / $dist);
      if ($link{$source}{$dest})
      {
         $wantdist = $wantdist - ($pull * $dist);
      }
      if ($link{$dest}{$source})
      {
         $wantdist = $wantdist - ($pull * $dist);
      }
      $percent = ($wantdist/$dist);
      $wantxdist = ($xdist * $percent);
      $wantydist = ($ydist * $percent);
      $xmove += ($xdist - $wantxdist)*$rate;
      $ymove += ($ydist - $wantydist)*$rate;
      $movecount++;
      $pullmove = $pull * $dist;
      $pushmove = $push / $dist;
      #print STDERR "dist: $dist, pull: $pullmove, push: $pushmove\n";
      #print STDERR "$source to ${dest}, Dist: $dist Want: $wantdist (${percent}x)\n";
      #print STDERR "is: $node[$source]{oldx} $node[$source]{oldy} $xdist $ydist, want: $wantxdist $wantydist ($newdist2)\n";

    }
    $xmove = $xmove / $movecount;
    $ymove = $ymove / $movecount;
    $node{$source}{x} -= $xmove;
    $node{$source}{y} -= $ymove;
    if ($xmove >= $done or $ymove >= $done)
    {
      $continue = 1;
    }
  }
  #print STDERR "$iter\n";
  if (0)
  {
    &draw;
    open (XV,"| xv -wait 1 -");
    #open (XV,"| xloadimage -delay 1 stdin");
    binmode XV;
    print XV $im->png;
    close XV;
  }
}
print STDERR "Iterations: $iter\n";
&draw;

undef $maxx;
undef $maxy;
sub draw
{
  for $nodenum (@nodelist)
  {
    if (!(defined $maxx) or (($node{$nodenum}{x} + (length($node{$nodenum}{'label'}) * 8 + 16)/2) > $maxx + (length($node{$nodenum}{'label'}) * 8 + 16)/2))
    {
      $maxx = $node{$nodenum}{x};# + (length($node{$nodenum}{'label'}) * 8 + 16)/2/2
      $maxxlength = (length($node{$nodenum}{'label'}) * 8 + 16)/2;
    }
    if (!(defined $minx) or (($node{$nodenum}{x} - (length($node{$nodenum}{'label'}) * 8 + 16)/2) < $minx - (length($node{$nodenum}{'label'}) * 8 + 16)/2))
    {
      $minx = $node{$nodenum}{x};# - (length($node{$nodenum}{'label'}) * 8 + 16)/2/2
      $minxlength = (length($node{$nodenum}{'label'}) * 8 + 16)/2;
    }

    $maxy = $node{$nodenum}{y} if (!(defined $maxy) or $node{$nodenum}{y} > $maxy);
    $miny = $node{$nodenum}{y} if (!(defined $miny) or $node{$nodenum}{y} < $miny);
  }
  for $nodenum (@nodelist)
  {
    #$node{$nodenum}{x} = ($node{$nodenum}{x} - $minx) * $scale + $margin;
    $node{$nodenum}{x} = ($node{$nodenum}{x} - $minx) * $scale + $minxlength -1 ;# + $margin;
    $node{$nodenum}{y} = ($node{$nodenum}{y} - $miny) * $scale + $nodesize/2 - 1;
  }
  $maxx = ($maxx - $minx) * $scale + $minxlength + $maxxlength;# + $margin*2;
  $maxy = ($maxy - $miny) * $scale + $nodesize/2*2;
  $im = new GD::Image($maxx,$maxy);
  $white = $im->colorAllocate(255,255,255);
  $blue = $im->colorAllocate(0,0,255);
  $powderblue = $im->colorAllocate(176,224,230);
  $black = $im->colorAllocate(0,0,0);
  $darkgrey = $im->colorAllocate(169,169,169);

  for $source (@nodelist)
  {
    #print STDERR "node: $source $node[$source]{x},$node[$source]{y}\n";
    for $dest (@nodelist)
    {
      if ($link{$source}{$dest})
      {
        $im->line($node{$source}{x},$node{$source}{y},$node{$dest}{x},$node{$dest}{y},$darkgrey);
      }
    }
  }

  for $source (@nodelist)
  {
    $im->arc($node{$source}{x},$node{$source}{y},(length($node{$source}{'label'}) * 8 + 16),$nodesize,0,360,$black);
    $color = $im->colorResolve($node{$source}{r},$node{$source}{g},$node{$source}{b});
    $im->fillToBorder($node{$source}{x},$node{$source}{y},$black,$color);
  }
  for $source (@nodelist)
  {
    $im->string(gdLargeFont,$node{$source}{x} - (length($node{$source}{'label'}) * 8 / 2) ,$node{$source}{y}-8,$node{$source}{'label'},$black);
  }


}


binmode STDOUT;
print $im->png;

sub hsv2rgb
{
#from http://faqchest.dynhost.com/prgm/perlu-l/perl-01/perl-0101/perl-010100/perl01010410_17820.html

# Given an h/s/v array, return an r/g/b array.
# The r/g/b values will each be between 0 and 255.
# The h value will be between 0 and 360, and
# the s and v values will be between 0 and 1.
#

                      my $h = shift;
                      my $s = shift;
                      my $v = shift;

                      # limit this to h values between 0 and 360 and s/v values
                      # between 0 and 1

                      unless (defined($h) && defined($s) && defined($v) &&
                             $h >= 0 && $s >= 0 && $v >= 0 &&
                             $h <= 360 && $s <= 1 && $v <= 1) {
                        return (undef, undef, undef);
                      }

                      my $r;
                      my $g;
                      my $b;

                      # 0.003 is less than 1/255; use this to make the floating point
                      # approximation of zero, since the resulting rgb values will
                      # normally be used as integers between 0 and 255.  Feel free to
                      # change this approximation of zero to something else, if this
                      # suits you.
                      if ($s < 0.003) {
                        $r = $g = $b = $v;
                      }
                      else {

                        $h /= 60;
                        my $sector = int($h);
                        my $fraction = $h - $sector;

                        my $p = $v * (1 - $s);
                        my $q = $v * (1 - ($s * $fraction));
                        my $t = $v * (1 - ($s * (1 - $fraction)));

                        if ($sector == 0) {
                          $r = $v;
                          $g = $t;
                          $b = $p;
                        }
                        elsif ($sector == 1) {
                          $r = $q;
                          $g = $v;
                          $b = $p;
                        }
                        elsif ($sector == 2) {
                          $r = $p;
                          $g = $v;
                          $b = $t;
                        }
                        elsif ($sector == 3) {
                          $r = $p;
                          $g = $q;
                          $b = $v;
                        }
                        elsif ($sector == 4) {
                          $r = $t;
                          $g = $p;
                          $b = $v;
                        }
                        else {
                          $r = $v;
                          $g = $p;
                          $b = $q;
                        }
                      }

                      # Convert the r/g/b values to all be between 0 and 255; use the
                      # ol' 0.003 approximation again, with the same comment as above.

                      $r = ($r < 0.003 ? 0.0 : $r * 255);
                      $g = ($g < 0.003 ? 0.0 : $g * 255);
                      $b = ($b < 0.003 ? 0.0 : $b * 255);

                      return ($r, $g, $b);
                    }