sugiyamalayoutalgorithm.java

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

// This file is part of the Echidna project
// (C) 2002 Forschungszentrum Informatik (FZI) Karlsruhe
// Please visit our website at http://echidna.sf.net
package com.opensymphony.workflow.designer.layout;

import javax.swing.*;

import org.jgraph.JGraph;
import org.jgraph.graph.*;

import java.awt.Point;
import java.awt.Rectangle;
import java.text.NumberFormat;
import java.util.*;

/**
 * Arranges the nodes with the Sugiyama Layout Algorithm.<br>
 *
 * <a href="http://plg.uwaterloo.ca/~itbowman/CS746G/Notes/Sugiyama1981_MVU/">
 *  Link to the algorithm</a>
 *
 *<br>
 *<br>
 * @author Sven Luzar<br>
 * @version 1.0 init
 */
public class SugiyamaLayoutAlgorithm implements LayoutAlgorithm
{

  /** Field for debug output
   */
  protected final boolean verbose = false;

  /** Const to add Attributes at the Nodes
   *
   */
  public static final String SUGIYAMA_VISITED = "SugiyamaVisited"/*#Frozen*/;

  /** Const to add the Cell Wrapper to the Nodes
   */
  public static final String SUGIYAMA_CELL_WRAPPER = "SugiyamaCellWrapper"/*#Frozen*/;

  /** represents the size of the grid in horizontal grid elements
   *
   */
  protected int gridAreaSize = Integer.MIN_VALUE;

  /** A List with Integer Objects. The List contains the
   *  history of movements per loop
   *  It was needed for the progress dialog
   */
  List movements = null;
  /** Represents the movements in the current loop.
   *  It was needed for the progress dialog
   */
  int movementsCurrentLoop = -1;
  /** Represents the maximum of movements in the current loop.
   *  It was needed for the progress dialog
   */
  int movementsMax = Integer.MIN_VALUE;
  /** Represents the current loop number
   *  It was needed for the progress dialog
   */
  int iteration = 0;
  public static final String KEY_HORIZONTAL_SPACING = "HorizontalSpacing";
  public static final String KEY_VERTICAL_SPACING = "VerticalSpacing";

  /**
   * Implementation.
   *
   * First of all the Algorithm searches the roots from the
   * Graph. Starting from this roots the Algorithm creates
   * levels and stores them in the member <code>levels</code>.
   * The Member levels contains List Objects and the List per level
   * contains Cell Wrapper Objects. After that the Algorithm
   * tries to solve the edge crosses from level to level and
   * goes top down and bottom up. After minimization of the
   * edge crosses the algorithm moves each node to its
   * bary center. Last but not Least the method draws the Graph.
   *
   * @see LayoutAlgorithm
   *
   */
  public void perform(JGraph jgraph, boolean applyToAll, Properties configuration)
  {

    Object[] selectedCells = (applyToAll ? jgraph.getRoots() : jgraph.getSelectionCells());
    CellView[] selectedCellViews = jgraph.getGraphLayoutCache().getMapping(selectedCells);

    Point spacing = new Point();
    /*  The Algorithm distributes the nodes on a grid.
     *  For this grid you can configure the horizontal spacing.
     *  This field specifies the configured value
     *
     */
    spacing.x = Integer.parseInt(configuration.getProperty(KEY_HORIZONTAL_SPACING));

    /*  The Algorithm distributes the nodes on a grid.
     *  For this grid you can configure the vertical spacing.
     *  This field specifies the configured value
     *
     */

    spacing.y = Integer.parseInt(configuration.getProperty(KEY_VERTICAL_SPACING));

    // search all roots
    List roots = searchRoots(jgraph, selectedCellViews);

    // return if no root found
    if(roots.size() == 0)
      return;

    // create levels
    List levels = fillLevels(jgraph, selectedCellViews, roots);

    // solves the edge crosses
    solveEdgeCrosses(jgraph, levels);

    // move all nodes into the barycenter
    moveToBarycenter(jgraph, selectedCellViews, levels);

    Point min = findMinimumAndSpacing(selectedCellViews, spacing);

    // draw the graph in the window
    drawGraph(jgraph, levels, min, spacing);

    // clean temp values from the nodes / cells
    // the clean up was made in drawGraph
    //cleanUp(selectedCellViews);

  }

  /** Debugdisplay for the edge crosses indicators on the System out
   */
  protected void displayEdgeCrossesValues(List levels)
  {
    System.out.println("----------------Edge Crosses Indicator Values"/*#Frozen*/);

    for(int i = 0; i < levels.size() - 1; i++)
    {
      // Get the current level
      List currentLevel = (List)levels.get(i);
      System.out.print("Level (" + i + "):"/*#Frozen*/);
      for(int j = 0; j < currentLevel.size(); j++)
      {
        CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);

        System.out.print(NumberFormat.getNumberInstance().format(sourceWrapper.getEdgeCrossesIndicator()) + " - "/*#Frozen*/);
      }
      System.out.println();
    }
  }

  /** Debugdisplay for the grid positions on the System out
   */
  protected void displayGridPositions(List levels)
  {

    System.out.println("----------------GridPositions"/*#Frozen*/);

    for(int i = 0; i < levels.size() - 1; i++)
    {
      // Get the current level
      List currentLevel = (List)levels.get(i);
      System.out.print("Level (" + i + "):"/*#Frozen*/);
      for(int j = 0; j < currentLevel.size(); j++)
      {
        CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
        System.out.print(NumberFormat.getNumberInstance().format(sourceWrapper.getGridPosition()) + " - "/*#Frozen*/);
      }
      System.out.println();
    }
  }

  /** Debugdisplay for the priorities on the System out
   */
  protected void displayPriorities(List levels)
  {

    System.out.println("----------------down Priorities"/*#Frozen*/);

    for(int i = 0; i < levels.size() - 1; i++)
    {
      // Get the current level
      List currentLevel = (List)levels.get(i);
      System.out.print("Level (" + i + "):"/*#Frozen*/);
      for(int j = 0; j < currentLevel.size(); j++)
      {
        CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
        System.out.print(sourceWrapper.getPriority() + /*" (" +
                           sourceWrapper.nearestDownNeighborLevel + ") " +*/
                         " - "/*#Frozen*/);
      }
      System.out.println();
    }
  }

  /** Searches all Roots for the current Graph
   *  First the method marks any Node as not visited.
   *  Than calls searchRoots(MyGraphCell) for each
   *  not visited Cell.
   *  The Roots are stored in the List named roots
   *
   * 	@return returns a List with the roots
   *  @see #searchRoots(JGraph, CellView[])
   */
  protected List searchRoots(JGraph jgraph, CellView[] selectedCellViews)
  {

    // get all cells and relations
    List vertexViews = new ArrayList(selectedCellViews.length);
    List roots = new ArrayList();

    // first: mark all as not visited
    // O(allCells&Edges)
    for(int i = 0; i < selectedCellViews.length; i++)
    {
      if(selectedCellViews[i] instanceof VertexView)
      {
        VertexView vertexView = (VertexView)selectedCellViews[i];
        vertexView.getAttributes().remove(SUGIYAMA_VISITED);
        vertexViews.add(selectedCellViews[i]);
      }
    }

    // O(graphCells)
    for(int i = 0; i < vertexViews.size(); i++)
    {
      VertexView vertexView = (VertexView)vertexViews.get(i);
      if(vertexView.getAttributes().get(SUGIYAMA_VISITED) == null)
      {
        searchRoots(jgraph, vertexView, roots);
      }
    }

    // Error Msg if the graph has no roots
    if(roots.size() == 0)
    {
      JOptionPane.showMessageDialog(null, "The Graph is not a DAG. Can't use Sugiyama Algorithm!"/*#Finished:Original="The Graph is not a DAG. Can't use Sugiyama Algorithm!"*/, null, JOptionPane.ERROR_MESSAGE);
    }
    return roots;
  }

  /** Searches Roots for the current Cell.
   *
   *  Therefore he looks at all Ports from the Cell.
   *  At the Ports he looks for Edges.
   *  At the Edges he looks for the Target.
   *  If the Ports of the current Cell contains the target ReViewNodePort
   *  he follows the edge to the source and looks at the
   *  Cell for this source.
   *
   */
  protected void searchRoots(JGraph jgraph, VertexView vertexViewToInspect, List roots)
  {
    // the node already visited
    if(vertexViewToInspect.getAttributes().get(SUGIYAMA_VISITED) != null)
    {
      return;
    }

    // mark as visited for cycle tests
    vertexViewToInspect.getAttributes().put(SUGIYAMA_VISITED, new Boolean(true));

    GraphModel model = jgraph.getModel();

    // get all Ports and search the relations at the ports
    //List vertexPortViewList = new ArrayList() ;

    Object vertex = vertexViewToInspect.getCell();

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

      // Test all relations for where
      // the current node is a target node
      // for roots

      boolean isRoot = true;
      Iterator itrEdges = model.edges(port);
      while(itrEdges.hasNext())
      {
        Object edge = itrEdges.next();

        // if the current node is a target node
        // get the source node and test
        // the source node for roots

        if(model.getTarget(edge) == port)
        {
          Object sourcePort = model.getSource(edge);

          Object sourceVertex = model.getParent(sourcePort);

          CellView sourceVertexView = jgraph.getGraphLayoutCache().getMapping(sourceVertex, false);
          if(sourceVertexView instanceof VertexView)
          {
            searchRoots(jgraph, (VertexView)sourceVertexView, roots);
            isRoot = false;
          }
        }
      }
      // The current node is never a Target Node
      // -> The current node is a root node
      if(isRoot)
      {
        roots.add(vertexViewToInspect);
      }
    }
  }

  /** Method fills the levels and stores them in the member levels.

   *  Each level was represended by a List with Cell Wrapper objects.
   *  These Lists are the elements in the <code>levels</code> List.
   *
   */
  protected List fillLevels(JGraph jgraph, CellView[] selectedCellViews, List rootVertexViews)
  {
    List levels = new ArrayList();

    // mark as not visited
    // O(allCells)
    for(int i = 0; i < selectedCellViews.length; i++)
    {
      CellView cellView = selectedCellViews[i];
      cellView.getAttributes().remove(SUGIYAMA_VISITED);
    }

    Iterator roots = rootVertexViews.iterator();
    while(roots.hasNext())
    {
      VertexView vertexView = (VertexView)roots.next();
      fillLevels(jgraph, levels, 0, vertexView);
    }

    return levels;

  }

  /** Fills the List for the specified level with a wrapper
   *  for the MyGraphCell. After that the method called for
   *  each neighbor graph cell.
   *
   *  @param level        The level for the graphCell
   */
  protected void fillLevels(JGraph jgraph, List levels, int level, VertexView vertexView)
  {
    // be sure that a List container exists for the current level
    if(levels.size() == level)
      levels.add(level, new ArrayList());

    // if the cell already visited return
    if(vertexView.getAttributes().get(SUGIYAMA_VISITED) != null)
    {
      return;
    }

    // mark as visited for cycle tests
    vertexView.getAttributes().put(SUGIYAMA_VISITED, new Boolean(true));