1   /****************************************************************************
2    * This demo file is part of yFiles for Java 2.14.
3    * Copyright (c) 2000-2017 by yWorks GmbH, Vor dem Kreuzberg 28,
4    * 72070 Tuebingen, Germany. All rights reserved.
5    * 
6    * yFiles demo files exhibit yFiles for Java functionalities. Any redistribution
7    * of demo files in source code or binary form, with or without
8    * modification, is not permitted.
9    * 
10   * Owners of a valid software license for a yFiles for Java version that this
11   * demo is shipped with are allowed to use the demo source code as basis
12   * for their own yFiles for Java powered applications. Use of such programs is
13   * governed by the rights and conditions as set out in the yFiles for Java
14   * license agreement.
15   * 
16   * THIS SOFTWARE IS PROVIDED ''AS IS'' AND ANY EXPRESS OR IMPLIED
17   * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
18   * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN
19   * NO EVENT SHALL yWorks BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
20   * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
21   * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
22   * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
23   * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
24   * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25   * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26   *
27   ***************************************************************************/
28  package demo.view.flowchart.layout;
29  
30  import y.base.DataProvider;
31  import y.base.Edge;
32  import y.base.EdgeCursor;
33  import y.base.EdgeList;
34  import y.base.EdgeMap;
35  import y.base.ListCell;
36  import y.base.Node;
37  import y.base.NodeCursor;
38  import y.base.NodeMap;
39  import y.layout.LayoutGraph;
40  import y.layout.PortCandidate;
41  import y.layout.PortConstraint;
42  import y.layout.hierarchic.incremental.AbstractPortConstraintOptimizer;
43  import y.layout.hierarchic.incremental.EdgeData;
44  import y.layout.hierarchic.incremental.ItemFactory;
45  import y.layout.hierarchic.incremental.Layers;
46  import y.layout.hierarchic.incremental.LayoutDataProvider;
47  import y.layout.hierarchic.incremental.NodeData;
48  import y.layout.hierarchic.incremental.PCListOptimizer;
49  import y.layout.hierarchic.incremental.SwimLaneDescriptor;
50  import y.util.Comparators;
51  import y.util.Maps;
52  
53  import java.util.Collection;
54  import java.util.Comparator;
55  import java.util.HashSet;
56  import java.util.Iterator;
57  
58  /**
59   * @noinspection ImplicitNumericConversion, ObjectEquality
60   */
61  class FlowchartPortOptimizer extends AbstractPortConstraintOptimizer {
62    static final byte LANE_ALIGNMENT_LEFT = 0;
63    static final byte LANE_ALIGNMENT_RIGHT = 1;
64  
65    static final int PRIORITY_LOW = 1;
66    static final int PRIORITY_BASIC = 3;
67    static final int PRIORITY_HIGH = 5000;
68  
69    static final String NODE_TO_ALIGN_DP_KEY = "y.layout.hierarchic.incremental.SimlexNodePlacer.NODE_TO_ALIGN_WITH";
70  
71    private final FlowchartAlignmentCalculator alignmentCalculator;
72    private final PCListOptimizer pcListOptimizer;
73  
74    FlowchartPortOptimizer(byte layoutOrientation) {
75      this.alignmentCalculator = new FlowchartAlignmentCalculator();
76      this.pcListOptimizer = new PCListOptimizer();
77  
78      setLayoutOrientation(layoutOrientation);
79    }
80  
81    public void setLayoutOrientation(final byte layoutOrientation) {
82      super.setLayoutOrientation(layoutOrientation);
83  
84      alignmentCalculator.setLayoutOrientation(layoutOrientation);
85      pcListOptimizer.setLayoutOrientation(layoutOrientation);
86    }
87  
88    public void optimizeAfterLayering(LayoutGraph graph, Layers layers, LayoutDataProvider ldp, ItemFactory itemFactory) {
89      pcListOptimizer.optimizeAfterLayering(graph, layers, ldp, itemFactory);
90    }
91  
92    public void optimizeAfterSequencing(LayoutGraph graph, Layers layers, LayoutDataProvider ldp,
93                                        ItemFactory itemFactory) {
94      super.optimizeAfterSequencing(graph, layers, ldp, itemFactory);
95  
96      final EdgeMap edgePriority = Maps.createHashedEdgeMap();
97      final NodeMap nodeAlignment = Maps.createHashedNodeMap();
98  
99      alignmentCalculator.determineAlignment(graph, ldp, nodeAlignment, edgePriority);
100 
101     optimizeForAlignment(graph, ldp, itemFactory, nodeAlignment, edgePriority);
102 
103     optimizeMessageNodes(graph, ldp, itemFactory);
104   }
105 
106   protected void optimizeAfterSequencing(Node node, Comparator inEdgeOrder, Comparator outEdgeOrder, LayoutGraph graph,
107                                          LayoutDataProvider ldp, ItemFactory itemFactory) {
108     // set EAST or WEST temporary constraints for the same layer edges
109     for (EdgeCursor ec = node.edges(); ec.ok(); ec.next()) {
110       final Edge edge = ec.edge();
111 
112       if (isTemporarySameLayerEdge(edge, ldp)) {
113         final byte preferredSide = getPreferredSideForTemporarySameLayerEdge(edge, ldp);
114         itemFactory.setTemporaryPortConstraint(edge, node.equals(edge.source()), PortConstraint.create(preferredSide));
115       }
116     }
117 
118     // choose final temporary constraint for all non-assigned flatwise edges
119     optimizeFlatwiseEdges(node, true, outEdgeOrder, ldp, itemFactory);
120     optimizeFlatwiseEdges(node, false, inEdgeOrder, ldp, itemFactory);
121   }
122 
123   /**
124    * Chooses the final port constraint for all non-assigned flatwise edges.
125    */
126   private void optimizeFlatwiseEdges(final Node node, final boolean source, final Comparator edgeOrder,
127                                      final LayoutDataProvider ldp, final ItemFactory itemFactory) {
128     final Collection flatwiseEdges = new HashSet();
129     final EdgeList centralEdges = new EdgeList();
130 
131     for (EdgeCursor ec = source ? node.outEdges() : node.inEdges(); ec.ok(); ec.next()) {
132       final Edge edge = ec.edge();
133       final EdgeData edgeData = ldp.getEdgeData(edge);
134       final PortConstraint constraint = source ? edgeData.getSPC() : edgeData.getTPC();
135       final Collection candidates = source ? edgeData.getSourceCandidates() : edgeData.getTargetCandidates();
136 
137       if (constraint != null && (constraint.isAtEast() || constraint.isAtWest())) {
138         continue;
139       }
140 
141       if (isFlatwiseCandidateCollection(candidates, getLayoutOrientation())) {
142         flatwiseEdges.add(edge);
143       } else {
144         centralEdges.add(edge);
145       }
146     }
147 
148     if (flatwiseEdges.isEmpty()) {
149       return;
150     }
151 
152     centralEdges.addAll(flatwiseEdges);
153     Comparators.sort(centralEdges, edgeOrder);
154 
155     int i = 0;
156     for (EdgeCursor edgeCursor = centralEdges.edges(); edgeCursor.ok(); edgeCursor.next(), i++) {
157       final Edge edge = edgeCursor.edge();
158       if (flatwiseEdges.contains(edge)) {
159         final byte side = i < centralEdges.size() / 2 ? PortConstraint.WEST : PortConstraint.EAST;
160         itemFactory.setTemporaryPortConstraint(edge, source, PortConstraint.create(side));
161       }
162     }
163   }
164 
165   static boolean isTemporarySameLayerEdge(Edge edge, LayoutDataProvider ldp) {
166     return isTemporarySameLayerNode(edge.target(), ldp);
167   }
168 
169   static boolean isTemporarySameLayerNode(Node node, LayoutDataProvider ldp) {
170     return node.inDegree() == 2 && node.outDegree() == 0 && ldp.getNodeData(node) == null;
171   }
172 
173   static byte getPreferredSideForTemporarySameLayerEdge(Edge edge, LayoutDataProvider ldp) {
174     final Edge originalEdge = ldp.getEdgeData(edge).getAssociatedEdge();
175     final boolean source = originalEdge.source().equals(edge.source());
176     final NodeData sData = ldp.getNodeData(originalEdge.source());
177     final NodeData tData = ldp.getNodeData(originalEdge.target());
178 
179     if (sData.getPosition() < tData.getPosition()) {
180       return source ? PortConstraint.EAST : PortConstraint.WEST;
181     } else {
182       return !source ? PortConstraint.EAST : PortConstraint.WEST;
183     }
184   }
185 
186   private static boolean isAtPreferredPort(Edge edge, boolean source, LayoutDataProvider ldp) {
187     final Edge e = getOriginalEdge(edge, ldp);
188     final EdgeData edgeData = ldp.getEdgeData(e);
189     final PortConstraint pc = source ? edgeData.getSPC() : edgeData.getTPC();
190     return pc != null && (pc.isStrong() || pc.isAtEast() || pc.isAtWest());
191   }
192 
193   private void optimizeForAlignment(LayoutGraph graph, LayoutDataProvider ldp, ItemFactory itemFactory,
194                                     DataProvider node2AlignWith, DataProvider edge2Length) {
195     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
196       final Node node = nc.node();
197       if (!alignmentCalculator.isSpecialNode(graph, node, ldp) || node.degree() < 2) {
198         continue;
199       }
200 
201       node.sortOutEdges(new PositionEdgeComparator(false, ldp));
202       node.sortInEdges(new PositionEdgeComparator(true, ldp));
203 
204       final Edge criticalInEdge = getCriticalInEdge(node, node2AlignWith, edge2Length);
205       final Edge criticalOutEdge = getCriticalOutEdge(node, node2AlignWith, edge2Length);
206 
207       if (criticalInEdge != null || criticalOutEdge != null) {
208         optimizeWithCriticalEdges(node, ldp, itemFactory, criticalInEdge, criticalOutEdge);
209       } else if (node.degree() > 2) {
210         optimizeWithoutCriticalEdges(node, ldp, itemFactory);
211       }
212 
213       // Parallel edges of the critical edges which have a port constraints at the left or right side must have a
214       // port constraint for the same side at the opposite end, too. Otherwise, such an edge gets many bends and
215       // may even destroy the alignment.
216       if (criticalInEdge != null) {
217         for (EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
218           final Edge edge = ec.edge();
219           if (criticalInEdge != edge && criticalInEdge.source() == edge.source()) {
220             final PortConstraint pc = ldp.getEdgeData(edge).getTPC();
221             if (isFlatwisePortConstraint(pc)) {
222               itemFactory.setTemporaryPortConstraint(edge, true, PortConstraint.create(pc.getSide()));
223             }
224           }
225         }
226       }
227       if (criticalOutEdge != null) {
228         for (EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
229           final Edge edge = ec.edge();
230           if (criticalOutEdge != edge && criticalOutEdge.target() == edge.target()) {
231             final PortConstraint pc = ldp.getEdgeData(edge).getSPC();
232             if (isFlatwisePortConstraint(pc)) {
233               itemFactory.setTemporaryPortConstraint(edge, true, PortConstraint.create(pc.getSide()));
234             }
235           }
236         }
237       }
238     }
239   }
240 
241   private static void optimizeWithoutCriticalEdges(Node node, LayoutDataProvider ldp, ItemFactory factory) {
242     if (node.outDegree() > node.inDegree()) {
243       final Edge firstOut = node.firstOutEdge();
244       final Edge lastOut = node.lastOutEdge();
245 
246       if (!hasSameLayerEdge(node, true, ldp) && !isAtPreferredPort(firstOut, true, ldp) &&
247           (node.outDegree() != 2 || !isToRightPartition(firstOut.source(), firstOut.target(), ldp)
248               || hasSameLayerEdge(node, false, ldp))) {
249         factory.setTemporaryPortConstraint(firstOut, true, PortConstraint.create(PortConstraint.WEST));
250 
251       } else if (!hasSameLayerEdge(node, false, ldp) && !isAtPreferredPort(lastOut, true, ldp) &&
252           (node.outDegree() != 2 || !isToLeftPartition(lastOut.source(), lastOut.target(), ldp))) {
253         factory.setTemporaryPortConstraint(lastOut, true, PortConstraint.create(PortConstraint.EAST));
254       }
255 
256     } else {
257       final Edge firstIn = node.firstInEdge();
258       final Edge lastIn = node.lastInEdge();
259 
260       if (!hasSameLayerEdge(node, true, ldp) && !isAtPreferredPort(firstIn, false, ldp) &&
261           (node.degree() != 3 || !isToRightPartition(firstIn.target(), firstIn.source(), ldp)
262               || hasSameLayerEdge(node, false, ldp))) {
263         factory.setTemporaryPortConstraint(firstIn, false, PortConstraint.create(PortConstraint.WEST));
264 
265       } else if (!hasSameLayerEdge(node, false, ldp) && !isAtPreferredPort(lastIn, false, ldp) &&
266           (node.degree() != 3 || !isToLeftPartition(lastIn.target(), lastIn.source(), ldp))) {
267         factory.setTemporaryPortConstraint(lastIn, false, PortConstraint.create(PortConstraint.EAST));
268       }
269     }
270   }
271 
272   private static void optimizeWithCriticalEdges(Node node, LayoutDataProvider ldp, ItemFactory factory,
273                                                 Edge criticalInEdge, Edge criticalOutEdge) {
274     final Edge firstIn = node.firstInEdge();
275     final Edge firstOut = node.firstOutEdge();
276     final Edge lastIn = node.lastInEdge();
277     final Edge lastOut = node.lastOutEdge();
278 
279     if (node.degree() == 3 && node.outDegree() == 2 && criticalOutEdge == null) {
280       // Special case: the only in-edge is critical and there are two free out-edges
281       if ((!isToRightPartition(firstOut.source(), firstOut.target(), ldp) && isBackEdge(firstOut, ldp))
282           || isToLeftPartition(firstOut.source(), firstOut.target(), ldp)) {
283         setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
284         if ((!isToLeftPartition(lastOut.source(), lastOut.target(), ldp) && isBackEdge(lastOut, ldp))
285             || isToRightPartition(lastOut.source(), lastOut.target(), ldp)) {
286           setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
287         }
288       } else {
289         setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
290       }
291 
292     } else {
293 
294       if (node.degree() == 3 && node.inDegree() == 2 && criticalInEdge == null) {
295         // Special case: the only out-edge is critical and there are two free in-edges
296         if ((!isToRightPartition(firstIn.target(), firstIn.source(), ldp) && isBackEdge(firstIn, ldp))
297             || isToLeftPartition(firstIn.target(), firstIn.source(), ldp)) {
298           setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
299           if ((!isToRightPartition(lastIn.target(), lastIn.source(), ldp) && isBackEdge(lastIn, ldp))
300               || isToLeftPartition(lastIn.target(), lastIn.source(), ldp)) {
301             setOptimizedPortConstraint(lastIn, true, PortConstraint.EAST, ldp, factory);
302           }
303         } else {
304           setOptimizedPortConstraint(lastIn, true, PortConstraint.EAST, ldp, factory);
305         }
306 
307       } else if (criticalInEdge == null || (node.outDegree() > node.inDegree() && criticalOutEdge != null)) {
308 
309         if (!hasSameLayerEdge(node, true, ldp)) {
310           if (firstOut != criticalOutEdge) {
311             setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
312           } else if (firstIn != null && firstIn != criticalInEdge && node.inDegree() > 1) {
313             setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
314           }
315         }
316 
317         if (!hasSameLayerEdge(node, false, ldp)) {
318           if (lastOut != criticalOutEdge) {
319             setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
320           } else if (lastIn != null && lastIn != criticalInEdge && node.inDegree() > 1) {
321             setOptimizedPortConstraint(lastIn, false, PortConstraint.EAST, ldp, factory);
322           }
323         }
324 
325       } else {
326         if (!hasSameLayerEdge(node, true, ldp)) {
327           if (firstIn != criticalInEdge) {
328             setOptimizedPortConstraint(firstIn, false, PortConstraint.WEST, ldp, factory);
329           } else if (firstOut != null && firstOut != criticalOutEdge && node.outDegree() > 1) {
330             setOptimizedPortConstraint(firstOut, true, PortConstraint.WEST, ldp, factory);
331           }
332         }
333         if (!hasSameLayerEdge(node, false, ldp)) {
334           if (lastIn != criticalInEdge) {
335             setOptimizedPortConstraint(lastIn, false, PortConstraint.EAST, ldp, factory);
336           } else if (lastOut != null && lastOut != criticalOutEdge && node.outDegree() > 1) {
337             setOptimizedPortConstraint(lastOut, true, PortConstraint.EAST, ldp, factory);
338           }
339         }
340       }
341     }
342   }
343 
344   private static void setOptimizedPortConstraint(Edge edge, boolean source, byte direction, LayoutDataProvider ldp,
345                                                  ItemFactory factory) {
346     if (!isAtPreferredPort(edge, source, ldp)) {
347       factory.setTemporaryPortConstraint(edge, source, PortConstraint.create(direction));
348     }
349   }
350 
351   /**
352    * Special handling for messages (always attach them to the side of nodes)
353    */
354   private static void optimizeMessageNodes(LayoutGraph graph, LayoutDataProvider ldp, ItemFactory factory) {
355     final EdgeList edges = new EdgeList(graph.edges());
356     edges.splice(getSameLayerEdges(graph, ldp));
357 
358     for (EdgeCursor ec = edges.edges(); ec.ok(); ec.next()) {
359       final Edge e = ec.edge();
360       final Edge original = getOriginalEdge(e, ldp);
361       final int sourceLaneId = getSwimlaneId(original.source(), ldp);
362       final int targetLaneId = getSwimlaneId(original.target(), ldp);
363 
364       if (FlowchartElements.isMessageFlow(graph, e) && sourceLaneId != targetLaneId) {
365         if (ldp.getNodeData(e.source()).getType() == NodeData.TYPE_NORMAL
366             && FlowchartElements.isActivity(graph, e.source())) {
367           factory.setTemporaryPortConstraint(e, true, PortConstraint.create(
368               sourceLaneId < targetLaneId ? PortConstraint.EAST : PortConstraint.WEST));
369         }
370 
371         if (ldp.getNodeData(e.target()).getType() == NodeData.TYPE_NORMAL
372             && FlowchartElements.isActivity(graph, e.target())) {
373           factory.setTemporaryPortConstraint(e, false, PortConstraint.create(
374               sourceLaneId < targetLaneId ? PortConstraint.WEST : PortConstraint.EAST));
375         }
376       }
377     }
378   }
379 
380   static EdgeList getSameLayerEdges(LayoutGraph graph, LayoutDataProvider ldp) {
381     EdgeList sameLayerEdges = new EdgeList();
382     EdgeMap edge2Seen = Maps.createHashedEdgeMap();
383     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
384       Node n = nc.node();
385       NodeData nData = ldp.getNodeData(n);
386       for (ListCell cell = nData.getFirstSameLayerEdgeCell(); cell != null; cell = cell.succ()) {
387         Edge sameLayerEdge = (Edge) cell.getInfo();
388         Node opposite = sameLayerEdge.opposite(n);
389         if (!edge2Seen.getBool(sameLayerEdge) && graph.contains(opposite)) {
390           sameLayerEdges.add(sameLayerEdge);
391           edge2Seen.setBool(sameLayerEdge, true);
392         }
393       }
394     }
395     return sameLayerEdges;
396   }
397 
398   static EdgeList getSameLayerEdges(Node n, boolean left, LayoutDataProvider ldp) {
399     NodeData nData = ldp.getNodeData(n);
400     int nPos = nData.getPosition();
401     EdgeList result = new EdgeList();
402     for (ListCell cell = nData.getFirstSameLayerEdgeCell(); cell != null; cell = cell.succ()) {
403       Edge sameLayerEdge = (Edge) cell.getInfo();
404       Node other = sameLayerEdge.opposite(n);
405       int otherPos = ldp.getNodeData(other).getPosition();
406       if ((left && otherPos < nPos) || (!left && otherPos > nPos)) {
407         result.add(sameLayerEdge);
408       }
409     }
410     return result;
411   }
412 
413   static boolean hasSameLayerEdge(Node n, boolean left, LayoutDataProvider ldp) {
414     return !getSameLayerEdges(n, left, ldp).isEmpty();
415   }
416 
417   static boolean isFlatwisePortConstraint(PortConstraint pc) {
418     return pc != null && (pc.isAtEast() || pc.isAtWest());
419   }
420 
421   static boolean isFlatwiseCandidateCollection(Collection pcs, byte layoutOrientation) {
422     if (pcs == null) {
423       return false;
424     }
425 
426     boolean containsEast = false;
427     boolean containsWest = false;
428     for (Iterator iterator = pcs.iterator(); iterator.hasNext(); ) {
429       final PortCandidate pc = (PortCandidate) iterator.next();
430       final int direction = pc.getDirectionForLayoutOrientation(layoutOrientation);
431       if (!containsEast && (PortCandidate.EAST & direction) != 0) {
432         containsEast = true;
433       }
434       if (!containsWest && (PortCandidate.WEST & direction) != 0) {
435         containsWest = true;
436       }
437     }
438 
439     return containsEast && containsWest;
440   }
441 
442   static boolean isBackEdge(Edge edge, LayoutDataProvider ldp) {
443     return ldp.getEdgeData(edge).isReversed();
444   }
445 
446   /**
447    * Returns an in-edge for the given node which comes from the node it is aligned with. If several such edges exist,
448    * the edge with the highest length is returned.
449    */
450   private static Edge getCriticalInEdge(Node node, DataProvider node2AlignWith, DataProvider edge2Length) {
451     Edge bestEdge = null;
452     for (EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
453       final Edge edge = ec.edge();
454       if (node2AlignWith.get(node) == edge.source() &&
455           (bestEdge == null || edge2Length.getDouble(bestEdge) < edge2Length.getInt(edge))) {
456         bestEdge = edge;
457       }
458     }
459 
460     return bestEdge;
461   }
462 
463   /**
464    * Returns an out-edge for the given node which goes to the node it is aligned with. If several such edges exist, the
465    * edge with the highest length is returned.
466    */
467   private static Edge getCriticalOutEdge(Node node, DataProvider node2AlignWith, DataProvider edge2Length) {
468     Edge bestEdge = null;
469     for (EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
470       final Edge edge = ec.edge();
471       if (node2AlignWith.get(edge.target()) == node &&
472           (bestEdge == null || edge2Length.getDouble(bestEdge) < edge2Length.getInt(edge))) {
473         bestEdge = edge;
474       }
475     }
476 
477     return bestEdge;
478   }
479 
480   static Edge getOriginalEdge(Edge e, LayoutDataProvider ldp) {
481     NodeData sData = ldp.getNodeData(e.source());
482     if (sData.getType() == NodeData.TYPE_BEND && sData.getAssociatedEdge() != null) {
483       return sData.getAssociatedEdge();
484     }
485     NodeData tData = ldp.getNodeData(e.target());
486     if (tData.getType() == NodeData.TYPE_BEND && tData.getAssociatedEdge() != null) {
487       return tData.getAssociatedEdge();
488     }
489 
490 //    final EdgeData edgeData = ldp.getEdgeData(e);
491 //    if (edgeData.getAssociatedEdge() != null) {
492 //      return edgeData.getAssociatedEdge();
493 //    }
494 
495     return e;
496   }
497 
498   static int getSwimlaneId(Node n, LayoutDataProvider ldp) {
499     SwimLaneDescriptor laneDesc = ldp.getNodeData(n).getSwimLaneDescriptor();
500     return laneDesc == null ? -1 : laneDesc.getComputedLaneIndex();
501   }
502 
503   static boolean isToLeftPartition(Node source, Node target, LayoutDataProvider layoutData) {
504     SwimLaneDescriptor sourceDesc = layoutData.getNodeData(source).getSwimLaneDescriptor();
505     SwimLaneDescriptor targetDesc = layoutData.getNodeData(target).getSwimLaneDescriptor();
506     return sourceDesc != targetDesc && sourceDesc != null && targetDesc != null
507         && sourceDesc.getComputedLaneIndex() > targetDesc.getComputedLaneIndex();
508   }
509 
510   static boolean isToRightPartition(Node source, Node target, LayoutDataProvider layoutData) {
511     SwimLaneDescriptor sourceDesc = layoutData.getNodeData(source).getSwimLaneDescriptor();
512     SwimLaneDescriptor targetDesc = layoutData.getNodeData(target).getSwimLaneDescriptor();
513     return sourceDesc != targetDesc && sourceDesc != null && targetDesc != null
514         && sourceDesc.getComputedLaneIndex() < targetDesc.getComputedLaneIndex();
515   }
516 
517   /**
518    * Compares edges between the same layers according to the position of the end nodes of the specified end. Ties are
519    * broken by the direction of the port constraints at the specified end, then at the opposite end, where WEST is first
520    * and EAST is last.
521    * <p/>
522    * Can be used, for example, to sort in- or out-edges of a specific node in the typical best way.
523    */
524   static class PositionEdgeComparator implements Comparator {
525     private final boolean source;
526     private final LayoutDataProvider ldp;
527     private final SameLayerNodePositionComparator sameLayerNodePositionComparator;
528     private final SingleSidePortConstraintComparator portConstraintComparator;
529 
530     PositionEdgeComparator(boolean source, LayoutDataProvider ldp) {
531       sameLayerNodePositionComparator = new SameLayerNodePositionComparator(ldp);
532       portConstraintComparator = new SingleSidePortConstraintComparator();
533       this.source = source;
534       this.ldp = ldp;
535     }
536 
537     public int compare(Object o1, Object o2) {
538       final Edge e1 = (Edge) o1;
539       final Edge e2 = (Edge) o2;
540 
541       // compare positions at specified end
542       final int comparePos = sameLayerNodePositionComparator.compare(
543           source ? e1.source() : e1.target(), source ? e2.source() : e2.target());
544       if (comparePos != 0) {
545         return comparePos;
546       }
547 
548       // compare constraints at specified end
549       final int compareConstraints = portConstraintComparator.compare(
550           source ? ldp.getEdgeData(e1).getSPC() : ldp.getEdgeData(e1).getTPC(),
551           source ? ldp.getEdgeData(e2).getSPC() : ldp.getEdgeData(e2).getTPC());
552       if (compareConstraints != 0) {
553         return compareConstraints;
554       }
555 
556       // compare constraints at opposite end
557       return portConstraintComparator.compare(
558           source ? ldp.getEdgeData(e1).getTPC() : ldp.getEdgeData(e1).getSPC(),
559           source ? ldp.getEdgeData(e2).getTPC() : ldp.getEdgeData(e2).getSPC());
560     }
561   }
562 
563   /**
564    * Compares port constraints with respect to the upper or lower side of a node, that is WEST is first, EAST is last,
565    * and NORTH and SOUTH are neutral elements in the middle.
566    */
567   static class SingleSidePortConstraintComparator implements Comparator {
568 
569     public int compare(Object o1, Object o2) {
570       final PortConstraint pc1 = (PortConstraint) o1;
571       final PortConstraint pc2 = (PortConstraint) o2;
572 
573       // we use NORTH as neutral element since we care only about EST and WEST
574       final byte b1 = pc1 != null ? pc1.getSide() : PortConstraint.NORTH;
575       final byte b2 = pc2 != null ? pc2.getSide() : PortConstraint.NORTH;
576       if (b1 == b2) {
577         return 0;
578       } else if (b1 == PortConstraint.WEST || b2 == PortConstraint.EAST) {
579         return -1;
580       } else {
581         return 1;
582       }
583     }
584   }
585 
586   /**
587    * Compares nodes in the same layer according to their positions.
588    */
589   static class SameLayerNodePositionComparator implements Comparator {
590     private final LayoutDataProvider ldp;
591 
592     SameLayerNodePositionComparator(LayoutDataProvider ldp) {
593       this.ldp = ldp;
594     }
595 
596     public int compare(Object o1, Object o2) {
597       return Comparators.compare(ldp.getNodeData((Node) o1).getPosition(), ldp.getNodeData((Node) o2).getPosition());
598     }
599   }
600 
601 }
602