edge.java

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

package dk.itu.nulx30.graph;

import java.io.Serializable;

import java.lang.reflect.Field;

import java.util.Comparator;

/**
 * This class represents a undirected connection (with a directed trail-value)
 * to a neighbor <code>Vertex</code>. The class contains the cost/distance
 * between the two vertices, the total number of ants which have walked on this
 * <code>Edge</code> and several different trail-values.
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 */
public class Edge implements Serializable, Cloneable {
  /** One of the vertices at the end of the object */
  protected Vertex firstVertex;
  /** The other of the vertices at the other end of the object */
  protected Vertex secondVertex;
  /** The weight or distance of the object */
  protected double weight;

  // If the Graph has undirected trail-values the only the UP-variables are used.

  /** The current trail-value on the edge */
  private double trailValueUp, trailValueDown;

  /** The change in trail-value on the edge */
  private double changeInTrailValueUp, changeInTrailValueDown;

  /** The total amount of trail-value on the edge */
  private double totalTrailValueUp, totalTrailValueDown;

  /** The total number of ants which have walked on this edge */
  private double totalAnts;

  /** This variable is used for saving normalized values when drawing graphs */
  private double tempVal;

  /**
   * Class constructor specifying the two vertices and the weight on the edge.
   *
   * @param newFirstVertex  One end of the edge.
   * @param newSecondVertex The other end of the edge.
   * @param newWeight       The weight on the edge.
   */
  public Edge( Vertex newFirstVertex, Vertex newSecondVertex, double newWeight ) {
    this( newFirstVertex, newSecondVertex, newWeight, 0 );
  }

  /**
   * Class constructor specifying the two vertices and the weight on the edge
   * and the initial trail-value.
   *
   * @param newFirstVertex  One end of the edge.
   * @param newSecondVertex The other end of the edge.
   * @param newWeight       The weight on the edge.
   * @param newTrailValue   The initial trail-value on the edge.
   */
  public Edge( Vertex newFirstVertex, Vertex newSecondVertex,
               double newWeight, double newTrailValue ) {
    firstVertex = newFirstVertex;
    secondVertex = newSecondVertex;
    weight = newWeight;
    trailValueUp = newTrailValue / 2;
    trailValueDown = newTrailValue / 2;
  }

  /**
   * Returns the vertex at the other end of the edge. The method
   * takes the "start" of the edge and returns the other end.
   *
   * @param  fromVertex The vertex at the "start" of the edge.
   *
   * @return the <code>Vertex</code> at the other end of the edge.
   */
  public Vertex getDestination( Vertex fromVertex ) {
    if ( fromVertex.equals( firstVertex ) ) {
      return secondVertex;
    }
    else {
      return firstVertex;
    }
  }

  /**
   * This method returns one of the vertices from the edge.
   * If the argument <code>number</code> is 1 the first
   * <code>Vertex</code> is returned otherwise the
   * second <code>Vertex</code> is returned.
   *
   * @param  number a number indicating which of the vertices to
   *         return. If <code>number</code> is 1 the first
   *         <code>Vertex</code> is returned otherwise the
   *         second <code>Vertex</code> is returned.
   *
   * @return one of the two vertices in the edge.
   */  
  public Vertex getVertex( int number ) {
    return ( number == 1 ? firstVertex : secondVertex );
  }

  /**
   * Provides a string representation of this object consisting of 
   * the two vertices, weight and trail-values.
   *
   * @return a string representation of the object.
   */
  public String toString() {
    return "(from: " + firstVertex + ", to: " + secondVertex +
           ", weight: " + weight + 
           ", trail-values: (" + trailValueUp + ", " + trailValueDown + ") )";
  }

  /**
   * Updates the trail-value to the <code>newValue</code>.
   *
   * @param newValue the new value of the trail.
   */  
  public void updateTrail( double newValue ) {
    totalTrailValueUp += newValue;
    trailValueUp = newValue;
  }

  /**
   * Updates the trail-value to the <code>newValue</code> in the 
   * correct direction. The direction is calculated from 
   * <code>destVertex</code>.
   *
   * @param newValue   the new value of the trail.
   * @param destVertex the vertex at the end of the edge.
   */    
  public void updateTrail( double newValue, Vertex destVertex ) {
    if ( destVertex.compareTo( getDestination( destVertex ) ) < 0 ) {
      totalTrailValueDown += newValue;
      trailValueDown = newValue;
    }
    else {
      totalTrailValueUp += newValue;
      trailValueUp = newValue;
    }
  }

  /**
   * <code>getWeight</code> returns the weight of the edge (is 
   * an assessor for weight).
   * 
   * @return the weight of the edge.
   */  
  public double getWeight() {
    return weight;
  }

  /**
   * This method use reflection to access the a field in the object.
   * The field is either accessed in this class or in one of the superclasses
   * (if they exist).
   * The argument <code>attrName</code> must contain a string 
   * representation of one of the fields in <code>Edge</code>.
   *
   * @param attrName the name of the wanted field. If an incorrect
   * name is used the program will terminate.
   *
   * @return the value of the wanted field.
   */
  public double getAttribute( String attrName ) {
    Class sc = getClass();
    while ( sc != null ) {
      try {
        Field theField = sc.getDeclaredField( attrName );
        return theField.getDouble( this );
      }
      catch ( NoSuchFieldException e ) {
        sc = getClass().getSuperclass();
        // There is no matching field in this class, try the the superclass
      }
      catch ( IllegalAccessException e ){
        e.printStackTrace();
        System.exit( 1 );
      }
    }

    System.err.println( "There is no field of the name " + attrName +
                        " in the Class hierarchy" );
    System.exit( 1 );

    // Will never happen because of System.exit's above
    return Double.MIN_VALUE;
  }
  
