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.Cycles;
17  import y.algo.GraphConnectivity;
18  import y.algo.Paths;
19  import y.algo.RankAssignments;
20  import y.base.DataAcceptor;
21  import y.base.DataProvider;
22  import y.base.Edge;
23  import y.base.EdgeCursor;
24  import y.base.EdgeList;
25  import y.base.EdgeMap;
26  import y.base.Graph;
27  import y.base.GraphInterface;
28  import y.base.Node;
29  import y.base.NodeCursor;
30  import y.base.NodeList;
31  import y.base.NodeMap;
32  import y.base.YCursor;
33  import y.layout.LayoutGraph;
34  import y.layout.LayoutOrientation;
35  import y.layout.PortConstraint;
36  import y.layout.grouping.GroupingKeys;
37  import y.layout.hierarchic.incremental.EdgeData;
38  import y.layout.hierarchic.incremental.LayoutDataProvider;
39  import y.layout.hierarchic.incremental.NodeData;
40  import y.layout.hierarchic.incremental.PartitionGrid;
41  import y.util.Comparators;
42  import y.util.DataProviderAdapter;
43  import y.util.GraphHider;
44  import y.util.GraphPartitionManager;
45  import y.util.Maps;
46  
47  import java.util.Arrays;
48  import java.util.Comparator;
49  import java.util.HashMap;
50  import java.util.Map;
51  
52  /**
53   *
54   */
55  class FlowchartAlignmentCalculator {
56    private byte layoutOrientation;
57  
58    FlowchartAlignmentCalculator() {
59      this.layoutOrientation = LayoutOrientation.TOP_TO_BOTTOM;
60    }
61  
62    public byte getLayoutOrientation() {
63      return layoutOrientation;
64    }
65  
66    public void setLayoutOrientation(byte layoutOrientation) {
67      this.layoutOrientation = layoutOrientation;
68    }
69  
70    public void determineAlignment(LayoutGraph graph, LayoutDataProvider ldp, NodeMap nodeAlignment, EdgeMap edgeLength) {
71      graph.sortEdges(new FlowchartPortOptimizer.PositionEdgeComparator(true, ldp),
72          new FlowchartPortOptimizer.PositionEdgeComparator(false, ldp));
73  
74      final DataProvider edgeIsAlignable = determineAlignableEdges(graph, ldp);
75      determineEdgeLengths(graph, ldp, edgeIsAlignable, edgeLength);
76      final DataProvider edgePriority = determineEdgePriorities(graph, edgeIsAlignable, edgeLength);
77  
78      final NodeAlignmentCalculator nodeAlignmentCalculator = new NodeAlignmentCalculator(layoutOrientation);
79      nodeAlignmentCalculator.calculateAlignment(graph, ldp, edgeIsAlignable, edgePriority, nodeAlignment);
80  
81      graph.addDataProvider(FlowchartPortOptimizer.NODE_TO_ALIGN_DP_KEY, nodeAlignment);
82  
83  //    // TODO remove debug code
84  //    for (NodeCursor nodeCursor = graph.nodes(); nodeCursor.ok(); nodeCursor.next()) {
85  //      final Node node = nodeCursor.node();
86  //      final Object o = nodeAlignment.get(node);
87  //      if (o != null) {
88  //        System.out.println("Align '" + node + "' with '" + o + '\'');
89  //      }
90  //    }
91    }
92  
93    boolean isSpecialNode(Graph graph, Node n, LayoutDataProvider ldp) {
94      return (ldp.getNodeData(n).getType() == NodeData.TYPE_NORMAL)
95          && !FlowchartElements.isAnnotation(n.getGraph(), n)
96          && !FlowchartTransformerStage.isGroupingDummy(graph, n);
97    }
98  
99    boolean isRelevant(Graph graph, Edge e, LayoutDataProvider ldp) {
100     return !FlowchartElements.isMessageFlow(graph, FlowchartPortOptimizer.getOriginalEdge(e, ldp));
101   }
102 
103   /**
104    * Returns true if the given edge can be aligned, that is its port constraints are not flatwise, and its end nodes are
105    * not in different swimlanes and do not belong to different groups.
106    */
107   private boolean isAlignable(GraphInterface graph, LayoutDataProvider ldp, Edge edge) {
108     final EdgeData edgeData = ldp.getEdgeData(edge);
109 
110     if (hasFlatwisePortConstraint(edgeData) || hasFlatwiseCandidateCollection(edgeData, getLayoutOrientation())) {
111       return false;
112     }
113 
114     final Node source = edge.source();
115     final Node target = edge.target();
116     final int laneId1 = FlowchartPortOptimizer.getSwimlaneId(source, ldp);
117     final int laneId2 = FlowchartPortOptimizer.getSwimlaneId(target, ldp);
118     if (laneId1 != -1 && laneId1 != laneId2) {
119       return false;
120     }
121 
122     final DataProvider node2Parent = graph.getDataProvider(GroupingKeys.PARENT_NODE_ID_DPKEY);
123     return node2Parent == null || node2Parent.get(source) == null ||
124         node2Parent.get(source).equals(node2Parent.get(target));
125   }
126 
127   private static boolean isRealEdge(Edge edge, LayoutDataProvider layoutData) {
128     return layoutData.getNodeData(edge.source()).getType() == NodeData.TYPE_NORMAL
129         && layoutData.getNodeData(edge.target()).getType() == NodeData.TYPE_NORMAL;
130   }
131 
132   private static boolean isStraightBranch(LayoutGraph graph, Edge edge, LayoutDataProvider ldp) {
133     return FlowchartLayouter.isStraightBranch(graph, FlowchartPortOptimizer.getOriginalEdge(edge, ldp));
134   }
135 
136   private DataProvider determineAlignableEdges(LayoutGraph graph, LayoutDataProvider ldp) {
137     EdgeMap edgeIsAlignable = Maps.createHashedEdgeMap();
138 
139     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
140       final Edge e = ec.edge();
141       edgeIsAlignable.setBool(e, isAlignable(graph, ldp, e) && isRelevant(graph, e, ldp));
142     }
143 
144     return edgeIsAlignable;
145   }
146 
147   /**
148    * Determines edge lengths such that, in longest paths, edges are preferred that guarantee a suitable port
149    * assignment.
150    */
151   private void determineEdgeLengths(LayoutGraph graph, LayoutDataProvider layoutData,
152                                     DataProvider edgeIsAlignable, EdgeMap edgeLength) {
153     final int ZERO_LENGTH = 0;
154     final int BASIC_DUMMY_EDGE_LENGTH = 1;
155     final int BASIC_EDGE_LENGTH = 5;
156     final int PENALTY_LENGTH = BASIC_EDGE_LENGTH + graph.nodeCount();
157     final int HIGH_PENALTY_LENGTH = PENALTY_LENGTH * 8;
158 
159     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
160       final Edge e = ec.edge();
161 
162       if (hasFlatwisePortConstraint(layoutData.getEdgeData(e))) {
163         edgeLength.setInt(e, ZERO_LENGTH);
164       } else if (isRealEdge(e, layoutData)) {
165         edgeLength.setInt(e, BASIC_EDGE_LENGTH);
166       } else {
167         edgeLength.setInt(e, BASIC_DUMMY_EDGE_LENGTH);
168       }
169     }
170 
171     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
172       final Node node = nc.node();
173 
174       final NodeData nodeData = layoutData.getNodeData(node);
175       final byte type = nodeData.getType();
176       if (type == NodeData.TYPE_SOURCE_GROUP_NODE || type == NodeData.TYPE_TARGET_GROUP_NODE) {
177         // assign higher length to inner edges
178         final Edge[] edges = type == NodeData.TYPE_SOURCE_GROUP_NODE ?
179             new EdgeList(node.outEdges()).toEdgeArray() :
180             new EdgeList(node.inEdges()).toEdgeArray();
181         for (int i = 1; i < edges.length - 1; i++) {
182           edgeLength.setInt(edges[i], edgeLength.getInt(edges[i]) + BASIC_EDGE_LENGTH);
183         }
184       }
185 
186       if (!isSpecialNode(graph, node, layoutData) || node.degree() < 3) {
187         continue;
188       }
189 
190       if (node.outDegree() == 2 && node.inDegree() == 2) {
191         final Edge firstIn = node.firstInEdge();
192         final Edge lastOut = node.lastOutEdge();
193         final Edge lastIn = node.lastInEdge();
194         final Edge firstOut = node.firstOutEdge();
195         final boolean preventFirstIn = !edgeIsAlignable.getBool(firstIn) || !edgeIsAlignable.getBool(lastOut);
196         final boolean preventFirstOut = !edgeIsAlignable.getBool(firstOut) || !edgeIsAlignable.getBool(lastIn);
197 
198         if (!preventFirstOut || !preventFirstIn) {
199           if (preventFirstIn) {
200             edgeLength.setInt(firstIn, ZERO_LENGTH);
201             edgeLength.setInt(lastOut, ZERO_LENGTH);
202           }
203 
204           if (preventFirstOut) {
205             edgeLength.setInt(firstOut, ZERO_LENGTH);
206             edgeLength.setInt(lastIn, ZERO_LENGTH);
207           }
208 
209           if (edgeLength.getInt(firstIn) + edgeLength.getInt(lastOut) >
210               edgeLength.getInt(lastIn) + edgeLength.getInt(firstOut)) {
211             edgeLength.setInt(firstIn, edgeLength.getInt(firstIn) + HIGH_PENALTY_LENGTH);
212             edgeLength.setInt(lastOut, edgeLength.getInt(lastOut) + HIGH_PENALTY_LENGTH);
213           } else {
214             edgeLength.setInt(lastIn, edgeLength.getInt(lastIn) + HIGH_PENALTY_LENGTH);
215             edgeLength.setInt(firstOut, edgeLength.getInt(firstOut) + HIGH_PENALTY_LENGTH);
216           }
217           continue;
218         }
219       }
220 
221       boolean hasStraightBranch = false;
222 
223       for (EdgeCursor ec = node.edges(); ec.ok(); ec.next()) {
224         final Edge edge = ec.edge();
225         if (isStraightBranch(graph, edge, layoutData)) {
226           hasStraightBranch = true;
227           edgeLength.setInt(edge, edgeLength.getInt(edge) + PENALTY_LENGTH);
228         }
229       }
230 
231       if (!hasStraightBranch) {
232         final Edge[] edges = node.outDegree() >= node.inDegree() ?
233             new EdgeList(node.outEdges()).toEdgeArray() : new EdgeList(node.inEdges()).toEdgeArray();
234 
235         //assign high length to inner edges (the two non-inner edges should be attached to the side ports)
236         for (int i = 1; i < edges.length - 1; i++) {
237           edgeLength.setInt(edges[i], edgeLength.getInt(edges[i]) + PENALTY_LENGTH);
238         }
239       }
240     }
241 
242 //    // TODO remove debug code
243 //    for (EdgeCursor edgeCursor = graph.edges(); edgeCursor.ok(); edgeCursor.next()) {
244 //      final Edge edge = edgeCursor.edge();
245 //      System.out.println(edge + " l:" + edgeLength.getDouble(edge));
246 //    }
247   }
248 
249   private static DataProvider determineEdgePriorities(LayoutGraph graph, DataProvider edgeIsAlignable,
250                                                       DataProvider edgeLength) {
251     final EdgeMap edgePriority = Maps.createHashedEdgeMap();
252 
253     final GraphHider hider = new GraphHider(graph);
254     try {
255       // hide irrelevant edges
256       for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
257         Edge e = ec.edge();
258         edgePriority.setInt(e, FlowchartPortOptimizer.PRIORITY_BASIC);
259 
260         if (!edgeIsAlignable.getBool(e)) {
261           hider.hide(e);
262         }
263       }
264 
265       // for each connected component we iteratively find a longest path that is used as critical path
266       NodeMap node2CompId = Maps.createHashedNodeMap();
267       int compCount = GraphConnectivity.connectedComponents(graph, node2CompId);
268       GraphPartitionManager gpm = new GraphPartitionManager(graph, node2CompId);
269 
270       try {
271         gpm.hideAll();
272 
273         for (int i = 0; i < compCount; i++) {
274           gpm.displayPartition(new Integer(i));
275           GraphHider localHider = new GraphHider(graph);
276           try {
277             EdgeList path = Paths.findLongestPath(graph, edgeLength);
278             while (!path.isEmpty()) {
279               // TODO remove debug code
280 //              System.out.println("** PATH **");
281               for (EdgeCursor ec = path.edges(); ec.ok(); ec.next()) {
282                 edgePriority.setInt(ec.edge(), FlowchartPortOptimizer.PRIORITY_HIGH);
283 //                System.out.println("* " + ec.edge() + " l:" + edgeLength.getDouble(ec.edge()));
284               }
285               localHider.hide(Paths.constructNodePath(path));
286               path = Paths.findLongestPath(graph, edgeLength);
287             }
288           } finally {
289             localHider.unhideAll();
290           }
291         }
292 
293       } finally {
294         gpm.unhideAll();
295       }
296 
297     } finally {
298       hider.unhideAll();
299     }
300 
301     return edgePriority;
302   }
303 
304   private static boolean hasFlatwisePortConstraint(final EdgeData edgeData) {
305     return FlowchartPortOptimizer.isFlatwisePortConstraint(
306         edgeData.getSPC()) || FlowchartPortOptimizer.isFlatwisePortConstraint(edgeData.getTPC());
307   }
308 
309   private static boolean hasFlatwiseCandidateCollection(final EdgeData edgeData, final byte layoutOrientation) {
310     return FlowchartPortOptimizer.isFlatwiseCandidateCollection(edgeData.getSourceCandidates(), layoutOrientation)
311         || FlowchartPortOptimizer.isFlatwiseCandidateCollection(edgeData.getTargetCandidates(), layoutOrientation);
312   }
313 
314   /**
315    * @noinspection ImplicitNumericConversion
316    */
317   static class NodeAlignmentCalculator {
318 
319     private final byte layoutOrientation;
320 
321     NodeAlignmentCalculator(byte layoutOrientation) {
322       this.layoutOrientation = layoutOrientation;
323     }
324 
325     boolean isHorizontalOrientation() {
326       return (int) layoutOrientation == (int) LayoutOrientation.LEFT_TO_RIGHT;
327     }
328 
329     void calculateAlignment(LayoutGraph graph, final LayoutDataProvider ldp, DataProvider edgeAlignable,
330                             DataProvider edgePriority, DataAcceptor nodeAlignment) {
331       final PartitionGrid grid = PartitionGrid.getPartitionGrid(graph);
332 
333       if (grid == null) {
334         calculateAlignmentImpl(graph, ldp, edgeAlignable, edgePriority, nodeAlignment);
335 
336       } else {
337         final GraphPartitionManager columnPartitionManager = new GraphPartitionManager(graph,
338             new DataProviderAdapter() {
339               public Object get(Object dataHolder) {
340                 final int swimlaneID = FlowchartPortOptimizer.getSwimlaneId((Node) dataHolder, ldp);
341                 return swimlaneID < 0 ? dataHolder : new Integer(swimlaneID);
342               }
343             });
344 
345         try {
346           columnPartitionManager.hideAll();
347           for (int i = 0; i < grid.getColumns().size(); i++) {
348             columnPartitionManager.displayPartition(new Integer(i));
349             if (graph.nodeCount() > 1) {
350               calculateAlignmentImpl(graph, ldp, edgeAlignable, edgePriority, nodeAlignment);
351             }
352           }
353         } finally {
354           columnPartitionManager.unhideAll();
355         }
356       }
357     }
358 
359     private void calculateAlignmentImpl(LayoutGraph graph, LayoutDataProvider ldp, DataProvider edgeAlignable,
360                                         DataProvider edgePriority, DataAcceptor node2AlignWith) {
361       final NodeMap node2LaneAlignment = createLaneAlignmentMap(graph, ldp);
362 
363       EdgeMap edgeMinLength = Maps.createHashedEdgeMap();
364       EdgeMap edgeWeight = Maps.createHashedEdgeMap();
365 
366       NodeMap node2NetworkRep = Maps.createHashedNodeMap();
367       Map groupNode2BeginRep = new HashMap();
368       Map groupNode2EndRep = new HashMap();
369       Graph network = new Graph();
370 
371       //create network nodes
372       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
373         Node n = nc.node();
374         NodeData data = ldp.getNodeData(n);
375         Node nRep;
376         if (data != null && data.getType() == NodeData.TYPE_GROUP_BEGIN) {
377           //all group begin dummies of the same group node are mapped to the same network node
378           nRep = (Node) groupNode2BeginRep.get(data.getGroupNode());
379           if (nRep == null) {
380             nRep = network.createNode();
381             groupNode2BeginRep.put(data.getGroupNode(), nRep);
382           }
383         } else if (data != null && data.getType() == NodeData.TYPE_GROUP_END) {
384           //all group end dummies of the same group node are mapped to the same network node
385           nRep = (Node) groupNode2EndRep.get(data.getGroupNode());
386           if (nRep == null) {
387             nRep = network.createNode();
388             groupNode2EndRep.put(data.getGroupNode(), nRep);
389           }
390         } else {
391           nRep = network.createNode();
392         }
393         node2NetworkRep.set(n, nRep);
394       }
395 
396       //consider edges
397       final EdgeList nonAlignableEdges = new EdgeList();
398 
399       for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
400         final Edge e = ec.edge();
401         if (e.isSelfLoop() || (isGroupNodeBorder(e.source(), ldp) && isGroupNodeBorder(e.target(), ldp))) {
402           continue;
403         }
404 
405         if (!edgeAlignable.getBool(e)) {
406           nonAlignableEdges.add(e);
407           continue;
408         }
409 
410         Node absNode = network.createNode();
411         int priority = edgePriority.getInt(e);
412         Node sRep = (Node) node2NetworkRep.get(e.source());
413         Node tRep = (Node) node2NetworkRep.get(e.target());
414         Edge sConnector = network.createEdge(sRep, absNode);
415         edgeMinLength.setInt(sConnector, 0);
416         edgeWeight.setInt(sConnector, priority);
417         Edge tConnector = network.createEdge(tRep, absNode);
418         edgeMinLength.setInt(tConnector, 0);
419         edgeWeight.setInt(tConnector, priority);
420       }
421 
422       //also consider same layer edges
423       for (EdgeCursor ec = FlowchartPortOptimizer.getSameLayerEdges(graph, ldp).edges(); ec.ok(); ec.next()) {
424         Edge e = ec.edge();
425         if (!e.isSelfLoop() && (!isGroupNodeBorder(e.source(), ldp) || !isGroupNodeBorder(e.target(), ldp))) {
426           Node sRep = (Node) node2NetworkRep.get(e.source());
427           Node tRep = (Node) node2NetworkRep.get(e.target());
428           Edge connector = ldp.getNodeData(e.source()).getPosition() < ldp.getNodeData(e.target()).getPosition() ?
429               network.createEdge(sRep, tRep) : network.createEdge(tRep, sRep);
430           edgeMinLength.setInt(connector, 1);
431           edgeWeight.setInt(connector, FlowchartPortOptimizer.PRIORITY_BASIC);
432         }
433       }
434 
435       Node[] nodes = graph.getNodeArray();
436       Arrays.sort(nodes, new NodePositionComparator(ldp));
437       Node last = null;
438       for (int i = 0; i < nodes.length; i++) {
439         Node n = nodes[i];
440         if (last != null && areInSameLayer(last, n, ldp)) {
441           Node nRep = (Node) node2NetworkRep.get(n);
442           Node lastRep = (Node) node2NetworkRep.get(last);
443           if (!network.containsEdge(lastRep, nRep)) {
444             Edge connector = network.createEdge(lastRep, nRep); //guarantees that last is placed to the left of n
445             int minLength = calcMinLength(last, n, graph, ldp);
446             edgeMinLength.setInt(connector, minLength);
447             edgeWeight.setInt(connector, 0);
448           }
449         }
450         last = n;
451       }
452 
453       // For each non-alignable edge, we create a connector with min length 1,
454       // but only it has no other alignable in-edge.
455       final EdgeMap nonAlignableConnectorMap = Maps.createHashedEdgeMap();
456       for (EdgeCursor edgeCursor = nonAlignableEdges.edges(); edgeCursor.ok(); edgeCursor.next()) {
457         final Edge edge = edgeCursor.edge();
458         final boolean hasAlignableInEdge = checkPredicate(edge.target().inEdges(), edgeAlignable);
459         if (hasAlignableInEdge) {
460           continue;
461         }
462 
463         final Node sRep = (Node) node2NetworkRep.get(edge.source());
464         final Node tRep = (Node) node2NetworkRep.get(edge.target());
465         final EdgeData edgeData = ldp.getEdgeData(edge);
466 
467         final Edge connector;
468         if (hasLeftConstraint(edgeData, true) || hasRightConstraint(edgeData, false)) {
469           connector = network.createEdge(tRep, sRep);
470         } else if (hasRightConstraint(edgeData, true) || hasLeftConstraint(edgeData, false)) {
471           connector = network.createEdge(sRep, tRep);
472         } else {
473           continue;
474         }
475 
476         nonAlignableConnectorMap.setBool(connector, true);
477         edgeMinLength.setInt(connector, 1);
478         edgeWeight.setInt(connector, FlowchartPortOptimizer.PRIORITY_BASIC);
479       }
480 
481       // Afterwards, we ensure that the network is still acyclic.
482       for (EdgeList cycle = Cycles.findCycle(network, true);
483            !cycle.isEmpty(); cycle = Cycles.findCycle(network, true)) {
484         boolean removed = false;
485         for (EdgeCursor ec = cycle.edges(); ec.ok() && !removed; ec.next()) {
486           final Edge edge = ec.edge();
487           if (nonAlignableConnectorMap.getBool(edge)) {
488             network.removeEdge(edge);
489             removed = true;
490           }
491         }
492 
493         if (!removed) {
494           network.removeEdge(cycle.firstEdge());
495         }
496       }
497 
498       //connect nodes to global source/sink
499       Node globalSource = network.createNode();
500       Node globalSink = network.createNode();
501       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
502         Node n = nc.node();
503         Node nRep = (Node) node2NetworkRep.get(n);
504         int nLaneAlignment = node2LaneAlignment.getInt(n);
505         if (!network.containsEdge(nRep, globalSink)) {
506           Edge globalSinkConnector = network.createEdge(nRep, globalSink);
507           edgeWeight.setInt(globalSinkConnector, nLaneAlignment == FlowchartPortOptimizer.LANE_ALIGNMENT_RIGHT ?
508               FlowchartPortOptimizer.PRIORITY_LOW : 0);
509           edgeMinLength.setInt(globalSinkConnector, 0);
510         }
511         if (!network.containsEdge(globalSource, nRep)) {
512           Edge globalSourceConnector = network.createEdge(globalSource, nRep);
513           edgeWeight.setInt(globalSourceConnector, nLaneAlignment == FlowchartPortOptimizer.LANE_ALIGNMENT_LEFT ?
514               FlowchartPortOptimizer.PRIORITY_LOW : 0);
515           edgeMinLength.setInt(globalSourceConnector, 0);
516         }
517       }
518 
519       //apply simplex to each connected component of the network
520       NodeMap networkNode2AlignmentLayer = Maps.createHashedNodeMap();
521       RankAssignments.simplex(network, networkNode2AlignmentLayer, edgeWeight, edgeMinLength);
522 
523       //transfer results to original nodes
524       NodeMap node2AlignmentLayer = Maps.createHashedNodeMap();
525       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
526         Node n = nc.node();
527         Node nRep = (Node) node2NetworkRep.get(n);
528         node2AlignmentLayer.setDouble(n, networkNode2AlignmentLayer.getInt(nRep));
529       }
530 
531       //we do not want to align bend nodes with common nodes except if the (chain of) dummy nodes can be aligned with the corresponding common node
532       NodeMap seenBendMap = Maps.createHashedNodeMap();
533       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
534         Node n = nc.node();
535         if (isBendNode(n, ldp) && !seenBendMap.getBool(n)) {
536           adjustAlignmentLayer(n, node2AlignmentLayer, seenBendMap, ldp);
537         }
538       }
539 
540       //add alignment constraints
541       Arrays.sort(nodes, new AlignedNodePositionComparator(ldp, node2AlignmentLayer));
542       last = null;
543       for (int i = 0; i < nodes.length; i++) {
544         Node n = nodes[i];
545         if (!isGroupNodeBorder(n, ldp) && !isGroupNodeProxy(n, ldp)) {
546           if (last != null && node2AlignmentLayer.getDouble(last) == node2AlignmentLayer.getDouble(n)) {
547             node2AlignWith.set(n, last); //node n should be aligned with last
548           }
549           last = n;
550         }
551       }
552     }
553 
554     private static boolean hasLeftConstraint(EdgeData edgeData, boolean source) {
555       final PortConstraint pc = source ? edgeData.getSPC() : edgeData.getTPC();
556       return pc != null && pc.isAtWest();
557     }
558 
559     private static boolean hasRightConstraint(EdgeData edgeData, boolean source) {
560       final PortConstraint pc = source ? edgeData.getSPC() : edgeData.getTPC();
561       return pc != null && pc.isAtEast();
562     }
563 
564     private static int calcMinLength(Node n1, Node n2, LayoutGraph graph, LayoutDataProvider ldp) {
565       DataProvider node2Parent = graph.getDataProvider(GroupingKeys.PARENT_NODE_ID_DPKEY);
566       if (isGroupNodeBorder(n1, ldp) && isGroupNodeBorder(n2, ldp)) {
567         Node n1GroupNode = ldp.getNodeData(n1).getGroupNode();
568         Node n2GroupNode = ldp.getNodeData(n2).getGroupNode();
569         if (n1GroupNode != n2GroupNode && node2Parent.get(n1) != n2GroupNode && node2Parent.get(n2) != n1GroupNode) {
570           return 1;
571         } else {
572           return 0;
573         }
574       } else if (isGroupNodeBorder(n1, ldp)) {
575         Node n1GroupNode = ldp.getNodeData(n1).getGroupNode();
576         Node n2GroupNode = isGroupNodeProxy(n2, ldp) ? ldp.getNodeData(n2).getGroupNode() : (Node) node2Parent.get(n2);
577         if (n2GroupNode == n1GroupNode) {
578           return 0;
579         } else {
580           return 1;
581         }
582       } else if (isGroupNodeBorder(n2, ldp)) {
583         Node n1GroupNode = isGroupNodeProxy(n1, ldp) ? ldp.getNodeData(n1).getGroupNode() : (Node) node2Parent.get(n1);
584         Node n2GroupNode = ldp.getNodeData(n2).getGroupNode();
585         if (n1GroupNode == n2GroupNode) {
586           return 0;
587         } else {
588           return 1;
589         }
590       } else {
591         return 1;
592       }
593     }
594 
595     private static void adjustAlignmentLayer(Node dummy, NodeMap node2AlignmentLayer, DataAcceptor seenBendMap,
596                                              LayoutDataProvider ldp) {
597       final double dummyAlignmentLayer = node2AlignmentLayer.getDouble(dummy);
598       NodeList seenDummyNodes = new NodeList(dummy);
599       boolean alignsWithCommonNode = false;
600 
601       Edge inEdge = dummy.firstInEdge();
602       while (inEdge != null && isBendNode(inEdge.source(), ldp)
603           && dummyAlignmentLayer == node2AlignmentLayer.getDouble(inEdge.source())) {
604         seenDummyNodes.add(inEdge.source());
605         inEdge = inEdge.source().firstInEdge();
606       }
607       if (inEdge != null && !isBendNode(inEdge.source(), ldp)) {
608         alignsWithCommonNode = dummyAlignmentLayer == node2AlignmentLayer.getDouble(inEdge.source());
609       }
610 
611       Edge outEdge = dummy.firstOutEdge();
612       while (outEdge != null && isBendNode(outEdge.target(), ldp)
613           && dummyAlignmentLayer == node2AlignmentLayer.getDouble(outEdge.target())) {
614         seenDummyNodes.add(outEdge.target());
615         outEdge = outEdge.target().firstOutEdge();
616       }
617       if (!alignsWithCommonNode && outEdge != null && !isBendNode(outEdge.target(), ldp)) {
618         alignsWithCommonNode = dummyAlignmentLayer == node2AlignmentLayer.getDouble(outEdge.target());
619       }
620 
621       for (NodeCursor nc = seenDummyNodes.nodes(); nc.ok(); nc.next()) {
622         seenBendMap.setBool(nc.node(), true);
623         if (!alignsWithCommonNode) {
624           node2AlignmentLayer.setDouble(nc.node(), dummyAlignmentLayer - 0.5); //assign dummy nodes to a separate layer
625         }
626       }
627     }
628 
629     private NodeMap createLaneAlignmentMap(LayoutGraph graph, LayoutDataProvider ldp) {
630       NodeMap node2LaneAlignment = Maps.createHashedNodeMap();
631       for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
632         Node n = nc.node();
633         node2LaneAlignment.setInt(n, getLaneAlignment(n, ldp));
634       }
635       return node2LaneAlignment;
636     }
637 
638     private byte getLaneAlignment(Node n, LayoutDataProvider ldp) {
639       int toLeftCount = 0;
640       int toRightCount = 0;
641       EdgeList nEdges = new EdgeList(n.edges());
642       nEdges.splice(FlowchartPortOptimizer.getSameLayerEdges(n, true, ldp));
643       nEdges.splice(FlowchartPortOptimizer.getSameLayerEdges(n, false, ldp));
644       for (EdgeCursor ec = nEdges.edges(); ec.ok(); ec.next()) {
645         Edge e = ec.edge();
646         if (FlowchartPortOptimizer.isToLeftPartition(n, e.opposite(n), ldp)) {
647           toLeftCount++;
648         } else if (FlowchartPortOptimizer.isToRightPartition(n, e.opposite(n), ldp)) {
649           toRightCount++;
650         }
651       }
652       if (toLeftCount > toRightCount) {
653         return FlowchartPortOptimizer.LANE_ALIGNMENT_LEFT;
654       } else if (toLeftCount < toRightCount) {
655         return FlowchartPortOptimizer.LANE_ALIGNMENT_RIGHT;
656       } else if (isHorizontalOrientation()) {
657         return FlowchartPortOptimizer.LANE_ALIGNMENT_RIGHT;
658       } else {
659         return FlowchartPortOptimizer.LANE_ALIGNMENT_LEFT;
660       }
661     }
662 
663     private static boolean checkPredicate(YCursor cursor, DataProvider predicate) {
664       for (cursor.toFirst(); cursor.ok(); cursor.next()) {
665         if (predicate.getBool(cursor.current())) {
666           return true;
667         }
668       }
669       return false;
670     }
671 
672     private static boolean areInSameLayer(Node n1, Node n2, LayoutDataProvider ldp) {
673       return ldp.getNodeData(n1).getLayer() == ldp.getNodeData(n2).getLayer();
674     }
675 
676     private static boolean isBendNode(Node n, LayoutDataProvider ldp) {
677       final NodeData data = ldp.getNodeData(n);
678       return data != null && (data.getType() == NodeData.TYPE_BEND);
679     }
680 
681     private static boolean isGroupNodeBorder(Node n, LayoutDataProvider ldp) {
682       final NodeData data = ldp.getNodeData(n);
683       return data != null && (data.getType() == NodeData.TYPE_GROUP_BEGIN || data.getType() == NodeData.TYPE_GROUP_END);
684     }
685 
686     private static boolean isGroupNodeProxy(Node n, LayoutDataProvider ldp) {
687       final NodeData data = ldp.getNodeData(n);
688       return data != null && (data.getType() == NodeData.TYPE_PROXY_FOR_EDGE_AT_GROUP);
689     }
690 
691     /**
692      *
693      */
694     static class AlignedNodePositionComparator implements Comparator {
695       private final LayoutDataProvider ldp;
696       private final DataProvider node2AlignmentLayer;
697 
698       AlignedNodePositionComparator(LayoutDataProvider ldp, DataProvider node2AlignmentLayer) {
699         this.ldp = ldp;
700         this.node2AlignmentLayer = node2AlignmentLayer;
701       }
702 
703       public int compare(Object o1, Object o2) {
704         final double al1 = node2AlignmentLayer.getDouble(o1);
705         final double al2 = node2AlignmentLayer.getDouble(o2);
706         if (al1 < al2) {
707           return -1;
708         } else if (al1 > al2) {
709           return 1;
710         } else {
711           return Comparators.compare(ldp.getNodeData((Node) o1).getLayer(), ldp.getNodeData((Node) o2).getLayer());
712         }
713       }
714     }
715 
716     /**
717      *
718      */
719     static class NodePositionComparator implements Comparator {
720       private final LayoutDataProvider ldp;
721 
722       NodePositionComparator(LayoutDataProvider ldp) {
723         this.ldp = ldp;
724       }
725 
726       public int compare(Object o1, Object o2) {
727         final NodeData nd1 = ldp.getNodeData((Node) o1);
728         final NodeData nd2 = ldp.getNodeData((Node) o2);
729         final int l1 = nd1.getLayer();
730         final int l2 = nd2.getLayer();
731         if (l1 < l2) {
732           return -1;
733         } else if (l1 > l2) {
734           return 1;
735         } else {
736           return Comparators.compare(nd1.getPosition(), nd2.getPosition());
737         }
738       }
739     }
740 
741   }
742 }
743