1   /****************************************************************************
2    **
3    ** This file is part of yFiles-2.9. 
4    ** 
5    ** yWorks proprietary/confidential. Use is subject to license terms.
6    **
7    ** Redistribution of this file or of an unauthorized byte-code version
8    ** of this file is strictly forbidden.
9    **
10   ** Copyright (c) 2000-2011 by yWorks GmbH, Vor dem Kreuzberg 28, 
11   ** 72070 Tuebingen, Germany. All rights reserved.
12   **
13   ***************************************************************************/
14  package demo.view.graphexplorer;
15  
16  import y.anim.AnimationObject;
17  import y.anim.CompositeAnimationObject;
18  import y.base.DataMap;
19  import y.base.DataProvider;
20  import y.base.Edge;
21  import y.base.EdgeCursor;
22  import y.base.Node;
23  import y.base.NodeCursor;
24  import y.layout.BufferedLayouter;
25  import y.layout.CompositeLayoutStage;
26  import y.layout.CompositeLayouter;
27  import y.layout.FixNodeLayoutStage;
28  import y.layout.GraphLayout;
29  import y.layout.LayoutGraph;
30  import y.layout.LayoutOrientation;
31  import y.layout.Layouter;
32  import y.layout.ParallelEdgeLayouter;
33  import y.layout.SelfLoopLayouter;
34  import y.layout.circular.CircularLayouter;
35  import y.layout.grouping.RecursiveGroupLayouter;
36  import y.layout.hierarchic.IncrementalHierarchicLayouter;
37  import y.layout.hierarchic.incremental.IncrementalHintsFactory;
38  import y.layout.organic.GroupedShuffleLayouter;
39  import y.layout.organic.ShuffleLayouter;
40  import y.layout.organic.SmartOrganicLayouter;
41  import y.layout.orthogonal.OrthogonalGroupLayouter;
42  import y.layout.orthogonal.OrthogonalLayouter;
43  import y.layout.partial.PartialLayouter;
44  import y.layout.router.OrthogonalEdgeRouter;
45  import y.layout.tree.BalloonLayouter;
46  import y.layout.tree.TreeReductionStage;
47  import y.util.Comparators;
48  import y.util.DataProviderAdapter;
49  import y.util.DataProviders;
50  import y.util.GraphHider;
51  import y.util.Maps;
52  import y.view.EdgeRealizer;
53  import y.view.Graph2D;
54  import y.view.Graph2DLayoutExecutor;
55  import y.view.Graph2DView;
56  import y.view.LayoutMorpher;
57  import y.view.NodeRealizer;
58  import y.view.ViewAnimationFactory;
59  import y.view.hierarchy.HierarchyManager;
60  
61  import java.util.ArrayList;
62  import java.util.Arrays;
63  import java.util.Comparator;
64  import java.util.HashMap;
65  import java.util.Iterator;
66  import java.util.List;
67  import java.util.Map;
68  
69  /**
70   * Provides several layout algorithms for partial/incremental and complete
71   * re-layout.
72   *
73   */
74  class LayoutSupport {
75  
76    private static final int DURATION_EXPLORE = 1000;
77  
78    /**
79     * Specialized partial orthogonal Layout for grouped graphs.
80     * @param context specifies new and old elements.
81     */
82    static void doGroupedOrthogonalLayout(final LayoutContext context) {
83      final OrthogonalGroupLayouter ol = new OrthogonalGroupLayouter();
84      ol.setGrid(10);
85      if (context.isFromSketch()) {
86        final PartialLayouter pl = new PartialLayouter(ol);
87        pl.setEdgeRoutingStrategy(PartialLayouter.EDGE_ROUTING_STRATEGY_ORTHOGONAL);
88        pl.setLayoutOrientation(PartialLayouter.ORIENTATION_NONE);
89        pl.setConsiderNodeAlignment(false);
90        pl.setMinimalNodeDistance(20);
91        pl.setFixedGroupResizingEnabled(false);
92        
93        ((OrthogonalEdgeRouter)pl.getEdgeRouter()).setCrossingCost(0);
94      
95        final LayoutGraph filteredGraph = context.getGraph2D();
96        filteredGraph.addDataProvider(
97                PartialLayouter.PARTIAL_NODES_DPKEY, new DataProviderAdapter() {
98                  public boolean getBool( final Object dataHolder ) {
99                    return context.isNewNode((Node) dataHolder);
100         }
101               });
102 
103       filteredGraph.addDataProvider(
104               PartialLayouter.PARTIAL_EDGES_DPKEY, new DataProviderAdapter() {
105                 public boolean getBool( final Object dataHolder ) {
106                   return context.isNewEdge((Edge) dataHolder);
107                 }
108               });
109 
110 
111       final GroupedShuffleLayouter gsl = new GroupedShuffleLayouter();
112       gsl.setCoreLayouter(pl);
113       ((ShuffleLayouter)gsl.getShuffleLayouter()).setMinimalNodeDistance(20);
114 
115       Layouter layouter = new Layouter() {
116         public boolean canLayout(LayoutGraph graph) {
117           return true;
118         }
119         public void doLayout(LayoutGraph graph) {
120           //use BufferedLayout to keep graph element order for subsequent edge routing phase.
121           BufferedLayouter bl = new BufferedLayouter(gsl);
122           bl.doLayout(graph);
123 
124           graph.addDataProvider(PartialLayouter.PARTIAL_EDGES_DPKEY, DataProviders.createConstantDataProvider(Boolean.TRUE));
125           graph.addDataProvider(PartialLayouter.PARTIAL_NODES_DPKEY, DataProviders.createConstantDataProvider(Boolean.FALSE));
126           pl.doLayout(graph);
127         }
128       };
129 
130       doLayout(layouter, context);
131 
132       //cleanup
133       filteredGraph.removeDataProvider(PartialLayouter.PARTIAL_NODES_DPKEY);
134       filteredGraph.removeDataProvider(PartialLayouter.PARTIAL_EDGES_DPKEY);
135     } else {
136       doLayout(ol, context);
137     }
138   }
139 
140   /**
141    * Arranges the graph in an orthogonal fashion.
142    * <p>
143    * This layout calculation is animated. Moreover, the layout animation
144    * is combined with fade in animations for new elements and fade out
145    * animations for old elements (which are automatically removed at animation
146    * end).
147    * </p>
148    * @param context specifies new and old elements.
149    */
150   static void doOrthogonalLayout( final LayoutContext context ) {
151 
152     if(containsGroups(context.getGraph2D())) {
153       doGroupedOrthogonalLayout(context);
154       return;
155     }
156     
157     final OrthogonalLayouter ol = new OrthogonalLayouter();
158     ol.setGrid(10);
159 
160     if (context.isFromSketch()) {
161       ol.setLayoutStyle(OrthogonalLayouter.NORMAL_TREE_STYLE);
162 
163       final PartialLayouter pl = new PartialLayouter(ol);
164       pl.setEdgeRoutingStrategy(PartialLayouter.EDGE_ROUTING_STRATEGY_ORTHOGONAL);
165       pl.setLayoutOrientation(PartialLayouter.ORIENTATION_NONE);
166       pl.setConsiderNodeAlignment(false);
167       pl.setMinimalNodeDistance(20);
168       ((OrthogonalEdgeRouter)pl.getEdgeRouter()).setCrossingCost(2);
169     
170       final LayoutGraph filteredGraph = context.getGraph2D();
171       filteredGraph.addDataProvider(
172               PartialLayouter.PARTIAL_NODES_DPKEY, new DataProviderAdapter() {
173                 public boolean getBool( final Object dataHolder ) {
174                   return context.isNewNode((Node) dataHolder);
175                 }
176               });
177 
178       filteredGraph.addDataProvider(
179               PartialLayouter.PARTIAL_EDGES_DPKEY, new DataProviderAdapter() {
180                 public boolean getBool( final Object dataHolder ) {
181                   return context.isNewEdge((Edge) dataHolder);
182                 }
183               });
184 
185       doLayout(pl, context);
186 
187       filteredGraph.removeDataProvider(PartialLayouter.PARTIAL_NODES_DPKEY);
188       filteredGraph.removeDataProvider(PartialLayouter.PARTIAL_EDGES_DPKEY);
189     } else {
190       doLayout(ol, context);
191     }
192   }    
193 
194   /**
195    * Arranges the graph in a hierarchical fashion.
196    * <p>
197    * This layout calculation is animated. Moreover, the layout animation
198    * is combined with fade in animations for new elements and fade out
199    * animations for old elements (which are automatically removed at animation
200    * end).
201    * </p>
202    * @param context specifies new and old elements.
203    */
204   static void doHierarchicLayout( final LayoutContext context ) {
205     final IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();
206     ihl.setLayoutOrientation(LayoutOrientation.LEFT_TO_RIGHT);    
207     ihl.setOrthogonallyRouted(true);
208    
209     final LayoutGraph filteredGraph = context.getGraph2D();
210     if (context.isFromSketch()) {
211       final DataMap obj2Hint = Maps.createHashedDataMap();
212       filteredGraph.addDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY, obj2Hint);
213       ihl.setLayoutMode(IncrementalHierarchicLayouter.LAYOUT_MODE_INCREMENTAL);
214       final IncrementalHintsFactory ihf = ihl.createIncrementalHintsFactory();
215       for (Iterator it = context.newNodes(); it.hasNext();) {
216         final Object viewNode = it.next();
217         obj2Hint.set(viewNode, ihf.createLayerIncrementallyHint(viewNode));
218       }
219       for (Iterator it = context.newEdges(); it.hasNext();) {
220         final Object viewEdge = it.next();
221         obj2Hint.set(viewEdge, ihf.createSequenceIncrementallyHint(viewEdge));
222       }
223     }
224 
225     doLayout(ihl, context);
226 
227     if (context.isFromSketch()) {
228       filteredGraph.removeDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY);
229     }
230   }
231 
232   /**
233    * Arranges the graph in a balloon-like fashion.
234    * <p>
235    * <b>Note:</b> The graph that is laid out has to be a <em>tree</em>.
236    * </p><p>
237    * This layout calculation is animated. Moreover, the layout animation
238    * is combined with fade in animations for new elements and fade out
239    * animations for old elements (which are automatically removed at animation
240    * end).
241    * </p>
242    * @param context specifies new and old elements.
243    */
244   static void doBalloonLayout( final LayoutContext context ) {
245 
246     final CompositeLayoutStage cls = new CompositeLayoutStage();
247  
248     final BalloonLayouter bl = new BalloonLayouter();
249     bl.setFromSketchModeEnabled(context.isFromSketch());
250     bl.setAllowOverlaps(false);
251 
252     final SelfLoopLayouter sll = new SelfLoopLayouter();
253     sll.setSmartSelfloopPlacementEnabled(true);
254     sll.setLayoutStyle(SelfLoopLayouter.STYLE_ROUNDED);
255     cls.appendStage(sll);
256  
257     final ParallelEdgeLayouter pl = new ParallelEdgeLayouter();    
258     pl.setUsingAdaptiveLineDistances(true);
259     cls.appendStage(pl);
260     
261     final TreeReductionStage trs = new TreeReductionStage();
262     cls.appendStage(trs);
263     
264     cls.setCoreLayouter(bl);
265 
266     if(context.isGroupingMode()) {
267       doLayout(new RecursiveGroupLayouter(cls), context);
268     }
269     else {
270       doLayout(cls, context);
271     }
272   }
273 
274   /**
275    * Arranges the graph in a circular fashion.
276    * <p>
277    * This layout calculation is animated. Moreover, the layout animation
278    * is combined with fade in animations for new elements and fade out
279    * animations for old elements (which are automatically removed at animation
280    * end).
281    * </p>
282    * @param context specifies new and old elements.
283    */
284   static void doCircularLayout( final LayoutContext context ) {
285 
286     final CircularLayouter cl = new CircularLayouter();
287     cl.setFromSketchModeEnabled(context.isFromSketch());
288 
289     cl.setPlaceChildrenOnCommonRadiusEnabled(false);
290     cl.getBalloonLayouter().setMinimalNodeDistance(20);
291     
292     final SelfLoopLayouter sll = (SelfLoopLayouter) cl.getSelfLoopLayouter();
293     sll.setSmartSelfloopPlacementEnabled(true);
294     sll.setLayoutStyle(SelfLoopLayouter.STYLE_ROUNDED);
295 
296     if(context.isGroupingMode()) {
297       doLayout(new RecursiveGroupLayouter(cl), context);
298     }
299     else {
300       doLayout(cl, context);
301     }
302   }
303 
304   /**
305    * Arranges the graph in organic layout style.
306    * <p>
307    * This layout calculation is animated. Moreover, the layout animation
308    * is combined with fade in animations for new elements and fade out
309    * animations for old elements (which are automatically removed at animation
310    * end).
311    * </p>
312    * @param context specifies new and old elements.
313    */
314   static void doOrganicLayout( final LayoutContext context ) {
315 
316     final SmartOrganicLayouter sol = new SmartOrganicLayouter();
317     sol.setDeterministic(true);
318     sol.setMinimalNodeDistance(30);
319     sol.setNodeOverlapsAllowed(false);
320     sol.setPreferredEdgeLength(50);
321     sol.setSmartComponentLayoutEnabled(true);
322 
323     if (context.isFromSketch()) {
324       final PartialLayouter pl = new PartialLayouter(sol);
325       pl.setEdgeRoutingStrategy(PartialLayouter.EDGE_ROUTING_STRATEGY_STRAIGHTLINE);
326       pl.setLayoutOrientation(PartialLayouter.ORIENTATION_NONE);
327       pl.setConsiderNodeAlignment(false);
328       pl.setMinimalNodeDistance(20);
329 
330       final LayoutGraph filteredGraph = context.getGraph2D();
331       filteredGraph.addDataProvider(
332               PartialLayouter.PARTIAL_NODES_DPKEY, new DataProviderAdapter() {
333                 public boolean getBool( final Object dataHolder ) {
334                   return context.isNewNode((Node) dataHolder);
335                 }
336               });
337 
338       final SelfLoopLayouter ssl = new SelfLoopLayouter();
339       ssl.setLayoutStyle(SelfLoopLayouter.STYLE_ROUNDED);
340       ssl.setSmartSelfloopPlacementEnabled(true);
341 
342       if(context.isGroupingMode()) {
343         final GroupedShuffleLayouter gsl = new GroupedShuffleLayouter();
344         gsl.setCoreLayouter(pl);
345         ((ShuffleLayouter)gsl.getShuffleLayouter()).setMinimalNodeDistance(20);
346         doLayout(new CompositeLayouter(ssl, gsl), context);
347       }
348       else {
349         doLayout(new CompositeLayouter(ssl, pl), context);
350       }
351       filteredGraph.removeDataProvider(PartialLayouter.PARTIAL_NODES_DPKEY);
352     } else {
353       doLayout(sol, context);
354     }
355   }
356 
357   /**
358    * Arranges the graph using the specified layout algorithm.
359    * @param layouter the layout algorithm to arrange the graph.
360    * @param context specifies the new and old elements.
361    */
362   private static void doLayout( final Layouter layouter, final LayoutContext context ) {
363     if (context.isAnimated()) {
364       doLayoutAnimated(layouter, context);
365     } else {
366       final Graph2D filteredGraph = context.getGraph2D();
367 
368       FilteringLayouter.markElements(filteredGraph, context);
369 
370       (new Graph2DLayoutExecutor()).doLayout(filteredGraph, new FilteringLayouter(layouter));
371 
372       FilteringLayouter.unmarkElements(filteredGraph);
373     }
374   }
375 
376   /**
377    * Arranges the graph using the specified layout algorithm.
378    * The layout calculation is animated. The layout animation is combined with
379    * fade in animations for new elements and fade out animations for old
380    * elements (which are automatically removed at animation end).
381    * @param layouter the layout algorithm to arrange the graph.
382    * @param context specifies the new and old elements.
383    */
384   private static void doLayoutAnimated( final Layouter layouter, final LayoutContext context ) {
385     final Graph2D filteredGraph = context.getGraph2D();
386 
387     FilteringLayouter.markElements(filteredGraph, context);
388 
389     final Graph2DLayoutExecutor graph2DLayoutExecutor =
390             new Graph2DLayoutExecutor(Graph2DLayoutExecutor.ANIMATED) {
391               protected AnimationObject createAnimation(
392                       final Graph2DView view,
393                       final Graph2D graph,
394                       final GraphLayout graphLayout
395               ) {
396                 // guarantees that fade out animations which are added to the
397                 // composite are disposed in the order of addition
398                 // therefore, all edges which are faded out are removed
399                 // before any of the nodes which are faded out are removed
400                 // (otherwise edges connected to nodes which have been faded out
401                 // would already be removed when their animation is disposed
402                 // resulting in IllegalArgumentExceptions)
403                 final CompositeLayoutAnimation composite =
404                         new CompositeLayoutAnimation(
405                                 graph,
406                                 super.createAnimation(view, graph, graphLayout));
407                 final long pd = composite.preferredDuration();
408 
409                 final ViewAnimationFactory factory = new ViewAnimationFactory(view);
410                 factory.setQuality(ViewAnimationFactory.HIGH_PERFORMANCE);
411                 for (Iterator it = context.newEdges(); it.hasNext();) {
412                   final Edge edge = (Edge) it.next();
413                   if (!context.isOldEdge(edge)) {
414                     final EdgeRealizer er = graph.getRealizer(edge);
415                     composite.addAnimation(factory.fadeIn(er, pd));
416                   }
417                 }
418                 for (Iterator it = context.removedEdges(); it.hasNext();) {
419                   final EdgeRealizer er = graph.getRealizer((Edge) it.next());
420                   composite.addAnimation(factory.fadeOut(
421                           er, ViewAnimationFactory.APPLY_EFFECT, pd));
422                 }
423                 for (Iterator it = context.newNodes(); it.hasNext();) {
424                   final Node node = (Node) it.next();
425                   if (!context.isOldNode(node)) {
426                     final NodeRealizer nr = graph.getRealizer(node);
427                     composite.addNodeAnimation(node, factory.fadeIn(nr, pd));
428                   }
429                 }
430                 for (Iterator it = context.removedNodes(); it.hasNext();) {
431                   final Node node = (Node) it.next();
432                   final NodeRealizer nr = graph.getRealizer(node);
433                   composite.addNodeAnimation(node, factory.fadeOut(
434                           nr, ViewAnimationFactory.APPLY_EFFECT, pd));
435                 }
436 
437                 return composite;
438               }
439             };
440     final LayoutMorpher morpher = graph2DLayoutExecutor.getLayoutMorpher();
441     if (context.isFromSketch()) {
442       morpher.setKeepZoomFactor(true);
443       morpher.setSmoothViewTransform(false);
444       morpher.setFocusNode(null);
445     } else {
446       morpher.setSmoothViewTransform(true);
447     }
448     morpher.setPreferredDuration(DURATION_EXPLORE);
449     graph2DLayoutExecutor.doLayout(context.getView(), new FilteringLayouter(layouter));
450 
451     FilteringLayouter.unmarkElements(filteredGraph);
452   }
453 
454 
455   /**
456    * Decorator for layout algorithms that hides specifically marked elements
457    * from its core layout algorithm.
458    * @see #IGNORED_EDGES_DPKEY
459    * @see #IGNORED_NODES_DPKEY
460    */
461   static final class FilteringLayouter implements Layouter {
462     /**
463      * Key to register a data provider that marks edges to hide from the
464      * core layout algorithm. For each edge in the graph, the data provider's
465      * {@link DataProvider#getBool(Object)} method determines whether or not
466      * the edge has to be hidden.
467      * A data provider registered with this key <b>is required</b>.
468      */
469     static final String IGNORED_EDGES_DPKEY =
470             "FilteringLayouter.IGNORED_EDGES_DPKEY";
471     /**
472      * Key to register a data provider that marks nodes to hide from the
473      * core layout algorithm. For each node in the graph, the data provider's
474      * {@link DataProvider#getBool(Object)} method determines whether or not
475      * the node has to be hidden.
476      * A data provider registered with this key <b>is required</b>.
477      */
478     static final String IGNORED_NODES_DPKEY =
479             "FilteringLayouter.IGNORED_NODES_DPKEY";
480 
481     private final Layouter core;
482 
483     FilteringLayouter( final Layouter core ) {
484       this.core = new FixNodeLayoutStage(core);
485     }
486 
487     public boolean canLayout( final LayoutGraph graph ) {
488       return core.canLayout(graph);
489     }
490 
491     /**
492      * Calculates a new layout for the specified graph after hiding marked. 
493      * elements.
494      * @param graph the graph to be laid out.
495      * @see #IGNORED_EDGES_DPKEY
496      * @see #IGNORED_NODES_DPKEY
497      */
498     public void doLayout( final LayoutGraph graph ) {
499       final GraphHider hider = new GraphHider(graph);
500 
501       // hide marked edges
502       final DataProvider edp = graph.getDataProvider(IGNORED_EDGES_DPKEY);
503       for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
504         final Edge edge = ec.edge();
505         if (edp.getBool(edge)) {
506           hider.hide(edge);
507         }
508       }
509       // hide marked nodes
510       final DataProvider ndp = graph.getDataProvider(IGNORED_NODES_DPKEY);
511       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
512         final Node node = nc.node();
513         if (ndp.getBool(node)) {
514           hider.hide(node);
515         }
516       }
517 
518       try {
519         core.doLayout(graph);
520       } finally {
521         // restore original graph structure
522         hider.unhideAll();
523       }
524     }
525 
526     /**
527      * Marks the elements to be removed as ignored for layout calculation and
528      * the fix node as fixed.
529      * @param graph the graph whose elements are marked.
530      * @param context specifies the elements to be removed as well as the
531      * fix node.
532      * @see #unmarkElements(y.layout.LayoutGraph)
533      * @see #IGNORED_EDGES_DPKEY
534      * @see #IGNORED_NODES_DPKEY
535      * @see FixNodeLayoutStage#FIXED_NODE_DPKEY
536      * @see LayoutContext#isRemovedEdge(y.base.Edge)
537      * @see LayoutContext#isRemovedNode(y.base.Node)
538      */
539     static void markElements(
540             final LayoutGraph graph, final LayoutContext context
541     ) {
542       graph.addDataProvider(
543               FixNodeLayoutStage.FIXED_NODE_DPKEY, new DataProviderAdapter() {
544                 public boolean getBool( final Object dataHolder ) {
545                   return dataHolder == context.getFixedNode();
546                 }
547               });
548 
549       graph.addDataProvider(
550               IGNORED_NODES_DPKEY, new DataProviderAdapter() {
551                 public boolean getBool( final Object dataHolder ) {
552                   return context.isRemovedNode((Node) dataHolder);
553                 }
554               });
555       graph.addDataProvider(
556               IGNORED_EDGES_DPKEY, new DataProviderAdapter() {
557                 public boolean getBool( final Object dataHolder ) {
558                   return context.isRemovedEdge((Edge) dataHolder);
559                 }
560               });
561     }
562 
563     /**
564      * Removes the markers for ignored and fixed elements.
565      * @param graph the graph whose elements were marked.
566      * @see #markElements(y.layout.LayoutGraph, LayoutContext)
567      * @see #IGNORED_EDGES_DPKEY
568      * @see #IGNORED_NODES_DPKEY
569      * @see FixNodeLayoutStage#FIXED_NODE_DPKEY
570      */
571     static void unmarkElements( final LayoutGraph graph ) {
572       graph.removeDataProvider(FixNodeLayoutStage.FIXED_NODE_DPKEY);
573       graph.removeDataProvider(IGNORED_EDGES_DPKEY);
574       graph.removeDataProvider(IGNORED_NODES_DPKEY);
575     }
576   }
577 
578 
579   /**
580    * Composite animation that guarantees that animations are disposed in the
581    * order they are/were added.
582    */
583   static final class CompositeLayoutAnimation implements CompositeAnimationObject {
584     private final Graph2D graph;
585     private final AnimationObject morpher;
586     private final List animations;
587     private final Map elements;
588 
589     CompositeLayoutAnimation( final Graph2D graph, final AnimationObject morpher ) {
590       this.graph = graph;
591       this.morpher = morpher;
592       animations = new ArrayList();
593       elements = new HashMap();
594     }
595 
596     void addNodeAnimation( final Node node, final AnimationObject ao ) {
597       elements.put(ao, node);
598       addAnimation(ao);
599     }
600 
601     /*
602      * ###################################################################
603      * CompositeAnimationObject
604      * ###################################################################
605      */
606 
607     public void addAnimation( final AnimationObject ao ) {
608       animations.add(ao);
609     }
610 
611     public void removeAnimation( final AnimationObject ao ) {
612       animations.remove(ao);
613     }
614 
615     public boolean isEmpty() {
616       return false;
617     }
618 
619     /*
620      * ###################################################################
621      * AnimationObject
622      * ###################################################################
623      */
624 
625     public void disposeAnimation() {
626       morpher.disposeAnimation();
627 
628       for (Iterator it = animations.iterator(); it.hasNext();) {
629         ((AnimationObject) it.next()).disposeAnimation();
630       }
631     }
632 
633     public void calcFrame( final double time ) {
634       for (Iterator it = animations.iterator(); it.hasNext();) {
635         ((AnimationObject) it.next()).calcFrame(time);
636       }
637 
638       morpher.calcFrame(time);
639     }
640 
641     public void initAnimation() {
642       final HierarchyManager hierarchy = graph.getHierarchyManager();
643       if (hierarchy == null) {
644         for (Iterator it = animations.iterator(); it.hasNext();) {
645           ((AnimationObject) it.next()).initAnimation();
646         }
647       } else {
648         // the order of initialization determines the paint order of the
649         // animation objects
650         // for nodes, it is important that animation effects of group nodes
651         // are painted *before* the animation effects of the child nodes
652         final HashMap depth = new HashMap();
653         final Integer edgeDepth = new Integer(Integer.MAX_VALUE);
654         final AnimationObject[] order = new AnimationObject[animations.size()];
655         int i = 0;
656         for (Iterator it = animations.iterator(); it.hasNext(); ++i) {
657           final AnimationObject ao = (AnimationObject) it.next();
658           order[i] = ao;
659           final Object e = elements.get(ao);
660           if (e == null) {
661             depth.put(ao, edgeDepth);
662           } else {
663             depth.put(ao, new Integer(hierarchy.getLocalGroupDepth((Node) e)));
664           }
665         }
666         Arrays.sort(order, new Comparator() {
667           public int compare( final Object o1, final Object o2 ) {
668             final int d1 = ((Integer) depth.get(o1)).intValue();
669             final int d2 = ((Integer) depth.get(o2)).intValue();
670             return Comparators.compare(d1, d2);
671           }
672         });
673         for (int j = 0; j < order.length; ++j) {
674           order[j].initAnimation();
675         }
676       }
677 
678       morpher.initAnimation();
679     }
680 
681     public long preferredDuration() {
682       return morpher.preferredDuration();
683     }
684   }
685 
686   static boolean containsGroups(Graph2D graph) {
687     HierarchyManager hm = graph.getHierarchyManager();
688     return hm != null && hm.containsGroups();
689   }
690 }
691