// This file is part of the Echidna project// (C) 2002 Forschungszentrum Informatik (FZI) Karlsruhe// Please visit our website at http://echidna.sf.netpackage 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));