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.layout.module;
29  
30  import y.module.LayoutModule;
31  import y.module.YModule;
32  
33  import y.base.DataProvider;
34  import y.base.Edge;
35  import y.base.EdgeCursor;
36  import y.base.EdgeMap;
37  import y.base.Node;
38  import y.base.NodeCursor;
39  import y.layout.ComponentLayouter;
40  import y.layout.LabelLayoutConstants;
41  import y.layout.LabelRanking;
42  import y.layout.LayoutGraph;
43  import y.layout.OrientationLayouter;
44  import y.layout.PortConstraintKeys;
45  import y.layout.PreferredPlacementDescriptor;
46  import y.layout.labeling.GreedyMISLabeling;
47  import y.layout.orthogonal.DirectedOrthogonalLayouter;
48  import y.layout.orthogonal.EdgeLayoutDescriptor;
49  import y.option.ArrowCellRenderer;
50  import y.option.ConstraintManager;
51  import y.option.EnumOptionItem;
52  import y.option.IntOptionItem;
53  import y.option.OptionGroup;
54  import y.option.OptionHandler;
55  import y.option.OptionItem;
56  import y.option.StrokeCellRenderer;
57  import y.util.DataProviderAdapter;
58  import y.util.pq.BHeapIntNodePQ;
59  import y.view.Arrow;
60  import y.view.EdgeLabel;
61  import y.view.EdgeRealizer;
62  import y.view.Graph2D;
63  import y.view.LineType;
64  
65  import java.awt.Color;
66  
67  
68  /**
69   * This module represents an interactive configurator and launcher for
70   * {@link y.layout.orthogonal.DirectedOrthogonalLayouter}.
71   *
72   * @see <a href="http://docs.yworks.com/yfiles/doc/api/index.html#/dguide/directed_orthogonal_layouter#directed_orthogonal_layouter" target="_blank">Section Directed Orthogonal Layout</a> in the yFiles for Java Developer's Guide
73   */
74  public class DirectedOrthogonalLayoutModule extends LayoutModule {
75    //// Module 'Directed Orthogonal Layout' / 'UML Style'
76    protected static final String MODULE_DIRECTED_ORTHOGONAL_LAYOUTER = "DIRECTED_ORTHOGONAL_LAYOUTER";
77    
78    //// Section 'Layout'
79    protected static final String SECTION_LAYOUT = "LAYOUT";
80    // Section 'Layout' items
81    protected static final String ITEM_GRID = "GRID";
82    protected static final String ITEM_ORIENTATION = "ORIENTATION";
83    protected static final String VALUE_TOP_TO_BOTTOM = "TOP_TO_BOTTOM";
84    protected static final String VALUE_LEFT_TO_RIGHT = "LEFT_TO_RIGHT";
85    protected static final String VALUE_BOTTOM_TO_TOP = "BOTTOM_TO_TOP";
86    protected static final String VALUE_RIGHT_TO_LEFT = "RIGHT_TO_LEFT";
87    protected static final String ITEM_USE_EXISTING_DRAWING_AS_SKETCH = "USE_EXISTING_DRAWING_AS_SKETCH";
88    protected static final String TITLE_IDENTIFY_DIRECTED_EDGES = "IDENTIFY_DIRECTED_EDGES";
89    protected static final String ITEM_USE_AS_CRITERIA = "USE_AS_CRITERIA";
90    protected static final String ITEM_LINE_COLOR = "LINE_COLOR";
91    protected static final String ITEM_TARGET_ARROW = "TARGET_ARROW";
92    protected static final String ITEM_LINE_TYPE = "LINE_TYPE";
93    protected static final String ITEM_AUTO_GROUP_DIRECTED_EDGES = "AUTO_GROUP_DIRECTED_EDGES";
94    protected static final String ITEM_MINIMUM_FIRST_SEGMENT_LENGTH = "MINIMUM_FIRST_SEGMENT_LENGTH";
95    protected static final String ITEM_MINIMUM_LAST_SEGMENT_LENGTH = "MINIMUM_LAST_SEGMENT_LENGTH";
96    protected static final String ITEM_MINIMUM_SEGMENT_LENGTH = "MINIMUM_SEGMENT_LENGTH";
97    protected static final String ITEM_PERCEIVED_BENDS_POSTPROCESSING = "PERCEIVED_BENDS_POSTPROCESSING";
98    protected static final String ITEM_ALIGN_DEGREE_ONE_NODES = "ALIGN_DEGREE_ONE_NODES";
99    protected static final String ITEM_POSTPROCESSING_ENABLED = "POSTPROCESSING_ENABLED";
100   
101   //// Section 'Labeling'
102   protected static final String SECTION_LABELING = "LABELING";
103   // Section 'Labeling' items
104   protected static final String ITEM_EDGE_LABELING = "EDGE_LABELING";
105   protected static final String VALUE_NONE = "NONE";
106   protected static final String VALUE_INTEGRATED = "INTEGRATED";
107   protected static final String VALUE_GENERIC = "GENERIC";
108   protected static final String ITEM_EDGE_LABEL_MODEL = "EDGE_LABEL_MODEL";
109   protected static final String VALUE_BEST = "BEST";
110   protected static final String VALUE_AS_IS = "AS_IS";
111   protected static final String VALUE_CENTER_SLIDER = "CENTER_SLIDER";
112   protected static final String VALUE_SIDE_SLIDER = "SIDE_SLIDER";
113   protected static final String VALUE_FREE = "FREE";
114   protected static final String ITEM_CONSIDER_NODE_LABELS = "CONSIDER_NODE_LABELS";
115   
116   // data provider delete flag
117   private boolean isEdgeDPAddedByModule = false;
118 
119   /**
120    * Creates an instance of this module.
121    */
122   public DirectedOrthogonalLayoutModule() {
123     super(MODULE_DIRECTED_ORTHOGONAL_LAYOUTER);
124     setPortIntersectionCalculatorEnabled(true);
125   }
126 
127   /**
128    * Creates an OptionHandler and adds the option items used by this module.
129    * @return the created <code>OptionHandler</code> providing module related options
130    */
131   protected OptionHandler createOptionHandler() {
132     final OptionHandler options = new OptionHandler(getModuleName());
133     final ConstraintManager optionConstraints = new ConstraintManager(options);
134 
135     //// Section 'Layout'
136     options.useSection(SECTION_LAYOUT);
137     // Populate section
138     options.addInt(ITEM_GRID,25).setAttribute(IntOptionItem.ATTRIBUTE_MIN_VALUE, new Integer(1));
139     options.addEnum(ITEM_ORIENTATION, new String[]{
140         VALUE_TOP_TO_BOTTOM,
141         VALUE_LEFT_TO_RIGHT,
142         VALUE_BOTTOM_TO_TOP,
143         VALUE_RIGHT_TO_LEFT
144     }, 0);
145     final OptionItem itemUseDrawingAsSketch = options.addBool(ITEM_USE_EXISTING_DRAWING_AS_SKETCH, false);
146 
147     // Group 'Identify Direct Edges'
148     final OptionGroup directEdgesGroup = new OptionGroup();
149     directEdgesGroup.setAttribute(OptionGroup.ATTRIBUTE_TITLE, TITLE_IDENTIFY_DIRECTED_EDGES);
150     // Populate group
151     final OptionItem itemUseAsCriteria = directEdgesGroup.addItem(
152         options.addEnum(ITEM_USE_AS_CRITERIA, new String[]{
153             ITEM_LINE_COLOR,
154             ITEM_TARGET_ARROW,
155             ITEM_LINE_TYPE
156         }, 0));
157     final OptionItem itemLineColor = directEdgesGroup.addItem(options.addColor(ITEM_LINE_COLOR, Color.red, true));
158     final EnumOptionItem itemTargetArrow = new EnumOptionItem(ITEM_TARGET_ARROW,
159         Arrow.availableArrows().toArray(), Arrow.STANDARD);
160     itemTargetArrow.setAttribute(EnumOptionItem.ATTRIBUTE_RENDERER, new ArrowCellRenderer());
161     itemTargetArrow.setUsingIntegers(true);
162     directEdgesGroup.addItem(options.addItem(itemTargetArrow));
163     final EnumOptionItem itemLineType = new EnumOptionItem(ITEM_LINE_TYPE,
164         LineType.availableLineTypes().toArray(), LineType.LINE_2);
165     itemLineType.setAttribute(EnumOptionItem.ATTRIBUTE_RENDERER, new StrokeCellRenderer());
166     itemLineType.setUsingIntegers(true);
167     directEdgesGroup.addItem(options.addItem(itemLineType));
168     // Enable/disable items depending on specific values
169     optionConstraints.setEnabledOnValueEquals(itemUseAsCriteria, ITEM_LINE_COLOR, itemLineColor);
170     optionConstraints.setEnabledOnValueEquals(itemUseAsCriteria, ITEM_TARGET_ARROW, itemTargetArrow);
171     optionConstraints.setEnabledOnValueEquals(itemUseAsCriteria, ITEM_LINE_TYPE, itemLineType);
172 
173     // Edge settings
174     // Populate section
175     final OptionItem itemAutoGroupDirectedEdges = options.addBool(ITEM_AUTO_GROUP_DIRECTED_EDGES, true);
176     options.addDouble(ITEM_MINIMUM_FIRST_SEGMENT_LENGTH, 10);
177     options.addDouble(ITEM_MINIMUM_LAST_SEGMENT_LENGTH, 10);
178     options.addDouble(ITEM_MINIMUM_SEGMENT_LENGTH, 10);
179     options.addBool(ITEM_PERCEIVED_BENDS_POSTPROCESSING, true);
180     options.addBool(ITEM_ALIGN_DEGREE_ONE_NODES, true);
181     options.addBool(ITEM_POSTPROCESSING_ENABLED, true);
182     // Enable/disable items depending on specific values
183     optionConstraints.setEnabledOnValueEquals(itemUseDrawingAsSketch, Boolean.FALSE,
184         itemAutoGroupDirectedEdges);
185 
186     //// Section 'Labeling'
187     options.useSection(SECTION_LABELING);
188     // Populate section
189     final EnumOptionItem itemEdgeLabeling = options.addEnum(ITEM_EDGE_LABELING, new String[]{
190         VALUE_NONE,
191         VALUE_INTEGRATED,
192         VALUE_GENERIC
193     }, 0);
194     final OptionGroup labelingGroup = new OptionGroup();
195     final OptionItem itemEdgeLabelModel = labelingGroup.addItem(
196         options.addEnum(ITEM_EDGE_LABEL_MODEL, new String[]{
197             VALUE_BEST,
198             VALUE_AS_IS,
199             VALUE_CENTER_SLIDER,
200             VALUE_SIDE_SLIDER,
201             VALUE_FREE,
202         }, 0));
203     labelingGroup.addItem(options.addBool(ITEM_CONSIDER_NODE_LABELS, false));
204     // Enable/disable items depending on specific values
205     optionConstraints.setEnabledOnValueEquals(itemEdgeLabeling, VALUE_NONE, itemEdgeLabelModel, true);
206 
207     return options;
208   }
209 
210   /**
211    * Main module execution routine.
212    * Launches the module's underlying algorithm on the module's graph based on user options.
213    */
214   protected void mainrun() {
215     final DirectedOrthogonalLayouter orthogonal = new DirectedOrthogonalLayouter();
216     
217     final OptionHandler options = getOptionHandler();
218     configure(orthogonal, options);
219     
220     final Graph2D graph = getGraph2D();
221     prepareGraph(graph, options);
222     try {
223       launchLayouter(orthogonal, true);
224     } finally {
225       restoreGraph(graph, options);
226     }
227   }
228 
229   /**
230    * Prepares a <code>graph</code> depending on the given options for the
231    * module's layout algorithm.
232    * <br>
233    * Additional resources created by this method have to be freed up by calling
234    * {@link #restoreGraph(y.view.Graph2D, y.option.OptionHandler)} after
235    * layout calculation.  
236    * @param graph the graph to be prepared
237    * @param options the options for the module's layout algorithm
238    */
239   protected void prepareGraph(final Graph2D graph, final OptionHandler options) {
240     final String el = options.getString(ITEM_EDGE_LABELING);
241     if (!el.equals(VALUE_NONE)) {
242       setupEdgeLabelModel(graph, el, options.getString(ITEM_EDGE_LABEL_MODEL));
243     }
244     
245     DataProvider upwardDP = graph.getDataProvider(DirectedOrthogonalLayouter.DIRECTED_EDGE_DPKEY);
246     if (upwardDP == null) {
247       //determine upward edges if not already marked.
248       upwardDP = new DataProviderAdapter() {
249         public boolean getBool(Object o) {
250           final EdgeRealizer er = graph.getRealizer((Edge)o);
251           if (options.get(ITEM_USE_AS_CRITERIA).equals(ITEM_LINE_COLOR)) {
252             final Color c1 = (Color) options.get(ITEM_LINE_COLOR);
253             final Color c2 = er.getLineColor();
254             return c1 != null && c1.equals(c2);
255           } else if (options.get(ITEM_USE_AS_CRITERIA).equals(ITEM_TARGET_ARROW)) {
256             final Arrow a1 = (Arrow) options.get(ITEM_TARGET_ARROW);
257             final Arrow a2 = er.getTargetArrow();
258             return a1 != null && a1.equals(a2);
259           } else if (options.get(ITEM_USE_AS_CRITERIA).equals(ITEM_LINE_TYPE)) {
260             final LineType l1 = (LineType) options.get(ITEM_LINE_TYPE);
261             final LineType l2 = er.getLineType();
262             return l1 != null && l1.equals(l2);
263           }
264           return false;
265         }
266       };
267       graph.addDataProvider(DirectedOrthogonalLayouter.DIRECTED_EDGE_DPKEY, upwardDP);
268       isEdgeDPAddedByModule = true;
269     }
270 
271     if (options.getBool(ITEM_AUTO_GROUP_DIRECTED_EDGES)) {
272       // backup existing data providers to prevent loss of user settings
273       backupDataProvider(graph, PortConstraintKeys.SOURCE_GROUPID_KEY);
274       backupDataProvider(graph, PortConstraintKeys.TARGET_GROUPID_KEY);
275       
276       final EdgeMap sgMap = graph.createEdgeMap();
277       final EdgeMap tgMap = graph.createEdgeMap();
278       graph.addDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY, sgMap);
279       graph.addDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY, tgMap);
280       autoGroupEdges(graph, sgMap, tgMap, upwardDP);
281     }
282   }
283 
284   /**
285    * Restores the given <code>graph</code> by freeing up resources created by
286    * {@link #prepareGraph(y.view.Graph2D, y.option.OptionHandler)}.
287    * @param graph the graph for which <code>prepareGraph</code> has been called
288    * @param options the options for the module's layout algorithm
289    */
290   protected void restoreGraph(final Graph2D graph, final OptionHandler options) {
291     if (options.getBool(ITEM_AUTO_GROUP_DIRECTED_EDGES)) {
292       // release resources
293       final EdgeMap sgMap = (EdgeMap) graph.getDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY);
294       final EdgeMap tgMap = (EdgeMap) graph.getDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY);
295       if (sgMap != null) {
296         graph.disposeEdgeMap(sgMap);
297       }
298       if (tgMap != null) {
299         graph.disposeEdgeMap(tgMap);
300       }
301       
302       // remove the data providers set by this module by restoring the initial state
303       restoreDataProvider(graph, PortConstraintKeys.SOURCE_GROUPID_KEY);
304       restoreDataProvider(graph, PortConstraintKeys.TARGET_GROUPID_KEY);
305     }
306     if (isEdgeDPAddedByModule) {
307       isEdgeDPAddedByModule = false;
308       graph.removeDataProvider(DirectedOrthogonalLayouter.DIRECTED_EDGE_DPKEY);
309     }
310   }
311 
312   /**
313    * Configures the module's layout algorithm according to the given options.
314    * @param orthogonal the <code>DirectedOrthogonalLayouter</code> to be configured
315    * @param options the layout options to set
316    */
317   protected void configure(final DirectedOrthogonalLayouter orthogonal, final OptionHandler options) {
318     final EdgeLayoutDescriptor layoutDescriptor = orthogonal.getEdgeLayoutDescriptor();
319     layoutDescriptor.setMinimumFirstSegmentLength(options.getDouble(ITEM_MINIMUM_FIRST_SEGMENT_LENGTH));
320     layoutDescriptor.setMinimumLastSegmentLength(options.getDouble(ITEM_MINIMUM_LAST_SEGMENT_LENGTH));
321     layoutDescriptor.setMinimumSegmentLength(options.getDouble(ITEM_MINIMUM_SEGMENT_LENGTH));
322 
323     orthogonal.setGrid(options.getInt(ITEM_GRID));
324     orthogonal.setPerceivedBendsOptimizationEnabled(options.getBool(ITEM_PERCEIVED_BENDS_POSTPROCESSING));
325     orthogonal.setUsePostprocessing(options.getBool(ITEM_POSTPROCESSING_ENABLED));
326     orthogonal.setAlignDegreeOneNodesEnabled(options.getBool(ITEM_ALIGN_DEGREE_ONE_NODES));
327     orthogonal.setUseSketchDrawing(options.getBool(ITEM_USE_EXISTING_DRAWING_AS_SKETCH));
328     ((ComponentLayouter) orthogonal.getComponentLayouter()).setStyle(ComponentLayouter.STYLE_MULTI_ROWS);
329 
330     final Object orientation = options.get(ITEM_ORIENTATION);
331     if (VALUE_TOP_TO_BOTTOM.equals(orientation)) {
332       orthogonal.setLayoutOrientation(OrientationLayouter.TOP_TO_BOTTOM);
333     } else if (VALUE_LEFT_TO_RIGHT.equals(orientation)) {
334       orthogonal.setLayoutOrientation(OrientationLayouter.LEFT_TO_RIGHT);
335     } else if (VALUE_BOTTOM_TO_TOP.equals(orientation)) {
336       orthogonal.setLayoutOrientation(OrientationLayouter.BOTTOM_TO_TOP);
337     } else if (VALUE_RIGHT_TO_LEFT.equals(orientation)) {
338       orthogonal.setLayoutOrientation(OrientationLayouter.RIGHT_TO_LEFT);
339     }
340 
341     ////////////////////////////////////////////////////////////////////////////
342     // Labels
343     ////////////////////////////////////////////////////////////////////////////
344 
345     if (options.getBool(ITEM_CONSIDER_NODE_LABELS)) {
346       orthogonal.setConsiderNodeLabelsEnabled(true);
347     }
348 
349     final String el = options.getString(ITEM_EDGE_LABELING);
350     orthogonal.setIntegratedEdgeLabelingEnabled(el.equals(VALUE_INTEGRATED));
351     orthogonal.setConsiderNodeLabelsEnabled(options.getBool(ITEM_CONSIDER_NODE_LABELS));
352     
353     if (el.equals(VALUE_GENERIC)) {
354       GreedyMISLabeling la = new GreedyMISLabeling();
355       la.setPlaceNodeLabels(false);
356       la.setPlaceEdgeLabels(true);
357       la.setAutoFlippingEnabled(true);
358       la.setProfitModel(new LabelRanking());
359       orthogonal.appendStage(la);
360     }
361   }
362 
363   private void setupEdgeLabelModel(final Graph2D graph, final String edgeLabeling, final String edgeLabelModel) {
364     if (edgeLabeling.equals(VALUE_NONE) || edgeLabelModel.equals(VALUE_AS_IS)) {
365       return; //nothing to do
366     }
367 
368     byte model = EdgeLabel.SIDE_SLIDER;
369     if (edgeLabelModel.equals(VALUE_CENTER_SLIDER)) {
370       model = EdgeLabel.CENTER_SLIDER;
371     } else if (edgeLabelModel.equals(VALUE_FREE) || edgeLabelModel.equals(VALUE_BEST)) {
372       model = EdgeLabel.FREE;
373     }
374 
375     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
376       final Edge e = ec.edge();
377       EdgeRealizer er = graph.getRealizer(e);
378       for (int i = 0; i < er.labelCount(); i++) {
379         final EdgeLabel el = er.getLabel(i);
380         el.setModel(model);
381         final byte prefOnSide = el.getPreferredPlacementDescriptor().getSideOfEdge();
382         if (model == EdgeLabel.CENTER_SLIDER && prefOnSide != LabelLayoutConstants.PLACE_ON_EDGE) {
383           setPreferredSide(el, LabelLayoutConstants.PLACE_ON_EDGE);
384         } else if (model == EdgeLabel.SIDE_SLIDER && prefOnSide == LabelLayoutConstants.PLACE_ON_EDGE) {
385           setPreferredSide(el, LabelLayoutConstants.PLACE_RIGHT_OF_EDGE);
386         }
387       }
388     }
389   }
390 
391   /**
392    * Automatically groups edges either on their source or target side, but never on
393    * both sides at the same time.
394    * @param graph input graph
395    * @param sgMap source group id map
396    * @param tgMap target group id map
397    */
398   private void autoGroupEdges(LayoutGraph graph, EdgeMap sgMap, EdgeMap tgMap, DataProvider positiveDP) {
399     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
400       sgMap.set(ec.edge(), null);
401       tgMap.set(ec.edge(), null);
402     }
403 
404     BHeapIntNodePQ sourceGroupPQ = new BHeapIntNodePQ(graph);
405     BHeapIntNodePQ targetGroupPQ = new BHeapIntNodePQ(graph);
406     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
407       final Node n = nc.node();
408       int outDegree = 0;
409       for (EdgeCursor ec = n.outEdges(); ec.ok(); ec.next()) {
410         if (positiveDP.getBool(ec.edge()) && !ec.edge().isSelfLoop()) {
411           outDegree++;
412         }
413       }
414       sourceGroupPQ.add(n, -outDegree);
415       int inDegree = 0;
416       for (EdgeCursor ec = n.inEdges(); ec.ok(); ec.next()) {
417         if (positiveDP.getBool(ec.edge()) && !ec.edge().isSelfLoop()) {
418           inDegree++;
419         }
420       }
421       targetGroupPQ.add(n, -inDegree);
422     }
423 
424     while (!sourceGroupPQ.isEmpty() && !targetGroupPQ.isEmpty()) {
425       int bestIn = 0, bestOut = 0;
426       if (!sourceGroupPQ.isEmpty()) {
427         bestOut = -sourceGroupPQ.getMinPriority();
428       }
429       if (!targetGroupPQ.isEmpty()) {
430         bestIn = -targetGroupPQ.getMinPriority();
431       }
432       if (bestIn > bestOut) {
433         final Node n = targetGroupPQ.removeMin();
434         for (EdgeCursor ec = n.inEdges(); ec.ok(); ec.next()) {
435           final Edge e = ec.edge();
436           if (sgMap.get(e) == null && positiveDP.getBool(e) && !e.isSelfLoop()) {
437             tgMap.set(e, n);
438             sourceGroupPQ.changePriority(e.source(), sourceGroupPQ.getPriority(e.source()) + 1);
439           }
440         }
441       } else {
442         final Node n = sourceGroupPQ.removeMin();
443         for (EdgeCursor ec = n.outEdges(); ec.ok(); ec.next()) {
444           final Edge e = ec.edge();
445           if (tgMap.get(e) == null && positiveDP.getBool(e) && !e.isSelfLoop()) {
446             sgMap.set(e, n);
447             targetGroupPQ.increasePriority(e.target(), targetGroupPQ.getPriority(e.target()) + 1);
448           }
449         }
450       }
451     }
452   }
453 
454 
455   private static void setPreferredSide(final EdgeLabel el, final byte preferredSide) {
456     final PreferredPlacementDescriptor oldDescriptor =
457             el.getPreferredPlacementDescriptor();
458     if (oldDescriptor.getSideOfEdge() != preferredSide) {
459       final PreferredPlacementDescriptor newDescriptor =
460               new PreferredPlacementDescriptor(oldDescriptor);
461       newDescriptor.setSideOfEdge(preferredSide);
462       el.setPreferredPlacementDescriptor(newDescriptor);
463     }
464   }
465 }
466