graph.java

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

package dk.itu.nulx30.graph;

import java.awt.Color;
import java.awt.Dimension;

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.io.Serializable;

import java.text.DecimalFormat;
import java.text.NumberFormat;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

import att.grappa.GrappaConstants;
import att.grappa.GrappaPoint;
import att.grappa.GrappaStyle;
import att.grappa.Node;

/**
 * This class is a simple implementation of a graph. The
 * graph contains an array of Vertices and a <code>List</code> of edges. The
 * graph also contains several methods for creation from different file-formats
 * and for drawing (by use of the Grappa package).
 *
 * @author  Mikkel Bundgaard
 * @author  Troels C. Damgaard
 * @author  Federico Decara
 * @author  Jacob W. Winther
 *
 * @see <a href="http://www.research.att.com/~john/Grappa/">Grappa</a>
 */
public class Graph implements Cloneable, Serializable {
  /** numberFormat can format decimal numbers to two decimals */
  private NumberFormat numberFormat = new DecimalFormat( "0.##" );
  /** the radius of a node in the drawing of the graph*/
  private static final String NODE_RADIUS = "0.5";
  /** the color of a node in the drawing of the graph*/
  private static final Color NODE_COLOR = new Color( 0, 0, 0 );
  /** the color of the font in a node in the drawing of the graph*/
  private static final Color NODE_FONTCOLOR = new Color( 29, 18, 233 );
  /** the size of the font in a node in the drawing of the graph*/
  private static final Integer NODE_FONTSIZE = new Integer( 25 );

  /** the color of a edge in the drawing of the graph*/
  private static final Color EDGE_COLOR = new Color( 0, 0, 0 );
  /** the color of the font on a edge in the drawing of the graph*/
  private static final Color EDGE_FONTCOLOR = new Color( 230, 34, 34 );
  /** the size of the font on a edge in the drawing of the graph*/
  private static final Integer EDGE_FONTSIZE = new Integer( 15 );

  /** the standard percentage of values to be shown */
  protected static final int SHOW_PERCENT_DEFAULT = 100;

  /** the scale of the positions of the nodes in the drawing of the graph*/
  protected static final double X_SCALE = 0.5, Y_SCALE = 0.5;

  /**
   * If the graph has double edges (that is two edges pr. nodepair) this value
   * is used to correct the positioning of the labels of the edges.
   */
  protected static final double DOUBLE_EDGES_X_CORRECT = 0;

  /**
   * If the graph has double edges (that is two edges pr. nodepair) this value
   * is used to correct the positioning of the labels of the edges.
   */  
  protected static final double DOUBLE_EDGES_Y_CORRECT = 20;

  /** the default scaling of the drawGraph()-method ( 1000, 1000 )*/
  protected static final Dimension PICTURE_SCALE = new Dimension( 1000, 1000 );

  /** the name of the graph*/
  protected String name;
  /** the filename which contains the design of this graph*/
  protected String fileName;
  /** an array containing all the vertices in the graph*/
  protected Vertex[] vertices;
  /** a <code>List</code> containing all the edges in the graph*/
  protected List edges;

  /**
   * Sets the number format to the new format given as argument
   *
   * @param nf the new number format for the decimal numbers in the graph 
   */
  public void setNumberFormat( NumberFormat nf ){
    numberFormat = nf;
  }

  /** Class constructor, which constructs a empty graph*/
  public Graph() {}

  /**
   * This method reads a file at the location given in <code>fileName</code> amd
   * constructs a corresponding graph. The initial trailvalue of the edges in
   * the graph is given as <code>initValue</code>. Below is given an example
   * of a file:<br>
   * Vertices<br>
   * 4<br>
   * Edges<br>
   * 1<br>
   * Position of vertices<br>
   * Name horizontal vertical<br>
   * 0 10 10<br>
   * 1 100 100<br>
   * 2 200 100<br>
   * 3 200 10<br>
   * The edges<br>
   * From To Length<br>
   * 1 0 10.0
   *
   * @param name the name of the graph
   * @param fileName the name of the file to read the graph from
   * @param initValue the initial trailvalue on the edges in the graph
   */
  public void createFromGraphMaker( String name, String fileName,
                                                                 double initValue ) {
    BufferedReader input = null;
    StringTokenizer st;
    int numberOfVertices;
    int numberOfEdges;
    String tmpInput;

    try {
      // Construct a new BufferedReader
      input = new BufferedReader( new FileReader( fileName ) );
    }
    catch ( FileNotFoundException FNFe ) {
      throw new RuntimeException("Could not find file : " + fileName );
    }
    try {
      this.fileName = fileName;
      this.name = name;

      // Read the header of the file
      while ( !input.readLine().equals( "Vertices" ) ){};

      numberOfVertices = Integer.parseInt( input.readLine() );

      // Read the rest of the header of the file
      while ( !input.readLine().equals( "Edges" ) ){};

      numberOfEdges = Integer.parseInt( input.readLine() );

      // Construct the array and the List with the correct size
      this.vertices = new Vertex[ numberOfVertices ];
      this.edges = new ArrayList( numberOfEdges );

      while ( !input.readLine().equals( "Name horizontal vertical" ) ){};

      // Create all the vertices
      for ( int i = 0; i < numberOfVertices; i++ ) {
        this.vertices[ i ] = new Vertex( i );
      }

      // Set the position of each of the vertices
      for ( int i = 0; i < numberOfVertices; i++) {
        st = new StringTokenizer( input.readLine() );

        // Skip vertex name
        st.nextToken();

        this.vertices[ i ].setXPos( ( int ) Double.parseDouble(
                                                   st.nextToken() ) * X_SCALE );
        this.vertices[ i ].setYPos( ( int ) Double.parseDouble(
                                                   st.nextToken() ) * Y_SCALE );
      }

      while ( !input.readLine().equals( "From To Length" ) ){};

      // Create all the edges in the graph
      for ( int i = 0; i < numberOfEdges; i++ ) {
        st = new StringTokenizer( input.readLine() );
        int fromVertex;
        int toVertex;
        double weight = 0;

        fromVertex = Integer.parseInt( st.nextToken() );
        toVertex = Integer.parseInt( st.nextToken() );
        weight = Double.parseDouble( st.nextToken() );

        // Create the new edge
        Edge fromToEdge = new Edge( this.vertices[ fromVertex ],
                                 this.vertices[ toVertex ], weight, initValue );

        // Add the new edge in both directions
        this.vertices[ fromVertex ].getEdges().add( fromToEdge  );
        this.vertices[ toVertex ].getEdges().add( fromToEdge  );

        // Insert edge in Graph-objects own list of edges
        this.edges.add( fromToEdge );
      }

      input.close();
    }
    catch ( IOException IOe ) {
      IOe.printStackTrace();
    }
  }

