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