sugiyamalayoutalgorithm.java

一个很好实用的工作流OSWORKFLOW开发例子.有着非常优秀的灵活性.

      for(int i = levels.size() - 1; i >= 0; i--)
      {
        movementsCurrentLoop += moveToBarycenter(jgraph, levels, i);
      }

      if(verbose)
      {
        System.out.println("----------------Grid Pos after bottom up"/*#Frozen*/);
        displayGridPositions(levels);
        //displayDownPriorities();
        System.out.println("======================================="/*#Frozen*/);
      }

      this.updateProgress4Movements();
    }

  }

  protected int moveToBarycenter(JGraph jgraph, List levels, int levelIndex)
  {

    // Counter for the movements
    int movements = 0;

    // Get the current level
    List currentLevel = (List)levels.get(levelIndex);
    GraphModel model = jgraph.getModel();

    for(int currentIndexInTheLevel = 0; currentIndexInTheLevel < currentLevel.size(); currentIndexInTheLevel++)
    {

      CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(currentIndexInTheLevel);

      float gridPositionsSum = 0;
      float countNodes = 0;

      VertexView vertexView = sourceWrapper.getVertexView();
      Object vertex = vertexView.getCell();
      int portCount = model.getChildCount(vertex);

      for(int i = 0; i < portCount; i++)
      {
        Object port = model.getChild(vertex, i);

        Iterator edges = model.edges(port);
        while(edges.hasNext())
        {
          Object edge = edges.next();

          // if it is a forward edge follow it
          Object neighborPort = null;
          if(port == model.getSource(edge))
          {
            neighborPort = model.getTarget(edge);
          }
          else
          {
            if(port == model.getTarget(edge))
            {
              neighborPort = model.getSource(edge);
            }
            else
            {
              continue;
            }
          }

          Object neighborVertex = model.getParent(neighborPort);

          VertexView neighborVertexView = (VertexView)jgraph.getGraphLayoutCache().getMapping(neighborVertex, false);
          CellWrapper targetWrapper = (CellWrapper)neighborVertexView.getAttributes().get(SUGIYAMA_CELL_WRAPPER);

          if(targetWrapper == sourceWrapper)
            continue;
          if(targetWrapper == null || targetWrapper.getLevel() == levelIndex)
            continue;

          gridPositionsSum += targetWrapper.getGridPosition();
          countNodes++;
        }
      }

      //----------------------------------------------------------
      // move node to new x coord
      //----------------------------------------------------------

      if(countNodes > 0)
      {
        float tmp = (gridPositionsSum / countNodes);
        int newGridPosition = Math.round(tmp);
        boolean toRight = (newGridPosition > sourceWrapper.getGridPosition());

        boolean moved = true;

        while(newGridPosition != sourceWrapper.getGridPosition() && moved)
        {
          int tmpGridPos = sourceWrapper.getGridPosition();

          moved = move(toRight, currentLevel, currentIndexInTheLevel, sourceWrapper.getPriority());

          if(moved)
            movements++;

          if(verbose)
          {

            System.out.print("try move at Level " + levelIndex + " with index " + currentIndexInTheLevel + " to " + (toRight ? "Right" : "Left") + " CurrentGridPos: " + tmpGridPos + " NewGridPos: " + newGridPosition + " exact: " + NumberFormat.getInstance().format(tmp) + "..."/*#Frozen*/);
            System.out.println(moved ? "success"/*#Frozen*/ : "can't move"/*#Frozen*/);

          }
        }
      }
    }
    return movements;
  }

  /**@param  toRight <tt>true</tt> = try to move the currentWrapper to right; <tt>false</tt> = try to move the currentWrapper to left;
   * @param  currentLevel List which contains the CellWrappers for the current level
   * @param  currentIndexInTheLevel
   * @param  currentPriority
   *
   * @return The free GridPosition or -1 is position is not free.
   */
  protected boolean move(boolean toRight, List currentLevel, int currentIndexInTheLevel, int currentPriority)
  {

    CellWrapper currentWrapper = (CellWrapper)currentLevel.get(currentIndexInTheLevel);

    boolean moved = false;
    int neighborIndexInTheLevel = currentIndexInTheLevel + (toRight ? 1 : -1);
    int newGridPosition = currentWrapper.getGridPosition() + (toRight ? 1 : -1);

    // is the grid position possible?

    if(0 > newGridPosition || newGridPosition >= gridAreaSize)
    {
      return false;
    }

    // if the node is the first or the last we can move
    if(toRight && currentIndexInTheLevel == currentLevel.size() - 1 || !toRight && currentIndexInTheLevel == 0)
    {

      moved = true;

    }
    else
    {
      // else get the neighbor and ask his gridposition
      // if he has the requested new grid position
      // check the priority

      CellWrapper neighborWrapper = (CellWrapper)currentLevel.get(neighborIndexInTheLevel);

      int neighborPriority = neighborWrapper.getPriority();

      if(neighborWrapper.getGridPosition() == newGridPosition)
      {
        if(neighborPriority >= currentPriority)
        {
          return false;
        }
        else
        {
          moved = move(toRight, currentLevel, neighborIndexInTheLevel, currentPriority);
        }
      }
      else
      {
        moved = true;
      }
    }

    if(moved)
    {
      currentWrapper.setGridPosition(newGridPosition);
    }
    return moved;
  }

  /** This Method draws the graph. For the horizontal position
   *  we are using the grid position from each graphcell.
   *  For the vertical position we are using the level position.
   *
   */
  protected void drawGraph(JGraph jgraph, List levels, Point min, Point spacing)
  {
    // paint the graph

    Map viewMap = new HashMap();

    for(int rowCellCount = 0; rowCellCount < levels.size(); rowCellCount++)
    {
      List level = (List)levels.get(rowCellCount);

      for(int colCellCount = 0; colCellCount < level.size(); colCellCount++)
      {
        CellWrapper wrapper = (CellWrapper)level.get(colCellCount);
        VertexView view = wrapper.vertexView;

        // remove the temp objects
        /* While the Algorithm is running we are putting some
         *  attributeNames to the MyGraphCells. This method
         *  cleans this objects from the MyGraphCells.
         *
         */
        view.getAttributes().remove(SUGIYAMA_CELL_WRAPPER);
        view.getAttributes().remove(SUGIYAMA_VISITED);
        wrapper.vertexView = null;

        // get the bounds from the cellView
        Rectangle bounds = (Rectangle)view.getBounds().clone();

        // adjust
        bounds.x = min.x + spacing.x * wrapper.getGridPosition();
        bounds.y = min.y + spacing.y * rowCellCount;

        Object cell = view.getCell();
        Map map = new AttributeMap();
        GraphConstants.setBounds(map, bounds);
        viewMap.put(cell, map);
      }

    }
    jgraph.getGraphLayoutCache().edit(viewMap, null, null, null);
  }

  /** cell wrapper contains all values
   *  for one node
   */
  class CellWrapper implements Comparable
  {

    /** sum value for edge Crosses
     */
    private double edgeCrossesIndicator = 0;
    /** counter for additions to the edgeCrossesIndicator
     */
    private int additions = 0;
    /** the vertical level where the cell wrapper is inserted
     */
    int level = 0;
    /** current position in the grid
     */
    int gridPosition = 0;
    /** priority for movements to the barycenter
     */
    int priority = 0;
    /** reference to the wrapped cell
     */
    VertexView vertexView = null;

    /** creates an instance and memorizes the parameters
     *
     */
    CellWrapper(int level, double edgeCrossesIndicator, VertexView vertexView)
    {
      this.level = level;
      this.edgeCrossesIndicator = edgeCrossesIndicator;
      this.vertexView = vertexView;
      additions++;
    }

    /** returns the wrapped cell
     */
    VertexView getVertexView()
    {
      return vertexView;
    }

    /** resets the indicator for edge crosses to 0
     */
    void resetEdgeCrossesIndicator()
    {
      edgeCrossesIndicator = 0;
      additions = 0;
    }

    /** retruns the average value for the edge crosses indicator
     *
     *  for the wrapped cell
     *
     */

    double getEdgeCrossesIndicator()
    {
      if(additions == 0)
        return 0;
      return edgeCrossesIndicator / additions;
    }

    /** Addes a value to the edge crosses indicator
     *  for the wrapped cell
     *
     */
    void addToEdgeCrossesIndicator(double addValue)
    {
      edgeCrossesIndicator += addValue;
      additions++;
    }

    /** gets the level of the wrapped cell
     */
    int getLevel()
    {
      return level;
    }

    /** gets the grid position for the wrapped cell
     */
    int getGridPosition()
    {
      return gridPosition;
    }

    /** Sets the grid position for the wrapped cell
     */
    void setGridPosition(int pos)
    {
      this.gridPosition = pos;
    }

    /** increments the the priority of this cell wrapper.
     *
     *  The priority was used by moving the cell to its
     *  barycenter.
     *
     */

    void incrementPriority()
    {
      priority++;
    }

    /** returns the priority of this cell wrapper.
     *
     *  The priority was used by moving the cell to its
     *  barycenter.
     */
    int getPriority()
    {
      return priority;
    }

    /**
     * @see java.lang.Comparable#compareTo(Object)
     */
    public int compareTo(Object compare)
    {
      if(((CellWrapper)compare).getEdgeCrossesIndicator() == this.getEdgeCrossesIndicator())
        return 0;

      double compareValue = (((CellWrapper)compare).getEdgeCrossesIndicator() - this.getEdgeCrossesIndicator());

      return (int)(compareValue * 1000);

    }
  }
}