nodes = array() ;
$this->edges = array() ;
$this->d = $dimensions ;
$scalar = min($dimensions['height'], $dimensions['width']) / $range ;
foreach($connections as $key1 => $elements){
foreach($elements as $key2 => $elements2){
if($key1 != $key2 && !$this->edgeExists($key2, $key1)){
$this->addEdge($key1, $key2, $connections[$key1][$key2]* $scalar) ;
}
}
}
//echo 'no. nodes: ' . sizeof($this->nodes) . '
';
//echo 'no. edges: ' . sizeof($this->edges) . '
';
}//end constructor
function run(){
$start = time() ;
$time = 0 ;
do{
$this->relax();
$current = time() ;
$time = $current - $start ;
}while ((!$this->isOrganised()) and ($time+10) < ini_get('max_execution_time')) ;
}
function isOrganised(){
for ($i=0;$inodes);$i++) {
if ($this->nodes[$i]->unchanged == false) {
return false ;
}
}
return true ;
}
function addNode($lbl) {
//echo 'adding node: ' . $lbl . '
';
$n = new Node();
$n->x = rand(0,$this->d['width']);
$n->y = rand(0,$this->d['height']);
$n->startx = $n->x ;
$n->starty = $n->y ;
$n->lbl = $lbl;
$n->fixed = false ;
$n->unchanged = false ;
$this->nodes[] = $n;
return sizeof($this->nodes)-1;
}
function findNode($lbl) {
for ($i=0;$inodes);$i++) {
if ($this->nodes[$i]->lbl == $lbl) {
return $i;
}
}
return $this->addNode($lbl);
}
function nodeExists($lbl) {
for ($i=0;$inodes);$i++) {
if ($this->nodes[$i]->lbl == $lbl) {
return $i;
}
}
return -1;
}
function edgeExists($from, $to) {
$node1index = $this->nodeExists($from) ;
$node2index = $this->nodeExists($to) ;
if( $node1index > -1 && $node2index > -1){
//echo 'both nodes exist
' ;
for ($i=0;$iedges);$i++) {
if ($this->edges[$i]->to == $node2index && $this->edges[$i]->from == $node1index) {
return true;
}
}
}
return false;
}
function addEdge($from, $to, $len){
//echo 'adding edge: ' . $from . '-' . $to . '/' . $len . '
';
$e = new Edge();
$e->from = $this->findNode($from);
$e->to = $this->findNode($to);
$e->len = $len;
$e->f = 0.5 ;
$this->edges[] = $e;
}
function relax(){
//echo 'relaxing...
' ;
for($i=0 ; $iedges) ; $i++){
$e = $this->edges[$i];
$vx = $this->nodes[$e->to]->x - $this->nodes[$e->from]->x;
$vy = $this->nodes[$e->to]->y - $this->nodes[$e->from]->y;
$len = sqrt($vx * $vx + $vy * $vy);
$f = ($this->edges[$i]->len - $len) / ($len * 3) ;
$dx = $f * $vx;
$dy = $f * $vy;
$this->nodes[$e->to]->dx += $dx;
$this->nodes[$e->to]->dy += $dy;
$this->nodes[$e->from]->dx += -$dx;
$this->nodes[$e->from]->dy += -$dy;
}
for ($i=0 ; $inodes) ; $i++){
$dx = 0;
$dy = 0;
for ($j = 0 ; $j < sizeof($this->nodes) ; $j++) {
if (!$i == $j){
$vx = $this->nodes[$i]->x - $this->nodes[$j]->x;
$vy = $this->nodes[$i]->y - $this->nodes[$j]->y;
$len = $vx * $vx + $vy * $vy;
if ($len == 0){
$dx += (rand(0,1000000.0) / 1000000.0);
$dy += (rand(0,1000000.0) / 1000000.0);
}else{
if ($len < 100*100){
$dx += $vx / $len;
$dy += $vy / $len;
}
}
}
$dlen = $dx * $dx + $dy * $dy;
if ($dlen > 0){
$dlen = sqrt($dlen) / 2;
$this->nodes[$i]->dx += $dx / $dlen;
$this->nodes[$i]->dy += $dy / $dlen;
}
}
}
for ($i=0 ; $inodes);$i++) {
if (!$this->nodes[$i]->fixed) {
$this->nodes[$i]->x += max(-5.0, min(5.0, $this->nodes[$i]->dx));
$this->nodes[$i]->y += max(-5.0, min(5.0, $this->nodes[$i]->dy));
$olddx = $this->nodes[$i]->mx ;
$olddy = $this->nodes[$i]->my ;
$this->nodes[$i]->mx = $this->nodes[$i]->dx;
$this->nodes[$i]->my = $this->nodes[$i]->dy;
if((abs($this->nodes[$i]->mx-$olddx) < 0.00000001) and (abs($this->nodes[$i]->my-$olddy) < 0.00000001)){
$this->nodes[$i]->unchanged = true ;
}
if ($this->nodes[$i]->x < 0) {
$this->nodes[$i]->x = 0;
}else{
if ($this->nodes[$i]->x > $this->d['width']) {
$this->nodes[$i]->x = $this->d['width'];
}
}
if ($this->nodes[$i]->y < 0) {
$this->nodes[$i]->y = 0;
}else{
if ($this->nodes[$i]->y > $this->d['height']) {
$this->nodes[$i]->y = $this->d['height'];
}
}
}//end if not fixed
$this->nodes[$i]->dx = $this->nodes[$i]->dx / 2;
$this->nodes[$i]->dy = $this->nodes[$i]->dy / 2;
//echo "node " . $i . " position is: " . $this->nodes[$i]->x . ',' . $this->nodes[$i]->y . "
" ;
}
}//end of relax function
function exportNodePositions(){
$data = array() ;
for($i=0;$inodes);$i++){
$n = $this->nodes[$i] ;
$data[] = array($n->lbl, $n->x, $n->y, $n->startx, $n->starty) ;
}
$json = new Services_JSON();
$output = $json->encode($data);
return $output;
}
}//end of Graph class
/****************** EXAMPLE OF USE ********************/
/* define the area within which the graph algorithm should work - this usually
is based on the size of the page or element in which the result is to be
displayed */
$pagedim = array('height' => 400, 'width' => 400) ;
/* Next is a rather long-winded way of declaring a 2D array :) - The only things
you should take on board here is that the indices used correspond to the tag
names and that the value they index corresponds to the distance between them.
The only other point is that the array is symmetrical (I forget the technical
term) i.e. it has the structure
0 b c
b 0 d
c d 0
This is to ensure that the index ['tag1']['tag2'] returns the same value as
the index ['tag'2]['tag1']...since both indices refer to the same distance
between tags - This could probably be adjusted so as to save on the amount
of data being moved around but saved me the effort of coding column/row
checks for each tag lookup.
*/
$tags = array() ;
$tags['tag1']['tag1']=0; $tags['tag1']['tag2']=10 ; $tags['tag1']['tag3']=5 ;
$tags['tag2']['tag1']=10; $tags['tag2']['tag2']=0 ; $tags['tag2']['tag3']=7 ;
$tags['tag3']['tag1']=5; $tags['tag3']['tag2']=7 ; $tags['tag3']['tag3']=0 ;
/* define the range of the data found in the array just defined (
usually maxValue - minValue) - so 10-0=10 - this could probably be worked out
in the Graph class constructor and not be passed in - if anyone wants to do
it then send me a copy */
$range = 10 ;
/* create an instance of the Graph class and start it running */
$graph = new Graph($tags, $range, $pagedim) ;
$graph->run() ;
/* when done export the data in JSON format */
$jsonData = $graph->exportNodePositions() ;
echo($jsonData) ;
?>