
<?php



function sendGetPage () {

  //too many ' and " in heredoc?

  $serverNamePhpSelf = $_SERVER['SERVER_NAME'].$_SERVER['PHP_SELF'];

  $width = $_POST['width'];

  $height = $_POST['height'];

  $numVertices = $_POST['numVertices'];

  $percentConnected = $_POST['percentConnected'];



 echo <<< endOfGetPage

<html>

<head>

<title>PHP Create graph</title>

</head>

<body>

<form name="drawingForm" 

action="http://$serverNamePhpSelf";

method="post">

<input name="generate" value="random" type="radio" checked>Random

<!--

  <input name="generate" value="clickablemap" type="radio">Clickable map (later)

-->

<br>

Number vertices

<input type="text" size="2" maxlength="3"  name="numVertices" value="$numVertices">

Percent connected

<input type="text" size="2" maxlength="3"  name="percentConnected" value="$percentConnected">

Image size: Width

<input type="text" size="3" maxlength="4"  name="width" value="$width">

Height

<input type="text" size="3" maxlength="4"  name="height" value="$height">

<input value="Create it" type="submit">

</form>

endOfGetPage;

}

########################################################



//initial page load.  display form

if ($_SERVER['REQUEST_METHOD'] == 'GET') {

  bail("");   //no error

}





$width = $_POST['width'];

$height = $_POST['height'];

$numVertices = $_POST['numVertices'];

$percentConnected = $_POST['percentConnected'];

//  test

/*

$width = 200;

$height = 200;

$numVertices = 8;

$percentConnected = 50;

*/



//type check and range check here...

//form input is always string!!!  must use is-numeric, not is-int

if (!is_numeric($width) || !is_numeric($height) || 

    !is_numeric($numVertices) || !is_numeric($percentConnected) || 

    $width<1 || $width>1000 || $height<1 || $height>1000 ||

    $numVertices<0 || $numVertices>500 || $percentConnected<0 || $percentConnected>100) {

  bail( "BAD INPUT. width: $width h: $height numVertices: $numVertices percentConnected: $percentConnected \n"); 

}  



sendGetPage();





$g = new Graph($numVertices, $percentConnected, $width, $height);





$im = drawGraph( $g, $width, $height);



//my directory needs to be 777 for apache to write to it:

if (($fp = fopen("graphfile.png","w")) == false) {

  echo "<p>file open failed!</p>";

  exit();

}

ImagePNG($im,"graphfile.png");



echo "<hr>\n<img src=\"graphfile.png\">\n";





echo "<hr>Vertices:<br>\n";

$g->resetVertices();

$i = 0;

while ($v = $g->eachVertex()) {

  echo $v->printVertex()."&nbsp;&nbsp;&nbsp;";

  if ((++$i) % 10 == 0)

    echo "<br>";

}



$numEdges = $g->getNumEdges();  

echo "<hr>$numEdges Edges:<br>\n";

$g->resetEdges();

$i = 0;

while ($e = $g->eachEdge()) {

  //echo $e->printEdge()."&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";

  $v1 = $e->getV1();

  $v2 = $e->getV2();  //syntax error to chain method calls

  echo $v1->getId()."-".$v2->getId()."[".round($e->getDistance())."]&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";

  if ((++$i) % 10 == 0)

    echo "<br>\n";

}





echo "<hr>All pairs Dijkstra shortest paths:<br>";

echo "<table border=1>";

$g->resetVertices();

$i = 0;

while ($s = $g->eachVertex()) {

  $g->Dijkstra($s->getId());

  $paths = explode("\n", $g->printDijkstraShortestPaths());

  echo "<tr>\n";

  foreach ($paths as $path)

    echo "<td>$path</td>\n";

  echo "</tr>\n";

}

echo "</table>\n";







echo "<hr># connected components: ";

$g->DFS();

$numComponents = $g->getNumComponents();

echo "$numComponents<br>\n";

$components = explode("\n", $g->printComponents());

foreach ($components as $component)

     echo "$component<br>\n";