  /**
   * This method reads a file at the location given in <code>fileName</code> amd
   * constructs a corresponding graph. The initial trailvalue of the edges in
   * the graph is given as <code>initValue</code>. The format of the file is
   * UpperRowMatrix described in TSPLIB.
   *
   * @param fileName the name of the file to read the graph from
   * @param initValue the initial trailvalue on the edges in the graph
   *
   * @see
   * <a href="http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/">
   * TSPLIB</a>
   */
  public void createFromUpperRowMatrix( String fileName, double initValue )  {
    createFromUpperRowMatrix( fileName, Integer.MAX_VALUE, initValue );
  }

  /**
   * This method reads a file at the location given in <code>fileName</code> amd
   * constructs a corresponding graph. The initial trailvalue of the edges in
   * the graph is given as <code>initValue</code>. The format of the file is
   * UpperRowMatrix described in TSPLIB.
   *
   * @param fileName the name of the file to read the graph from
   * @param maxDistance the maximum distance of an edge. All edges greather than
   * this distance is discarded.
   * @param initValue the initial trailvalue on the edges in the graph
   *
   * @see
   * <a href="http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/">
   * TSPLIB</a>
   */
  public void createFromUpperRowMatrix( String fileName, int maxDistance,
                                                            double initValue ) {
    BufferedReader input = null;
    StringTokenizer st;
    int numberOfVertices;
    int numberOfEdges;

    try {
      input = new BufferedReader( new FileReader( fileName ) );
    }
    catch ( FileNotFoundException FNFe ) {
      throw new RuntimeException("Could not find file : " + fileName );
    }
    try {
      // Read the header of the file
      do {
        st = new StringTokenizer( input.readLine() );
      } while ( !st.nextToken().equals( "NAME:" ) );
      this.fileName = fileName;
      this.name = st.nextToken();

      do {
        st = new StringTokenizer( input.readLine() );
      } while ( !st.nextToken().equals( "DIMENSION:" ) );
      numberOfVertices = Integer.parseInt( st.nextToken() );
      // Because the graph is fully connected
      numberOfEdges = ( numberOfVertices * ( numberOfVertices - 1 ));

      this.vertices = new Vertex[ numberOfVertices ];
      this.edges = new ArrayList( numberOfEdges );

      while ( !input.readLine().equals( "EDGE_WEIGHT_SECTION" ) ){};

      // Create all the vertices
      for ( int i = 0; i < numberOfVertices; i++ ) {
        this.vertices[ i ] = new Vertex( i );
      }

      int toVertex = 0;
      int weight = 0;

      // for each vertex in the graph read its edges
      for ( int i = 0; i < numberOfVertices - 1; i++ ) {
        st = new StringTokenizer( input.readLine() );
        toVertex = i + 1;

        // While the vertex has more edges
        while ( st.hasMoreTokens() ) {
          weight = Integer.parseInt( st.nextToken() );
          // Create a new Edge
          Edge fromToEdge = new Edge( this.vertices[ i ],
                                 this.vertices[ toVertex ], weight, initValue );
          // If this edge is smaller than maxDistance insert it in both directions
          if ( fromToEdge.getWeight() < maxDistance ) {
            this.vertices[ i ].getEdges().add( fromToEdge  );
            this.vertices[ toVertex ].getEdges().add( fromToEdge  );
            // Insert edge in Graph-objects own list of edges
            this.edges.add( fromToEdge );
          }

          toVertex++;
        }
      }

      // read in the coordinates of the vertices
      while ( !input.readLine().equals( "DISPLAY_DATA_SECTION" ) ){};

      for ( int i = 0; i < numberOfVertices; i++) {
        st = new StringTokenizer( input.readLine() );

        // Skip vertex name
        st.nextToken();

        this.vertices[ i ].setXPos( ( int ) Double.parseDouble( st.nextToken() )
                                                                    * X_SCALE );
        this.vertices[ i ].setYPos( ( int ) Double.parseDouble( st.nextToken() )
                                                                    * Y_SCALE );
      }
      input.close();