<?php
error_reporting(0);
  // based on http://www.eng.auburn.edu/department/cse/research/graph_drawing/graph_drawing.html

  $G = new Graph();

  $size = 9;

  for($i = 1; $i <= $size; $i++)
    $G->addNode($i);

  for($i = 2; $i <= $size; $i++)
    for($j = 1; $j < $i; $j++)
      if($i % $j == 0)
        $G->addEdge($i, $j);

  $S = new Spring($G);
  $S->compute($G);

  $G->display();
  exit;

  class Graph
  {
    var $nodes;

    function Graph()
    {
      $this->nodes = array();
    }

    function addNode($name)
    {
      $this->nodes[$name] = new Node($name);
    }

    function addEdge($n1, $n2)
    {
      $this->nodes[$n1]->addChild($n2);
      $this->nodes[$n2]->addChild($n1);
    }

    function numberofNodes()
    {
      return sizeof($this->nodes);
    }

    function display()
    {
      $keys = array_keys($this->nodes);
      foreach($keys as $key)
      {
        if(!isset($xmin) || $this->nodes[$key]->X < $xmin) $xmin = $this->nodes[$key]->X;
        if(!isset($ymin) || $this->nodes[$key]->Y < $ymin) $ymin = $this->nodes[$key]->Y;
        if(!isset($xmax) || $this->nodes[$key]->X > $xmax) $xmax = $this->nodes[$key]->X;
        if(!isset($ymax) || $this->nodes[$key]->Y > $ymax) $ymax = $this->nodes[$key]->Y;
      }
      $xmin -= 50; $xmax += 50; $ymin -= 50; $ymax += 50;

      foreach($keys as $key)
      {
        $this->nodes[$key]->X -= $xmin;
        $this->nodes[$key]->Y -= $ymin;
      }

      $img = imagecreate($xmax - $xmin, $ymax - $ymin);
      $bg = imagecolorallocate($img, 255, 255, 255);
      imagecolortransparent($img, $bg);
      $fg = imagecolorallocate($img, 0, 0, 0);

      foreach($keys as $key)
        foreach($this->nodes[$key]->children as $child)
          imageline($img, $this->nodes[$key]->X, $this->nodes[$key]->Y, $this->nodes[$child]->X, $this->nodes[$child]->Y, $fg);
      foreach($keys as $key)
        $this->nodes[$key]->display($img, $bg, $fg);

      header('Content-type: image/png');
      imagepng($img);
      imagedestroy($img);
    }

  }

  class Node
  {
    var $X;
    var $Y;
    var $name;
    var $children;

    function Node($name)
    {
      $this->name = $name;
      $this->children = array();
      $this->X = rand(0, 200);
      $this->Y = rand(0, 200);
    }

    function hasChild($n)
    {
      if(in_array($n, $this->children))
        return true;
      else
        return false;
    }

    function addChild($n)
    {
      $this->children[] = $n;
    }

    function display($img, $bg, $fg)
    {
      imagefilledellipse($img, $this->X, $this->Y, 30, 30, $bg);
      imageellipse($img, $this->X, $this->Y, 30, 30, $fg);
      imagestring($img, 1, $this->X, $this->Y, $this->name, $fg);
    }
  }

  class Spring
  {
    var $size;
    var $orderedList;
    var $EDGES;
    var $D, $K, $Ko, $L;
    var $epsilon;
    var $delta;
    var $MAX_TIMES_REPOSITIONED;
    var $numTimesRepositioned;
    var $NUM_TIMES_MOVED;
    var $HY_SIZE, $HY_PERCENTAGE;
    var $E, $E_HY;
    var $COUNTER;
    var $mv;
    var $partial_x, $partial_y, $partial_xx, $partial_xy, $partial_yx, $partial_yy;
    var $connected;
    var $MAX_VALUE;

    function Spring(&$G)
    {
      $this->Initialize($G);
    }

    function compute(&$G)
    {
      // local vars: tempValue, maxValue, maxDel, maxTimes, mvi, i, v, u;

      $maxTimes = 0;
      $this->Initialize($G);

      if($this->connected == false) return 'Graph must be connected';

      while(true)
      {
        $this->CheckPositions($G);

        // determine the next vertex to move according to TempFunction
        $maxDel = 0;
        for($vi = sizeof($this->orderedList) - 1; $vi >= 0; $vi--)
        {
          $v = $this->orderedList[$vi];
          $this->delta[$vi] = sqrt($this->findDelta2($G, $v));
          if($this->delta[$vi] > $maxDel)
            $maxDel = $this->delta[$vi];
          if($this->NUM_TIMES_MOVED[$vi] > $maxTimes)
            $maxTimes = $this->NUM_TIMES_MOVED[$vi];
        }
        $this->mv = $this->orderedList[0];
        $mvi = 0;
        $maxValue = 0;
        for($vi = $mvi; $vi < sizeof($this->orderedList); $vi++)
        {
          $v = $this->orderedList[$vi];
          if($maxTimes != 0)
            $tempValue = $this->TempFunction($this->delta[$vi] / $maxDel, 1 - $this->NUM_TIMES_MOVED[$vi] / $maxTimes);
          else
          {
            // the first time, base the decision only upon delta
            $tempValue = $this->delta[$vi] / $maxDel;
          }
          if($tempValue > $maxValue)
          {
            $this->mv = $v;
            $mvi = $vi;
            $maxValue = $tempValue;
          }
        }

        if($this->delta[$mvi] < $this->epsilon)  return 'Quitting because of epsilon';

        $this->E = $this->findE($G);
        if($this->COUNTER > $this->HY_SIZE && $this->E_HY[$this->COUNTER % $this->HY_SIZE] * $this->HY_PERCENTAGE / 100.0 > $this->E)
          return 'Quitting because of history';

        // can't quit yet, so put the E in the history array and get ready to find a new position for vertex 'mv'
        $this->E_HY[$this->COUNTER % $this->HY_SIZE] = $this->E;

        $this->numTimesRepositioned = 0;
        while(($this->delta[$mvi] > $this->epsilon) && ($this->numTimesRepositioned < $this->MAX_TIMES_REPOSITIONED))
        {
          $this->MoveToNewPosition($G);
          $this->delta[$mvi] = sqrt($this->findDelta2($G, $this->mv));
          $this->numTimesRepositioned++;
        }
        $this->NUM_TIMES_MOVED[$mvi]++;
      }
      return '';
    }

    function Initialize(&$G)
    {
      $this->COUNTER = 0;
      $this->HY_SIZE = 10;
      $this->HY_PERCENTAGE = 5;
      $this->MAX_TIMES_REPOSITIONED = 10;
      $this->numTimesRepositioned = 0;
      $this->MAX_VALUE = 9999999999999999999999999999999;
      $this->size = 800;

      $N = $G->numberofNodes();
      $this->orderedList = array_keys($G->nodes);
      for($i = 0; $i < $N; $i++)
        $this->NUM_TIMES_MOVED[$i] = 0;
      $this->EDGES = 0;
      for($i = 0; $i < sizeof($this->orderedList); $i++)
        for($j = $i + 1; $j < sizeof($this->orderedList); $j++)
          if($G->nodes[$this->orderedList[$i]]->hasChild($this->orderedList[$j]))
            $this->EDGES++;
      $this->epsilon = .5 * ($N + $this->EDGES);
      $this->findDistances($G);
      $this->find_l_and_k($G);
      $this->delta = array();
      $this->E_HY = array();
    }

    function find_l_and_k(&$G)
    {
      $this->Ko = 0;
      $this->L = array();
      $this->K = array();
      $diam = $this->D[0][0];
      for($i = 0; $i < $G->numberOfNodes(); $i++)
      {
        for($j = $i + 1; $j < $G->numberOfNodes(); $j++)
        {
          if(($diam < $this->D[$i][$j]) && ($this->D[$i][$j] < $this->MAX_VALUE))
            $diam = $this->D[$i][$j];
          $this->Ko += $this->D[$i][$j];
        }
      }

      $this->Ko = $this->Ko / $G->numberOfNodes();
      $Lo = sqrt($this->size * $this->size / 4) / $diam;
      for($i = 0; $i < $G->numberOfNodes(); $i++)
      {
        for($j = $i + 1; $j < $G->numberOfNodes(); $j++)
        {
          $this->L[$i][$j] = $Lo * $this->D[$i][$j];
          $this->L[$j][$i] = $this->L[$i][$j];
          if($this->D[$i][$j] < $this->MAX_VALUE)
            $this->K[$i][$j] = $this->Ko * $this->Ko / ($this->D[$i][$j] * $this->D[$i][$j]);
          else
            $this->K[$i][$j] = 0;
          $this->K[$j][$i] = $this->K[$i][$j];
        }
      }
    }

    function findDistances(&$G)
    {
      $queue = array();

      for($i = $G->numberOfNodes() - 1; $i >= 0; $i--)
      {
        for($j = $i - 1; $j >= 0; $j--)
        {
          $this->D[$i][$j] = 0;
          $this->D[$j][$i] = 0;
        }
      }

      for($si = 0; $si < sizeof($this->orderedList); $si++)
      {
        $s = $this->orderedList[$si];

        for($j = $G->numberOfNodes() - 1; $j >= 0; $j--) $done[$j] = false;

        $done[$si] = true;
        for($vi = 0; $vi < sizeof($this->orderedList); $vi++)
        {
          $v = $this->orderedList[$vi];
          if($G->nodes[$s]->hasChild($v))
          {
            $queue[] = $v;
            $queue[] = $s;
            $done[$vi] = true;
          }
        }

        while(sizeof($queue))
        {
          reset($queue);
          list($key1, $v) = each($queue);
          list($key2, $p) = each($queue);
          unset($queue[$key1]);
          unset($queue[$key2]);
          $pi = array_search($p, $this->orderedList);
          $vi = array_search($v, $this->orderedList);
          $this->D[$si][$vi] = $this->D[$pi][$si] + 1;
          $this->D[$vi][$si] = $this->D[$si][$vi];
          for($ui = 0; $ui < sizeof($this->orderedList); $ui++)
          {
            $u = $this->orderedList[$ui];
            if($G->nodes[$v]->hasChild($u))
            {
              if(!$done[$ui])
              {
                $queue[] = $u;
                $queue[] = $v;
                $done[$ui] = true;
              }
            }
          }
        }
      }

      $this->connected = true;
      for($i = $G->numberOfNodes() - 1; $i >= 0; $i--)
      {
        for($j = $i - 1; $j >= 0; $j--)
        {
          if($this->D[$i][$j] == 0)
          {
            $this->connected = false;
            $this->D[$i][$j] = $this->MAX_VALUE;
            $this->D[$j][$i] = $this->MAX_VALUE;
          }
        }
      }
    }

    function CheckPositions(&$G)
    {
      $OK = false;
      while(!$OK)
      {
        $OK = true;
        for($vi = sizeof($this->orderedList) - 1; $vi >= 0; $vi--)
        {
          $v = $this->orderedList[$vi];
          for($ui = $vi - 1; $ui >= 0; $ui--)
          {
            $u = $this->orderedList[$ui];
            if($G->nodes[$v]->X == $G->nodes[$u]->X && $G->nodes[$v]->Y == $G->nodes[$u]->Y)
            {
              $G->nodes[$u]->X += (1.4 * rand() - 1) * $this->L[$vi][$ui];
              $G->nodes[$u]->Y += (1.4 * rand() - 1) * $this->L[$vi][$ui];
              $OK = false;
            }
          }
        }
      }
    }

    function findDelta2(&$G, $v)
    {
      $this->findPartials($G, $v);
      return ($this->partial_x * $this->partial_x + $this->partial_y * $this->partial_y);
    }

    function findPartials(&$G, $v)
    {
      $vi = array_search($v, $this->orderedList);
      $this->partial_x = 0;
      $this->partial_y = 0;
      $this->partial_xx = 0;
      $this->partial_xy = 0;
      $this->partial_yx = 0;
      $this->partial_yy = 0;
      for($ui = 0; $ui < sizeof($this->orderedList); $ui++)
      {
        if($vi != $ui)
        {
          $u = $this->orderedList[$ui];
          $dx = $G->nodes[$v]->X - $G->nodes[$u]->X;
          $dy = $G->nodes[$v]->Y - $G->nodes[$u]->Y;
          $dd = hypot($dx, $dy);
          $this->partial_x += $this->K[$vi][$ui] * ($dx - $this->L[$vi][$ui] * $dx / $dd);
          $this->partial_y += $this->K[$vi][$ui] * ($dy - $this->L[$vi][$ui] * $dy / $dd);
          $this->partial_xx += $this->K[$vi][$ui] * (1 - $this->L[$vi][$ui] * $dy * $dy / ($dd * $dd * $dd));
          $this->partial_xy += $this->K[$vi][$ui] * ($this->L[$vi][$ui] * $dx * $dy / ($dd * $dd * $dd));
          $this->partial_xy += $this->K[$vi][$ui] * ($this->L[$vi][$ui] * $dy * $dx / ($dd * $dd * $dd));
          $this->partial_yy += $this->K[$vi][$ui] * (1 - $this->L[$vi][$ui] * $dx * $dx / ($dd * $dd * $dd));
        }
      }
    }

    function TempFunction($del, $times)
    {
      return ($del + $times) / 2;
    }

    function findE(&$G)
    {
      $total = 0;
      for($vi = 0; $vi < sizeof($this->orderedList); $vi++)
      {
        $v = $this->orderedList[$vi];
        for($ui = 0; $ui < sizeof($this->orderedList); $ui++)
        {
          $u = $this->orderedList[$ui];
          $dx = $G->nodes[$v]->X - $G->nodes[$u]->X;
          $dx = $G->nodes[$v]->Y - $G->nodes[$u]->Y;
          $dd = hypot($dx, $dy);
          $dif = $dd - $this->L[$vi][$ui];
          $total += $this->K[$vi][$ui] * $diff * $diff;
        }
      }
      return $total / 2;
    }

    function MoveToNewPosition(&$G)
    {
      $mvi = array_search($this->mv, $this->orderedList);
      $this->findPartials($G, $this->mv);
      $denom = $this->partial_xx * $this->partial_yy - $this->partial_xy * $this->partial_yx;
      $G->nodes[$this->mv]->Y += ($this->partial_x * $this->partial_yx - $this->partial_xx * $this->partial_y) / $denom;
      $G->nodes[$this->mv]->X += ($this->partial_xy * $this->partial_y - $this->partial_x * $this->partial_yy) / $denom;
    }

  }
?>