if ($numComponents == 1) {    //has a MST



  $kruskal = new MST( $g, "kruskal");  

  echo "<hr>MST Kruskal total distance: ".$kruskal->getKruskalDistance()."<br>\n";

  $im = drawGraph( $kruskal, $width, $height);



  if (($fp = fopen("graphfilekruskal.png","w")) == false) {

    echo "<p>file open failed!</p>";

    exit();

  }

  ImagePNG($im,"graphfilekruskal.png");

  echo "<img src=\"graphfilekruskal.png\"><hr>\n";





  $prim = new MST( $g, "prim");  

  echo "MST Prim total distance: ".$prim->getPrimDistance()."<br>\n";

  $im = drawGraph( $prim, $width, $height);



  if (($fp = fopen("graphfileprim.png","w")) == false) {

    echo "<p>file open failed!</p>";

    exit();

  }

  ImagePNG($im,"graphfileprim.png");

  echo "<img src=\"graphfileprim.png\">\n";

}





echo "<hr>Shortest paths (min # edges):\n";

echo "<table border=1>";

$g->resetVertices();

$i = 0;

while ($v = $g->eachVertex()) {

  //echo "<th>$v->getId()</th>\n";

  $g->BFS($v->getId());

  $paths = explode("\n", $g->printShortestPaths());

  echo "<tr>\n";

  foreach ($paths as $path)

    echo "<td>$path</td>\n";

  echo "</tr>\n";

}

echo "</table>\n";







echo "</body>\n</html>";



exit();



########################################################





function drawGraph( $g, $width, $height) {



  //$im = ImageCreateTrueColor($width, $height);

  //fonts doesn't work in TrueColor ?!?!?!

  $im = ImageCreate($width, $height);

  

  $colors['white'] = ImageColorAllocate($im, 255, 255, 255);

  

  ImageAlphaBlending($im, false);

  ImageFilledRectangle($im, 0, 0, $width, $height, $colors['white']);

  

  

  $colors['black'] = ImageColorAllocate($im, 0, 0, 0);

  $colors['red'] = ImageColorAllocate($im, 255, 0, 0);

  $colors['magenta'] = ImageColorAllocate($im, 255, 0, 255);

  $colors['cyan'] = ImageColorAllocate($im, 0, 255, 255);

  /*

$colors['yellow'] = ImageColorAllocate($im, 255, 255, 0);

$colors['blue'] = ImageColorAllocate($im, 0, 0, 255);

$colors['green'] = ImageColorAllocate($im, 0, 255, 0);

  */

  

  

  $edgecolor = $colors['magenta'];  

  $midcolor = $colors['cyan'];  

  

  $g->resetEdges();

  while ($e = $g->eachEdge()) {

    $v1 = $e->getV1();   //can not chain ???

    $x1 = $v1->getX();

    $y1 = $v1->getY();

    $v2 = $e->getV2();

    $x2 = $v2->getX();

    $y2 = $v2->getY();

    ImageLine($im, $x1, $y1, $x2, $y2, $edgecolor);

    

    list($xMid,$yMid) = $e->midPoint();

    $angle = $e->angle();

    //convert to GD angles: rt horiz is 0, up is 90, left horiz is 180 etc

    if ($angle > 0)    //neg. slope (2nd quadrant)

      $angle = 180 - $angle;

    else               //pos. slope (1st quadrant)

      $angle = -$angle;

    if ($angle > 90)    //empirically.  flips the orientation

      $angle += 180;

    //ImageTTFText($im, 10, $angle, $xMid, $yMid, $midcolor, 'courb', (int)($angle));

    ImageTTFText($im, 10, $angle, $xMid, $yMid, $midcolor, 'courb', round($e->getDistance()));

    

  }

  

  

  $vertexcolor = $colors['red'];  

  $fontcolor = $colors['black'];  

  //$ttfont = trim (`locate -n 1 .ttf`);   //found at onlamp article...

  $g->resetVertices();

  while ($v = $g->eachVertex()) {

    $x = $v->getX();

    $y = $v->getY();

    ImageFilledRectangle($im, $x, $y, $x+3, $y+3, $vertexcolor);

    //ImageTTFText($im, 10, 0, $x+4, $y+4, $fontcolor, $ttfont, $v->getId());

    ImageTTFText($im, 12, 0, $x+4, $y+4, $fontcolor, 'courb', $v->getId());

  }

  

  return $im;

  

}

########################################################







function bail ($message) {

  echo $message;

  sendGetPage();

  echo "</body>\n</html>";

  exit();

}



########################################################



class Vertex {

  var $x, $y, $name, $id;



  function Vertex($x, $y, $name="") {

    static $count=1;    //pseudo- class field

    $this->id = $count++;

    $this->x = $x;

    $this->y = $y;

    $this->name = $name;

  }



  function printVertex() {

    return $this->id.":(".$this->x.",".$this->y.")";

  }



