#!/usr/bin/perl -w

# springgraph, (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 

use GD;
use strict;
use vars qw(
$push
$pull
%node
$im
$source
$dest
$nodenum
$nodecount
$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
);

#$push = 10000;
#$push = 20000;
$push = 2000;
#$push = 20000;
$pull = .1;
$maxiter = 400;
#$rate = 2;
$rate = 2;
$nodes = 5;
#$maxx = 500;
#$maxy = 500;
$done = 0.1;
$margin = 20;
$nodesize = 40;

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

##$link[0][1] = 1;
##$link[1][2] = 1;
#$link{0}{1} = 1;
#$link{1}{2} = 1;
#$link{2}{3} = 1;
#$link{3}{4} = 1;
#$link{4}{0} = 1;
##$link[4][2] = 1;
##$link[3][4] = 1;
##$link[4][0] = 1;
#$link{2}{0} = 1;

while ($line = <STDIN>)
{
  chomp $line;
  if ($line =~ m#^(.*)->(.*)#)
  {
    $source = $1;
    $dest = $2;
    $source =~ s/^\W*//;
    $source =~ s/\W*$//;
    $dest =~ s/^\W*//;
    $dest =~ s/\W*$//;
    #print "source:$source: dest:$dest:\n";
    $link{$source}{$dest} = 1;
    push (@nodelist,$source,$dest);
  } else {
    if ($line =~ m#^(.*) \[.*label=([^,]*)\]#)
    {
      $name = $1;
      $label = $2;
      $name =~ tr/"//d;
      $label =~ tr/"//d;
      #print STDERR "name:$name: label:$label:\n";
      $node{$name}{'label'} = $label;
    }
  }
}

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;
  }
}




$nodecount = scalar(%node)  ;


&draw;
#for($iter = 0; ; $iter++)
$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 = $dist + ($push / $dist) - ($pull * $dist);
      $wantdist = $wantdist + ($push / $dist);
      if ($link{$source}{$dest})
      {
         $wantdist = $wantdist - ($pull * $dist);
      }
      if ($link{$dest}{$source})
      {
         $wantdist = $wantdist - ($pull * $dist);
      }
      #$percent = abs($wantdist/$dist);
      $percent = ($wantdist/$dist);
      $wantxdist = ($xdist * $percent);
      $wantydist = ($ydist * $percent);
      #$newdist2 = sqrt($wantxdist**2 + $wantydist**2);
      $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;
    }
  }
  #if ($iter % 100 == 0)
  #print STDERR "$iter\n";
  if (0)
  {
    &draw;
    open (XV,"| xv -wait 1 -");
    #open (XV,"| xloadimage -delay 1 stdin");
    binmode XV;
    print XV $im->png;
    #sleep 1;
    #`killall xv`;
    close XV;
  }
}
print STDERR "iter: $iter\n";
#print STDERR "final:\n";
&draw;

undef $maxx;
undef $maxy;
#print "rows:$rows\n";
sub draw
{
  for $nodenum (@nodelist)
  {
    $maxx = $node{$nodenum}{x} if (!(defined $maxx) or $node{$nodenum}{x} > $maxx);
    $maxy = $node{$nodenum}{y} if (!(defined $maxy) or $node{$nodenum}{y} > $maxy);

    $minx = $node{$nodenum}{x} if (!(defined $minx) or $node{$nodenum}{x} < $minx);
    $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}{y} = ($node{$nodenum}{y} - $miny) * $scale + $margin;
  }
  $maxx = ($maxx - $minx) * $scale + $margin*2;
  $maxy = ($maxy - $miny) * $scale + $margin*2;
  $im = new GD::Image($maxx,$maxy);
  $white = $im->colorAllocate(255,255,255);
  $blue = $im->colorAllocate(0,0,255);
  $black = $im->colorAllocate(0,0,0);

  for $source (@nodelist)
  {
    #print STDERR "node: $source $node[$source]{x},$node[$source]{y}\n";
    $im->arc($node{$source}{x},$node{$source}{y},$nodesize,$nodesize,0,360,$black);
    $im->string(gdLargeFont,$node{$source}{x}-4,$node{$source}{y}-8,$node{$source}{'label'},$black);
    for $dest (@nodelist)
    {
      if ($link{$source}{$dest})
      {
        $im->line($node{$source}{x},$node{$source}{y},$node{$dest}{x},$node{$dest}{y},$black);
      }
    }
  }
}


binmode STDOUT;
print $im->png;