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