  function getX() {

    return $this->x;

  }

  function getY() {

    return $this->y;

  }

  function getId() {

    return $this->id;

  }



}



########################################################



class Edge {

  var $v1, $v2, $w, $distance;



  function Edge($v1, $v2, $w=0) {

    $this->v1 = $v1;      //change to reference ??

    $this->v2 = $v2;

    $this->w = $w;

    //euclidean distance:

    $dx = $this->v1->getX() - $this->v2->getX();

    $dy = $this->v1->getY() - $this->v2->getY();

    $this->distance = sqrt($dx*$dx + $dy*$dy);

  }



  function printEdge() {

    return $this->v1->printVertex()."-".$this->v2->printVertex();

  }



  function getV1() {

    return $this->v1;

  }



  function getV2() {

    return $this->v2;

  }



  function getDistance() {

    return $this->distance;

  }



  function midPoint() {

    $coord = array();

    $coord[] = ($this->v1->getX() + $this->v2->getX()) / 2;

    $coord[] = ($this->v1->getY() + $this->v2->getY()) / 2;

    return $coord;

  }



  //positive slope / is negative angle 0-90

  //negative slope \ is positive angle 0-90

  function angle() {      

    $x = $this->v1->getX() - $this->v2->getX();

    $y = $this->v1->getY() - $this->v2->getY();

    return rad2deg(atan($y/$x));

  }



}



########################################################



class Graph {

  var $vertices;  //array of Vertex

  var $edges;     //array of Edge

  var $Adj;       //2d array: adjacency (by vertex id)

  var $numVertices;

  var $numEdges;

  var $vertexIndex;   //iterator

  var $edgeIndex;     //iterator

  var $pred;     //array for BFT of BFS

  var $predS;    //root vertex of BFT

  var $DFSpred;  //array for DFS

  var $numComponents;  //number of connected components

  var $components;     //2d array 

  var $d;         //value of Dijkstra shortest path from s to each vertex



  function Graph($numVertices, $percentConnected, $width, $height, $edgeType="undirected") {

    $this->vertices = array();

    $this->edges = array();

    $this->numVertices = $numVertices;

    $this->numEdges = 0;

    //generate random vertices

    for ($i=0; $i<$this->numVertices; $i++)

      $this->vertices[] = new Vertex(rand(1,$width), rand(1,$height));

    

    //generate random (undirected) edges

    for ($i=0; $i<$this->numVertices; $i++) {

      for ($j=$i+1; $j<$this->numVertices; $j++)  //to remaining vertices in array

    if (rand(1,100) <= $percentConnected) {

      $v1 = $this->vertices[$i];

      $v2 = $this->vertices[$j];

      $this->edges[] = new Edge($v1,$v2);

      $this->numEdges++;

      $this->Adj[$v1->getId()][] = $v2->getId();

      $this->Adj[$v2->getId()][] = $v1->getId();

    }

    }

  }





  function getNumEdges() {

    return $this->numEdges;

  }



  function resetVertices() {

    $this->vertexIndex = 0;

  }



  function eachVertex() {

    if ($this->vertexIndex < $this->numVertices) 

      return $this->vertices[$this->vertexIndex++];

    else

      return false;

  }



  function resetEdges() {

    $this->edgeIndex = 0;

  }



  function eachEdge() {

    if ($this->edgeIndex < $this->numEdges) 

      return $this->edges[$this->edgeIndex++];

    else

      return false;

  }

  

  //breadth-first search from vertex s (id)

  //CLR p. 470

  function BFS ($s=1) { 

    $this->predS = $s;   //remember which vertex is root of this BFT

    $color = array();

    $d = array();

    $this->pred = array();

    $Q = array();   //queue of vertices on the fringe



    for ($i=0; $i<$this->numVertices; $i++) {

      $u = $this->vertices[$i]->getId();   //id

      $color[$u] = "white";  //undiscoverdd

      $d[$u] = 1000000000;   //distance to s: infinity

      $this->pred[$u] = "";  //predecessor in the BFT: nil

    }



    $color[$s] = "gray";   //on the fringe

    $d[$s] = 0;

    $this->pred[$s] = "";  //is root, has no pred

    $Q[] = $s;     //enqueue.  Q contains exactly the gray vertices



    while (count($Q) > 0) { //not empty

      $u = $Q[0];     //head of queue

      $uNeighbors = count($this->Adj[$u]);

      for ($i=0; $i<$uNeighbors; $i++)  {   //each v of Adj[u]

    $v = $this->Adj[$u][$i];

    if ($color[$v] == "white") {    //v is undiscovered

      $color[$v] = "gray";    //put v on fringe

      $d[$v] = $d[$u] + 1;   //one edge more than u away from s

      $this->pred[$v] = $u;  //v's pred is u

      $Q[] = $v;             //enqueue v

    }

      }

      array_shift($Q);    //dequeue u

      $color[$u] = "black";  //u is on tree. done with it

    }

  }



