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.algo.Bfs;
31  import y.algo.Cycles;
32  import y.algo.RankAssignments;
33  import y.base.DataAcceptor;
34  import y.base.DataProvider;
35  import y.base.Edge;
36  import y.base.EdgeCursor;
37  import y.base.EdgeList;
38  import y.base.EdgeMap;
39  import y.base.Graph;
40  import y.base.Node;
41  import y.base.NodeCursor;
42  import y.base.NodeList;
43  import y.base.NodeMap;
44  import y.layout.LayoutGraph;
45  import y.layout.PortConstraintKeys;
46  import y.layout.grouping.GroupingKeys;
47  import y.layout.hierarchic.incremental.EdgeData;
48  import y.layout.hierarchic.incremental.Layer;
49  import y.layout.hierarchic.incremental.Layerer;
50  import y.layout.hierarchic.incremental.Layers;
51  import y.layout.hierarchic.incremental.LayoutDataProvider;
52  import y.util.Comparators;
53  import y.util.GraphHider;
54  
55  import java.util.Arrays;
56  
57  /**
58   * Customized layering for flowcharts.
59   */
60  class FlowchartLayerer implements Layerer {
61    private static final int WEIGHT_DEFAULT_EDGE = 3;
62    private static final int WEIGHT_DEFAULT_EDGE_IN_SUBPROCESS = 5;
63    private static final int WEIGHT_MESSAGE_FLOW = 3;
64    private static final int WEIGHT_ASSOCIATION = 2;
65  
66    private static final int MIN_LENGTH_DEFAULT_EDGE = 1;
67    private static final int MIN_LENGTH_FLATWISE_BRANCH = 0;
68    private static final int MIN_LENGTH_MESSAGE_FLOW = 0;
69    private static final int MIN_LENGTH_ASSOCIATION = 0;
70  
71    private static final double CYCLE_WEIGHT_BACKEDGE = 1.0;
72    private static final double CYCLE_WEIGHT_NON_BACKEDGE = 5.0;
73  
74    private boolean assignStartNodesToLeftOrTop;
75    private boolean allowFlatwiseDefaultFlow;
76  
77    FlowchartLayerer() {
78      assignStartNodesToLeftOrTop = false;
79    }
80  
81    public boolean isAssignStartNodesToLeftOrTop() {
82      return assignStartNodesToLeftOrTop;
83    }
84  
85    public void setAssignStartNodesToLeftOrTop(boolean assignStartNodesToLeftOrTop) {
86      this.assignStartNodesToLeftOrTop = assignStartNodesToLeftOrTop;
87    }
88  
89    public boolean isAllowFlatwiseDefaultFlow() {
90      return allowFlatwiseDefaultFlow;
91    }
92  
93    public void setAllowFlatwiseDefaultFlow(boolean allowFlatwiseDefaultFlow) {
94      this.allowFlatwiseDefaultFlow = allowFlatwiseDefaultFlow;
95    }
96  
97    public void assignLayers(LayoutGraph graph, Layers layers, LayoutDataProvider ldp) {
98      final EdgeList reversedEdges = reverseCycles(graph);
99  
100     //assign weights/min length to edges
101     GraphHider hider = new GraphHider(graph);
102     EdgeMap minLength = graph.createEdgeMap();
103     NodeMap node2Layer = graph.createNodeMap();
104     EdgeMap weight = graph.createEdgeMap();
105 
106     try {
107       // transform graph
108       final NodeList dummies = insertDummyEdges(graph, hider, weight, minLength);
109       dummies.add(insertSuperRoot(graph, weight, minLength));
110 
111       // assign layers
112       RankAssignments.simplex(graph, node2Layer, weight, minLength);
113 
114       // undo graph transformation
115       for (NodeCursor nc = dummies.nodes(); nc.ok(); nc.next()) {
116         graph.removeNode(nc.node());
117       }
118       hider.unhideAll();
119       for (EdgeCursor ec = reversedEdges.edges(); ec.ok(); ec.next()) {
120         graph.reverseEdge(ec.edge());
121       }
122 
123       // special handling for some degree 1 nodes (draw the incident edge as same layer edge)
124       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
125         final Node node = nc.node();
126         if (isDegreeOneNode(node, ldp)) {
127           handleDegreeOneNode(node, graph, node2Layer, ldp);
128         }
129       }
130 
131       // build result data structure
132       int layerCount = normalize(graph, node2Layer);
133       for (int i = 0; i < layerCount; i++) {
134         layers.insert(Layer.TYPE_NORMAL, i);
135       }
136       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
137         Node node = nc.node();
138         int layer = node2Layer.getInt(node);
139         layers.getLayer(layer).add(node);
140       }
141     } finally {
142       //dispose
143       graph.disposeEdgeMap(weight);
144       graph.disposeEdgeMap(minLength);
145       graph.disposeNodeMap(node2Layer);
146     }
147   }
148 
149   private NodeList insertDummyEdges(LayoutGraph graph, GraphHider hider, DataAcceptor weight,
150                                     DataAcceptor minLength) {
151     final boolean nodeTypeSet = graph.getDataProvider(FlowchartLayouter.NODE_TYPE_DPKEY) != null;
152 
153     final DataProvider parentNodeIdDP = graph.getDataProvider(GroupingKeys.PARENT_NODE_ID_DPKEY);
154     final DataProvider preferredDirectionDP = graph.getDataProvider(FlowchartLayouter.PREFERRED_DIRECTION_KEY);
155     final DataProvider groupingNodesDP = graph.getDataProvider(FlowchartTransformerStage.GROUPING_NODES_DP_KEY);
156     final DataProvider targetGroupIdDP = graph.getDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY);
157 
158     final NodeMap outEdgeBranchTypes = graph.createNodeMap();
159     for (NodeCursor nodeCursor = graph.nodes(); nodeCursor.ok(); nodeCursor.next()) {
160       final Node node = nodeCursor.node();
161       int type = 0;
162       for (EdgeCursor edgeCursor = node.outEdges(); edgeCursor.ok(); edgeCursor.next()) {
163         type |= preferredDirectionDP.getInt(edgeCursor.edge());
164       }
165       outEdgeBranchTypes.setInt(node, type);
166     }
167 
168     final NodeList dummies = new NodeList();
169 
170     final Edge[] edges = graph.getEdgeArray();
171     for (int i = 0; i < edges.length; i++) {
172       final Edge edge = edges[i];
173 
174       switch (getType(graph, edge)) {
175         case FlowchartElements.EDGE_TYPE_MESSAGE_FLOW: {
176           final Node dummyNode = graph.createNode();
177           dummies.add(dummyNode);
178 
179           Edge dummyEdge1 = graph.createEdge(edge.source(), dummyNode);
180           weight.setInt(dummyEdge1, WEIGHT_MESSAGE_FLOW);
181           minLength.setInt(dummyEdge1, MIN_LENGTH_MESSAGE_FLOW);
182 
183           Edge dummyEdge2 = graph.createEdge(edge.target(), dummyNode);
184           weight.setInt(dummyEdge2, WEIGHT_MESSAGE_FLOW);
185           minLength.setInt(dummyEdge2, MIN_LENGTH_MESSAGE_FLOW);
186 
187           hider.hide(edge);
188           break;
189         }
190         case FlowchartElements.EDGE_TYPE_ASSOCIATION: {
191           final Node dummyNode = graph.createNode();
192           dummies.add(dummyNode);
193 
194           Edge dummyEdge1 = graph.createEdge(edge.source(), dummyNode);
195           weight.setInt(dummyEdge1, WEIGHT_ASSOCIATION);
196           minLength.setInt(dummyEdge1, MIN_LENGTH_ASSOCIATION);
197 
198           Edge dummyEdge2 = graph.createEdge(edge.target(), dummyNode);
199           weight.setInt(dummyEdge2, WEIGHT_ASSOCIATION);
200           minLength.setInt(dummyEdge2, MIN_LENGTH_ASSOCIATION);
201 
202           hider.hide(edge);
203           break;
204         }
205         default: {
206           weight.setInt(edge, isContainedInSubProcess(edge, graph, parentNodeIdDP, nodeTypeSet) ?
207               WEIGHT_DEFAULT_EDGE_IN_SUBPROCESS : WEIGHT_DEFAULT_EDGE);
208 
209           if (isFlatwiseConnectorGroupingEdge(groupingNodesDP, edge) &&
210               !FlowchartLayouter.isStraightBranch(preferredDirectionDP, edge)) {
211             minLength.setInt(edge, MIN_LENGTH_FLATWISE_BRANCH);
212 
213           } else if (isFirstGroupingEdgeToSucceedingLayers(groupingNodesDP, edge)) {
214             minLength.setInt(edge, MIN_LENGTH_FLATWISE_BRANCH);
215 
216           } else if (!allowFlatwiseDefaultFlow
217               || !FlowchartLayouter.isFlatwiseBranch(preferredDirectionDP, edge)
218               || containsOnlyFlatwise(outEdgeBranchTypes.getInt(edge.target()))
219               || isValueSet(targetGroupIdDP, edge)) {
220             minLength.setInt(edge, MIN_LENGTH_DEFAULT_EDGE);
221 
222           } else {
223             minLength.setInt(edge, MIN_LENGTH_FLATWISE_BRANCH);
224           }
225           break;
226         }
227       }
228     }
229 
230     return dummies;
231   }
232 
233   /**
234    * Inserts a super root to guarantee that graph is connected.
235    */
236   private Node insertSuperRoot(LayoutGraph graph, DataAcceptor weight, DataAcceptor minLength) {
237     final Node superRoot = graph.createNode();
238 
239     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
240       final Node v = nc.node();
241       if (!v.equals(superRoot) && v.inDegree() == 0) {
242         final Edge dummyEdge = graph.createEdge(superRoot, v);
243         weight.setInt(dummyEdge, assignStartNodesToLeftOrTop && FlowchartElements.isStartEvent(graph, v) ? 100 : 0);
244         minLength.setInt(dummyEdge, 0);
245       }
246     }
247 
248     return superRoot;
249   }
250 
251   private static EdgeList reverseCycles(LayoutGraph graph) {
252     //we only consider edges of type sequence flow
253     final GraphHider hider = new GraphHider(graph);
254     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
255       Edge e = ec.edge();
256       if ((int) getType(graph, e) != (int) FlowchartElements.EDGE_TYPE_SEQUENCE_FLOW) {
257         hider.hide(e);
258       }
259     }
260 
261     final EdgeMap edge2Weight = graph.createEdgeMap();
262     final EdgeMap cyclingEdges = graph.createEdgeMap();
263     final EdgeList reversedEdges;
264     try {
265       // try to identify backedges and assign lower weights to them
266       NodeList coreNodes = new NodeList();
267       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
268         Node n = nc.node();
269         if (n.inDegree() == 0) {
270           coreNodes.add(n);
271         }
272       }
273 
274       final NodeMap node2Depth = graph.createNodeMap();
275       try {
276         Bfs.getLayers(graph, coreNodes, true, node2Depth);
277         for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
278           Edge e = ec.edge();
279           if (node2Depth.getInt(e.source()) > node2Depth.getInt(e.target())) {
280             //likely to be a backedge
281             edge2Weight.setDouble(e, CYCLE_WEIGHT_BACKEDGE);
282           } else {
283             edge2Weight.setDouble(e, CYCLE_WEIGHT_NON_BACKEDGE);
284           }
285         }
286       } finally {
287         graph.disposeNodeMap(node2Depth);
288       }
289 
290       // find and remove cycles
291       reversedEdges = new EdgeList();
292 
293       Cycles.findCycleEdges(graph, cyclingEdges, edge2Weight);
294       for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
295         Edge e = ec.edge();
296         if (cyclingEdges.getBool(e)) {
297           graph.reverseEdge(e);
298           reversedEdges.add(e);
299         }
300       }
301     } finally {
302       graph.disposeEdgeMap(cyclingEdges);
303       graph.disposeEdgeMap(edge2Weight);
304       hider.unhideAll();
305     }
306 
307     return reversedEdges;
308   }
309 
310   private static byte getType(LayoutGraph g, Edge e) {
311     if (!FlowchartElements.isUndefined(g, e)) {
312       return FlowchartElements.getType(g, e);
313     } else {
314       //special handling if constraint incremental layerer calls this layerer
315       final String originalEdgeDpKey = "y.layout.hierarchic.incremental.ConstraintIncrementalLayerer.ORIG_EDGES";
316 
317       final DataProvider edge2OrigEdge = g.getDataProvider(originalEdgeDpKey);
318       if (edge2OrigEdge != null && edge2OrigEdge.get(e) != null) {
319         final Edge realEdge = (Edge) edge2OrigEdge.get(e);
320         if (!FlowchartElements.isUndefined(realEdge.getGraph(), realEdge)) {
321           return FlowchartElements.getType(realEdge.getGraph(), realEdge);
322         }
323       }
324 
325       return FlowchartElements.isAnnotation(g, e.source()) || FlowchartElements.isAnnotation(g, e.target()) ?
326           FlowchartElements.EDGE_TYPE_ASSOCIATION : FlowchartElements.EDGE_TYPE_SEQUENCE_FLOW;
327     }
328   }
329 
330   private static boolean isContainedInSubProcess(Edge e, LayoutGraph g, DataProvider node2Parent,
331                                                  boolean considerNodeType) {
332     if (node2Parent == null) {
333       return false;
334     }
335 
336     final Node sourceParent = (Node) node2Parent.get(e.source());
337     final Node targetParent = (Node) node2Parent.get(e.target());
338     return sourceParent != null && sourceParent.equals(targetParent) &&
339         (!considerNodeType || FlowchartElements.isGroup(g, sourceParent));
340   }
341 
342   //Be careful: due to the handling of edges attaching to group nodes the degree of "degree-one" nodes may be > 1.
343   //We are interested in nodes with degree one in the initial graph.
344   private static boolean isDegreeOneNode(Node n, LayoutDataProvider ldp) {
345     int realDegree = 0;
346     for (EdgeCursor ec = n.edges(); ec.ok(); ec.next()) {
347       if (isRealEdge(ldp.getEdgeData(ec.edge()))) {
348         realDegree++;
349         if (realDegree > 1) {
350           return false;
351         }
352       }
353     }
354     return realDegree == 1;
355   }
356 
357   private static void handleDegreeOneNode(Node n, LayoutGraph g, NodeMap node2Layer, LayoutDataProvider ldp) {
358     if (!FlowchartElements.isEvent(g, n) || FlowchartElements.isStartEvent(g, n)) {
359       return;
360     }
361 
362     final Edge realEdge = findIncidentRealEdge(ldp, n);
363     if (realEdge == null) {
364       return;
365     }
366 
367     final Node opposite = realEdge.opposite(n);
368     int sameLayerEdgeCount = 0;
369     int oppositeOutDegree = 0;
370     int oppositeInDegree = 0;
371     for (EdgeCursor ec = opposite.outEdges(); ec.ok(); ec.next()) {
372       final Edge e = ec.edge();
373       if (!e.equals(realEdge) && isRealEdge(ldp.getEdgeData(e))) {
374         final int layerDiff = node2Layer.getInt(e.source()) - node2Layer.getInt(e.target());
375         if (layerDiff > 0) {
376           oppositeInDegree++;
377         } else if (layerDiff == 0) {
378           sameLayerEdgeCount++;
379         } else {
380           oppositeOutDegree++;
381         }
382       }
383     }
384     for (EdgeCursor ec = opposite.inEdges(); ec.ok(); ec.next()) {
385       final Edge e = ec.edge();
386       if (!e.equals(realEdge) && isRealEdge(ldp.getEdgeData(e))) {
387         final int layerDiff = node2Layer.getInt(e.source()) - node2Layer.getInt(e.target());
388         if (layerDiff > 0) {
389           oppositeOutDegree++;
390         } else if (layerDiff == 0) {
391           sameLayerEdgeCount++;
392         } else {
393           oppositeInDegree++;
394         }
395       }
396     }
397 
398     if ((realEdge.target().equals(n) && sameLayerEdgeCount < 2 && oppositeOutDegree >= 1 && oppositeInDegree <= 2)
399         || (realEdge.source().equals(n) && sameLayerEdgeCount < 2 && oppositeInDegree >= 1 && oppositeOutDegree <= 2)) {
400       node2Layer.setInt(n, node2Layer.getInt(opposite));
401     }
402   }
403 
404   private static boolean isRealEdge(final EdgeData eData) {
405     return (eData != null) && ((int) eData.getType() == (int) EdgeData.TYPE_NORMAL);
406   }
407 
408   private static Edge findIncidentRealEdge(LayoutDataProvider ldp, Node n) {
409     for (EdgeCursor ec = n.edges(); ec.ok(); ec.next()) {
410       final Edge edge = ec.edge();
411       if (isRealEdge(ldp.getEdgeData(edge))) {
412         return edge;
413       }
414     }
415 
416     return null;
417   }
418 
419   private static boolean containsOnlyFlatwise(int branchType) {
420     return branchType != 0 && (branchType & FlowchartLayouter.DIRECTION_STRAIGHT) == 0;
421   }
422 
423   private static boolean isFlatwiseConnectorGroupingEdge(DataProvider groupingDummies, Edge edge) {
424     return groupingDummies != null &&
425         ((edge.target().inDegree() > 1 && groupingDummies.getInt(edge.source()) == 0 &&
426             groupingDummies.getInt(edge.target()) == FlowchartTransformerStage.NODE_TYPE_PRECEDING_LAYER) ||
427             (edge.source().outDegree() > 1 && groupingDummies.getInt(edge.target()) == 0 &&
428                 groupingDummies.getInt(edge.source()) == FlowchartTransformerStage.NODE_TYPE_SUCCEEDING_LAYER));
429   }
430 
431   private static boolean isFirstGroupingEdgeToSucceedingLayers(DataProvider groupingDummies, Edge edge) {
432     return groupingDummies != null
433         && groupingDummies.getInt(edge.source()) == 0
434         && groupingDummies.getInt(edge.target()) == FlowchartTransformerStage.NODE_TYPE_SUCCEEDING_LAYER;
435   }
436 
437   private static boolean isValueSet(DataProvider dataProvider, Edge edge) {
438     return dataProvider != null && dataProvider.get(edge) != null;
439   }
440 
441   /**
442    * Removes empty layers and ensures that the smallest layer has value 0.
443    */
444   private static int normalize(Graph g, NodeMap layer) {
445     if (g.isEmpty()) {
446       return 0;
447     }
448 
449     Node[] nodes = g.getNodeArray();
450     Arrays.sort(nodes, Comparators.createIntDataComparator(layer));
451     int lastLayer = layer.getInt(nodes[0]);
452     int realLayer = 0;
453     for (int i = 0; i < nodes.length; i++) {
454       int currentLayer = layer.getInt(nodes[i]);
455       if (currentLayer != lastLayer) {
456         realLayer++;
457         lastLayer = currentLayer;
458       }
459       layer.setInt(nodes[i], realLayer);
460     }
461     return realLayer + 1;
462   }
463 
464 }
465 
466