<?php

class shortestPath {
    private $_longestPath = 0;
    private $_nodes=array();
    private $_dist=array();
    private $_previous=array();
    private $_users=false;
    
    public $numlinks=0;
    
    /**
     * @var Cwd_Log
     */
    public $log;
    
    public function __construct(){
        $m = new UserModel();
        $db=$m->getDefaultAdapter();
        $this->log = new Cwd_Log('',$db);
    }
    
    public function getPath($fromid,$toid){
        $this->_buildSkel($fromid);
        
        $this->log->log($this->_dist,Zend_Log::DEBUG);
        
        $this->_findPath($toid);
        
        $curnode = $toid;
        $links=array();
        
        $this->log->log($this->_dist,Zend_Log::DEBUG);
        
        while($curnode != $fromid && $curnode !=-1){
            $links[$this->numlinks++]=$curnode;
            $curnode = $this->_previous[$curnode];
            if($this->numlinks > $this->_longestPath){
                throw new Exception('To many Links');
            }
        }
        

        /**
        if($curnode != $fromid){
            echo "WARNING: No path from $fromid to $toid<br>";
        }else{
            echo "Number of Links: ".$this->numlinks."<br>";
        }
        **/        
    
        return array_reverse($links);
    }
    
    public function getNumLinks(){
        return $this->numlinks;
    }

    private function _fetchUser(){
        $m_user = new UserModel();
        $this->_users = $m_user->fetchAll();
        $this->_longestPath = $this->_users->count()+1;
    }
    
    private function _buildSkel($fromid){
        if(!$this->_users){
            $this->_fetchUser();
        }
        
        foreach($this->_users as $user){
            $this->_nodes[]=$user->id;
            $this->_dist[$user->id]=$this->_longestPath;
            $this->_previous[$user->id]=-1;
        }
        
        if($fromid>0)
            $this->_dist[$fromid]=0;
    }
    
    private function _findPath($toid){
        $Q = $this->_nodes;
        while(count($Q)>0){
            $qsize=count($Q);
            $unode = $this->_findMin($Q);
            
            if($unode == $toid){
                break; // We have found ToId
            }
            
            $u = array_search($unode, $Q);
            $Q[$u]=false;
            
            $Q = array_filter($Q);
            
            if($qsize == count($Q)){
                throw new Exception("Qsize doesnt shrink!");
            }
            
            $m_link = new LinksModel();
            
            $invitees = $m_link->fetchAll("fromid='$unode'");
            $inviters = $m_link->fetchAll("toid='$unode'");
            
            if($invitees->count()>0)
                $this->_relaxNeighbors($unode,$invitees,'toid');
                
            if($inviters->count()>0)
                $this->_relaxNeighbors($unode,$inviters,'fromid');

        }
    }
    
    private function _relaxNeighbors($unode,$neighbors,$col){
        foreach($neighbors as $neighbor){
            $this->_relax($unode,$neighbor->$col);
        }
    }
    
    private function _relax($u,$v){
        if($this->_dist[$v] > $this->_dist[$u]+1){
            $this->_dist[$v]=$this->_dist[$u]+1;
            $this->_previous[$v] = $u;
        }
    }

    private function _findMin($nodes){
        $keys = array_keys($nodes);
        $minid = $nodes[$keys[0]];
        $mindist = $this->_dist[$minid];


        foreach ($keys as $key){
            $tnode = $nodes[$key];
            if($this->_dist[$tnode] < $mindist){
                $mindist = $this->_dist[$tnode];
                $minid=$tnode;
            }
        }
        
        return $minid;
    
    }
    
    
    
    
}