  function printShortestPaths() {

    for ($i=0; $i<$this->numVertices; $i++) {

      $v = $this->vertices[$i]->getId();   //id

      $pathStrings .= $this->print_path($this->predS, $v, "")."\n";

    }

    return $pathStrings;

  }



  //CLR p. 476

  function print_path($s, $v, $path) {

    if ($v == $s)

      return $path."  $s";

    else if ($this->pred[$v] != "")   //not nil

      return $this->print_path($s,$this->pred[$v])."  $v";

    else //no path to v

      return "$s # $v";

  }





  //CLR p. 478

  function DFS () { 

    $color = array();

    //$d = array();   //discovery time

    $this->DFSpred = array();

    $this->numComponents = 0;

    $this->components = array();



    for ($i=0; $i<$this->numVertices; $i++) {

      $u = $this->vertices[$i]->getId();   //id

      $color[$u] = "white";  //undiscoverdd

      $this->DFSpred[$u] = "";  //predecessor in DFS depth-first forest

    }

    for ($i=0; $i<$this->numVertices; $i++) {

      $u = $this->vertices[$i]->getId();   //id

      if ($color[$u] == "white") { //not yet discovered

    $this->numComponents++;

    $this->DFSvisit($u, $color);

      }

    }

  }



  function DFSvisit( $u, &$color) {

    $color[$u] = "gray";     //just been discovered

    $this->components[$this->numComponents][] = $u;  //add to vertex list of this component

    $uNeighbors = count($this->Adj[$u]);

    for ($i=0; $i<$uNeighbors; $i++)  {   //each v of Adj[u]

      $v = $this->Adj[$u][$i];

      if ($color[$v] == "white") {    //v is undiscovered

    $this->DFSpred[$v] = $u;

    $this->DFSvisit($v, $color);

      }

    }

    $color[$u] = "black";   //done

  }



  function getNumComponents() {

    return $this->numComponents;

  }



  function printComponents() {

    for ($i=1; $i<=$this->numComponents; $i++) {

      $numV = count($this->components[$i]);

      for ($j=0; $j<$numV; $j++)

    $complist .= $this->components[$i][$j]." ";

      $complist .= "\n";

    }

    return $complist;

  }



  //search edges array for vertices u, v  Needed by Prim MST

  function findEdge($u, $v) {

    for ($i=0; $i<$this->numEdges; $i++) {

      $v1 = $this->edges[$i]->getV1();

      $v2 = $this->edges[$i]->getV2();

      if ($u==$v1->getId() && $v==$v2->getID())

    return $i;

      else if ($v==$v1->getId() && $u==$v2->getId())    //undirected

    return $i;

    }

    return false;

  }





  //CLR p. 520, 527

  function Dijkstra( $s ) {   //shortest distance path from s to every other vertex

    $this->predS = $s;   //remember which vertex is starter

    $Q = array();  //priority queue

    $this->pred = array();

    //$parent = array();

    $this->d = array();   //need this separate from Q.  Q gets dequeued but d doesn't.

    

    for ($i=0; $i<$this->numVertices; $i++) {

      $v = $this->vertices[$i]->getId();   //id is index

      $Q[$v] = 1000000000;   //infinity 

      $this->d[$v] = $Q[$v];

      $this->pred[$v] = "";

    }

    $Q[$s] = $this->d[$s] = 0;

    

    while (count($Q) > 0) {  //not empty

      arsort($Q);   //reverse sort, preserve id indexes

      end($Q);   //set pointer to end

      $u = key($Q);  //return key of last (min) element

      array_pop($Q);  //remove and return last (min) element, throw value away

      $uNeighbors = count($this->Adj[$u]);

      for ($i=0; $i<$uNeighbors; $i++)  {   //each v of Adj[u]

    $v = $this->Adj[$u][$i];

    $eUV = &$this->edges[$this->findEdge($u,$v)];

    $weightUV = round($eUV->getDistance());

    if ($this->d[$v] > $this->d[$u] + $weightUV) {   //

      $this->pred[$v] = $u;

      $this->d[$v] = $this->d[$u] + $weightUV;

      $Q[$v] = $this->d[$v];

    }

      }

    }

  }



