abstractgridlayout.java

OpenJGraph是一个开源的Java库

    int     xmedian, ymedian;

    adjacentcount = adjacentVertices.size();
    // Do not do anything if the number of adjacent vertices is less than 2.
    if( adjacentcount < 1 ) return;
    if( adjacentcount == 1 ) {
      iterator = adjacentVertices.iterator();
      VisualVertex  only1adjacentvertex = (VisualVertex) iterator.next();

      this.minimalEdgePlacement( vvertex, only1adjacentvertex, finalplacedvertices, grid );
      return;
    }

    // Now find the median placement of the vertex
    iterator = adjacentVertices.iterator();
    while( iterator.hasNext()){
      point = grid.findVisualVertex( (VisualVertex) iterator.next());
      xtotal += point.x;
      ytotal += point.y;
    }
    xmedian = xtotal / adjacentcount;
    ymedian = ytotal / adjacentcount;
    //System.out.println( "Calculated median at " + xmedian + ", " + ymedian );

    // Check if there is a vertex on the specified median grid point.
    // If there is none, or if it is the visual vertex itself, then set
    // median placement.
    preplacedvertex = grid.getGridPoint( xmedian, ymedian );
    if( preplacedvertex == null || preplacedvertex.equals( vvertex )){
      //System.out.println( "Set median at " + xmedian + ", " + ymedian );
      grid.setGridPoint( xmedian, ymedian, vvertex );
      }
    // If there is another visual vertex in the median grid point,
    // find an alternate median placement.
    else {
      alternatemedian = this.alternateMedianPlacement( vvertex, adjacentVertices, xmedian, ymedian, grid );

      // Use the alternate median grid point.
      if( alternatemedian != null ){
        //System.out.println( "Set alternate median at " + alternatemedian.x + ", " + alternatemedian.y );
        grid.setGridPoint( alternatemedian.x, alternatemedian.y, vvertex );
      }
      // If there is no alternate median placement, then force a swap
      //else {
        //System.out.println( "Swapped median at " + xmedian + ", " + ymedian );
        // Get the current grid point position of the vertex
      //  point = this.grid.findVisualVertex( vvertex );
        // Swap positions
      //  this.grid.setGridPoint( point.x, point.y, this.grid.getGridPoint( xmedian, ymedian ));
      //  this.grid.setGridPoint( xmedian, ymedian, vvertex );
      //}
    }

    // Notify the registered listener that a vertex has been laid out.
    if( listener != null )
      listener.layoutVisualVertex( new GraphLayoutEvent( this.vgraph, vvertex ));
  }

  /**
   * Finds an alternate median position based on the minimal total edge length
   * of the incident edges of the vertex.
   *
   * @param   vvertex   The VisualVertex which will be placed in the median
   * of its adjacent vertices.
   * @param   adjacentVertices    The adjacent vertices of the vertex.
   * @param   preferredXMedian    The original, preferred x median.
   * @param   preferredXMedian    The original, preferred y median.
   */
  private Point alternateMedianPlacement( VisualVertex vvertex, Set adjacentVertices,
    int preferredXMedian, int preferredYMedian, Grid grid ){

    List    alternateGridPoints = new ArrayList( 10 );
    VisualVertex  preplacedvertex;
    int     alternateXMedian, alternateYMedian;
    double  minimalLength = 0.00, alternateLength;

    int     level, n = 0;

    // Iterate through the preferred median point's surrounding to find
    // an alternate median placement by determining the total length of the
    // all incident edges for each alternation placement. The placement
    // with the lowest edge length will be the alternate median placement.

    for( level = 1; level <= 2; ++level ) {
      for( alternateYMedian = preferredYMedian - 1; alternateYMedian <= preferredYMedian + 1; alternateYMedian++ ) {
        if( level == 1 ) n = 0;
        if( level == 2 ) n = Math.abs( alternateYMedian - preferredYMedian ) == 2 ? 1 : 2;
        for( alternateXMedian = preferredXMedian - 1 * (level==1?1:n);
          alternateXMedian <= preferredXMedian + (level==1?1:n);
          alternateXMedian =  alternateXMedian + (level==1?1:2*(level==1?1:n))) {

          // If the grid point is valid (>=0) and there are no vertex in that grid point....
          if( alternateXMedian >= 0 && alternateYMedian >= 0 ) {
            preplacedvertex = grid.getGridPoint( alternateXMedian, alternateYMedian );
            if ( preplacedvertex == null || preplacedvertex.equals( vvertex ) ) {
              // get the length of the edges if the visualvertex was positioned in this grid point,
              alternateLength = this.getIncidentEdgesLength( adjacentVertices, alternateXMedian, alternateYMedian, grid );

              // ... and if this is less than all of previous edge lengths, empty the
              // set of alternate median placement and add this grid point to the set.
              if( alternateLength < minimalLength || alternateGridPoints.isEmpty() ){
                minimalLength = alternateLength;
                alternateGridPoints.clear();
                alternateGridPoints.add( new Point( alternateXMedian, alternateYMedian ));
              }
              // ... or if it is the same as the previous minimal edge length, simply
              // add it to the set of alternate median placement.
              else if( alternateLength == minimalLength || alternateGridPoints.isEmpty() )
                alternateGridPoints.add( new Point( alternateXMedian, alternateYMedian ));
            }
          }
        }
      }
      // Get the first alternate grid point in the set, if any.
      if( !alternateGridPoints.isEmpty() )
        return (Point) alternateGridPoints.get( 0 );
    }

    // Get the first alternate grid point in the set, if any.
    if( !alternateGridPoints.isEmpty() )
      return (Point) alternateGridPoints.get( 0 );
    else
      return null;
  }

  /**
   * Determines the total length of the incident edges of a vertex
   * if it were to be placed on an alternate median position.
   *
   * @param   adjacentVertices    The adjacent vertices of the vertex.
   * @param   alternateXMedian    The alternate x median.
   * @param   alternateYMedian    The alternate y median.
   * @return  The length of all the incident edges of the vertex if it
   * were placed in the specified alternate median position.
   */
  private double getIncidentEdgesLength( Set adjacentVertices, int alternateXMedian, int alternateYMedian, Grid grid ) {
    Iterator  iterator;
    Point     point;
    double    totaledgelength = 0.00;

    iterator = adjacentVertices.iterator();
    while( iterator.hasNext() ){
      point = grid.findVisualVertex( (VisualVertex) iterator.next() );
      totaledgelength += Math.sqrt(
        Math.pow(Math.abs( alternateXMedian - point.x ),2) +
        Math.pow(Math.abs( alternateYMedian - point.y ),2) );
    }
    return totaledgelength;
  }

  /**
   * Positions all vertices in median placement, starting with the
   * first vertex in the graph.
   */
  public void medianPlacement(){
    VisualVertex  vvertex;
    List        finalplacedvertices = new ArrayList();
    int   i, count = this.vgraph.getGraph().getVerticesCount();

    for( i = 0; i < count; i++ ) {
      vvertex = (VisualVertex) this.vgraph.getVisualVertices().get( i );
      this.medianPlacement( vvertex, finalplacedvertices );
      finalplacedvertices.add( vvertex );
    }
  }

  /**
   * Positions the adjacent vertex of a given vertex for minimal edge placement.
   *
   * @param   vvertex     The VisualVertex object whose adjacent vertex will be placed
   *                      as near as possible to it.
   * @param   adjacentVertex  The VisualVertex adjacent to vvertex that will be positioned
   *                          for minimal edge placement.
   * @param   grid        Grid object where the visual vertices are laid out.
   */
  private void minimalEdgePlacement( VisualVertex vvertex, VisualVertex adjacentVertex,
    List finalplaced, Grid grid ) {

    VisualVertex  preplacedVertex;
    Point     point, adjacentVertexpoint, alternatePlacement;
    int       preferredx=0, preferredy=0;

    point = grid.findVisualVertex( vvertex );
    adjacentVertexpoint = grid.findVisualVertex( adjacentVertex );

    // If the adjacent vertex is already in minimal edge placement, then just return.
    if( (Math.abs( point.x - adjacentVertexpoint.x ) == 1 && point.y == adjacentVertexpoint.y) ||
        (Math.abs( point.y - adjacentVertexpoint.y ) == 1 && point.x == adjacentVertexpoint.x)){
        //System.out.println( "   " + adjacentVertex.getVertex() + " was already at minimal position." );
        return;
        }

    // If the adjacent vertex is in its final placement, then reverse the roles of the vertices.
    if( finalplaced.contains( adjacentVertex )) {
      if( Math.abs( point.x - adjacentVertexpoint.x ) == 1 && Math.abs( point.y - adjacentVertexpoint.y ) == 1) {
        //System.out.println( "   " + adjacentVertex.getVertex() + " was already at NEAR minimal position." );
        return;
      }

      if( finalplaced.contains( vvertex )) return;

      //System.out.println( "   Reversing roles with " + adjacentVertex.getVertex()  );
      //System.out.println( "   " + adjacentVertex + " is already in final:" + finalplaced );
      //this.minimalEdgePlacement( adjacentVertex, vvertex, finalplaced, interimfinalplaced, vertexqueue, grid );
      this.minimalEdgePlacement( adjacentVertex, vvertex, finalplaced, grid );
      return;
      }

    // ... find the preferred placement of the adjacent vertex ...
    if( Math.abs( point.x - adjacentVertexpoint.x ) <= Math.abs( point.y - adjacentVertexpoint.y )){
      preferredx = point.x;
      preferredy = point.y > adjacentVertexpoint.y ? point.y - 1 : point.y + 1;
    }

    if( Math.abs( point.x - adjacentVertexpoint.x ) >= Math.abs( point.y - adjacentVertexpoint.y )){
      preferredy = point.y;
      preferredx = point.x > adjacentVertexpoint.x ? point.x - 1 : point.x + 1;
    }

    preplacedVertex = grid.getGridPoint( preferredx, preferredy );
    if( preplacedVertex == null  ){
      //System.out.println( "   Set minimal placement of " + adjacentVertex.getVertex() + ": " + preferredx + "," + preferredy );
      grid.setGridPoint( preferredx, preferredy, adjacentVertex );
      //vertexqueue.add( adjacentVertex );
    }
    //else if ( preplacedVertex != null && !finalplaced.contains( preplacedVertex ) && !interimfinalplaced.contains( preplacedVertex )) {
    else if ( preplacedVertex != null && !finalplaced.contains( preplacedVertex )) {
      Point   origpoint = grid.findVisualVertex( adjacentVertex );

      //System.out.println( "   Swapped " + preplacedVertex.getVertex() + ": " + origpoint.x + "," + origpoint.y );
      grid.setGridPoint( origpoint.x, origpoint.y, preplacedVertex );
      //vertexqueue.add( preplacedVertex );

      //System.out.println( "   Set minimal placement of " + adjacentVertex.getVertex() + ": " + preferredx + "," + preferredy );
      grid.setGridPoint( preferredx, preferredy, adjacentVertex );
      //vertexqueue.add( adjacentVertex );
    }
    else {
      //System.out.println( "   Finding alternate minimal placement because of " + preplacedVertex.getVertex() + " at " + grid.findVisualVertex( preplacedVertex ));
      alternatePlacement = this.alternateMinimalEdgePlacement(
        vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, grid, preferredx, preferredy );
        //vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, interimfinalplaced, grid, preferredx, preferredy );

      alternatePlacement = this.alternateMinimalEdgePlacement(
        vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, grid, preferredx, preferredy,
        new int[] {-1,1,-1,1,0,-1,1}, new int[] {-1,-1,0,0,-2,-2} );
        //vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, interimfinalplaced, grid, preferredx, preferredy );

      if( alternatePlacement == null )
        alternatePlacement = this.alternateMinimalEdgePlacement(
          vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, grid, preferredx, preferredy,
          new int[] {-1,1,-2,2,-2,2,-1,1}, new int[] {1,1,0,0,-2,-2,-3,-3} );

      if( alternatePlacement == null )
        alternatePlacement = this.alternateMinimalEdgePlacement(
          vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, grid, preferredx, preferredy,
          new int[] {-1,1,-2,2,-1,1,-2,2}, new int[] {2,2,2,2,-4,-4,-4,-4} );

      if( alternatePlacement == null )
        alternatePlacement = this.alternateMinimalEdgePlacement(
          vvertex, adjacentVertex, point, adjacentVertexpoint, finalplaced, grid, preferredx, preferredy,
          new int[] {-1,1,-2,2,-3,3,-1,1,-2,2,-3,3}, new int[] {3,3,3,3,3,3,-5,-5,-5,-5,-5,-5} );

      if( alternatePlacement != null ) {
        preplacedVertex = grid.getGridPoint( alternatePlacement.x, alternatePlacement.y );
        if( preplacedVertex != null ) {
          Point   origpoint = grid.findVisualVertex( adjacentVertex );

          //System.out.println( "         Swapping with " + preplacedVertex + " to: " + origpoint );
          grid.setGridPoint( origpoint.x, origpoint.y, preplacedVertex );
          //vertexqueue.add( preplacedVertex );
          }
        grid.setGridPoint( alternatePlacement.x, alternatePlacement.y, adjacentVertex );
        //vertexqueue.add( adjacentVertex );
        }
    }

  }

  /**
   * Finds an alternate minimal edge placement for a specified VisualVertex,
   * testing for each alternate grid point until an alternate position is found
   * or the alternate grid points are exhausted.
   *
   * The process for determining the alternate minimal edge placement is shown
   * by the following diagram below:
   *
   *    3   *P   4      4   P*  3
   *    1    A   2      2   A   1
   *    6    5   7      7   5   6
   *
   * where:
   *    - A is the anchor vertex
   *    - P is the preferred grid point of the adjacent vertex
   *    - 1, 2, 3, 4 ... 7 are the sequence of alternate grid points surrounding
   *      the anchor vertex A to be tested.
   *    - * marks which side of P is the original position of the adjacent vertex
   *      If the adjacent vertex was originally at the left side of the preferred
   *      placement, then use the sequence on the left diagram. Otherwise, use
   *      the sequence on the right diagram.
   *
   * For each alternate grid point, a test is made if there is already a vertex
   * in the alternate grid point. If there is none, that is used as the final
   * placement of the adjacent vertex.
   *
   * However, if there is already a vertex (called preplaced vertex) in the alternate grid point,
   * and it is not the final position of the preplaced vertex, then than grid point
   * is the alternate grid point for the specified vertex. Otherwise,
   * the next alternate grid point ( in the above sequence )
   * is tried until either an alternate grid point is found or all the alternates
   * are exhausted.
   *
   * The above diagram are used if the preferred placement is above the anchor vertex.
   * If the preferred placement is to the right of the anchor vertex, the diagam is rotated as follows:
   *
   *    6   1   3       7   2   4
   *            *
   *    5   A   P       5   A   P
   *                        *
   *    7   2   4       6   1   3
   *
   * Rotate the diagram further if the preferred placement is below or to the left
   * of the anchor vertex.
   *
   * @param   achorVertex     Anchor vertex. This is represented as A in the diagram above.
   * @param   adjacentVertex  The VisualVertex adjacent to anchorVertex. This is the
   *                          VisualVertex object we want to position for minimal edge placement.
   * @param   anchorPoint     Point object representing the position of anchorVertex within
   *                          the Grid object.
   * @param   adjacentPoint   Point object representing the original position of adjacentVertex.
   * @param   finalplaced     List of visual vertices that must no longer be moved from its current
   *                          grid point assingment.
   * @param   interimfinalplaced  List of visual vertices that must not be moved from its current
   *                          grid point assignment only for the duration of the current vertex's iteration.
   * @param   grid            Grid object where the visual vertices are laid out.
   * @param   preferredx      The x-coordinate of the preferred position of the adjacentVertex.
   * @param   preferredy      The y-coordinate of the preferred position of the adjacentVertex.
   */
  private Point alternateMinimalEdgePlacement(
    VisualVertex anchorVertex, VisualVertex adjacentVertex,
    Point anchorPoint, Point adjacentPoint, List finalplaced,
    Grid grid, int preferredx, int preferredy )