routingtable.java

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

package dk.itu.nulx30.networkModel;

import java.io.Serializable;

import java.util.ArrayList;
import java.util.List;

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

/**
 * The class <code>RoutingTable</code> contains all the routing information that
 * a given <code>Router</code> contains. A routingtable contains a
 * <code>AntRoutingEntry</code> for each destination for each outgoing queue in
 * the router.
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 *
 * @see AntRoutingEntry
 */
public class RoutingTable implements Serializable {
  /**
   * This array of lists contain an entry for each destination. A given list
   * then contains all the wires that can be used to get to the destination.
   */
  private List[] antRoutingTable;
  /** The number of routers in this routingtable*/
  private int numberOfRouters;
  /** The router which contains this routingtable*/
  private Router host;

  /**
   * Class constructor for class <code>RoutingTable</code> which takes as
   * argument the host of this routingtable and the number of routers in the
   * network.
   *
   * @param host the host of this routingtable
   * @param numberOfRouters the number of routers that should be created in the
   * routingtable
   */
  public RoutingTable( Router host, int numberOfRouters ) {
    antRoutingTable = new ArrayList[ numberOfRouters ];
    for ( int i = 0; i < antRoutingTable.length; i++ ) {
      antRoutingTable[ i ] = new ArrayList();
    }
    this.numberOfRouters = numberOfRouters;
    this.host = host;
  }

  /**
   * This method adds an outputwire to the routingtable.
   *
   * @param outputWire the wire to add to the routingtable
   */
  public void addOutputWire( Wire outputWire ) {
    for ( int i = 0; i < antRoutingTable.length; i++ ) {
      // Add this wire to all targets (except the host) 
      if ( host.getIndex() != i ) {
        antRoutingTable[ i ].add( new AntRoutingEntry( outputWire ) );
      }
    }
  }

  /**
   * This method adds a new target router to the this routingtable. This method
   * should only be used if Routers are added dynamically.
   *
   * @param target the new target router for this routingtable.
   */
  public void addRouter( Router target ) {
    List[] temp = new ArrayList[ numberOfRouters + 1 ];
    System.arraycopy( antRoutingTable, 0, temp, 0, antRoutingTable.length );
    temp[ numberOfRouters ] = new ArrayList();
    //Insert an AntRoutingEntry for each wire in router
    int copyFrom = 0;
    if ( host.getIndex() == copyFrom ) {
      copyFrom = 1;
    }
    for ( int i = 0; i < temp[ copyFrom ].size(); i++ ) {
      temp[ numberOfRouters ].add( new AntRoutingEntry( ( ( AntRoutingEntry )
                                      temp[ copyFrom ].get( i ) ).getWire() ) );
    }
    numberOfRouters++;
  }

  /**
   * Returns all the AntRoutingEntries for this destination router.
   *
   * @param routerIndex the index of the router which contains all the wanted
   * entries
   *
   * @return a <code>List</code> containing AntRoutingEntries
   */
  public List getRoutingList( int routerIndex ) {
    return antRoutingTable[ routerIndex ];
  }

  /**
   * Returns the number of routers in <code>this</code> routing table.
   *
   * @return number of routers in <code>this</code> routing table
   */
  public int getNumberOfRouters(){
    return numberOfRouters;
  }

  /**
   * Returns the number of wires in <code>this</code> routing table.
   *
   * @return number of wires in <code>this</code> routing table
   */
  public int getNumberOfWires(){
    int routerIndex = ( host.getIndex() == 0 ) ? 1 : 0;
    return antRoutingTable[ routerIndex ].size();
  }

  /**
   * This method sets the pheromone value of the <code>AntRoutingEntry</code>
   * that is found in <code>index</code> and using the wire given in
   * <code>usedWire</code>.
   *
   * @param index the index of the target router
   * @param usedWire the wire used to get to the target router
   * @param newValue the new value for the pheromone trail
   *
   * @exception AntRoutingEntryNotFoundException this exception is thrown if
   * the router with index: <code>index</code> does not contain the given
   * wire: <code>usedWire</code>
   */
  public void setPheromoneValue( int index, Wire usedWire, double newValue )
                                       throws AntRoutingEntryNotFoundException {
    AntRoutingEntry are = findAntRoutingEntry( index, usedWire );
    are.setPheromoneValue( newValue );
  }


  /**
   * This method adds the pheromone value to the <code>AntRoutingEntry</code>
   * that is found in <code>index</code> and using the wire given in
   * <code>usedWire</code>.
   *
   * @param index the index of the target router
   * @param usedWire the wire used to get to the target router
   * @param toAdd the pheromone to add to the pheromone trail
   *
   * @exception AntRoutingEntryNotFoundException this exception is thrown if
   * the router with index: <code>index</code> does not contain the given
   * wire: <code>usedWire</code>
   */
  public void incrementPheromoneValue( int index, Wire usedWire, double toAdd )
                                       throws AntRoutingEntryNotFoundException {
    AntRoutingEntry are = findAntRoutingEntry( index, usedWire );
    are.incrementPheromoneValue( toAdd );
  }

