Java > Open Source Codes > com > opensymphony > workflow > designer > layout > SugiyamaLayoutAlgorithm


1 // This file is part of the Echidna project
2 // (C) 2002 Forschungszentrum Informatik (FZI) Karlsruhe
3 // Please visit our website at http://echidna.sf.net
4 package com.opensymphony.workflow.designer.layout;
5
6 import javax.swing.*;
7
8 import org.jgraph.JGraph;
9 import org.jgraph.graph.*;
10
11 import java.awt.Point ;
12 import java.awt.Rectangle ;
13 import java.text.NumberFormat ;
14 import java.util.*;
15
16 /**
17  * Arranges the nodes with the Sugiyama Layout Algorithm.<br>
18  *
19  * <a HREF="http://plg.uwaterloo.ca/~itbowman/CS746G/Notes/Sugiyama1981_MVU/">
20  * Link to the algorithm</a>
21  *
22  *<br>
23  *<br>
24  * @author Sven Luzar<br>
25  * @version 1.0 init
26  */
27 public class SugiyamaLayoutAlgorithm implements LayoutAlgorithm
28 {
29
30   /** Field for debug output
31    */
32   protected final boolean verbose = false;
33
34   /** Const to add Attributes at the Nodes
35    *
36    */
37   public static final String SUGIYAMA_VISITED = "SugiyamaVisited"/*#Frozen*/;
38
39   /** Const to add the Cell Wrapper to the Nodes
40    */
41   public static final String SUGIYAMA_CELL_WRAPPER = "SugiyamaCellWrapper"/*#Frozen*/;
42
43   /** represents the size of the grid in horizontal grid elements
44    *
45    */
46   protected int gridAreaSize = Integer.MIN_VALUE;
47
48   /** A List with Integer Objects. The List contains the
49    * history of movements per loop
50    * It was needed for the progress dialog
51    */
52   List movements = null;
53   /** Represents the movements in the current loop.
54    * It was needed for the progress dialog
55    */
56   int movementsCurrentLoop = -1;
57   /** Represents the maximum of movements in the current loop.
58    * It was needed for the progress dialog
59    */
60   int movementsMax = Integer.MIN_VALUE;
61   /** Represents the current loop number
62    * It was needed for the progress dialog
63    */
64   int iteration = 0;
65   public static final String KEY_HORIZONTAL_SPACING = "HorizontalSpacing";
66   public static final String KEY_VERTICAL_SPACING = "VerticalSpacing";
67
68   /**
69    * Implementation.
70    *
71    * First of all the Algorithm searches the roots from the
72    * Graph. Starting from this roots the Algorithm creates
73    * levels and stores them in the member <code>levels</code>.
74    * The Member levels contains List Objects and the List per level
75    * contains Cell Wrapper Objects. After that the Algorithm
76    * tries to solve the edge crosses from level to level and
77    * goes top down and bottom up. After minimization of the
78    * edge crosses the algorithm moves each node to its
79    * bary center. Last but not Least the method draws the Graph.
80    *
81    * @see LayoutAlgorithm
82    *
83    */
84   public void perform(JGraph jgraph, boolean applyToAll, Properties configuration)
85   {
86
87     Object [] selectedCells = (applyToAll ? jgraph.getRoots() : jgraph.getSelectionCells());
88     CellView[] selectedCellViews = jgraph.getGraphLayoutCache().getMapping(selectedCells);
89
90     Point spacing = new Point ();
91     /* The Algorithm distributes the nodes on a grid.
92      * For this grid you can configure the horizontal spacing.
93      * This field specifies the configured value
94      *
95      */
96     spacing.x = Integer.parseInt(configuration.getProperty(KEY_HORIZONTAL_SPACING));
97
98     /* The Algorithm distributes the nodes on a grid.
99      * For this grid you can configure the vertical spacing.
100      * This field specifies the configured value
101      *
102      */
103
104     spacing.y = Integer.parseInt(configuration.getProperty(KEY_VERTICAL_SPACING));
105
106     // search all roots
107 List roots = searchRoots(jgraph, selectedCellViews);
108
109     // return if no root found
110 if(roots.size() == 0)
111       return;
112
113     // create levels
114 List levels = fillLevels(jgraph, selectedCellViews, roots);
115
116     // solves the edge crosses
117 solveEdgeCrosses(jgraph, levels);
118
119     // move all nodes into the barycenter
120 moveToBarycenter(jgraph, selectedCellViews, levels);
121
122     Point min = findMinimumAndSpacing(selectedCellViews, spacing);
123
124     // draw the graph in the window
125 drawGraph(jgraph, levels, min, spacing);
126
127     // clean temp values from the nodes / cells
128 // the clean up was made in drawGraph
129 //cleanUp(selectedCellViews);
130
131   }
132
133   /** Debugdisplay for the edge crosses indicators on the System out
134    */
135   protected void displayEdgeCrossesValues(List levels)
136   {
137     System.out.println("----------------Edge Crosses Indicator Values"/*#Frozen*/);
138
139     for(int i = 0; i < levels.size() - 1; i++)
140     {
141       // Get the current level
142 List currentLevel = (List)levels.get(i);
143       System.out.print("Level (" + i + "):"/*#Frozen*/);
144       for(int j = 0; j < currentLevel.size(); j++)
145       {
146         CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
147
148         System.out.print(NumberFormat.getNumberInstance().format(sourceWrapper.getEdgeCrossesIndicator()) + " - "/*#Frozen*/);
149       }
150       System.out.println();
151     }
152   }
153
154   /** Debugdisplay for the grid positions on the System out
155    */
156   protected void displayGridPositions(List levels)
157   {
158
159     System.out.println("----------------GridPositions"/*#Frozen*/);
160
161     for(int i = 0; i < levels.size() - 1; i++)
162     {
163       // Get the current level
164 List currentLevel = (List)levels.get(i);
165       System.out.print("Level (" + i + "):"/*#Frozen*/);
166       for(int j = 0; j < currentLevel.size(); j++)
167       {
168         CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
169         System.out.print(NumberFormat.getNumberInstance().format(sourceWrapper.getGridPosition()) + " - "/*#Frozen*/);
170       }
171       System.out.println();
172     }
173   }
174
175   /** Debugdisplay for the priorities on the System out
176    */
177   protected void displayPriorities(List levels)
178   {
179
180     System.out.println("----------------down Priorities"/*#Frozen*/);
181
182     for(int i = 0; i < levels.size() - 1; i++)
183     {
184       // Get the current level
185 List currentLevel = (List)levels.get(i);
186       System.out.print("Level (" + i + "):"/*#Frozen*/);
187       for(int j = 0; j < currentLevel.size(); j++)
188       {
189         CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
190         System.out.print(sourceWrapper.getPriority() + /*" (" +
191                            sourceWrapper.nearestDownNeighborLevel + ") " +*/
192                          " - "/*#Frozen*/);
193       }
194       System.out.println();
195     }
196   }
197
198   /** Searches all Roots for the current Graph
199    * First the method marks any Node as not visited.
200    * Than calls searchRoots(MyGraphCell) for each
201    * not visited Cell.
202    * The Roots are stored in the List named roots
203    *
204    * @return returns a List with the roots
205    * @see #searchRoots(JGraph, CellView[])
206    */
207   protected List searchRoots(JGraph jgraph, CellView[] selectedCellViews)
208   {
209
210     // get all cells and relations
211 List vertexViews = new ArrayList(selectedCellViews.length);
212     List roots = new ArrayList();
213
214     // first: mark all as not visited
215 // O(allCells&Edges)
216 for(int i = 0; i < selectedCellViews.length; i++)
217     {
218       if(selectedCellViews[i] instanceof VertexView)
219       {
220         VertexView vertexView = (VertexView)selectedCellViews[i];
221         vertexView.getAttributes().remove(SUGIYAMA_VISITED);
222         vertexViews.add(selectedCellViews[i]);
223       }
224     }
225
226     // O(graphCells)
227 for(int i = 0; i < vertexViews.size(); i++)
228     {
229       VertexView vertexView = (VertexView)vertexViews.get(i);
230       if(vertexView.getAttributes().get(SUGIYAMA_VISITED) == null)
231       {
232         searchRoots(jgraph, vertexView, roots);
233       }
234     }
235
236     // Error Msg if the graph has no roots
237 if(roots.size() == 0)
238     {
239       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);
240     }
241     return roots;
242   }
243
244   /** Searches Roots for the current Cell.
245    *
246    * Therefore he looks at all Ports from the Cell.
247    * At the Ports he looks for Edges.
248    * At the Edges he looks for the Target.
249    * If the Ports of the current Cell contains the target ReViewNodePort
250    * he follows the edge to the source and looks at the
251    * Cell for this source.
252    *
253    */
254   protected void searchRoots(JGraph jgraph, VertexView vertexViewToInspect, List roots)
255   {
256     // the node already visited
257 if(vertexViewToInspect.getAttributes().get(SUGIYAMA_VISITED) != null)
258     {
259       return;
260     }
261
262     // mark as visited for cycle tests
263 vertexViewToInspect.getAttributes().put(SUGIYAMA_VISITED, new Boolean (true));
264
265     GraphModel model = jgraph.getModel();
266
267     // get all Ports and search the relations at the ports
268 //List vertexPortViewList = new ArrayList() ;
269
270     Object vertex = vertexViewToInspect.getCell();
271
272     int portCount = model.getChildCount(vertex);
273     for(int j = 0; j < portCount; j++)
274     {
275       Object port = model.getChild(vertex, j);
276
277       // Test all relations for where
278 // the current node is a target node
279 // for roots
280
281       boolean isRoot = true;
282       Iterator itrEdges = model.edges(port);
283       while(itrEdges.hasNext())
284       {
285         Object edge = itrEdges.next();
286
287         // if the current node is a target node
288 // get the source node and test
289 // the source node for roots
290
291         if(model.getTarget(edge) == port)
292         {
293           Object sourcePort = model.getSource(edge);
294
295           Object sourceVertex = model.getParent(sourcePort);
296
297           CellView sourceVertexView = jgraph.getGraphLayoutCache().getMapping(sourceVertex, false);
298           if(sourceVertexView instanceof VertexView)
299           {
300             searchRoots(jgraph, (VertexView)sourceVertexView, roots);
301             isRoot = false;
302           }
303         }
304       }
305       // The current node is never a Target Node
306 // -> The current node is a root node
307 if(isRoot)
308       {
309         roots.add(vertexViewToInspect);
310       }
311     }
312   }
313
314   /** Method fills the levels and stores them in the member levels.
315
316    * Each level was represended by a List with Cell Wrapper objects.
317    * These Lists are the elements in the <code>levels</code> List.
318    *
319    */
320   protected List fillLevels(JGraph jgraph, CellView[] selectedCellViews, List rootVertexViews)
321   {
322     List levels = new ArrayList();
323
324     // mark as not visited
325 // O(allCells)
326 for(int i = 0; i < selectedCellViews.length; i++)
327     {
328       CellView cellView = selectedCellViews[i];
329       cellView.getAttributes().remove(SUGIYAMA_VISITED);
330     }
331
332     Iterator roots = rootVertexViews.iterator();
333     while(roots.hasNext())
334     {
335       VertexView vertexView = (VertexView)roots.next();
336       fillLevels(jgraph, levels, 0, vertexView);
337     }
338
339     return levels;
340
341   }
342
343   /** Fills the List for the specified level with a wrapper
344    * for the MyGraphCell. After that the method called for
345    * each neighbor graph cell.
346    *
347    * @param level The level for the graphCell
348    */
349   protected void fillLevels(JGraph jgraph, List levels, int level, VertexView vertexView)
350   {
351     // be sure that a List container exists for the current level
352 if(levels.size() == level)
353       levels.add(level, new ArrayList());
354
355     // if the cell already visited return
356 if(vertexView.getAttributes().get(SUGIYAMA_VISITED) != null)
357     {
358       return;
359     }
360
361     // mark as visited for cycle tests
362 vertexView.getAttributes().put(SUGIYAMA_VISITED, new Boolean (true));
363
364     // put the current node into the current level
365 // get the Level List
366 List vecForTheCurrentLevel = (List)levels.get(level);
367
368     // Create a wrapper for the node
369 int numberForTheEntry = vecForTheCurrentLevel.size();
370
371     CellWrapper wrapper = new CellWrapper(level, numberForTheEntry, vertexView);
372
373     // put the Wrapper in the LevelList
374 vecForTheCurrentLevel.add(wrapper);
375
376     // concat the wrapper to the cell for an easy access
377 vertexView.getAttributes().put(SUGIYAMA_CELL_WRAPPER, wrapper);
378
379     // if the Cell has no Ports we can return, there are no relations
380 Object vertex = vertexView.getCell();
381     GraphModel model = jgraph.getModel();
382     int portCount = model.getChildCount(vertex);
383
384     // iterate any NodePort
385 for(int i = 0; i < portCount; i++)
386     {
387
388       Object port = model.getChild(vertex, i);
389
390       // iterate any Edge in the port
391 Iterator itrEdges = model.edges(port);
392
393       while(itrEdges.hasNext())
394       {
395         Object edge = itrEdges.next();
396
397         // if the Edge is a forward edge we should follow this edge
398 if(port == model.getSource(edge))
399         {
400           Object targetPort = model.getTarget(edge);
401           Object targetVertex = model.getParent(targetPort);
402           VertexView targetVertexView = (VertexView)jgraph.getGraphLayoutCache().getMapping(targetVertex, false);
403           fillLevels(jgraph, levels, (level + 1), targetVertexView);
404         }
405       }
406     }
407
408     if(vecForTheCurrentLevel.size() > gridAreaSize)
409     {
410       gridAreaSize = vecForTheCurrentLevel.size();
411     }
412
413   }
414
415   /** calculates the minimum for the paint area.
416    *
417    */
418   protected Point findMinimumAndSpacing(CellView[] graphCellViews, Point spacing)
419   {
420     try
421     {
422
423       // variables
424 /* represents the minimum x value for the paint area
425        */
426       int min_x = 1000000;
427
428       /* represents the minimum y value for the paint area
429        */
430       int min_y = 1000000;
431
432       // find the maximum & minimum coordinates
433
434       for(int i = 0; i < graphCellViews.length; i++)
435       {
436
437         // the cellView and their bounds
438 CellView cellView = graphCellViews[i];
439
440         Rectangle cellViewBounds = cellView.getBounds().getBounds();
441
442         // checking min area
443 try
444         {
445           if(cellViewBounds.x < min_x)
446             min_x = cellViewBounds.x;
447           if(cellViewBounds.y < min_y)
448             min_y = cellViewBounds.y;
449           /*
450           if (cellViewBounds.width > spacing.x)
451             spacing.x = cellViewBounds.width;
452           if (cellViewBounds.height > spacing.y)
453             spacing.y = cellViewBounds.height;
454             */
455
456         }
457         catch(Exception e)
458         {
459           System.err.println("---------> ERROR in calculateValues."/*#Frozen*/);
460           e.printStackTrace();
461         }
462       }
463       // if the cell sice is bigger than the userspacing
464 // dublicate the spacingfactor
465 return new Point (min_x, min_y);
466
467     }
468     catch(Exception e)
469     {
470       e.printStackTrace();
471     }
472     return null;
473   }
474
475   /** Updates the progress based on the movements count
476    *
477    */
478   protected void updateProgress4Movements()
479   {
480     // adds the current loop count
481 movements.add(new Integer (movementsCurrentLoop));
482     iteration++;
483
484     // if the current loop count is higher than the max movements count
485 // memorize the new max
486 if(movementsCurrentLoop > movementsMax)
487     {
488       movementsMax = movementsCurrentLoop;
489     }
490
491   }
492
493   protected void solveEdgeCrosses(JGraph jgraph, List levels)
494   {
495     movements = new ArrayList(100);
496     movementsCurrentLoop = -1;
497     movementsMax = Integer.MIN_VALUE;
498     iteration = 0;
499
500     while(movementsCurrentLoop != 0)
501     {
502
503       // reset the movements per loop count
504 movementsCurrentLoop = 0;
505
506       if(verbose)
507       {
508         System.out.println("---------------------------- vor Sort"/*#Frozen*/);
509         displayEdgeCrossesValues(levels);
510       }
511
512       // top down
513 for(int i = 0; i < levels.size() - 1; i++)
514       {
515         movementsCurrentLoop += solveEdgeCrosses(jgraph, true, levels, i);
516       }
517
518       // bottom up
519 for(int i = levels.size() - 1; i >= 1; i--)
520       {
521         movementsCurrentLoop += solveEdgeCrosses(jgraph, false, levels, i);
522       }
523
524       if(verbose)
525       {
526         System.out.println("---------------------------- nach Sort"/*#Frozen*/);
527         displayEdgeCrossesValues(levels);
528       }
529
530       updateProgress4Movements();
531     }
532   }
533
534   /**
535    * @return movements
536    */
537   protected int solveEdgeCrosses(JGraph jgraph, boolean down, List levels, int levelIndex)
538   {
539     // Get the current level
540 List currentLevel = (List)levels.get(levelIndex);
541     int movements = 0;
542
543     // restore the old sort
544 Object [] levelSortBefore = currentLevel.toArray();
545
546     // new sort
547 Collections.sort(currentLevel);
548
549     // test for movements
550 for(int j = 0; j < levelSortBefore.length; j++)
551     {
552       if(((CellWrapper)levelSortBefore[j]).getEdgeCrossesIndicator() != ((CellWrapper)currentLevel.get(j)).getEdgeCrossesIndicator())
553       {
554         movements++;
555
556       }
557     }
558
559     GraphModel model = jgraph.getModel();
560
561     // Collecations Sort sorts the highest value to the first value
562 for(int j = currentLevel.size() - 1; j >= 0; j--)
563     {
564       CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(j);
565
566       VertexView sourceView = sourceWrapper.getVertexView();
567
568       Object sourceVertex = sourceView.getCell();
569       int sourcePortCount = model.getChildCount(sourceVertex);
570
571       for(int k = 0; k < sourcePortCount; k++)
572       {
573         Object sourcePort = model.getChild(sourceVertex, k);
574
575         Iterator sourceEdges = model.edges(sourcePort);
576         while(sourceEdges.hasNext())
577         {
578           Object edge = sourceEdges.next();
579
580           // if it is a forward edge follow it
581 Object targetPort = null;
582           if(down && sourcePort == model.getSource(edge))
583           {
584             targetPort = model.getTarget(edge);
585           }
586           if(!down && sourcePort == model.getTarget(edge))
587           {
588             targetPort = model.getSource(edge);
589           }
590           if(targetPort == null)
591             continue;
592
593           Object targetCell = model.getParent(targetPort);
594           VertexView targetVertexView = (VertexView)jgraph.getGraphLayoutCache().getMapping(targetCell, false);
595           CellWrapper targetWrapper = (CellWrapper)targetVertexView.getAttributes().get(SUGIYAMA_CELL_WRAPPER);
596
597           // do it only if the edge is a forward edge to a deeper level
598 if(down && targetWrapper != null && targetWrapper.getLevel() > levelIndex)
599           {
600             targetWrapper.addToEdgeCrossesIndicator(sourceWrapper.getEdgeCrossesIndicator());
601           }
602           if(!down && targetWrapper != null && targetWrapper.getLevel() < levelIndex)
603           {
604             targetWrapper.addToEdgeCrossesIndicator(sourceWrapper.getEdgeCrossesIndicator());
605           }
606         }
607       }
608     }
609
610     return movements;
611   }
612
613   protected void moveToBarycenter(JGraph jgraph, CellView[] allSelectedViews, List levels)
614   {
615
616     //================================================================
617 // iterate any ReViewNodePort
618 GraphModel model = jgraph.getModel();
619     for(int i = 0; i < allSelectedViews.length; i++)
620     {
621       if(!(allSelectedViews[i] instanceof VertexView))
622         continue;
623
624       VertexView vertexView = (VertexView)allSelectedViews[i];
625
626       CellWrapper currentwrapper = (CellWrapper)vertexView.getAttributes().get(SUGIYAMA_CELL_WRAPPER);
627
628       Object vertex = vertexView.getCell();
629       int portCount = model.getChildCount(vertex);
630
631       for(int k = 0; k < portCount; k++)
632       {
633         Object port = model.getChild(vertex, k);
634
635         // iterate any Edge in the port
636
637         Iterator edges = model.edges(port);
638         while(edges.hasNext())
639         {
640           Object edge = edges.next();
641
642           Object neighborPort = null;
643           // if the Edge is a forward edge we should follow this edge
644 if(port == model.getSource(edge))
645           {
646             neighborPort = model.getTarget(edge);
647           }
648           else
649           {
650             if(port == model.getTarget(edge))
651             {
652               neighborPort = model.getSource(edge);
653             }
654             else
655             {
656               continue;
657             }
658           }
659
660           Object neighborVertex = model.getParent(neighborPort);
661
662           VertexView neighborVertexView = (VertexView)jgraph.getGraphLayoutCache().getMapping(neighborVertex, false);
663
664           if(neighborVertexView == vertexView)
665             continue;
666
667           CellWrapper neighborWrapper = (CellWrapper)neighborVertexView.getAttributes().get(SUGIYAMA_CELL_WRAPPER);
668
669           if(currentwrapper == null || neighborWrapper == null || currentwrapper.level == neighborWrapper.level)
670             continue;
671
672           currentwrapper.priority++;
673
674         }
675       }
676     }
677
678     //================================================================
679 for(int j = 0; j < levels.size(); j++)
680     {
681       List level = (List)levels.get(j);
682       for(int i = 0; i < level.size(); i++)
683       {
684         // calculate the initial Grid Positions 1, 2, 3, .... per Level
685 CellWrapper wrapper = (CellWrapper)level.get(i);
686         wrapper.setGridPosition(i);
687       }
688     }
689
690     if(verbose)
691     {
692       System.out.println("----------------Grid Pos before top down"/*#Frozen*/);
693       displayPriorities(levels);
694       displayGridPositions(levels);
695       System.out.println("======================================="/*#Frozen*/);
696     }
697
698     movements = new ArrayList(100);
699     movementsCurrentLoop = -1;
700     movementsMax = Integer.MIN_VALUE;
701     iteration = 0;
702
703     //int movements = 1;
704
705     while(movementsCurrentLoop != 0)
706     {
707
708       // reset movements
709 movementsCurrentLoop = 0;
710
711       // top down
712 for(int i = 1; i < levels.size(); i++)
713       {
714         movementsCurrentLoop += moveToBarycenter(jgraph, levels, i);
715       }
716
717       if(verbose)
718       {
719         System.out.println("----------------Grid Pos after top down"/*#Frozen*/);
720         displayGridPositions(levels);
721         System.out.println("======================================="/*#Frozen*/);
722       }
723
724       // bottom up
725 for(int i = levels.size() - 1; i >= 0; i--)
726       {
727         movementsCurrentLoop += moveToBarycenter(jgraph, levels, i);
728       }
729
730       if(verbose)
731       {
732         System.out.println("----------------Grid Pos after bottom up"/*#Frozen*/);
733         displayGridPositions(levels);
734         //displayDownPriorities();
735 System.out.println("======================================="/*#Frozen*/);
736       }
737
738       this.updateProgress4Movements();
739     }
740
741   }
742
743   protected int moveToBarycenter(JGraph jgraph, List levels, int levelIndex)
744   {
745
746     // Counter for the movements
747 int movements = 0;
748
749     // Get the current level
750 List currentLevel = (List)levels.get(levelIndex);
751     GraphModel model = jgraph.getModel();
752
753     for(int currentIndexInTheLevel = 0; currentIndexInTheLevel < currentLevel.size(); currentIndexInTheLevel++)
754     {
755
756       CellWrapper sourceWrapper = (CellWrapper)currentLevel.get(currentIndexInTheLevel);
757
758       float gridPositionsSum = 0;
759       float countNodes = 0;
760
761       VertexView vertexView = sourceWrapper.getVertexView();
762       Object vertex = vertexView.getCell();
763       int portCount = model.getChildCount(vertex);
764
765       for(int i = 0; i < portCount; i++)
766       {
767         Object port = model.getChild(vertex, i);
768
769         Iterator edges = model.edges(port);
770         while(edges.hasNext())
771         {
772           Object edge = edges.next();
773
774           // if it is a forward edge follow it
775 Object neighborPort = null;
776           if(port == model.getSource(edge))
777           {
778             neighborPort = model.getTarget(edge);
779           }
780           else
781           {
782             if(port == model.getTarget(edge))
783             {
784               neighborPort = model.getSource(edge);
785             }
786             else
787             {
788               continue;
789             }
790           }
791
792           Object neighborVertex = model.getParent(neighborPort);
793
794           VertexView neighborVertexView = (VertexView)jgraph.getGraphLayoutCache().getMapping(neighborVertex, false);
795           CellWrapper targetWrapper = (CellWrapper)neighborVertexView.getAttributes().get(SUGIYAMA_CELL_WRAPPER);
796
797           if(targetWrapper == sourceWrapper)
798             continue;
799           if(targetWrapper == null || targetWrapper.getLevel() == levelIndex)
800             continue;
801
802           gridPositionsSum += targetWrapper.getGridPosition();
803           countNodes++;
804         }
805       }
806
807       //----------------------------------------------------------
808 // move node to new x coord
809 //----------------------------------------------------------
810
811       if(countNodes > 0)
812       {
813         float tmp = (gridPositionsSum / countNodes);
814         int newGridPosition = Math.round(tmp);
815         boolean toRight = (newGridPosition > sourceWrapper.getGridPosition());
816
817         boolean moved = true;
818
819         while(newGridPosition != sourceWrapper.getGridPosition() && moved)
820         {
821           int tmpGridPos = sourceWrapper.getGridPosition();
822
823           moved = move(toRight, currentLevel, currentIndexInTheLevel, sourceWrapper.getPriority());
824
825           if(moved)
826             movements++;
827
828           if(verbose)
829           {
830
831             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*/);
832             System.out.println(moved ? "success"/*#Frozen*/ : "can't move"/*#Frozen*/);
833
834           }
835         }
836       }
837     }
838     return movements;
839   }
840
841   /**@param toRight <tt>true</tt> = try to move the currentWrapper to right; <tt>false</tt> = try to move the currentWrapper to left;
842    * @param currentLevel List which contains the CellWrappers for the current level
843    * @param currentIndexInTheLevel
844    * @param currentPriority
845    *
846    * @return The free GridPosition or -1 is position is not free.
847    */
848   protected boolean move(boolean toRight, List currentLevel, int currentIndexInTheLevel, int currentPriority)
849   {
850
851     CellWrapper currentWrapper = (CellWrapper)currentLevel.get(currentIndexInTheLevel);
852
853     boolean moved = false;
854     int neighborIndexInTheLevel = currentIndexInTheLevel + (toRight ? 1 : -1);
855     int newGridPosition = currentWrapper.getGridPosition() + (toRight ? 1 : -1);
856
857     // is the grid position possible?
858
859     if(0 > newGridPosition || newGridPosition >= gridAreaSize)
860     {
861       return false;
862     }
863
864     // if the node is the first or the last we can move
865 if(toRight && currentIndexInTheLevel == currentLevel.size() - 1 || !toRight && currentIndexInTheLevel == 0)
866     {
867
868       moved = true;
869
870     }
871     else
872     {
873       // else get the neighbor and ask his gridposition
874 // if he has the requested new grid position
875 // check the priority
876
877       CellWrapper neighborWrapper = (CellWrapper)currentLevel.get(neighborIndexInTheLevel);
878
879       int neighborPriority = neighborWrapper.getPriority();
880
881       if(neighborWrapper.getGridPosition() == newGridPosition)
882       {
883         if(neighborPriority >= currentPriority)
884         {
885           return false;
886         }
887         else
888         {
889           moved = move(toRight, currentLevel, neighborIndexInTheLevel, currentPriority);
890         }
891       }
892       else
893       {
894         moved = true;
895       }
896     }
897
898     if(moved)
899     {
900       currentWrapper.setGridPosition(newGridPosition);
901     }
902     return moved;
903   }
904
905   /** This Method draws the graph. For the horizontal position
906    * we are using the grid position from each graphcell.
907    * For the vertical position we are using the level position.
908    *
909    */
910   protected void drawGraph(JGraph jgraph, List levels, Point min, Point spacing)
911   {
912     // paint the graph
913
914     Map viewMap = new HashMap();
915
916     for(int rowCellCount = 0; rowCellCount < levels.size(); rowCellCount++)
917     {
918       List level = (List)levels.get(rowCellCount);
919
920       for(int colCellCount = 0; colCellCount < level.size(); colCellCount++)
921       {
922         CellWrapper wrapper = (CellWrapper)level.get(colCellCount);
923         VertexView view = wrapper.vertexView;
924
925         // remove the temp objects
926 /* While the Algorithm is running we are putting some
927          * attributeNames to the MyGraphCells. This method
928          * cleans this objects from the MyGraphCells.
929          *
930          */
931         view.getAttributes().remove(SUGIYAMA_CELL_WRAPPER);
932         view.getAttributes().remove(SUGIYAMA_VISITED);
933         wrapper.vertexView = null;
934
935         // get the bounds from the cellView
936 Rectangle bounds = (Rectangle )view.getBounds().clone();
937
938         // adjust
939 bounds.x = min.x + spacing.x * wrapper.getGridPosition();
940         bounds.y = min.y + spacing.y * rowCellCount;
941
942         Object cell = view.getCell();
943         Map map = new AttributeMap();
944         GraphConstants.setBounds(map, bounds);
945         viewMap.put(cell, map);
946       }
947
948     }
949     jgraph.getGraphLayoutCache().edit(viewMap, null, null, null);
950   }
951
952   /** cell wrapper contains all values
953    * for one node
954    */
955   class CellWrapper implements Comparable
956   {
957
958     /** sum value for edge Crosses
959      */
960     private double edgeCrossesIndicator = 0;
961     /** counter for additions to the edgeCrossesIndicator
962      */
963     private int additions = 0;
964     /** the vertical level where the cell wrapper is inserted
965      */
966     int level = 0;
967     /** current position in the grid
968      */
969     int gridPosition = 0;
970     /** priority for movements to the barycenter
971      */
972     int priority = 0;
973     /** reference to the wrapped cell
974      */
975     VertexView vertexView = null;
976
977     /** creates an instance and memorizes the parameters
978      *
979      */
980     CellWrapper(int level, double edgeCrossesIndicator, VertexView vertexView)
981     {
982       this.level = level;
983       this.edgeCrossesIndicator = edgeCrossesIndicator;
984       this.vertexView = vertexView;
985       additions++;
986     }
987
988     /** returns the wrapped cell
989      */
990     VertexView getVertexView()
991     {
992       return vertexView;
993     }
994
995     /** resets the indicator for edge crosses to 0
996      */
997     void resetEdgeCrossesIndicator()
998     {
999       edgeCrossesIndicator = 0;
1000      additions = 0;
1001    }
1002
1003    /** retruns the average value for the edge crosses indicator
1004     *
1005     * for the wrapped cell
1006     *
1007     */
1008
1009    double getEdgeCrossesIndicator()
1010    {
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    {
1022      edgeCrossesIndicator += addValue;
1023      additions++;
1024    }
1025
1026    /** gets the level of the wrapped cell
1027     */
1028    int getLevel()
1029    {
1030      return level;
1031    }
1032
1033    /** gets the grid position for the wrapped cell
1034     */
1035    int getGridPosition()
1036    {
1037      return gridPosition;
1038    }
1039
1040    /** Sets the grid position for the wrapped cell
1041     */
1042    void setGridPosition(int pos)
1043    {
1044      this.gridPosition = pos;
1045    }
1046
1047    /** increments the the priority of this cell wrapper.
1048     *
1049     * The priority was used by moving the cell to its
1050     * barycenter.
1051     *
1052     */
1053
1054    void incrementPriority()
1055    {
1056      priority++;
1057    }
1058
1059    /** returns the priority of this cell wrapper.
1060     *
1061     * The priority was used by moving the cell to its
1062     * barycenter.
1063     */
1064    int getPriority()
1065    {
1066      return priority;
1067    }
1068
1069    /**
1070     * @see java.lang.Comparable#compareTo(Object)
1071     */
1072    public int compareTo(Object compare)
1073    {
1074      if(((CellWrapper)compare).getEdgeCrossesIndicator() == this.getEdgeCrossesIndicator())
1075        return 0;
1076
1077      double compareValue = (((CellWrapper)compare).getEdgeCrossesIndicator() - this.getEdgeCrossesIndicator());
1078
1079      return (int)(compareValue * 1000);
1080
1081    }
1082  }
1083}
1084
1085

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags