graph.java

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

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

  /**
   * This method returns the number of vertices in the graph
   *
   * @return the number of vertices in the graph
   */
  public int getNumberOfVertices(){
    return vertices.length;
  }

  /**
   * This method returns the number of edges in the graph
   *
   * @return the number of edges in the graph
   */
  public int getNumberOfEdges(){
    return edges.size();
  }

  /**
   * This method returns a <code>List</code> containing all the outgoing edges
   * from a given vertex.
   *
   * @param fromVertex the vertex containing the edges
   *
   * @return a <code>List</code> containing all the outgoing edges from the
   * vertex
   */
  public List getOutgoingEdges( Vertex fromVertex ) {
    return fromVertex.getEdges();
  }

  /**
   * This method returns a <code>List</code> containing all the edges in the
   * graph
   *
   * @return a <code>List</code> containing all the edges in the graph
   */
  public List getAllEdges() {
    return edges;
  }

  /**
   * This method return the vertex having the index <code>u</code>
   *
   * @param u the index of the vertex
   *
   * @return the vertex having the index <code>u</code>
   */
  public Vertex getVertex( int u ) {
    return vertices[ u ];
  }

  /**
   * This method return all the vertices in the graph
   *
   * @return all the vertices in the graph
   */
  public Vertex[] getAllVertices() {
    return vertices;
  }

  /**
   * drawGraph draws a jpg-file (in the file <code>outputFile</code>) which
   * represents the vertices and the edges (with weights) given as argument.
   *
   * @param outputFile the location of the file
   * @param edges a <code>List</code> containing all the edges to draw
   * @param shortDescription a short description of the graph
   * @param doubleEdges does this graph have double edges
   * (that is two edges pr. nodepair)
   */
  public void drawGraph( String outputFile, List edges, String shortDescription,
                                                         boolean doubleEdges ) {
    drawGraph( outputFile, shortDescription, false, 100,
               "weight", false, true, edges, doubleEdges );
  }

  /**
   * drawGraph draws a jpg-file (in the file <code>outputFile</code>) which
   * represents the vertices and the edges with the chosen field given as
   * argument. This method calls <code>
   * drawGraph(String, String, boolean, int, String, boolean, boolean, List)
   * </code> by filling out the missing arguments.
   *
   * @param outputFile the location of the file
   * @param shortDescription a short description of the graph
   * @param normalize decides if the values should be normalized or not
   * @param edgeLabelField the name of the field on the edges
   * @param doubleEdges does this graph have double edges (that is two edges
   * pr. nodepair)
   */
  public void drawGraph( String outputFile, String shortDescription,
               boolean normalize, String edgeLabelField, boolean doubleEdges ) {
    drawGraph( outputFile, shortDescription, normalize, SHOW_PERCENT_DEFAULT,
                               edgeLabelField, false, true, null, doubleEdges );
  }

  /**
   * drawGraph draws a jpg-file (in the file <code>outputFile</code>) which
   * represents the vertices and the edges with the chosen field given as
   * argument. The values can be normalized or not and only the xx percent of
   * the top or bottom can be shown.
   *
   * This method calls <code>
   * drawGraph(String, String, boolean, int, String, boolean, boolean, List)
   * </code> by filling out the missing arguments.
   *
   * @param outputFile the location of the file
   * @param shortDescription a short description of the graph
   * @param normalize decides if the values should be normalized or not
   * @param selectPercent the percentage of edges to show
   * @param edgeLabelField the name of the field on the edges
   * @param showEdgesInColor decides if the edges should be shown in color
   * @param showTopPercent decides if the top percent should be shown or the
   * bottom percent
   * @param doubleEdges does this graph have double edges (that is two edges
   * pr. nodepair)
   */
  public void drawGraph( String outputFile, String shortDescription,
       boolean normalize, int selectPercent, String edgeLabelField,
       boolean showEdgesInColor, boolean showTopPercent, boolean doubleEdges ) {
    drawGraph( outputFile, shortDescription, normalize, selectPercent,
          edgeLabelField, showEdgesInColor, showTopPercent, null, doubleEdges );
  }

  /**
   * drawGraph draws a jpg-file (in the file <code>outputFile</code>) which
   * represents the vertices and the edges with the chosen field given as
   * argument. The values can be normalized or not and only the xx percent of
   * the top or bottom can be shown. This method is the main drawing method,
   * which all the other drawGraph-methods call.
   *
   * @param outputFile the location of the file
   * @param shortDescription a short description of the graph
   * @param normalize decides if the values should be normalized or not
   * @param selectPercent the percentage of edges to show
   * @param edgeLabelField the name of the field on the edges
   * @param showEdgesInColor decides if the edges should be shown in color
   * @param showTopPercent decides if the top percent should be shown or the
   * bottom percent
   * @param listOfEdges a <code>List</code> containing the edges to be shown
   * @param doubleEdges does this graph have double edges (that is two edges
   * pr. nodepair)
   */
  private void drawGraph( String outputFile, String shortDescription,
          boolean normalize, int selectPercent, String edgeLabelField,
          boolean showEdgesInColor, boolean showTopPercent, List listOfEdges,
          boolean doubleEdges ) {
    boolean simpleGraph = true;
    if ( listOfEdges == null ) {
      simpleGraph = false;
    }

    att.grappa.Graph dotGraph = new att.grappa.Graph( name, false, false );

    String fileLabel = "File : " + outputFile;

    // build a graph-label according to the type of graph
    String graphLabel = "Graph : " + this.name + "  |  Description : " +
                                                               shortDescription;
    if ( !simpleGraph ) {
      graphLabel += ( normalize ? "  (Values are normalized (1-100))"
                                : "  (Values not normalized)" );
    }
    graphLabel += "  |  Values on edges : " + edgeLabelField;
    if ( !simpleGraph ) {
      graphLabel += ( showTopPercent ? "  |  Top " : "  |  Bottom " )
                                     + selectPercent + "% shown";
    }

    dotGraph.setAttribute( GrappaConstants.LABEL_ATTR, graphLabel );
    Node[] dotVertices = new Node[ getNumberOfVertices() ];

    // find min and max x- and y-vals
    double minX = vertices[ 0 ].getXPos();
    double minY = vertices[ 0 ].getYPos();
    double maxX = vertices[ 0 ].getXPos();
    double maxY = vertices[ 0 ].getYPos();
    for ( int i = 1; i < getNumberOfVertices(); i++ ) {
      minX = Math.min( minX, vertices[ i ].getXPos() );
      minY = Math.min( minY, vertices[ i ].getYPos() );
      maxX = Math.max( maxX, vertices[ i ].getXPos() );
      maxY = Math.max( maxY, vertices[ i ].getYPos() );
    }

    // make all vertices scale all position-attributes according to picture-dim of
    // constants PICTURE_DIMENSION (normalized by and positioned according to above
    // found min and max-vals)
    for ( int i = 0; i < getNumberOfVertices(); i++ ) {
      dotVertices[ i ] = new Node( dotGraph, new Integer( i ).toString() );
      dotVertices[ i ].setAttribute( GrappaConstants.POS_ATTR,
          new GrappaPoint(
           PICTURE_SCALE.getWidth() *
           ( vertices[ i ].getXPos() - minX ) / maxX,
         ( PICTURE_SCALE.getHeight() ) *
           ( vertices[ i ].getYPos() - minY ) / maxY ) );
      // Set style attributes
      dotVertices[ i ].setAttribute( GrappaConstants.WIDTH_ATTR, NODE_RADIUS );
      dotVertices[ i ].setAttribute( GrappaConstants.HEIGHT_ATTR, NODE_RADIUS );
      dotVertices[ i ].setAttribute( GrappaConstants.COLOR_ATTR, NODE_COLOR );
      dotVertices[ i ].setAttribute( GrappaConstants.FONTCOLOR_ATTR,
                                                               NODE_FONTCOLOR );
      dotVertices[ i ].setAttribute( GrappaConstants.FONTSIZE_ATTR,
                                                                NODE_FONTSIZE );
      dotGraph.addNode( dotVertices[ i ] );
    }

    // Temporary Edge-ref that is used multiple times below
    Edge tmpEdge;

    // Initialize the edges-list (that is to be drawn)
    List edges = listOfEdges;

    if ( !simpleGraph ) {
      edges = getAllEdges();
      if ( normalize ) {
        // Find the max-value of the field among all edges
        double maxVal = 0;
          for ( int i = 0; i < edges.size(); i++ ) {
          double fldVal = ( ( Edge ) edges.get( i ) ).getAttribute( edgeLabelField );
          if ( fldVal > maxVal ) {
            maxVal = fldVal;
          }
        }

        // Normalize all edges' field value according to the max value found
        for ( int i = 0; i < edges.size(); i++ ) {
          tmpEdge = ( ( Edge ) edges.get( i ) );
          tmpEdge.setTempVal( tmpEdge.getAttribute( edgeLabelField ) /
                                                                      maxVal * 100 );
        }

        // after normalization the values to be output are held in the
        // tempVal-field of the Edge-objects
        edgeLabelField = "tempVal";
      }

      // Sort the edges to be able to select only the top/bottom X %
      // (given by param showTopPercent)
      Collections.sort( edges, Edge.getComparator( edgeLabelField,
                                                             showTopPercent ) );
    }

    // Draw the (selectPercent %) edges of all edges on the Graph
    for ( int i = 0; i < ( selectPercent / 100.0 ) * edges.size(); i++ ) {
      tmpEdge = ( Edge ) edges.get( i );
      att.grappa.Edge tmpGraphEdge = new att.grappa.Edge(
          dotGraph, dotVertices[ tmpEdge.getVertex( 1 ).getIndex() ],
                    dotVertices[ tmpEdge.getVertex( 2 ).getIndex() ] );

      int upOrDown = 0;
      if ( doubleEdges ){
        // calculate whether "up or down" pointing edge
        upOrDown = ( tmpEdge.getVertex( 1 ).getIndex() >
                                   tmpEdge.getVertex( 2 ).getIndex() ? 1 : -1 );
      }

      if ( showEdgesInColor && normalize ){
        // set width and color according to the value of the field given in
        // edgeLabelField
        int scaleVal = (int) tmpEdge.getAttribute( edgeLabelField );

        tmpGraphEdge.setAttribute( GrappaConstants.COLOR_ATTR,
                             new Color( 50 + scaleVal * 2, scaleVal, scaleVal ) );

        String widthVal = Integer.toString( 1 + scaleVal / 7 );

        GrappaStyle style = new GrappaStyle( GrappaConstants.EDGE,
                                                 "linewidth(" + widthVal + ")" );
        tmpGraphEdge.setAttribute( GrappaConstants.STYLE_ATTR, style );
      }
      // else print the value of the field given in edgeLabelField on edges with
      // appropriate colors
      else {
      StringBuffer label = new StringBuffer( "" );
      if ( doubleEdges ){
        label.append( "" + tmpEdge.getVertex( 1 ).getIndex() );
        label.append( " -> " + tmpEdge.getVertex( 2 ).getIndex() + " : ");
      }
      label.append( numberFormat.format( tmpEdge.getAttribute( edgeLabelField ) ) );

        tmpGraphEdge.setAttribute( GrappaConstants.LABEL_ATTR, label.toString() );
        tmpGraphEdge.setAttribute( GrappaConstants.LP_ATTR, new GrappaPoint(
            ( tmpGraphEdge.getHead().getCenterPoint().getX() ) / 2 +
            ( tmpGraphEdge.getTail().getCenterPoint().getX() ) / 2 +
                                               DOUBLE_EDGES_X_CORRECT * upOrDown
        ,
            ( tmpGraphEdge.getHead().getCenterPoint().getY() ) / 2 +
            ( tmpGraphEdge.getTail().getCenterPoint().getY() ) / 2 +
                                               DOUBLE_EDGES_Y_CORRECT * upOrDown
        ) );

        // Set style attributes
        tmpGraphEdge.setAttribute( GrappaConstants.COLOR_ATTR, EDGE_COLOR );
        tmpGraphEdge.setAttribute( GrappaConstants.FONTCOLOR_ATTR,
                                                               EDGE_FONTCOLOR );
        tmpGraphEdge.setAttribute( GrappaConstants.FONTSIZE_ATTR,
                                                                EDGE_FONTSIZE );
      }

      tmpGraphEdge.printAllAttributes = true;
      tmpGraphEdge.printDefaultAttributes = true;

      dotGraph.addEdge( tmpGraphEdge );
    }

    // generate jpeg-image
    JpgEncodeGraph tmp = new JpgEncodeGraph( dotGraph, outputFile, false );
  }
}