/* Learning Net - shlomy boshy 031868912
 * Reinforcement Learning network simulation  
 */
package learnnet;
import java.util.*;

public class BellmanFordEstimator{
   /** estimations of Bellman Ford for node */
      
   private double[] d;  /* distances */
   private double[][] w;  /* edge sizes */
   private int[] father; 
   /* father[v] - the "father" of v in
    *             the shortest-path tree
    *             of the graph
    */
   
               
   private int numNodes=0;
   private Network NT;
   private Node mynode;

   private static final double INFINITE=999999;

   BellmanFordEstimator(Network NT,Node N) {
     this.NT = NT;
     this.mynode = N;
     numNodes = NT.size();
     d = new double[numNodes];
     father = new int[numNodes];
     for (int i=0;i<father.length;i++) father[i]=(int)INFINITE; /*invalid value*/     
     for (int i=0;i<numNodes;i++) d[i]=INFINITE;
     d[NT.indexOf(mynode)]=0;
     w = new double[numNodes][numNodes];     
     buildEdgeSizes(); 
     makeShortestPaths();
     if (Network.Debug_Results)
       printDistances();
   }
        
   private void makeShortestPaths(){
    /** do belman-ford estimate on network */   
   Enumeration e;
   Node n,nb;
          
                  
    for (int t=0;t<numNodes;t++) { 
       /* t times do relax for each edge (u,v) */                                                             
     for (int i=0;i<numNodes;i++) {
       n = (Node)NT.elementAt(i);
       e= n.Q.getNeighbors();
       while (e.hasMoreElements()) {
         nb = (Node)e.nextElement();
         relax(i,NT.indexOf(nb));
       }  
     }       
    }
  }
                  
  private void buildEdgeSizes(){
    Enumeration e;
    Node n,nb;
    
    for (int i=0;i<numNodes;i++) 
       for (int j=0;j<numNodes;j++) 
          w[i][j]=INFINITE;
              
    for (int i=0;i<numNodes;i++) {
       n = (Node)NT.elementAt(i);
       e= n.Q.getNeighbors();  
       while (e.hasMoreElements()) {
         nb = (Node)e.nextElement();
         w[i][NT.indexOf(nb)] = 
                      n.Q.getTransferTimeTo(nb);
       } 
     }
   //for (int i=0;i<numNodes;i++) 
   //    for (int j=0;j<numNodes;j++) 
   //       Network.debugPrint("w["+i+","+j+"]="+w[i][j]);
         
  }  
  
  private void relax(int u,int v){
   
   if ( d[u] + w[u][v] < d[v]) {
       d[v] = d[u] + w[u][v];
       father[v]=u;  
     }
     
  }                      
    
  public double getValue(Node N){
    /** get B.F. value (distance) to node N (from current) */  
    return d[NT.indexOf(N)];
  }    
  
  public Node getMinValueNode(Node dest){
    /** the neighbor node in the shortest path to dest*/
    int p=NT.indexOf(dest),lastp=-1;
    int myindex=NT.indexOf(mynode);
    
    /* go back through shortest paths tree
     * from dest until current node
     */
    while (p != myindex) {
        lastp=p;
        p=father[p];
      }
    /* lastp is the neighbor in the shortest path */      
    return (Node)NT.elementAt(lastp);           
  }
  
  public void printDistances(){
   Network.debugPrint("Paths from node "+mynode+":");
   for (int i=0;i<numNodes;i++) {
     Node fi = (father[i]==INFINITE) ? null : (Node)NT.elementAt(father[i]);
     Network.debugPrint("distance to dest "+(Node)NT.elementAt(i)+"is:"+d[i]+" with father "+fi);    
   }
  }
}