1
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
74 public class DirectedOrthogonalLayoutModule extends LayoutModule {
75 protected static final String MODULE_DIRECTED_ORTHOGONAL_LAYOUTER = "DIRECTED_ORTHOGONAL_LAYOUTER";
77
78 protected static final String SECTION_LAYOUT = "LAYOUT";
80 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 protected static final String SECTION_LABELING = "LABELING";
103 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 private boolean isEdgeDPAddedByModule = false;
118
119
122 public DirectedOrthogonalLayoutModule() {
123 super(MODULE_DIRECTED_ORTHOGONAL_LAYOUTER);
124 setPortIntersectionCalculatorEnabled(true);
125 }
126
127
131 protected OptionHandler createOptionHandler() {
132 final OptionHandler options = new OptionHandler(getModuleName());
133 final ConstraintManager optionConstraints = new ConstraintManager(options);
134
135 options.useSection(SECTION_LAYOUT);
137 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 final OptionGroup directEdgesGroup = new OptionGroup();
149 directEdgesGroup.setAttribute(OptionGroup.ATTRIBUTE_TITLE, TITLE_IDENTIFY_DIRECTED_EDGES);
150 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 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 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 optionConstraints.setEnabledOnValueEquals(itemUseDrawingAsSketch, Boolean.FALSE,
184 itemAutoGroupDirectedEdges);
185
186 options.useSection(SECTION_LABELING);
188 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 optionConstraints.setEnabledOnValueEquals(itemEdgeLabeling, VALUE_NONE, itemEdgeLabelModel, true);
206
207 return options;
208 }
209
210
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
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 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 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
290 protected void restoreGraph(final Graph2D graph, final OptionHandler options) {
291 if (options.getBool(ITEM_AUTO_GROUP_DIRECTED_EDGES)) {
292 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 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
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
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; }
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
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