<?php
/*
****************************************************************************
* class graf *
* Version 0.7b *
* *
* A PHP class for calculating all posible ways from a point to another *
* (or to all the posible points) the shortest way from one point to *
* another and the distance for that ways *
* *
* Copyright (C) 2003 by Dragos Protung - dragos@protung.ro *
* *
* This PHP class is free software; you can redistribute it and/or *
* modify it under the terms of the GNU Lesser General Public *
* License as published by the Free Software Foundation; either *
* version 2.1 of the License, or (at your option) any later version. *
* *
* This PHP class is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
* Lesser General Public License for more details. *
* *
* *
* Author: *
* Dragos Protung, 500164 Brasov, Romania, dragos@protung.ro *
* *
****************************************************************************
*/
class graf {
function graf($matrix){
$this -> m = $matrix; // the matrix
$this -> n = count($this -> m);
$this -> varf = 0;
$this -> s = array();
$this -> nod = null;
$this -> end = null;
$this -> routs = array();
}
function verific($c) {
for ($i=0; $i<$this -> varf; $i++)
if ($this -> s[$i]==($c)) return true;
return false;
}
function return_all($y) {
(int)$y;
if($this -> varf==1)
return;
for ($i=0; $i<$this -> varf ; $i++) {
$this -> routs[$y] = array_merge($this -> routs[$y], $this -> s[$i]);
}
$dist =0;
for ($i=0; $i<$this -> varf-1 ; $i++) {
$dist += $this -> m[$this -> s[$i]][$this -> s[$i+1]];
}
$sum = array("dist" => $dist);
$this -> routs[$y] = array_merge($this -> routs[$y], $sum);
}
function ways_from_point($nod) {
$this -> routs = array();
(int)$this -> nod = $nod;
$this -> s[$this -> varf] = $this -> nod;
$this -> varf++;
$rand = $this -> nod;
$col = 0;
$parcurs = 0;
$x = 0;
while ($parcurs == 0) {
while (($this -> m[$rand][$col]==0) && ($col<$this -> n))
$col++;
if ($col<$this -> n) {
if (!graf::verific($col)) {
$this -> s[$this -> varf] = $col;
$this -> varf++;
$rand = $col;
$col = 0;
}
else $col++;
}
else {
graf::return_all($x);
$x++;
$extrag = $this -> s[($this -> varf-1)];
$this -> varf--;
if ($extrag == $this -> nod)
$parcurs = 1;
else {
$col = ($extrag+1);
$rand = $this -> s[($this -> varf-1)];
}
}
}
}
function ways_from_point_to_point($nod, $end) {
graf::ways_from_point($nod);
$z=0;
$dir_routs = array();
for ($i=0; $i<count($this -> routs); $i++) {
if ($this -> routs[$i][count($this -> routs[$i])-2] == $end) {
$dir_routs[$z] = $this -> routs[$i];
$z++;
}
}
$this-> routs = $dir_routs;
}
function shortest_way($nod, $end) {
graf::ways_from_point_to_point($nod, $end);
$z=0;
$dir_routs = array();
for ($i=0; $i<count($this -> routs);$i++) {
if ($this -> routs[$i]["dist"] < $this -> routs[$i-1]["dist"] or $this -> routs[$i-1]["dist"]=="") {
$dir_routs[$z] = $this -> routs[$i];
$z++;
}
}
$this-> routs = $dir_routs;
}
}
?>
|
ReTweet
Stumble It!
Bookmark in del.icio.us
Advertise on this site
Site map
Statistics
Site tips
Privacy policy
Contact