<?php


//-------------------------------------------------------------------------------
// itinerary.php
// Implementation of the itinerary searching algorithm. 
//
//
// written by Bart Meganck, Royal Museum for Central Africa
// bart.meganck@africamuseum.be
//
// with code taken from : http://www.fonant.com/demos/douglas_peucker/algorithm
//
//
// This program is free & open source, under the GNU General Public License, v.2
// See : http://www.gnu.org/copyleft/gpl.html for more details.
//
//-------------------------------------------------------------------------------

// Dijkstra shortest path algorithm
require ("DijkstraModule.php");

// Ramen-Douglas-Peucker algorithm for polyline simplification 
require ("RDP_Module.php");


class Itinerary {


	public function dijkstra_matrix($distance_matrix,$max_distance) {
	
	//var_dump ($distance_matrix);
	
		// for the moment, we do a simple Dijkstra shortest path search
		// later on, a full-scale itinerary searching algorithm will be here
	
		// ( from : http://codeguru.earthweb.com/forum/showthread.php?t=430962)
		// this code taken from : http://en.giswiki.net/wiki/Dijkstra's_algorithm 
 
		define('I',1000); // I is the infinite distance.
 		$matrixWidth = 20; // Size of the matrix
 
		// $points is an array in the following format: (router1,router2,distance-between-them)
		$points = $distance_matrix; 
		$ourMap = array();
 
 
		// Read in the points and push them into the map
 
		for ($i=0,$m=count($points); $i<$m; $i++) {
			$x = $points[$i][0];
			$y = $points[$i][1];
			$c = $points[$i][2];
			$ourMap[$x][$y] = $c;
			$ourMap[$y][$x] = $c;
		}
		
		
		
		//echo('$+$+$+$');
		//var_dump ($ourMap);
		//echo('$+$+$+$');
 
		// ensure that the distance from a node to itself is always zero
		// Purists may want to edit this bit out.
 
		for ($i=0; $i < $matrixWidth; $i++) {
		    for ($k=0; $k < $matrixWidth; $k++) {
		        if ($i == $k) $ourMap[$i][$k] = 0;
		    }
		}
 
 
		// initialize the algorithm class
		$my_DijkstraModule = new DijkstraModule($ourMap, I,$matrixWidth);
 
		$my_DijkstraModule->findShortestPath(0);
		// Display the results
 
		//echo '<pre>';
		//echo "the map looks like:\n\n";
		//echo $my_dijkstra -> printMap($ourMap);
		//echo "\n\nthe shortest paths from point 0:\n";
		$text = $my_DijkstraModule -> getResults();
		//echo $text;
		 //var_dump ($path_array);
		//echo '</pre>';
		
		return $text;
	
	} // function dijkstra_matrix


} // class Itinerary



// Code taken from : http://www.fonant.com/demos/douglas_peucker/algorithm
class GeoPoint {

    public $latitude;
    public $longitude;

    public function __construct($lat,$lng)
    {
        $this->latitude = (float)$lat;
        $this->longitude = (float)$lng;
    }
    
} // class Geopoint



?>