  /**
   * Evaporates pheromone from all entries in this <code>RoutingTable</code> by
   * mutiplying with the value given as argument
   * given as argument.
   *
   * @param factor the factor til multiply the pheromone value with
   */
  public void evaporatePheromoneValues( double factor ) {
    for ( int i = 0; i < antRoutingTable.length; i++ ) {
      for ( int j = 0; j < antRoutingTable[ i ].size(); j++ ) {
        ( ( AntRoutingEntry ) antRoutingTable[i].get( j ) ).evaporatePheromoneValue(
                                                                            factor );
      }
    }
  }


  /**
   * Initializes all the entries in this <code>RoutingTable</code> with the value
   * given as argument.
   *
   * @param value the initial value of all entries in this <code>RoutingTable</code>
   */
  public void initializePheromoneValues( double value ) {
    for ( int i = 0; i < antRoutingTable.length; i++ ) {
      for ( int j = 0; j < antRoutingTable[ i ].size(); j++ ) {
        ( ( AntRoutingEntry ) antRoutingTable[i].get( j ) ).setPheromoneValue(
                                                                             value );
      }
    }
  }

  /**
   * Updates the pheromone trails on this routingtable normalized. E.g. the values
   * of the pheromone trails sum to 1 and the values are kept within a bound.
   *
   * @param targetRouterIndex the index of the target router
   * @param usedWire the wire, which pheromone trail we want to update
   * @param update the value to use to update the specific wire
   * @param bound the bound to keep the pheromone values within
   */
  public void updatePheromoneNormalized( int targetRouterIndex, Wire usedWire,
                                          double update, double bound ) {
    List usedPheroList = antRoutingTable[ targetRouterIndex ];

    double newPhero = 0;
    double oldPhero = 0;
    double newOtherPhero = 0;
    double oldOtherPhero = 0;

    for ( int i = 0 ; i < usedPheroList.size(); i++ ) {
      AntRoutingEntry are = (AntRoutingEntry) usedPheroList.get( i );
      if ( usedWire.equals( are.getWire() ) ) {
        oldPhero = are.getPheromoneValue();
        newPhero = ( oldPhero <= 0.5 ) ? oldPhero + update * oldPhero :
                                         oldPhero + update * ( 1 - oldPhero );
        // implement bound
        if ( newPhero > ( 1 - bound )  ) {
          newPhero = 1 - bound;
        }
        if ( newPhero < bound ) {
          newPhero = bound;
        }
        are.setPheromoneValue( newPhero );
        break;
      }
    }

    for ( int j = 0 ; j < usedPheroList.size(); j++ ) {
      AntRoutingEntry are = (AntRoutingEntry) usedPheroList.get( j );
      if ( !usedWire.equals( are.getWire() ) ) {
        oldOtherPhero = are.getPheromoneValue();
        newOtherPhero = oldOtherPhero - ( newPhero - oldPhero ) * (
                        oldOtherPhero / ( 1 - newPhero ));
        are.setPheromoneValue( newOtherPhero );
      }
    }
  }


  /**
   * This method returns an <code>AntRoutingEntry</code>, which match the search
   * criteria.
   *
   * @param index the index of the target router
   * @param usedWire the wire to use to get to the target router
   *
   * @return the <code>AntRoutingEntry</code> for the router in <code>index</code>
   * using the wire given in <code>usedWire</code>.
   *
   * @exception AntRoutingEntryNotFoundException this is trown if the
   * <code>AntRoutingEntry</code> does not contain the wanted wire.
   */
  private AntRoutingEntry findAntRoutingEntry( int index, Wire usedWire )
                                       throws AntRoutingEntryNotFoundException {
    for ( int i = 0; i < antRoutingTable[ index ].size(); i++ ) {
      AntRoutingEntry tmp = ( AntRoutingEntry ) antRoutingTable[ index ].get( i );
      if ( tmp.getWire().equals( usedWire ) ) {
        return tmp;
      }
    }
    throw new AntRoutingEntryNotFoundException( "Could not find the wire " +
        usedWire + " in the router " + index );
  }

  /**
   * Provides a string representation of this object. The string representation,
   * which consists of all the information in the routingtable.
   *
   * @return a string representation of this object.
   */
  public String toString() {
    StringBuffer tmp = new StringBuffer();
    // For each entry (destination router) in the RoutingTable
    for ( int i = 0; i < antRoutingTable.length; i++ ) {
      tmp.append( i + " :\t" );
      // For each wire
      for ( int j = 0; j < antRoutingTable[ i ].size(); j++ ) {
        tmp.append( antRoutingTable[ i ].get( j ) );
      }
      tmp.append('\n');
    }
    return tmp.toString();
  }
}