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.layout.tree;
15  
16  import demo.view.DemoBase;
17  import y.algo.GraphConnectivity;
18  import y.algo.Trees;
19  import y.base.DataMap;
20  import y.base.DataProvider;
21  import y.base.Edge;
22  import y.base.EdgeCursor;
23  import y.base.EdgeList;
24  import y.base.Node;
25  import y.base.NodeCursor;
26  import y.base.NodeList;
27  import y.base.NodeMap;
28  import y.geom.YPoint;
29  import y.layout.AbstractLayoutStage;
30  import y.layout.LayoutGraph;
31  import y.layout.LayoutOrientation;
32  import y.layout.LayoutTool;
33  import y.layout.Layouter;
34  import y.layout.NodeLayout;
35  import y.layout.organic.SmartOrganicLayouter;
36  import y.layout.hierarchic.IncrementalHierarchicLayouter;
37  import y.layout.hierarchic.incremental.IncrementalHintsFactory;
38  import y.layout.hierarchic.incremental.SimplexNodePlacer;
39  import y.layout.tree.BalloonLayouter;
40  import y.layout.tree.TreeLayouter;
41  import y.layout.tree.XCoordComparator;
42  import y.util.DataProviderAdapter;
43  import y.util.Maps;
44  import y.util.DataProviders;
45  import y.view.EdgeRealizer;
46  import y.view.EditMode;
47  import y.view.Graph2D;
48  import y.view.LineType;
49  import y.view.NavigationMode;
50  import y.view.NodeLabel;
51  import y.view.NodeRealizer;
52  import y.view.SmartNodeLabelModel;
53  import y.view.ViewMode;
54  import y.view.Graph2DLayoutExecutor;
55  
56  import javax.swing.AbstractAction;
57  import javax.swing.ButtonGroup;
58  import javax.swing.Icon;
59  import javax.swing.JLabel;
60  import javax.swing.JMenu;
61  import javax.swing.JMenuBar;
62  import javax.swing.JToggleButton;
63  import javax.swing.JToolBar;
64  import javax.swing.SwingUtilities;
65  
66  import java.awt.Color;
67  import java.awt.Component;
68  import java.awt.Dimension;
69  import java.awt.Graphics;
70  import java.awt.Insets;
71  import java.awt.EventQueue;
72  import java.awt.event.ActionEvent;
73  import java.awt.event.MouseEvent;
74  import java.net.URL;
75  import java.util.Locale;
76  import java.util.WeakHashMap;
77  import java.util.HashSet;
78  
79  /**
80   * This demo shows how to collapse and expand sub trees by simply clicking on
81   * a root node. Several different layout algorithms can be chosen:
82   * {@link y.layout.tree.TreeLayouter},
83   * {@link y.layout.tree.BalloonLayouter},
84   * {@link y.layout.organic.SmartOrganicLayouter} and
85   * {@link y.layout.hierarchic.IncrementalHierarchicLayouter}.
86   */
87  public class CollapsibleTreeDemo extends DemoBase {
88    public static final byte STYLE_TREE = 1;
89    public static final byte STYLE_BALLOON = 2;
90    private static final byte STYLE_ORGANIC = 3;
91    private static final byte STYLE_HIERARCHIC = 4;
92  
93    private static final Color LEAF_COLOR = new Color(154, 205, 54);
94    private static final Color COLLAPSIBLE_COLOR = new Color(154, 205, 255);
95    private static final Color EXPANDABLE_COLOR = new Color(255, 154, 0);
96  
97    static final Icon expandableIcon;
98    static final Icon collapsibleIcon;
99  
100   static {
101     collapsibleIcon = new Icon(){
102       public void paintIcon(Component c, Graphics g, int x, int y) {
103         Color col = g.getColor();
104         g.setColor(Color.white);
105         g.fillRect(x + 1, y + 1, 19, 9);
106         g.setColor(Color.darkGray);
107         g.fillRect(x + 3, y + 3, 15, 5);
108         g.setColor(Color.gray);
109         g.setColor(col);
110       }
111 
112       public int getIconWidth() {
113         return 18;
114       }
115 
116       public int getIconHeight() {
117         return 9;
118       }
119     };
120 
121     expandableIcon = new Icon(){
122       public void paintIcon(Component c, Graphics g, int x, int y) {
123         Color col = g.getColor();
124         g.setColor(Color.white);
125         g.fillRect(x + 6, y + 1, 9, 19);
126         g.fillRect(x + 1, y + 6, 19, 9);
127         g.setColor(Color.darkGray);
128         g.fillRect(x + 3, y + 8, 15, 5);
129         g.fillRect(x + 8, y + 3, 5, 15);
130         g.setColor(Color.gray);
131         g.setColor(col);
132       }
133 
134       public int getIconWidth() {
135         return 18;
136       }
137 
138       public int getIconHeight() {
139         return 18;
140       }
141     };
142   }
143 
144   private byte style = STYLE_TREE;
145   private TreeLayouter treeLayouter;
146   private BalloonLayouter balloonLayouter;
147   private SmartOrganicLayouter organicLayouter;
148   private IncrementalHierarchicLayouter hierarchicLayouter;
149   private CollapsibleTreeDemo.CollapseExpandViewMode viewMode;
150   private DataMap ihlHintMap;
151   private IncrementalHintsFactory hintsFactory;
152 
153   public CollapsibleTreeDemo() {
154     Graph2D graph = view.getGraph2D();
155     
156     //create a sample tree structure
157     createTree(graph);
158 
159     //collapse/expand some nodes
160     viewMode.collapseSubtree(graph, Trees.getRoot(graph));
161     Node root = Trees.getRoot(graph);
162     viewMode.expandSubtree(graph, root, 2);
163 
164     //configure layouters
165     treeLayouter = new TreeLayouter();
166     treeLayouter.setComparator(new XCoordComparator()); //important to keep node order of collapsed/expanded items.
167     treeLayouter.setLayoutOrientation(LayoutOrientation.LEFT_TO_RIGHT);
168     treeLayouter.setLayoutStyle(TreeLayouter.ORTHOGONAL_STYLE);
169 
170     balloonLayouter = new BalloonLayouter();
171     balloonLayouter.setFromSketchModeEnabled(true);
172     balloonLayouter.setCompactnessFactor(0.1);
173     balloonLayouter.setAllowOverlaps(true);
174 
175     organicLayouter = new SmartOrganicLayouter();
176     organicLayouter.setScope(SmartOrganicLayouter.SCOPE_MAINLY_SUBSET);
177     organicLayouter.setMinimalNodeDistance(20);
178 
179     hierarchicLayouter = new IncrementalHierarchicLayouter();
180     hierarchicLayouter.setOrthogonallyRouted(true);
181     hierarchicLayouter.setLayoutOrientation(LayoutOrientation.TOP_TO_BOTTOM);
182     // read the "old" nodes from the sketch
183     hierarchicLayouter.setLayoutMode(IncrementalHierarchicLayouter.LAYOUT_MODE_INCREMENTAL);
184     ((SimplexNodePlacer) hierarchicLayouter.getNodePlacer()).setBaryCenterModeEnabled(true);
185 
186     // create a map to store the hints for the incremental layout mechanism
187     ihlHintMap = Maps.createHashedDataMap();
188     graph.addDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY, ihlHintMap);
189     // get a reference to a hints factory
190     hintsFactory = hierarchicLayouter.createIncrementalHintsFactory();
191 
192     //layout the graph
193     SwingUtilities.invokeLater(new Runnable() {
194       public void run() {
195         layout(view.getGraph2D(), null, true);
196       }
197     });
198   }
199   
200   protected void configureDefaultRealizers() {
201     super.configureDefaultRealizers();
202     NodeRealizer nr = view.getGraph2D().getDefaultNodeRealizer();
203     nr.setSize(80, 30);
204     NodeLabel nl = nr.createNodeLabel();
205     nr.addLabel(nl);
206     nr.setLineColor(null);
207     nl.setIcon(collapsibleIcon);
208     nl.setIconTextGap((byte) 0);
209     SmartNodeLabelModel model = new SmartNodeLabelModel();
210     nl.setLabelModel(model);
211     nl.setModelParameter(model.createDiscreteModelParameter(SmartNodeLabelModel.POSITION_CENTER));
212     nl.setInsets(new Insets(4, 4, 4, 4));
213     nl.setDistance(0);    
214     EdgeRealizer er = view.getGraph2D().getDefaultEdgeRealizer();
215     er.setLineType(LineType.LINE_2);
216     er.setLineColor(Color.gray);
217   }
218   
219   protected void loadGraph(URL resource) {
220     super.loadGraph(resource);
221     Graph2D graph = view.getGraph2D();
222     viewMode.collapseSubtree(graph, Trees.getRoot(graph));
223     Node root = Trees.getRoot(graph);
224     viewMode.expandSubtree(graph, root, 2);
225     layout(graph, null, true);
226   }
227   
228   protected void initialize() {  
229     super.initialize();
230     view.setPreferredSize(new Dimension(900,600));
231   }
232   
233   /** EditMode not supported by this demo. */
234   protected EditMode createEditMode() {
235     return null;
236   }
237 
238   /** Register CollapseExpandViewMode and NavigationMode to support panning */
239   protected void registerViewModes() {
240     viewMode = new CollapseExpandViewMode();    
241     view.addViewMode(viewMode); 
242     NavigationMode navigationMode = new NavigationMode();
243     view.addViewMode(navigationMode);
244   }
245 
246   /** Create menu bar for this demo */
247   protected JMenuBar createMenuBar() {
248     JMenuBar menuBar = new JMenuBar();
249     JMenu menu = new JMenu("File");
250     menu.add(new PrintAction());
251     menu.addSeparator();
252     menu.add(new ExitAction());
253     menuBar.add(menu);
254     return menuBar;
255   }
256 
257   /**
258    * A ViewMode that allows to expand and collapse the subtrees rooted at a node by simply clicking on the node.
259    * Clicking on a node, while the CTRL modifier key is pushed, will expand/collapse all nodes in the subtree. Note that this view mode
260    * is also responsible to keeping track of the expansion state of each node.
261    */
262   class CollapseExpandViewMode extends ViewMode {
263     NodeMap collapsedEdges = Maps.createNodeMap(new WeakHashMap());
264     NodeMap collapsedState = Maps.createNodeMap(new WeakHashMap());
265 
266     public void mouseClicked(MouseEvent ev) {
267       //if (ev.getClickCount() != 2) return;
268       Node node = getHitInfo(ev).getHitNode();
269 
270       if (node != null) {
271         prepareForLayout(view.getGraph2D(), node);
272         if (collapsedState.getBool(node)) {
273           if (ev.isControlDown()) {//ctrl is pressed expand whole subtree (max depth of 10000) of current node
274             expandSubtree(getGraph2D(), node, 10000);
275           } else {//ctrl is not pressed expand only current node
276             expandNode(getGraph2D(), node);
277           }
278         } else {
279           if (ev.isControlDown()) {//ctrl is pressed collapse whole subtree of current node
280             collapseSubtree(getGraph2D(), node);
281           } else {//ctrl is not pressed collapse only current node
282             collapseNode(getGraph2D(), node);
283           }
284         }
285         layout(getGraph2D(), node, false);
286       } 
287     }
288 
289     /**
290      * Collapses the given node and it's whole subtree.
291      *
292      * @param graph the graph, the root node belongs to.
293      * @param root  the node whose subtree is to be collapsed.
294      */
295     public void collapseSubtree(Graph2D graph, Node root) {
296       NodeList list = GraphConnectivity.getSuccessors(graph, new NodeList(root), graph.N());
297       NodeCursor nodeCursor = list.nodes();
298       for (nodeCursor.toLast(); nodeCursor.ok(); nodeCursor.prev()) {
299         Node node = nodeCursor.node();
300         if (!collapsedState.getBool(node) && node != root) {
301           collapseNode(graph, node);
302         }
303       }
304       collapseNode(graph, root);
305     }
306 
307     /**
308      * collapses the given node.
309      *
310      * @param graph the graph, the root node belongs to.
311      * @param root  the node which is to be collapsed.
312      */
313     public void collapseNode(Graph2D graph, final Node root) {
314       EdgeList edgeList = collapsedEdges.get(root) != null ? (EdgeList) collapsedEdges.get(root) : new EdgeList();
315       edgeList.addAll(root.outEdges());
316       NodeList collapsedNodes = GraphConnectivity.getSuccessors(graph, new NodeList(root), graph.N());
317 
318       for (NodeCursor nc = collapsedNodes.nodes(); nc.ok(); nc.next()) {
319         Node n = nc.node();
320         edgeList.addAll(n.outEdges());
321         double x = graph.getCenterX(n) - graph.getCenterX(root);
322         double y = graph.getCenterY(n) - graph.getCenterY(root);
323 
324         // store relative location to root
325         graph.getRealizer(n).setLocation(0.01 * x, 0.01 * y);
326 
327         //remove node from graph
328         graph.hide(n);
329       }
330       collapsedState.setBool(root, true);
331       collapsedEdges.set(root, edgeList);
332       
333       if (!edgeList.isEmpty()) {
334         NodeRealizer rootR = getGraph2D().getRealizer(root);
335         if(rootR.labelCount() > 1) {
336           getGraph2D().getRealizer(root).getLabel(1).setIcon(expandableIcon);
337         }
338         rootR.setFillColor(EXPANDABLE_COLOR);
339       }
340     }
341 
342     /**
343      * Expands a node and it's subtree to a given depth.
344      *
345      * @param graph the graph, the root node belongs to.
346      * @param root  the node whose subtree is to be expanded.
347      * @param depth determines the depth (how many layers) till which the subtree should be expanded.
348      */
349     public void expandSubtree(Graph2D graph, Node root, int depth) {
350       if (depth <= 0) {
351         return;
352       }
353       //expand the root
354       expandNode(graph, root);
355       NodeList list = GraphConnectivity.getSuccessors(graph, new NodeList(root), depth);
356       for (NodeCursor nodeCursor = list.nodes(); nodeCursor.ok(); nodeCursor.next()) {
357         Node node = nodeCursor.node();
358         if (collapsedState.getBool(node)) {
359           //expand the subtree
360           expandSubtree(graph, node, depth - 1);
361         }
362       }
363     }
364 
365     /**
366      * Expands a single node.
367      *
368      * @param graph the graph, the root node belongs to.
369      * @param root  the node which is to be expanded.
370      */
371     public void expandNode(Graph2D graph, Node root) {
372       final EdgeList edgeList = (EdgeList) collapsedEdges.get(root);
373       if (edgeList != null) {
374         for (EdgeCursor ec = edgeList.edges(); ec.ok(); ec.next()) {
375           Edge e = ec.edge();
376           if (!graph.contains(e.source())) {
377             graph.unhide(e.source());
378             graph.setLocation(e.source(), graph.getX(root) + graph.getX(e.source()),
379                 graph.getY(root) + graph.getY(e.source()));
380           }
381           if (!graph.contains(e.target())) {
382             graph.unhide(e.target());
383             graph.setLocation(e.target(), graph.getX(root) + graph.getX(e.target()),
384                 graph.getY(root) + graph.getY(e.target()));
385           }
386           //inserts the edge into the graph
387           graph.unhide(e);
388           //cosmetics
389           graph.getRealizer(e).clearBends();
390         }
391         collapsedEdges.set(root, null);
392       }
393       collapsedState.setBool(root, false);
394 
395       if (root.outDegree() > 0) {
396         NodeRealizer rootR = getGraph2D().getRealizer(root);
397         if(rootR.labelCount() > 1) {
398           rootR.getLabel(1).setIcon(collapsibleIcon);
399         }
400         rootR.setFillColor(COLLAPSIBLE_COLOR);
401       }
402     }
403   }
404 
405   /**
406    * Layout the tree according to the set layout style.
407    *
408    * @param graph2D    the graph, which will be laid out.
409    * @param focusNode  the current focus.
410    * @param fitContent determines whether to fit the content to the current view. Should be prevented, if layout. is
411    *                   started due to a mouse click on a node.
412    */
413   void layout(Graph2D graph2D, final Node focusNode, boolean fitContent) {
414     //calculate layout according to chosen style
415     Layouter layouter = null;
416     switch (style) {
417       case CollapsibleTreeDemo.STYLE_TREE:
418         layouter = treeLayouter;
419         break;
420       case CollapsibleTreeDemo.STYLE_BALLOON:
421         layouter = balloonLayouter;
422         break;
423       case CollapsibleTreeDemo.STYLE_ORGANIC:
424         prepareForLayout(graph2D, focusNode);
425         layouter = organicLayouter;
426         break;
427       case CollapsibleTreeDemo.STYLE_HIERARCHIC:
428         prepareForLayout(graph2D, focusNode);
429         layouter = hierarchicLayouter;
430         break;
431       default:
432         layouter = treeLayouter;
433     }
434     
435     graph2D.addDataProvider(FocusNodeLayoutStage.FOCUS_NODE_DPKEY, FocusNodeLayoutStage.createFocusNodeDataProvider(focusNode));
436 
437     final Graph2DLayoutExecutor layoutExecutor = new Graph2DLayoutExecutor();
438     if (fitContent) {
439       layoutExecutor.getLayoutMorpher().setSmoothViewTransform(true);
440     } else {
441       layoutExecutor.getLayoutMorpher().setKeepZoomFactor(true);
442     }
443     layoutExecutor.getLayoutMorpher().setEasedExecution(true);
444     layoutExecutor.doLayout(view, new FocusNodeLayoutStage(layouter));
445   }
446 
447   public static class FocusNodeLayoutStage extends AbstractLayoutStage {
448     
449     public static final Object FOCUS_NODE_DPKEY = "FocusNodeStage#FOCUS_NODE_DPKEY";
450     
451     public FocusNodeLayoutStage(Layouter coreLayouter) {
452       super(coreLayouter);
453     }
454     
455     public boolean canLayout(LayoutGraph graph) {
456       return canLayoutCore(graph);
457     }
458 
459     public void doLayout(LayoutGraph graph) {
460       DataProvider dp = graph.getDataProvider(FOCUS_NODE_DPKEY);
461       if(dp != null) {
462         Node focusNode = null;
463         for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
464           Node n = nc.node();
465           if(dp.getBool(n)) {
466             focusNode = n;
467             break;
468           }
469         }
470         YPoint oldFocus = null;
471         if(focusNode != null) {
472           oldFocus = graph.getCenter(focusNode);
473           doLayoutCore(graph);
474           NodeLayout nl = graph.getNodeLayout(focusNode);
475           YPoint newFocus = new YPoint(nl.getX() + 0.5 * nl.getWidth(), nl.getY() + 0.5 * nl.getHeight());
476           double dx = newFocus.x - oldFocus.x;
477           double dy = newFocus.y - oldFocus.y;
478           LayoutTool.moveSubgraph(graph, graph.nodes(), -dx, -dy);            
479         } 
480         else {
481           doLayoutCore(graph);
482         }
483       }
484       else {
485         doLayoutCore(graph);
486       }  
487     }
488   
489     public static DataProvider createFocusNodeDataProvider(final Node focusNode) {
490       return new DataProviderAdapter() {
491         public boolean getBool(Object obj) {
492           return obj == focusNode;
493         }
494       };
495     }    
496   }
497   
498   private void prepareForLayout(Graph2D graph2D, Node node) {
499     if (node != null){
500       NodeList incrementalNodes = GraphConnectivity.getSuccessors(graph2D, new NodeList(node), graph2D.N());
501       final HashSet incrementalNodesSet = new HashSet(incrementalNodes);
502       // mark nodes as "new"
503       for (NodeCursor nodeCursor = incrementalNodes.nodes(); nodeCursor.ok(); nodeCursor.next()) {
504         ihlHintMap.set(nodeCursor.node(), hintsFactory.createLayerIncrementallyHint(nodeCursor.node()));
505       }
506       graph2D.addDataProvider(SmartOrganicLayouter.NODE_SUBSET_DATA, new DataProviderAdapter() {
507         public boolean getBool(Object dataHolder) {
508           return incrementalNodesSet.contains(dataHolder);
509         }
510       });
511       graph2D.addDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY, ihlHintMap);
512       organicLayouter.setScope(SmartOrganicLayouter.SCOPE_MAINLY_SUBSET);
513     } else {
514       graph2D.removeDataProvider(IncrementalHierarchicLayouter.INCREMENTAL_HINTS_DPKEY);
515       graph2D.addDataProvider(SmartOrganicLayouter.NODE_SUBSET_DATA, DataProviders.createConstantDataProvider(Boolean.FALSE));
516       organicLayouter.setScope(SmartOrganicLayouter.SCOPE_ALL);
517     }
518   }
519 
520 
521   /** Adds some buttons to the toolbar, to choose the layout style from. */
522   protected JToolBar createToolBar() {
523     JToolBar toolbar = super.createToolBar();
524     toolbar.addSeparator();
525     toolbar.add(new JLabel("Layout:"));
526     toolbar.addSeparator(TOOLBAR_SMALL_SEPARATOR);
527 
528     ButtonGroup group = new ButtonGroup();
529     JToggleButton b1 = new JToggleButton(new AbstractAction(
530             "Tree", SHARED_LAYOUT_ICON) {
531       public void actionPerformed(ActionEvent e) {
532         style = CollapsibleTreeDemo.STYLE_TREE;
533         layout(view.getGraph2D(), null, true);
534       }
535     });
536     b1.setSelected(true);
537     group.add(b1);
538     toolbar.add(b1);
539 
540 
541     JToggleButton b2 = new JToggleButton(new AbstractAction(
542             "Balloon", SHARED_LAYOUT_ICON) {
543       public void actionPerformed(ActionEvent e) {
544         style = CollapsibleTreeDemo.STYLE_BALLOON;
545         layout(view.getGraph2D(), null, true);
546       }
547     });
548     group.add(b2);
549     toolbar.add(b2);
550 
551     JToggleButton b3 = new JToggleButton(new AbstractAction(
552             "Organic", SHARED_LAYOUT_ICON) {
553       public void actionPerformed(ActionEvent e) {
554         style = CollapsibleTreeDemo.STYLE_ORGANIC;
555         layout(view.getGraph2D(), null, true);
556       }
557     });
558     group.add(b3);
559     toolbar.add(b3);
560 
561     JToggleButton b4 = new JToggleButton(new AbstractAction(
562             "Hierarchic", SHARED_LAYOUT_ICON) {
563       public void actionPerformed(ActionEvent e) {
564         style = CollapsibleTreeDemo.STYLE_HIERARCHIC;
565         Graph2D graph = view.getGraph2D();
566         layout(graph, Trees.getRoot(graph), true);
567       }
568     });
569     group.add(b4);
570     toolbar.add(b4);
571 
572     return toolbar;
573   }
574 
575   void createTree(Graph2D graph) {
576     NodeList queue = new NodeList();
577     queue.add(graph.createNode());
578     for (int i = 0; i < 50; i++) {
579       Node root = queue.popNode();
580       Node c1 = graph.createNode();
581       Edge e1 = graph.createEdge(root, c1);
582       Node c2 = graph.createNode();
583       Edge e2 = graph.createEdge(root, c2);
584       queue.add(c2);
585       queue.add(c1);
586       if (i == 25 || i == 40) {
587         for (int j = 0; j < 20; j++) {
588           Node c3 = graph.createNode();
589           Edge e3 = graph.createEdge(root, c3);
590           queue.add(c3);
591         }
592       }
593     }
594     for (NodeCursor nodeCursor = graph.nodes(); nodeCursor.ok(); nodeCursor.next()) {
595       Node node = nodeCursor.node();
596       if (node.outDegree() == 0) {
597         graph.getRealizer(node).getLabel(1).setIcon(null);
598         graph.getRealizer(node).setFillColor(LEAF_COLOR);
599       }
600     }
601   }
602 
603 
604   public static void main(String[] args) {
605     EventQueue.invokeLater(new Runnable() {
606       public void run() {
607         Locale.setDefault(Locale.ENGLISH);
608         initLnF();
609         (new CollapsibleTreeDemo()).start();
610       }
611     });
612   }
613 }