PHP Classes
elePHPant
Icontem

File: graph.class.php

Recommend this page to a friend!
Stumble It! Stumble It! Bookmark in del.icio.us Bookmark in del.icio.us
  Classes of Protung Dragos  >  Graf  >  graph.class.php  >  Download  
File: graph.class.php
Role: Class source
Content type: text/plain
Description: the class file
Class: Graf
Computing routes and distances between two points
Author: By
Last change: Change the code so now you can use it with more flexibility.
For example you can use:
ways_from_point($point) -- will compute all routs (ways) from that point
ways_from_point_to_point($point1, $point2) -- will compute all routs (ways) from that point to another
shortest_path($point1, $point2) -- will compute all routs (ways) from that point to another that are the shortest
Date: 10 years ago
Size: 4,828 bytes
 

Contents

Class file image Download
<?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;
   }
}

?>