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