dijkstrarouting.java

JAVA版的蚂蚁算法(Ant Colony Optimization Algorithms)

package dk.itu.nulx30.networkModel;

import dk.itu.nulx30.util.Algorithms;
import dk.itu.nulx30.util.ShortestPaths;

import dk.itu.nulx30.eventSimulation.EventUpdateDijkstra;
import dk.itu.nulx30.eventSimulation.EventSimulation;

import dk.itu.nulx30.networkModel.exceptions.NoPossibleRoutingException;

/**
 * <code>DijkstraRouting</code> implements a routing algorithm using Dijkstra's
 * algorithm to calculate the shortest paths.
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class DijkstraRouting implements RoutingAlgorithm {
  /** the network which this algorithm should route packages on*/
  private Network network;
  /** the update frequency with which the routing tables are updated*/
  private int updateFrequency;
  /** the result of running Dijkstra SSSP on the network*/
  private ShortestPaths[] shortestPaths;
  /**
   * This routing table has the format :<br>
   * [source][dest] = nextRouterIndex
   */
  private int[][] routingTable;

  /**
   * Class constructor for <code>DijkstraRouting</code> which takes an
   * <code>Network</code> as argument. This constructor also initializes
   * the routingtables.
   *
   * @param network the network which this algorithm should route packages on
   * @param updateFrequency the update frequency with which the routing tables are
   * updated (-1 is interpreted as never)
   */
  public DijkstraRouting( Network network, Double updateFrequency ) {
    this.network = network;
    this.updateFrequency = updateFrequency.intValue();
    shortestPaths = new ShortestPaths[ network.getNumberOfVertices() ];
    routingTable = new int[ network.getNumberOfVertices() ]
                                                   [ network.getNumberOfVertices() ];
    updateRoutingTable();
  }

  /**
   * Updates all the routing tables for all routers using Dijkstra SSSP.
   */
  public void updateRoutingTable() {
    System.err.println( "Running dijkstra");
    double length;
    for ( int i = 0; i < network.getNumberOfVertices(); i++ ) {
      RouterQueue[] rq = ( ( Router )
                                    network.getAllVertices()[ i ]).getOutputQueues();
      for ( int j = 0; j < rq.length; j++ ){
        length = rq[ j ].getDelay() + rq[ j ].getWire().getDelay();
        length += rq[ j ].getWire().getTarget().getInputQueue().getDelay();
        if ( rq[ j ].isFull() ) {
          length += 50000;
        }
        rq[ j ].getWire().setTempVal( length );
      }
    }
    for ( int i = 0; i < network.getNumberOfVertices(); i++ ) {
      shortestPaths[ i ] = Algorithms.dijkstra( network, i, "tempVal" );
      for ( int j = 0; j < network.getNumberOfVertices(); j++ ) {
        // Find the predecessor of this cell
         routingTable[ i ][ j ] = shortestPaths[ i ].getNextVertexOnPath( i, j );
      }
    }
  }

  /**
   * This method should take a package and the router which currently holds the
   * package and calculate the next router on the path to the destination.
   *
   * @param router the router which currently holds the package
   * @param pack the pack to send to the destination router
   *
   * @exception NoPossibleRoutingException a
   * <code>NoPossibleRoutingException</code> is thrown if it is not possible to
   * route the package (it has reached a dead-end).
   *
   * @return the next router on the path to the destination
   */
  public Router routePackage( Router router, NetworkPackage pack )
                                                  throws NoPossibleRoutingException {
    return ( Router ) network.getVertex( routingTable[ router.getIndex() ]
                                              [ pack.getDestination().getIndex() ] );
  }

  /**
   * Implementation of <code>RoutingAlgorithm</code> interface. Does nothing in
   * this class.
   *
   * @param sim the simulation in which the events has to occur
   */
  public void scheduleRoutingEvents( EventSimulation sim ) {
    // For each package creation interval
    if ( updateFrequency == -1 ) {
      return;
    }
    for ( int time = updateFrequency; time < sim.getDuration();
                                                          time += updateFrequency ) {
      EventUpdateDijkstra input = new EventUpdateDijkstra( ( double ) time, sim );
      sim.getEventHeap().add( input );
    }
  }

  /**
   * Implementation of <code>RoutingAlgorithm</code> interface.<br>
   * This method is called when a package has reached its destination router.<br>
   * Not used in this routing algorithm.
   *
   * @param netPackage the package, which has arrived
   */
  public void packageArrived( NetworkPackage netPackage ){}

  /**
   * Implementation of <code>RoutingAlgorithm</code> interface.<br>
   * This method is called when a router detecs that a package did not arrive
   * at the router it was sent to.<br>
   * Not used in this routing algorithm.
   *
   * @param netPackage the package which has died
   */
  public void packageLost( NetworkPackage netPackage ){}
}