Login   Register  
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-$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;
   }
}

?>