0001: // This file is part of the Echidna project
0002: // (C) 2002 Forschungszentrum Informatik (FZI) Karlsruhe
0003: // Please visit our website at http://echidna.sf.net
0004: package com.opensymphony.workflow.designer.layout;
0005:
0006: import javax.swing.*;
0007:
0008: import org.jgraph.JGraph;
0009: import org.jgraph.graph.*;
0010:
0011: import java.awt.Point;
0012: import java.awt.Rectangle;
0013: import java.text.NumberFormat;
0014: import java.util.*;
0015:
0016: /**
0017: * Arranges the nodes with the Sugiyama Layout Algorithm.<br>
0018: *
0019: * <a href="http://plg.uwaterloo.ca/~itbowman/CS746G/Notes/Sugiyama1981_MVU/">
0020: * Link to the algorithm</a>
0021: *
0022: *<br>
0023: *<br>
0024: * @author Sven Luzar<br>
0025: * @version 1.0 init
0026: */
0027: public class SugiyamaLayoutAlgorithm implements LayoutAlgorithm {
0028:
0029: /** Field for debug output
0030: */
0031: protected final boolean verbose = false;
0032:
0033: /** Const to add Attributes at the Nodes
0034: *
0035: */
0036: public static final String SUGIYAMA_VISITED = "SugiyamaVisited"/*#Frozen*/;
0037:
0038: /** Const to add the Cell Wrapper to the Nodes
0039: */
0040: public static final String SUGIYAMA_CELL_WRAPPER = "SugiyamaCellWrapper"/*#Frozen*/;
0041:
0042: /** represents the size of the grid in horizontal grid elements
0043: *
0044: */
0045: protected int gridAreaSize = Integer.MIN_VALUE;
0046:
0047: /** A List with Integer Objects. The List contains the
0048: * history of movements per loop
0049: * It was needed for the progress dialog
0050: */
0051: List movements = null;
0052: /** Represents the movements in the current loop.
0053: * It was needed for the progress dialog
0054: */
0055: int movementsCurrentLoop = -1;
0056: /** Represents the maximum of movements in the current loop.
0057: * It was needed for the progress dialog
0058: */
0059: int movementsMax = Integer.MIN_VALUE;
0060: /** Represents the current loop number
0061: * It was needed for the progress dialog
0062: */
0063: int iteration = 0;
0064: public static final String KEY_HORIZONTAL_SPACING = "HorizontalSpacing";
0065: public static final String KEY_VERTICAL_SPACING = "VerticalSpacing";
0066:
0067: /**
0068: * Implementation.
0069: *
0070: * First of all the Algorithm searches the roots from the
0071: * Graph. Starting from this roots the Algorithm creates
0072: * levels and stores them in the member <code>levels</code>.
0073: * The Member levels contains List Objects and the List per level
0074: * contains Cell Wrapper Objects. After that the Algorithm
0075: * tries to solve the edge crosses from level to level and
0076: * goes top down and bottom up. After minimization of the
0077: * edge crosses the algorithm moves each node to its
0078: * bary center. Last but not Least the method draws the Graph.
0079: *
0080: * @see LayoutAlgorithm
0081: *
0082: */
0083: public void perform(JGraph jgraph, boolean applyToAll,
0084: Properties configuration) {
0085:
0086: Object[] selectedCells = (applyToAll ? jgraph.getRoots()
0087: : jgraph.getSelectionCells());
0088: CellView[] selectedCellViews = jgraph.getGraphLayoutCache()
0089: .getMapping(selectedCells);
0090:
0091: Point spacing = new Point();
0092: /* The Algorithm distributes the nodes on a grid.
0093: * For this grid you can configure the horizontal spacing.
0094: * This field specifies the configured value
0095: *
0096: */
0097: spacing.x = Integer.parseInt(configuration
0098: .getProperty(KEY_HORIZONTAL_SPACING));
0099:
0100: /* The Algorithm distributes the nodes on a grid.
0101: * For this grid you can configure the vertical spacing.
0102: * This field specifies the configured value
0103: *
0104: */
0105:
0106: spacing.y = Integer.parseInt(configuration
0107: .getProperty(KEY_VERTICAL_SPACING));
0108:
0109: // search all roots
0110: List roots = searchRoots(jgraph, selectedCellViews);
0111:
0112: // return if no root found
0113: if (roots.size() == 0)
0114: return;
0115:
0116: // create levels
0117: List levels = fillLevels(jgraph, selectedCellViews, roots);
0118:
0119: // solves the edge crosses
0120: solveEdgeCrosses(jgraph, levels);
0121:
0122: // move all nodes into the barycenter
0123: moveToBarycenter(jgraph, selectedCellViews, levels);
0124:
0125: Point min = findMinimumAndSpacing(selectedCellViews, spacing);
0126:
0127: // draw the graph in the window
0128: drawGraph(jgraph, levels, min, spacing);
0129:
0130: // clean temp values from the nodes / cells
0131: // the clean up was made in drawGraph
0132: //cleanUp(selectedCellViews);
0133:
0134: }
0135:
0136: /** Debugdisplay for the edge crosses indicators on the System out
0137: */
0138: protected void displayEdgeCrossesValues(List levels) {
0139: System.out
0140: .println("----------------Edge Crosses Indicator Values"/*#Frozen*/);
0141:
0142: for (int i = 0; i < levels.size() - 1; i++) {
0143: // Get the current level
0144: List currentLevel = (List) levels.get(i);
0145: System.out.print("Level (" + i + "):"/*#Frozen*/);
0146: for (int j = 0; j < currentLevel.size(); j++) {
0147: CellWrapper sourceWrapper = (CellWrapper) currentLevel
0148: .get(j);
0149:
0150: System.out
0151: .print(NumberFormat
0152: .getNumberInstance()
0153: .format(
0154: sourceWrapper
0155: .getEdgeCrossesIndicator())
0156: + " - "/*#Frozen*/);
0157: }
0158: System.out.println();
0159: }
0160: }
0161:
0162: /** Debugdisplay for the grid positions on the System out
0163: */
0164: protected void displayGridPositions(List levels) {
0165:
0166: System.out.println("----------------GridPositions"/*#Frozen*/);
0167:
0168: for (int i = 0; i < levels.size() - 1; i++) {
0169: // Get the current level
0170: List currentLevel = (List) levels.get(i);
0171: System.out.print("Level (" + i + "):"/*#Frozen*/);
0172: for (int j = 0; j < currentLevel.size(); j++) {
0173: CellWrapper sourceWrapper = (CellWrapper) currentLevel
0174: .get(j);
0175: System.out.print(NumberFormat.getNumberInstance()
0176: .format(sourceWrapper.getGridPosition())
0177: + " - "/*#Frozen*/);
0178: }
0179: System.out.println();
0180: }
0181: }
0182:
0183: /** Debugdisplay for the priorities on the System out
0184: */
0185: protected void displayPriorities(List levels) {
0186:
0187: System.out
0188: .println("----------------down Priorities"/*#Frozen*/);
0189:
0190: for (int i = 0; i < levels.size() - 1; i++) {
0191: // Get the current level
0192: List currentLevel = (List) levels.get(i);
0193: System.out.print("Level (" + i + "):"/*#Frozen*/);
0194: for (int j = 0; j < currentLevel.size(); j++) {
0195: CellWrapper sourceWrapper = (CellWrapper) currentLevel
0196: .get(j);
0197: System.out.print(sourceWrapper.getPriority() + /*" (" +
0198: sourceWrapper.nearestDownNeighborLevel + ") " +*/
0199: " - "/*#Frozen*/);
0200: }
0201: System.out.println();
0202: }
0203: }
0204:
0205: /** Searches all Roots for the current Graph
0206: * First the method marks any Node as not visited.
0207: * Than calls searchRoots(MyGraphCell) for each
0208: * not visited Cell.
0209: * The Roots are stored in the List named roots
0210: *
0211: * @return returns a List with the roots
0212: * @see #searchRoots(JGraph, CellView[])
0213: */
0214: protected List searchRoots(JGraph jgraph,
0215: CellView[] selectedCellViews) {
0216:
0217: // get all cells and relations
0218: List vertexViews = new ArrayList(selectedCellViews.length);
0219: List roots = new ArrayList();
0220:
0221: // first: mark all as not visited
0222: // O(allCells&Edges)
0223: for (int i = 0; i < selectedCellViews.length; i++) {
0224: if (selectedCellViews[i] instanceof VertexView) {
0225: VertexView vertexView = (VertexView) selectedCellViews[i];
0226: vertexView.getAttributes().remove(SUGIYAMA_VISITED);
0227: vertexViews.add(selectedCellViews[i]);
0228: }
0229: }
0230:
0231: // O(graphCells)
0232: for (int i = 0; i < vertexViews.size(); i++) {
0233: VertexView vertexView = (VertexView) vertexViews.get(i);
0234: if (vertexView.getAttributes().get(SUGIYAMA_VISITED) == null) {
0235: searchRoots(jgraph, vertexView, roots);
0236: }
0237: }
0238:
0239: // Error Msg if the graph has no roots
0240: if (roots.size() == 0) {
0241: JOptionPane
0242: .showMessageDialog(
0243: null,
0244: "The Graph is not a DAG. Can't use Sugiyama Algorithm!"/*#Finished:Original="The Graph is not a DAG. Can't use Sugiyama Algorithm!"*/,
0245: null, JOptionPane.ERROR_MESSAGE);
0246: }
0247: return roots;
0248: }
0249:
0250: /** Searches Roots for the current Cell.
0251: *
0252: * Therefore he looks at all Ports from the Cell.
0253: * At the Ports he looks for Edges.
0254: * At the Edges he looks for the Target.
0255: * If the Ports of the current Cell contains the target ReViewNodePort
0256: * he follows the edge to the source and looks at the
0257: * Cell for this source.
0258: *
0259: */
0260: protected void searchRoots(JGraph jgraph,
0261: VertexView vertexViewToInspect, List roots) {
0262: // the node already visited
0263: if (vertexViewToInspect.getAttributes().get(SUGIYAMA_VISITED) != null) {
0264: return;
0265: }
0266:
0267: // mark as visited for cycle tests
0268: vertexViewToInspect.getAttributes().put(SUGIYAMA_VISITED,
0269: new Boolean(true));
0270:
0271: GraphModel model = jgraph.getModel();
0272:
0273: // get all Ports and search the relations at the ports
0274: //List vertexPortViewList = new ArrayList() ;
0275:
0276: Object vertex = vertexViewToInspect.getCell();
0277:
0278: int portCount = model.getChildCount(vertex);
0279: for (int j = 0; j < portCount; j++) {
0280: Object port = model.getChild(vertex, j);
0281:
0282: // Test all relations for where
0283: // the current node is a target node
0284: // for roots
0285:
0286: boolean isRoot = true;
0287: Iterator itrEdges = model.edges(port);
0288: while (itrEdges.hasNext()) {
0289: Object edge = itrEdges.next();
0290:
0291: // if the current node is a target node
0292: // get the source node and test
0293: // the source node for roots
0294:
0295: if (model.getTarget(edge) == port) {
0296: Object sourcePort = model.getSource(edge);
0297:
0298: Object sourceVertex = model.getParent(sourcePort);
0299:
0300: CellView sourceVertexView = jgraph
0301: .getGraphLayoutCache().getMapping(
0302: sourceVertex, false);
0303: if (sourceVertexView instanceof VertexView) {
0304: searchRoots(jgraph,
0305: (VertexView) sourceVertexView, roots);
0306: isRoot = false;
0307: }
0308: }
0309: }
0310: // The current node is never a Target Node
0311: // -> The current node is a root node
0312: if (isRoot) {
0313: roots.add(vertexViewToInspect);
0314: }
0315: }
0316: }
0317:
0318: /** Method fills the levels and stores them in the member levels.
0319:
0320: * Each level was represended by a List with Cell Wrapper objects.
0321: * These Lists are the elements in the <code>levels</code> List.
0322: *
0323: */
0324: protected List fillLevels(JGraph jgraph,
0325: CellView[] selectedCellViews, List rootVertexViews) {
0326: List levels = new ArrayList();
0327:
0328: // mark as not visited
0329: // O(allCells)
0330: for (int i = 0; i < selectedCellViews.length; i++) {
0331: CellView cellView = selectedCellViews[i];
0332: cellView.getAttributes().remove(SUGIYAMA_VISITED);
0333: }
0334:
0335: Iterator roots = rootVertexViews.iterator();
0336: while (roots.hasNext()) {
0337: VertexView vertexView = (VertexView) roots.next();
0338: fillLevels(jgraph, levels, 0, vertexView);
0339: }
0340:
0341: return levels;
0342:
0343: }
0344:
0345: /** Fills the List for the specified level with a wrapper
0346: * for the MyGraphCell. After that the method called for
0347: * each neighbor graph cell.
0348: *
0349: * @param level The level for the graphCell
0350: */
0351: protected void fillLevels(JGraph jgraph, List levels, int level,
0352: VertexView vertexView) {
0353: // be sure that a List container exists for the current level
0354: if (levels.size() == level)
0355: levels.add(level, new ArrayList());
0356:
0357: // if the cell already visited return
0358: if (vertexView.getAttributes().get(SUGIYAMA_VISITED) != null) {
0359: return;
0360: }
0361:
0362: // mark as visited for cycle tests
0363: vertexView.getAttributes().put(SUGIYAMA_VISITED,
0364: new Boolean(true));
0365:
0366: // put the current node into the current level
0367: // get the Level List
0368: List vecForTheCurrentLevel = (List) levels.get(level);
0369:
0370: // Create a wrapper for the node
0371: int numberForTheEntry = vecForTheCurrentLevel.size();
0372:
0373: CellWrapper wrapper = new CellWrapper(level, numberForTheEntry,
0374: vertexView);
0375:
0376: // put the Wrapper in the LevelList
0377: vecForTheCurrentLevel.add(wrapper);
0378:
0379: // concat the wrapper to the cell for an easy access
0380: vertexView.getAttributes().put(SUGIYAMA_CELL_WRAPPER, wrapper);
0381:
0382: // if the Cell has no Ports we can return, there are no relations
0383: Object vertex = vertexView.getCell();
0384: GraphModel model = jgraph.getModel();
0385: int portCount = model.getChildCount(vertex);
0386:
0387: // iterate any NodePort
0388: for (int i = 0; i < portCount; i++) {
0389:
0390: Object port = model.getChild(vertex, i);
0391:
0392: // iterate any Edge in the port
0393: Iterator itrEdges = model.edges(port);
0394:
0395: while (itrEdges.hasNext()) {
0396: Object edge = itrEdges.next();
0397:
0398: // if the Edge is a forward edge we should follow this edge
0399: if (port == model.getSource(edge)) {
0400: Object targetPort = model.getTarget(edge);
0401: Object targetVertex = model.getParent(targetPort);
0402: VertexView targetVertexView = (VertexView) jgraph
0403: .getGraphLayoutCache().getMapping(
0404: targetVertex, false);
0405: fillLevels(jgraph, levels, (level + 1),
0406: targetVertexView);
0407: }
0408: }
0409: }
0410:
0411: if (vecForTheCurrentLevel.size() > gridAreaSize) {
0412: gridAreaSize = vecForTheCurrentLevel.size();
0413: }
0414:
0415: }
0416:
0417: /** calculates the minimum for the paint area.
0418: *
0419: */
0420: protected Point findMinimumAndSpacing(CellView[] graphCellViews,
0421: Point spacing) {
0422: try {
0423:
0424: // variables
0425: /* represents the minimum x value for the paint area
0426: */
0427: int min_x = 1000000;
0428:
0429: /* represents the minimum y value for the paint area
0430: */
0431: int min_y = 1000000;
0432:
0433: // find the maximum & minimum coordinates
0434:
0435: for (int i = 0; i < graphCellViews.length; i++) {
0436:
0437: // the cellView and their bounds
0438: CellView cellView = graphCellViews[i];
0439:
0440: Rectangle cellViewBounds = cellView.getBounds()
0441: .getBounds();
0442:
0443: // checking min area
0444: try {
0445: if (cellViewBounds.x < min_x)
0446: min_x = cellViewBounds.x;
0447: if (cellViewBounds.y < min_y)
0448: min_y = cellViewBounds.y;
0449: /*
0450: if (cellViewBounds.width > spacing.x)
0451: spacing.x = cellViewBounds.width;
0452: if (cellViewBounds.height > spacing.y)
0453: spacing.y = cellViewBounds.height;
0454: */
0455:
0456: } catch (Exception e) {
0457: System.err
0458: .println("---------> ERROR in calculateValues."/*#Frozen*/);
0459: e.printStackTrace();
0460: }
0461: }
0462: // if the cell sice is bigger than the userspacing
0463: // dublicate the spacingfactor
0464: return new Point(min_x, min_y);
0465:
0466: } catch (Exception e) {
0467: e.printStackTrace();
0468: }
0469: return null;
0470: }
0471:
0472: /** Updates the progress based on the movements count
0473: *
0474: */
0475: protected void updateProgress4Movements() {
0476: // adds the current loop count
0477: movements.add(new Integer(movementsCurrentLoop));
0478: iteration++;
0479:
0480: // if the current loop count is higher than the max movements count
0481: // memorize the new max
0482: if (movementsCurrentLoop > movementsMax) {
0483: movementsMax = movementsCurrentLoop;
0484: }
0485:
0486: }
0487:
0488: protected void solveEdgeCrosses(JGraph jgraph, List levels) {
0489: movements = new ArrayList(100);
0490: movementsCurrentLoop = -1;
0491: movementsMax = Integer.MIN_VALUE;
0492: iteration = 0;
0493:
0494: while (movementsCurrentLoop != 0) {
0495:
0496: // reset the movements per loop count
0497: movementsCurrentLoop = 0;
0498:
0499: if (verbose) {
0500: System.out
0501: .println("---------------------------- vor Sort"/*#Frozen*/);
0502: displayEdgeCrossesValues(levels);
0503: }
0504:
0505: // top down
0506: for (int i = 0; i < levels.size() - 1; i++) {
0507: movementsCurrentLoop += solveEdgeCrosses(jgraph, true,
0508: levels, i);
0509: }
0510:
0511: // bottom up
0512: for (int i = levels.size() - 1; i >= 1; i--) {
0513: movementsCurrentLoop += solveEdgeCrosses(jgraph, false,
0514: levels, i);
0515: }
0516:
0517: if (verbose) {
0518: System.out
0519: .println("---------------------------- nach Sort"/*#Frozen*/);
0520: displayEdgeCrossesValues(levels);
0521: }
0522:
0523: updateProgress4Movements();
0524: }
0525: }
0526:
0527: /**
0528: * @return movements
0529: */
0530: protected int solveEdgeCrosses(JGraph jgraph, boolean down,
0531: List levels, int levelIndex) {
0532: // Get the current level
0533: List currentLevel = (List) levels.get(levelIndex);
0534: int movements = 0;
0535:
0536: // restore the old sort
0537: Object[] levelSortBefore = currentLevel.toArray();
0538:
0539: // new sort
0540: Collections.sort(currentLevel);
0541:
0542: // test for movements
0543: for (int j = 0; j < levelSortBefore.length; j++) {
0544: if (((CellWrapper) levelSortBefore[j])
0545: .getEdgeCrossesIndicator() != ((CellWrapper) currentLevel
0546: .get(j)).getEdgeCrossesIndicator()) {
0547: movements++;
0548:
0549: }
0550: }
0551:
0552: GraphModel model = jgraph.getModel();
0553:
0554: // Collecations Sort sorts the highest value to the first value
0555: for (int j = currentLevel.size() - 1; j >= 0; j--) {
0556: CellWrapper sourceWrapper = (CellWrapper) currentLevel
0557: .get(j);
0558:
0559: VertexView sourceView = sourceWrapper.getVertexView();
0560:
0561: Object sourceVertex = sourceView.getCell();
0562: int sourcePortCount = model.getChildCount(sourceVertex);
0563:
0564: for (int k = 0; k < sourcePortCount; k++) {
0565: Object sourcePort = model.getChild(sourceVertex, k);
0566:
0567: Iterator sourceEdges = model.edges(sourcePort);
0568: while (sourceEdges.hasNext()) {
0569: Object edge = sourceEdges.next();
0570:
0571: // if it is a forward edge follow it
0572: Object targetPort = null;
0573: if (down && sourcePort == model.getSource(edge)) {
0574: targetPort = model.getTarget(edge);
0575: }
0576: if (!down && sourcePort == model.getTarget(edge)) {
0577: targetPort = model.getSource(edge);
0578: }
0579: if (targetPort == null)
0580: continue;
0581:
0582: Object targetCell = model.getParent(targetPort);
0583: VertexView targetVertexView = (VertexView) jgraph
0584: .getGraphLayoutCache().getMapping(
0585: targetCell, false);
0586: CellWrapper targetWrapper = (CellWrapper) targetVertexView
0587: .getAttributes().get(SUGIYAMA_CELL_WRAPPER);
0588:
0589: // do it only if the edge is a forward edge to a deeper level
0590: if (down && targetWrapper != null
0591: && targetWrapper.getLevel() > levelIndex) {
0592: targetWrapper
0593: .addToEdgeCrossesIndicator(sourceWrapper
0594: .getEdgeCrossesIndicator());
0595: }
0596: if (!down && targetWrapper != null
0597: && targetWrapper.getLevel() < levelIndex) {
0598: targetWrapper
0599: .addToEdgeCrossesIndicator(sourceWrapper
0600: .getEdgeCrossesIndicator());
0601: }
0602: }
0603: }
0604: }
0605:
0606: return movements;
0607: }
0608:
0609: protected void moveToBarycenter(JGraph jgraph,
0610: CellView[] allSelectedViews, List levels) {
0611:
0612: //================================================================
0613: // iterate any ReViewNodePort
0614: GraphModel model = jgraph.getModel();
0615: for (int i = 0; i < allSelectedViews.length; i++) {
0616: if (!(allSelectedViews[i] instanceof VertexView))
0617: continue;
0618:
0619: VertexView vertexView = (VertexView) allSelectedViews[i];
0620:
0621: CellWrapper currentwrapper = (CellWrapper) vertexView
0622: .getAttributes().get(SUGIYAMA_CELL_WRAPPER);
0623:
0624: Object vertex = vertexView.getCell();
0625: int portCount = model.getChildCount(vertex);
0626:
0627: for (int k = 0; k < portCount; k++) {
0628: Object port = model.getChild(vertex, k);
0629:
0630: // iterate any Edge in the port
0631:
0632: Iterator edges = model.edges(port);
0633: while (edges.hasNext()) {
0634: Object edge = edges.next();
0635:
0636: Object neighborPort = null;
0637: // if the Edge is a forward edge we should follow this edge
0638: if (port == model.getSource(edge)) {
0639: neighborPort = model.getTarget(edge);
0640: } else {
0641: if (port == model.getTarget(edge)) {
0642: neighborPort = model.getSource(edge);
0643: } else {
0644: continue;
0645: }
0646: }
0647:
0648: Object neighborVertex = model
0649: .getParent(neighborPort);
0650:
0651: VertexView neighborVertexView = (VertexView) jgraph
0652: .getGraphLayoutCache().getMapping(
0653: neighborVertex, false);
0654:
0655: if (neighborVertexView == vertexView)
0656: continue;
0657:
0658: CellWrapper neighborWrapper = (CellWrapper) neighborVertexView
0659: .getAttributes().get(SUGIYAMA_CELL_WRAPPER);
0660:
0661: if (currentwrapper == null
0662: || neighborWrapper == null
0663: || currentwrapper.level == neighborWrapper.level)
0664: continue;
0665:
0666: currentwrapper.priority++;
0667:
0668: }
0669: }
0670: }
0671:
0672: //================================================================
0673: for (int j = 0; j < levels.size(); j++) {
0674: List level = (List) levels.get(j);
0675: for (int i = 0; i < level.size(); i++) {
0676: // calculate the initial Grid Positions 1, 2, 3, .... per Level
0677: CellWrapper wrapper = (CellWrapper) level.get(i);
0678: wrapper.setGridPosition(i);
0679: }
0680: }
0681:
0682: if (verbose) {
0683: System.out
0684: .println("----------------Grid Pos before top down"/*#Frozen*/);
0685: displayPriorities(levels);
0686: displayGridPositions(levels);
0687: System.out
0688: .println("======================================="/*#Frozen*/);
0689: }
0690:
0691: movements = new ArrayList(100);
0692: movementsCurrentLoop = -1;
0693: movementsMax = Integer.MIN_VALUE;
0694: iteration = 0;
0695:
0696: //int movements = 1;
0697:
0698: while (movementsCurrentLoop != 0) {
0699:
0700: // reset movements
0701: movementsCurrentLoop = 0;
0702:
0703: // top down
0704: for (int i = 1; i < levels.size(); i++) {
0705: movementsCurrentLoop += moveToBarycenter(jgraph,
0706: levels, i);
0707: }
0708:
0709: if (verbose) {
0710: System.out
0711: .println("----------------Grid Pos after top down"/*#Frozen*/);
0712: displayGridPositions(levels);
0713: System.out
0714: .println("======================================="/*#Frozen*/);
0715: }
0716:
0717: // bottom up
0718: for (int i = levels.size() - 1; i >= 0; i--) {
0719: movementsCurrentLoop += moveToBarycenter(jgraph,
0720: levels, i);
0721: }
0722:
0723: if (verbose) {
0724: System.out
0725: .println("----------------Grid Pos after bottom up"/*#Frozen*/);
0726: displayGridPositions(levels);
0727: //displayDownPriorities();
0728: System.out
0729: .println("======================================="/*#Frozen*/);
0730: }
0731:
0732: this .updateProgress4Movements();
0733: }
0734:
0735: }
0736:
0737: protected int moveToBarycenter(JGraph jgraph, List levels,
0738: int levelIndex) {
0739:
0740: // Counter for the movements
0741: int movements = 0;
0742:
0743: // Get the current level
0744: List currentLevel = (List) levels.get(levelIndex);
0745: GraphModel model = jgraph.getModel();
0746:
0747: for (int currentIndexInTheLevel = 0; currentIndexInTheLevel < currentLevel
0748: .size(); currentIndexInTheLevel++) {
0749:
0750: CellWrapper sourceWrapper = (CellWrapper) currentLevel
0751: .get(currentIndexInTheLevel);
0752:
0753: float gridPositionsSum = 0;
0754: float countNodes = 0;
0755:
0756: VertexView vertexView = sourceWrapper.getVertexView();
0757: Object vertex = vertexView.getCell();
0758: int portCount = model.getChildCount(vertex);
0759:
0760: for (int i = 0; i < portCount; i++) {
0761: Object port = model.getChild(vertex, i);
0762:
0763: Iterator edges = model.edges(port);
0764: while (edges.hasNext()) {
0765: Object edge = edges.next();
0766:
0767: // if it is a forward edge follow it
0768: Object neighborPort = null;
0769: if (port == model.getSource(edge)) {
0770: neighborPort = model.getTarget(edge);
0771: } else {
0772: if (port == model.getTarget(edge)) {
0773: neighborPort = model.getSource(edge);
0774: } else {
0775: continue;
0776: }
0777: }
0778:
0779: Object neighborVertex = model
0780: .getParent(neighborPort);
0781:
0782: VertexView neighborVertexView = (VertexView) jgraph
0783: .getGraphLayoutCache().getMapping(
0784: neighborVertex, false);
0785: CellWrapper targetWrapper = (CellWrapper) neighborVertexView
0786: .getAttributes().get(SUGIYAMA_CELL_WRAPPER);
0787:
0788: if (targetWrapper == sourceWrapper)
0789: continue;
0790: if (targetWrapper == null
0791: || targetWrapper.getLevel() == levelIndex)
0792: continue;
0793:
0794: gridPositionsSum += targetWrapper.getGridPosition();
0795: countNodes++;
0796: }
0797: }
0798:
0799: //----------------------------------------------------------
0800: // move node to new x coord
0801: //----------------------------------------------------------
0802:
0803: if (countNodes > 0) {
0804: float tmp = (gridPositionsSum / countNodes);
0805: int newGridPosition = Math.round(tmp);
0806: boolean toRight = (newGridPosition > sourceWrapper
0807: .getGridPosition());
0808:
0809: boolean moved = true;
0810:
0811: while (newGridPosition != sourceWrapper
0812: .getGridPosition()
0813: && moved) {
0814: int tmpGridPos = sourceWrapper.getGridPosition();
0815:
0816: moved = move(toRight, currentLevel,
0817: currentIndexInTheLevel, sourceWrapper
0818: .getPriority());
0819:
0820: if (moved)
0821: movements++;
0822:
0823: if (verbose) {
0824:
0825: System.out
0826: .print("try move at Level "
0827: + levelIndex
0828: + " with index "
0829: + currentIndexInTheLevel
0830: + " to "
0831: + (toRight ? "Right" : "Left")
0832: + " CurrentGridPos: "
0833: + tmpGridPos
0834: + " NewGridPos: "
0835: + newGridPosition
0836: + " exact: "
0837: + NumberFormat.getInstance()
0838: .format(tmp) + "..."/*#Frozen*/);
0839: System.out.println(moved ? "success"/*#Frozen*/
0840: : "can't move"/*#Frozen*/);
0841:
0842: }
0843: }
0844: }
0845: }
0846: return movements;
0847: }
0848:
0849: /**@param toRight <tt>true</tt> = try to move the currentWrapper to right; <tt>false</tt> = try to move the currentWrapper to left;
0850: * @param currentLevel List which contains the CellWrappers for the current level
0851: * @param currentIndexInTheLevel
0852: * @param currentPriority
0853: *
0854: * @return The free GridPosition or -1 is position is not free.
0855: */
0856: protected boolean move(boolean toRight, List currentLevel,
0857: int currentIndexInTheLevel, int currentPriority) {
0858:
0859: CellWrapper currentWrapper = (CellWrapper) currentLevel
0860: .get(currentIndexInTheLevel);
0861:
0862: boolean moved = false;
0863: int neighborIndexInTheLevel = currentIndexInTheLevel
0864: + (toRight ? 1 : -1);
0865: int newGridPosition = currentWrapper.getGridPosition()
0866: + (toRight ? 1 : -1);
0867:
0868: // is the grid position possible?
0869:
0870: if (0 > newGridPosition || newGridPosition >= gridAreaSize) {
0871: return false;
0872: }
0873:
0874: // if the node is the first or the last we can move
0875: if (toRight
0876: && currentIndexInTheLevel == currentLevel.size() - 1
0877: || !toRight && currentIndexInTheLevel == 0) {
0878:
0879: moved = true;
0880:
0881: } else {
0882: // else get the neighbor and ask his gridposition
0883: // if he has the requested new grid position
0884: // check the priority
0885:
0886: CellWrapper neighborWrapper = (CellWrapper) currentLevel
0887: .get(neighborIndexInTheLevel);
0888:
0889: int neighborPriority = neighborWrapper.getPriority();
0890:
0891: if (neighborWrapper.getGridPosition() == newGridPosition) {
0892: if (neighborPriority >= currentPriority) {
0893: return false;
0894: } else {
0895: moved = move(toRight, currentLevel,
0896: neighborIndexInTheLevel, currentPriority);
0897: }
0898: } else {
0899: moved = true;
0900: }
0901: }
0902:
0903: if (moved) {
0904: currentWrapper.setGridPosition(newGridPosition);
0905: }
0906: return moved;
0907: }
0908:
0909: /** This Method draws the graph. For the horizontal position
0910: * we are using the grid position from each graphcell.
0911: * For the vertical position we are using the level position.
0912: *
0913: */
0914: protected void drawGraph(JGraph jgraph, List levels, Point min,
0915: Point spacing) {
0916: // paint the graph
0917:
0918: Map viewMap = new HashMap();
0919:
0920: for (int rowCellCount = 0; rowCellCount < levels.size(); rowCellCount++) {
0921: List level = (List) levels.get(rowCellCount);
0922:
0923: for (int colCellCount = 0; colCellCount < level.size(); colCellCount++) {
0924: CellWrapper wrapper = (CellWrapper) level
0925: .get(colCellCount);
0926: VertexView view = wrapper.vertexView;
0927:
0928: // remove the temp objects
0929: /* While the Algorithm is running we are putting some
0930: * attributeNames to the MyGraphCells. This method
0931: * cleans this objects from the MyGraphCells.
0932: *
0933: */
0934: view.getAttributes().remove(SUGIYAMA_CELL_WRAPPER);
0935: view.getAttributes().remove(SUGIYAMA_VISITED);
0936: wrapper.vertexView = null;
0937:
0938: // get the bounds from the cellView
0939: Rectangle bounds = (Rectangle) view.getBounds().clone();
0940:
0941: // adjust
0942: bounds.x = min.x + spacing.x
0943: * wrapper.getGridPosition();
0944: bounds.y = min.y + spacing.y * rowCellCount;
0945:
0946: Object cell = view.getCell();
0947: Map map = new AttributeMap();
0948: GraphConstants.setBounds(map, bounds);
0949: viewMap.put(cell, map);
0950: }
0951:
0952: }
0953: jgraph.getGraphLayoutCache().edit(viewMap, null, null, null);
0954: }
0955:
0956: /** cell wrapper contains all values
0957: * for one node
0958: */
0959: class CellWrapper implements Comparable {
0960:
0961: /** sum value for edge Crosses
0962: */
0963: private double edgeCrossesIndicator = 0;
0964: /** counter for additions to the edgeCrossesIndicator
0965: */
0966: private int additions = 0;
0967: /** the vertical level where the cell wrapper is inserted
0968: */
0969: int level = 0;
0970: /** current position in the grid
0971: */
0972: int gridPosition = 0;
0973: /** priority for movements to the barycenter
0974: */
0975: int priority = 0;
0976: /** reference to the wrapped cell
0977: */
0978: VertexView vertexView = null;
0979:
0980: /** creates an instance and memorizes the parameters
0981: *
0982: */
0983: CellWrapper(int level, double edgeCrossesIndicator,
0984: VertexView vertexView) {
0985: this .level = level;
0986: this .edgeCrossesIndicator = edgeCrossesIndicator;
0987: this .vertexView = vertexView;
0988: additions++;
0989: }
0990:
0991: /** returns the wrapped cell
0992: */
0993: VertexView getVertexView() {
0994: return vertexView;
0995: }
0996:
0997: /** resets the indicator for edge crosses to 0
0998: */
0999: void resetEdgeCrossesIndicator() {
1000: edgeCrossesIndicator = 0;
1001: additions = 0;
1002: }
1003:
1004: /** retruns the average value for the edge crosses indicator
1005: *
1006: * for the wrapped cell
1007: *
1008: */
1009:
1010: double getEdgeCrossesIndicator() {
1011: if (additions == 0)
1012: return 0;
1013: return edgeCrossesIndicator / additions;
1014: }
1015:
1016: /** Addes a value to the edge crosses indicator
1017: * for the wrapped cell
1018: *
1019: */
1020: void addToEdgeCrossesIndicator(double addValue) {
1021: edgeCrossesIndicator += addValue;
1022: additions++;
1023: }
1024:
1025: /** gets the level of the wrapped cell
1026: */
1027: int getLevel() {
1028: return level;
1029: }
1030:
1031: /** gets the grid position for the wrapped cell
1032: */
1033: int getGridPosition() {
1034: return gridPosition;
1035: }
1036:
1037: /** Sets the grid position for the wrapped cell
1038: */
1039: void setGridPosition(int pos) {
1040: this .gridPosition = pos;
1041: }
1042:
1043: /** increments the the priority of this cell wrapper.
1044: *
1045: * The priority was used by moving the cell to its
1046: * barycenter.
1047: *
1048: */
1049:
1050: void incrementPriority() {
1051: priority++;
1052: }
1053:
1054: /** returns the priority of this cell wrapper.
1055: *
1056: * The priority was used by moving the cell to its
1057: * barycenter.
1058: */
1059: int getPriority() {
1060: return priority;
1061: }
1062:
1063: /**
1064: * @see java.lang.Comparable#compareTo(Object)
1065: */
1066: public int compareTo(Object compare) {
1067: if (((CellWrapper) compare).getEdgeCrossesIndicator() == this
1068: .getEdgeCrossesIndicator())
1069: return 0;
1070:
1071: double compareValue = (((CellWrapper) compare)
1072: .getEdgeCrossesIndicator() - this
1073: .getEdgeCrossesIndicator());
1074:
1075: return (int) (compareValue * 1000);
1076:
1077: }
1078: }
1079: }
|