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.flowchart.layout;
15  
16  import y.base.DataProvider;
17  import y.base.Edge;
18  import y.base.EdgeCursor;
19  import y.base.EdgeMap;
20  import y.base.Graph;
21  import y.base.NodeMap;
22  import y.base.YCursor;
23  import y.geom.YDimension;
24  import y.layout.EdgeLabelLayout;
25  import y.layout.LayoutGraph;
26  import y.layout.LayoutOrientation;
27  import y.layout.Layouter;
28  import y.layout.hierarchic.IncrementalHierarchicLayouter;
29  import y.layout.hierarchic.incremental.ColumnDescriptor;
30  import y.layout.hierarchic.incremental.EdgeLayoutDescriptor;
31  import y.layout.hierarchic.incremental.HierarchicLayouter;
32  import y.layout.hierarchic.incremental.PartitionGrid;
33  import y.layout.hierarchic.incremental.RowDescriptor;
34  import y.layout.hierarchic.incremental.SimplexNodePlacer;
35  import y.layout.labeling.GreedyMISLabeling;
36  import y.util.Maps;
37  
38  /**
39   * An automatic layout algorithm for Flowchart diagrams. The different type of elements have to be marked with the
40   * DataProvider keys {@link #EDGE_TYPE_DPKEY} and {@link #NODE_TYPE_DPKEY}.
41   */
42  public class FlowchartLayouter implements Layouter {
43  
44    /**
45     * {@link y.base.DataProvider} key used to specify the flowchart specific type of each node. Valid are all node type
46     * constants specified by class {@link FlowchartElements}.
47     */
48    public static final Object NODE_TYPE_DPKEY =
49        "demo.view.flowchart.layout.FlowchartLayouter.NODE_TYPE_DPKEY";
50  
51    /**
52     * {@link y.base.DataProvider} key used to specify the flowchart specific type of each edge. Valid are all edge type
53     * constants specified by class {@link FlowchartElements}.
54     */
55    public static final Object EDGE_TYPE_DPKEY =
56        "demo.view.flowchart.layout.FlowchartLayouter.EDGE_TYPE_DPKEY";
57  
58    /**
59     * {@link y.base.DataProvider} key used to specify the preferred source port direction of an edge. Valid are direction
60     * type constants specified in this class.
61     */
62    public static final Object PREFERRED_DIRECTION_KEY =
63        "demo.view.flowchart.layout.FlowchartLayouter.DIRECTION_KEY";
64  
65    // TODO replace with PortCandidates constants or add documentation
66    public static final int DIRECTION_UNDEFINED = 0x0;
67    public static final int DIRECTION_WITH_THE_FLOW = 0x1;
68    public static final int DIRECTION_AGAINST_THE_FLOW = 0x2;
69    public static final int DIRECTION_LEFT_IN_FLOW = 0x4;
70    public static final int DIRECTION_RIGHT_IN_FLOW = 0x8;
71    public static final int DIRECTION_STRAIGHT = DIRECTION_WITH_THE_FLOW | DIRECTION_AGAINST_THE_FLOW;
72    public static final int DIRECTION_FLATWISE = DIRECTION_LEFT_IN_FLOW | DIRECTION_RIGHT_IN_FLOW;
73  
74    private boolean allowFlatwiseEdges;
75    private byte layoutOrientation;
76    private double laneInsets;
77    private double minimumEdgeLength;
78    private double minimumEdgeDistance;
79    private double minimumNodeDistance;
80    private double minimumPoolDistance;
81    private final double minimumLabelDistance;
82  
83    private FlowchartTransformerStage transformerStage;
84  
85    public FlowchartLayouter() {
86      transformerStage = new FlowchartTransformerStage();
87      layoutOrientation = LayoutOrientation.TOP_TO_BOTTOM;
88      laneInsets = 10.0;
89      minimumEdgeDistance = 15.0;
90      minimumEdgeLength = 30.0;
91      minimumLabelDistance = 20.0;
92      minimumNodeDistance = 30.0;
93      minimumPoolDistance = 30.0;
94    }
95  
96    /**
97     * Returns whether or not flatwise edges are allowed.
98     *
99     * @return whether or not flatwise edges are allowed.
100    */
101   public boolean isAllowFlatwiseEdges() {
102     return allowFlatwiseEdges;
103   }
104 
105   /**
106    * Sets whether or not flatwise edges are allowed.
107    *
108    * @param allow whether or not flatwise edges are allowed.
109    */
110   public void setAllowFlatwiseEdges(boolean allow) {
111     this.allowFlatwiseEdges = allow;
112   }
113 
114   /**
115    * Returns the insets used for swimlanes.
116    * <p/>
117    * Defaults to <code>10.0</code>.
118    *
119    * @see #setLaneInsets(double)
120    */
121   public double getLaneInsets() {
122     return laneInsets;
123   }
124 
125   /**
126    * Sets the insets for swimlanes, that is the distance between a graph element and the border of its enclosing
127    * swimlane.
128    * <p/>
129    * Defaults to <code>10.0</code>.
130    *
131    * @param laneInsets the distance between graph elements and the border of their enclosing swimlanes.
132    * @see #getLaneInsets()
133    */
134   public void setLaneInsets(double laneInsets) {
135     this.laneInsets = laneInsets;
136   }
137 
138   /**
139    * Returns the minimum distance between two node elements.
140    * <p/>
141    * Defaults to <code>30.0</code>.
142    *
143    * @see #setMinimumNodeDistance(double)
144    */
145   public double getMinimumNodeDistance() {
146     return minimumNodeDistance;
147   }
148 
149   /**
150    * Sets the minimum distance between two node elements.
151    * <p/>
152    * Defaults to <code>30.0</code>.
153    *
154    * @see #getMinimumNodeDistance()
155    */
156   public void setMinimumNodeDistance(double minimumNodeDistance) {
157     this.minimumNodeDistance = minimumNodeDistance;
158   }
159 
160   /**
161    * Returns the minimum distance between two edge elements.
162    * <p/>
163    * Defaults to <code>30.0</code>.
164    *
165    * @see #setMinimumEdgeDistance(double)
166    */
167   public double getMinimumEdgeDistance() {
168     return minimumEdgeDistance;
169   }
170 
171   /**
172    * Sets the minimum distance between two edge elements.
173    * <p/>
174    * Defaults to <code>30.0</code>.
175    *
176    * @see #getMinimumEdgeDistance()
177    */
178   public void setMinimumEdgeDistance(double minimumEdgeDistance) {
179     this.minimumEdgeDistance = minimumEdgeDistance;
180   }
181 
182   /**
183    * Returns the minimum length of edges.
184    * <p/>
185    * Defaults to <code>20.0</code>.
186    *
187    * @see #setMinimumEdgeLength(double)
188    */
189   public double getMinimumEdgeLength() {
190     return minimumEdgeLength;
191   }
192 
193   /**
194    * Sets the minimum length of edges.
195    * <p/>
196    * Defaults to <code>20.0</code>.
197    *
198    * @see #getMinimumEdgeLength()
199    */
200   public void setMinimumEdgeLength(double minimumEdgeLength) {
201     this.minimumEdgeLength = minimumEdgeLength;
202   }
203 
204   /**
205    * Returns the used minimum distance between two pool elements.
206    * <p/>
207    * Defaults to <code>50.0</code>.
208    *
209    * @see #setMinimumPoolDistance(double)
210    */
211   public double getMinimumPoolDistance() {
212     return minimumPoolDistance;
213   }
214 
215   /**
216    * Sets the minimum distance between two pool elements.
217    * <p/>
218    * Defaults to <code>50.0</code>.
219    *
220    * @see #getMinimumPoolDistance()
221    */
222   public void setMinimumPoolDistance(double distance) {
223     this.minimumPoolDistance = distance;
224   }
225 
226   /**
227    * Returns the layout orientation.
228    * <p/>
229    * Defaults to {@link LayoutOrientation#TOP_TO_BOTTOM}
230    *
231    * @see #setLayoutOrientation(byte)
232    */
233   public byte getLayoutOrientation() {
234     return layoutOrientation;
235   }
236 
237   /**
238    * Specifies the layout orientation.
239    * <p/>
240    * Defaults to {@link LayoutOrientation#TOP_TO_BOTTOM}.
241    *
242    * @param layoutOrientation one of {@link LayoutOrientation#TOP_TO_BOTTOM} and {@link LayoutOrientation#LEFT_TO_RIGHT}
243    * @throws IllegalArgumentException if the specified orientation does not match any of the layout orientation
244    *                                  constants defined in this class.
245    * @see #getLayoutOrientation()
246    */
247   public void setLayoutOrientation(byte layoutOrientation) {
248     switch (layoutOrientation) {
249       case LayoutOrientation.TOP_TO_BOTTOM:
250       case LayoutOrientation.LEFT_TO_RIGHT:
251         this.layoutOrientation = layoutOrientation;
252         break;
253       default:
254         throw new IllegalArgumentException("Invalid layout orientation: " + layoutOrientation);
255     }
256   }
257 
258   /**
259    * Returns <code>true</code>. This method does not check whether the specified graph can be laid out by this algorithm
260    * at all.
261    */
262   public boolean canLayout(LayoutGraph graph) {
263     return true;
264   }
265 
266   /**
267    * Layouts the specified graph.
268    */
269   public void doLayout(LayoutGraph graph) {
270     if (graph.isEmpty()) {
271       return;
272     }
273 
274     PartitionGrid grid = PartitionGrid.getPartitionGrid(graph);
275     if (grid != null) {
276       //adjust insets
277       for (YCursor cur = grid.getColumns().cursor(); cur.ok(); cur.next()) {
278         ColumnDescriptor column = (ColumnDescriptor) cur.current();
279         column.setLeftInset(laneInsets);
280         column.setRightInset(laneInsets);
281       }
282       for (YCursor cur = grid.getRows().cursor(); cur.ok(); cur.next()) {
283         RowDescriptor row = (RowDescriptor) cur.current();
284         row.setTopInset(laneInsets);
285         row.setBottomInset(laneInsets);
286       }
287     }
288 
289     try {
290       final IncrementalHierarchicLayouter ihl = configureHierarchicLayouter();
291 
292       transformerStage = new FlowchartTransformerStage();
293       transformerStage.setCoreLayouter(ihl);
294 
295       final NodeMap layerIds = Maps.createHashedNodeMap();
296       try {
297         graph.addDataProvider(HierarchicLayouter.LAYER_VALUE_HOLDER_DPKEY, layerIds);
298         ihl.getHierarchicLayouter().setAlgorithmProperty("HierarchicLayouter.stopAfterLayering", Boolean.TRUE);
299 
300         transformerStage.doLayout(graph);
301       } finally {
302         graph.removeDataProvider(HierarchicLayouter.LAYER_VALUE_HOLDER_DPKEY);
303         ihl.getHierarchicLayouter().setAlgorithmProperty("HierarchicLayouter.stopAfterLayering", Boolean.FALSE);
304       }
305 
306       final EdgeMap edge2LayoutDescriptor = Maps.createHashedEdgeMap();
307       for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
308         edge2LayoutDescriptor.set(ec.edge(), createEdgeLayoutDescriptor(ec.edge(), graph,
309             ihl.getEdgeLayoutDescriptor(), isHorizontalOrientation()));
310       }
311 
312       // do core layout
313       try {
314         graph.addDataProvider(FlowchartTransformerStage.LAYER_ID_DP_KEY, layerIds);
315         graph.addDataProvider(HierarchicLayouter.EDGE_LAYOUT_DESCRIPTOR_DPKEY, edge2LayoutDescriptor);
316 
317         transformerStage.doLayout(graph);
318       } finally {
319         graph.removeDataProvider(FlowchartTransformerStage.LAYER_ID_DP_KEY);
320         graph.removeDataProvider(HierarchicLayouter.EDGE_LAYOUT_DESCRIPTOR_DPKEY);
321       }
322 
323     } finally {
324       // remove key set by the FlowchartPortOptimizer
325       graph.removeDataProvider(FlowchartPortOptimizer.NODE_TO_ALIGN_DP_KEY);
326     }
327 
328     doLabelPlacement(graph);
329   }
330 
331   /**
332    * Returns an IncrementalHierarchicLayouter that is configured to fit this layouter's needs.
333    */
334   private IncrementalHierarchicLayouter configureHierarchicLayouter() {
335     IncrementalHierarchicLayouter ihl = new IncrementalHierarchicLayouter();
336     ihl.setOrthogonallyRouted(true);
337     ihl.setRecursiveGroupLayeringEnabled(false);
338     ihl.setComponentLayouterEnabled(false);
339     ihl.setMinimumLayerDistance(minimumNodeDistance);
340     ihl.setNodeToNodeDistance(minimumNodeDistance);
341     ihl.setEdgeToEdgeDistance(minimumEdgeDistance);
342     ihl.setBackloopRoutingEnabled(false);
343     ihl.setLayoutOrientation(isHorizontalOrientation() ?
344         LayoutOrientation.LEFT_TO_RIGHT : LayoutOrientation.TOP_TO_BOTTOM);
345     ihl.setIntegratedEdgeLabelingEnabled(false);
346     ihl.setConsiderNodeLabelsEnabled(true);
347 
348     final EdgeLayoutDescriptor descriptor = new EdgeLayoutDescriptor();
349     descriptor.setMinimumDistance(minimumEdgeDistance);
350     descriptor.setMinimumLength(15.0);
351     descriptor.setMinimumFirstSegmentLength(15.0);
352     descriptor.setMinimumLastSegmentLength(15.0);
353     descriptor.setOrthogonallyRouted(true);
354     ihl.setEdgeLayoutDescriptor(descriptor);
355 
356     ihl.getHierarchicLayouter().setPortConstraintOptimizer(new FlowchartPortOptimizer(getLayoutOrientation()));
357 
358     final FlowchartLayerer layerer = new FlowchartLayerer();
359     layerer.setAllowFlatwiseDefaultFlow(isAllowFlatwiseEdges());
360     ihl.setFromScratchLayerer(layerer);
361 
362     SimplexNodePlacer nodePlacer = (SimplexNodePlacer) ihl.getNodePlacer();
363     nodePlacer.setBaryCenterModeEnabled(true);
364     nodePlacer.setEdgeStraighteningOptimizationEnabled(true);
365 
366     return ihl;
367   }
368 
369   /**
370    * Creates a descriptor that has a minimum edge length that is long enough for a proper placement of all of the edge's
371    * labels.
372    */
373   private EdgeLayoutDescriptor createEdgeLayoutDescriptor(Edge e, LayoutGraph g, EdgeLayoutDescriptor defaultDescriptor,
374                                                           boolean horizontal) {
375     final EdgeLabelLayout[] ell = g.getEdgeLabelLayout(e);
376 
377     double minLength = 0.0;
378     for (int i = 0; i < ell.length; i++) {
379       final YDimension labelSize = ell[i].getBox();
380       if (FlowchartElements.isRegularEdge(g, e)) {
381         minLength += horizontal ? labelSize.getWidth() : labelSize.getHeight();
382       } else {
383         minLength += horizontal ? labelSize.getHeight() : labelSize.getWidth();
384       }
385     }
386 
387     // add distance between labels and to the end-nodes
388     if (ell.length > 0) {
389       minLength += minimumNodeDistance + (double) (ell.length - 1) * minimumLabelDistance;
390     }
391 
392     EdgeLayoutDescriptor descriptor = new EdgeLayoutDescriptor();
393     descriptor.setMinimumDistance(defaultDescriptor.getMinimumDistance());
394     descriptor.setMinimumLength(Math.max(minLength, defaultDescriptor.getMinimumLength()));
395     descriptor.setMinimumFirstSegmentLength(defaultDescriptor.getMinimumFirstSegmentLength());
396     descriptor.setMinimumLastSegmentLength(defaultDescriptor.getMinimumLastSegmentLength());
397     descriptor.setOrthogonallyRouted(defaultDescriptor.isOrthogonallyRouted());
398 
399     return descriptor;
400   }
401 
402   /**
403    * Does the label placement.
404    */
405   private static void doLabelPlacement(final LayoutGraph graph) {
406     final GreedyMISLabeling labeling = new GreedyMISLabeling();
407     labeling.setPlaceNodeLabels(true);
408     labeling.setPlaceEdgeLabels(true);
409     labeling.setProfitModel(new FlowchartLabelProfitModel(graph));
410     labeling.setCustomProfitModelRatio(0.25);
411 
412     labeling.doLayout(graph);
413   }
414 
415   private boolean isHorizontalOrientation() {
416     return (int) layoutOrientation == (int) LayoutOrientation.LEFT_TO_RIGHT;
417   }
418 
419   static boolean isFlatwiseBranch(DataProvider branchTypes, Object dataHolder) {
420     return branchTypes != null && isFlatwiseBranchType(branchTypes.getInt(dataHolder));
421   }
422 
423   static boolean isStraightBranch(DataProvider branchTypes, Object dataHolder) {
424     return branchTypes != null && isStraightBranchType(branchTypes.getInt(dataHolder));
425   }
426 
427   static boolean isStraightBranch(Graph graph, Object dataHolder) {
428     return isStraightBranch(graph.getDataProvider(FlowchartLayouter.PREFERRED_DIRECTION_KEY), dataHolder);
429   }
430 
431   static boolean isFlatwiseBranchType(int type) {
432     return (type & DIRECTION_FLATWISE) != 0;
433   }
434 
435   static boolean isStraightBranchType(int type) {
436     return (type & DIRECTION_STRAIGHT) != 0;
437   }
438 
439   static void restoreDataProvider(LayoutGraph graph, DataProvider dataProvider, Object key) {
440     graph.removeDataProvider(key);
441     if (dataProvider != null) {
442       graph.addDataProvider(key, dataProvider);
443     }
444   }
445 
446 }
447