  /**
   * This method is an accessor method for trailValue.
   *
   * @return the value of trailValue.
   */
  public double getTrail() {
    return trailValueUp;
  }

  /**
   * This method is an accessor method for trailValue- (Up or Down). The
   * correct direction is decided from <code>destVertex</code>.
   *
   * @param destVertex the vertex at the end of the edge.
   *
   * @return the value in trailValue- (Up or Down).
   *         The correct direction is decided from <code>destVertex</code>.
   */
  public double getTrail( Vertex destVertex ) {
    return ( destVertex.compareTo( getDestination( destVertex ) ) < 0 ) ?
                                                  trailValueDown : trailValueUp;
  }

  /**
   * This method is an accessor method for changeInTrailValue.
   *
   * @return the value of <code>changeInTrailValue</code>
   */
  public double getChangeInTrailValue() {
    return changeInTrailValueUp;
  }

  /**
   * This method is an accessor method for changeInTrailValue- (Up or Down). The
   * correct direction is decided from <code>destVertex</code>.
   *
   * @param destVertex the vertex at the end of the edge.
   *
   * @return the value in changeInTrailValue- (Up or Down).
   *         The correct direction is decided from <code>destVertex</code>.
   */
  public double getChangeInTrailValue( Vertex destVertex ) {
    return ( destVertex.compareTo( getDestination( destVertex ) ) < 0 ) ?
                                  changeInTrailValueDown : changeInTrailValueUp;
  }

  /**
   * Mutator method for <code>changeInTrailValueUp</code>.
   * <code>changeInTrailValueUp</code> gets the value in the argument
   * <code>newChange</code>.
   *
   * @param newChange the new value for <code>changeInTrailValueUp</code>.
   */    
  public void setChangeInTrailValue( double newChange ) {
    changeInTrailValueUp = newChange;
  }

  /**
   * Mutator method for changeInTrailValue- (either Up or Down). The
   * correct direction is decided from <code>destVertex</code>.
   *
   * @param newChange the new value for the changeInTrailValue in the correct
   * direction (the direction is decidede from <code>destVertex</code>.
   * @param destVertex the vertex at the end of the edge.
   */    
  public void setChangeInTrailValue( double newChange, Vertex destVertex ) {
    if ( destVertex.compareTo( getDestination( destVertex ) ) < 0 ) {
      changeInTrailValueDown = newChange;
    }
    else {
      changeInTrailValueUp = newChange;
    }
  }  
  
  /**
   * This method is called on every ant move via this edge.
   * NOTE : Currently this method only increments the variable 
   * <code>totalAnts</code>.
   */    
  public void antMoveBy(){
    incTotalAnts();
  }
  
  /**
   * Mutator method for <code>totalAnts</code>. <code>totalAnts</code>
   * gets the value in the argument <code>newTotal</code>.
   *
   * @param newTotal the new value for <code>totalAnts</code>.
   */    
  public void setTotalAnts( double newTotal ) {
    totalAnts = newTotal;  
  }

  /**
   * Mutator method for <code>totalAnts</code>. <code>totalAnts</code>
   * is increased by 1.
   */    
  public void incTotalAnts(){
    totalAnts++;  
  }

  /**
   * This method is an accessor method for <code>totalAnts</code>.
   *
   * @return the total number of ants which have walked on this edge.
   */    
  public double getTotalAnts() {
    return totalAnts;
  }

  /**
   * <code>setTempVal</code> is an mutator method for <code>tempVal</code>.
   * <code>tempVal</code> gets the value in <code>newTempVal</code>.
   *
   * @param newTempVal the new value for <code>tempVal</code>.
   */
  public void setTempVal( double newTempVal ) {
    tempVal = newTempVal;
  }

  /**
   * <code>getTempVal</code> is an accessor method for <code>tempVal</code>.
   * 
   * @return <code>tempVal</code> which is used for saving normalized 
   * values when drawing graphs.
   */  
  public double getTempVal() {
    return tempVal;  
  }
  
  /**
   * <code>getComparator</code> returns a <code>Comparator</code> which 
   * compares the edges after the criterions given as arguments.
   * <code>compareToField</code> gives which field in <code>Edge</code>
   * we shall use in the sort and <code>sortTopFirst</code> decides the
   * sort order (ascending or descending).
   *
   * @param compareToField --- the field in <code>Edge</code>
   * @param sortTopFirst --- if true => the largest first
   *
   * @return a <code>Comparator</code> which compares the edges after 
   *         the criterions given as arguments.
   */
  public static Comparator getComparator( String compareToField,
                                                         boolean sortTopFirst ){
    Comparator c = new EdgeComparator( compareToField, sortTopFirst );
    return c;
  }

  /**
   * Compares this <code>Edge</code> to the specified object. 
   * The result is true if and only if the argument is not null, 
   * is a <code>Edge</code> and connects the same vertices as
   * this object.
   *
   * @param other the <code>Object</code> to compare to.
   *
   * @return a boolean which is true if and only if this object is equal 
   * to the argument, otherwise false.
   */
  public boolean equals( Object other ) {
    return ( firstVertex == ( ( Edge ) other ).firstVertex ) &&
           ( secondVertex == ( ( Edge ) other ).secondVertex );
  }
}