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