  function printDijkstraShortestPaths() {

    for ($i=0; $i<$this->numVertices; $i++) {

      $v = $this->vertices[$i]->getId();   //id

      $pathStrings .= $this->print_path($this->predS, $v, "");

      if ($this->d[$v] < 1000000000)

    $pathStrings .= " {".$this->d[$v]."}";

      $pathStrings .= "\n";

    }

    return $pathStrings;

  }

  

}



########################################################

class MST extends Graph {



  var $kruskalDistance;

  var $primDistance;



  function MST ( $g, $whose) {

    $this->vertices = $g->vertices;

    $this->numVertices = $g->numVertices;

    $this->edges = array();  //MST edges empty

    $sortedEdges = array();



    if ($whose == "kruskal") {       //bascially CLR.  horrifically inefficient.

      $sortedEdges = $g->edges;    //copy of edges array

      usort( $sortedEdges, 'edgeDistanceSort');

      //test the sort:

      //for ($i=0; $i<$g->numEdges; $i++)

      //echo $sortedEdges[$i]->printEdge()." ".$sortedEdges[$i]->getDistance()."<br>\n";

      $sets = array();    

      for ($i=0; $i<$this->numVertices; $i++) {

    $u = $this->vertices[$i]->getId();   //id

    $sets[$u] = $u;   //each vertex in own singleton set

      }

      $numEdges = count($sortedEdges);

      for ($i=0; $i<$numEdges; $i++) {   //each edge in increasing order

    $v1 = $sortedEdges[$i]->getV1();

    $u = $v1->getId();

    $v2 = $sortedEdges[$i]->getV2();

    $v = $v2->getId();

    if ($sets[$u] != $sets[$v]) {    //if in different sets

      $this->edges[] = $sortedEdges[$i];  //add to MST

      $this->kruskalDistance += round($sortedEdges[$i]->getDistance());

      //union of the 2 sets:

      //scan set array, change every vertex in u's to v's

      $setU = $sets[$u];    //in case sets[u] changes.  debugged

      for ($w=1; $w<=$this->numVertices; $w++) {

        if ($sets[$w] == $setU)

          $sets[$w] = $sets[$v];   

      }

    }

      }

    }

    else if ($whose == "prim") {       //basically CLR.  horrifically inefficient.

      $Q = array();  //priority queue

      $parent = array();

      for ($i=0; $i<$this->numVertices; $i++) {

    $u = $this->vertices[$i]->getId();   //id is index

    $Q[$u] = 1000000000;   //infinity 

      }

      $root = rand(1,$this->numVertices);  //random vertex as root

      $Q[$root] = 0;

      $parent[$root] = "";   

      while (count($Q) > 0) {  //not empty

    arsort($Q);   //reverse sort, preserve id indexes

    end($Q);   //set pointer to end

    $u = key($Q);  //return key of last (min) element

    array_pop($Q);  //remove and return last (min) element, throw value away

    if ($parent[$u] != "") {   //not root

      $eUV = &$g->edges[$g->findEdge($parent[$u],$u)];

      $this->edges[] = $eUV;

      $this->primDistance += round($eUV->getDistance());

    }

    $uNeighbors = count($g->Adj[$u]);

    for ($i=0; $i<$uNeighbors; $i++)  {   //each v of Adj[u]

      $v = $g->Adj[$u][$i];

      if (key_exists($v,$Q)) {   //v not yet in MST

        $eUV = &$g->edges[$g->findEdge($u,$v)];

        $weightUV = round($eUV->getDistance());

        if ($weightUV < $Q[$v]) {   //

          $parent[$v] = $u;

          $Q[$v] = $weightUV;

        }

      }

    }

      }

    }

    

    $this->numEdges = $this->numVertices - 1;



  }



  function getKruskalDistance() {

    return $this->kruskalDistance;

  }



  function getPrimDistance() {

    return $this->primDistance;

  }



}



//compare 2 Edges for usort.    not a member function?

function edgeDistanceSort($e1, $e2) {

  $e1Distance = round($e1->getDistance()); 

  $e2Distance = round($e2->getDistance());

  if ($e1Distance < $e2Distance)

    return -1;

  else if ($e1Distance > $e2Distance)

    return 1;

  else

    return 0;

}

?>