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.router;
29  
30  import demo.view.DemoBase;
31  import y.base.DataProvider;
32  import y.base.Edge;
33  import y.base.EdgeCursor;
34  import y.base.EdgeList;
35  import y.base.EdgeMap;
36  import y.base.Graph;
37  import y.base.Node;
38  import y.base.NodeCursor;
39  import y.base.NodeList;
40  import y.base.NodeMap;
41  import y.base.YList;
42  import y.geom.YPoint;
43  import y.layout.LayoutGraph;
44  import y.layout.PortConstraintKeys;
45  import y.layout.router.polyline.EdgeRouter;
46  import y.option.Editor;
47  import y.option.OptionHandler;
48  import y.option.OptionItem;
49  import y.option.TableEditorFactory;
50  import y.util.DataProviderAdapter;
51  import y.util.Maps;
52  import y.util.Tuple;
53  import y.util.pq.BHeapIntNodePQ;
54  import y.view.Bend;
55  import y.view.BendCursor;
56  import y.view.BridgeCalculator;
57  import y.view.CreateEdgeMode;
58  import y.view.DefaultGraph2DRenderer;
59  import y.view.EdgeRealizer;
60  import y.view.EditMode;
61  import y.view.Graph2D;
62  import y.view.HotSpotMode;
63  import y.view.MovePortMode;
64  import y.view.PopupMode;
65  import y.view.Port;
66  import y.view.PortAssignmentMoveSelectionMode;
67  import y.view.Selections;
68  
69  import javax.swing.AbstractAction;
70  import javax.swing.Action;
71  import javax.swing.JComponent;
72  import javax.swing.JPanel;
73  import javax.swing.JPopupMenu;
74  import javax.swing.JSplitPane;
75  import javax.swing.JToolBar;
76  import java.awt.BorderLayout;
77  import java.awt.Color;
78  import java.awt.Cursor;
79  import java.awt.Dimension;
80  import java.awt.EventQueue;
81  import java.awt.event.ActionEvent;
82  import java.beans.PropertyChangeEvent;
83  import java.beans.PropertyChangeListener;
84  import java.net.URL;
85  import java.util.ArrayList;
86  import java.util.Arrays;
87  import java.util.HashMap;
88  import java.util.HashSet;
89  import java.util.Iterator;
90  import java.util.List;
91  import java.util.Locale;
92  import java.util.Map;
93  import java.util.Set;
94  
95  /**
96   * This demo shows yFiles' octilinear edge routing capabilities. An edge routing algorithm routes edges without changing
97   * the current node positions. While an orthogonal edge routing algorithm only produces horizontal and vertical edge
98   * segments, this router also allows octilinear edge segments, i.e., it produces edge routes where the slope of each
99   * segment is a multiple of 45 degrees. Besides the basic octilinear edge routing capabilities, this class also
100  * demonstrates the edge grouping feature.
101  *
102  * @see <a href="http://docs.yworks.com/yfiles/doc/api/index.html#/dguide/polyline_edge_router" target="_blank">Section Polyline Edge Routing</a> in the yFiles for Java Developer's Guide
103  */
104 public class OctilinearEdgeRouterDemo extends DemoBase {
105   //mode constants that specify which edges should be routed
106   protected static final byte MODE_ROUTE_ALL_EDGES = 0;
107   protected static final byte MODE_ROUTE_SELECTED_EDGES = 1;
108   protected static final byte MODE_ROUTE_EDGES_OF_SELECTED_NODES = 2;
109 
110   private OptionHandler optionHandler;
111   private boolean automaticRoutingEnabled; //if this option is enabled, the edge routing is automatically triggered when creating new edges, changing edges or moving/resizing nodes
112 
113   private EdgeMap sourceGroupID;
114   private EdgeMap targetGroupID;
115   private Color[] groupColors;
116   private YList availableColors;
117   private HashMap groupId2Color;
118 
119   /** Creates a new instance of this demo. */
120   public OctilinearEdgeRouterDemo() {
121     this(null);
122   }
123 
124   /** Creates a new instance of this demo and adds a help pane for the specified file. */
125   public OctilinearEdgeRouterDemo(final String helpFilePath) {
126     this.automaticRoutingEnabled = true;
127     this.groupId2Color = new HashMap();
128     sourceGroupID = Maps.createHashedEdgeMap();
129     targetGroupID = Maps.createHashedEdgeMap();
130     this.availableColors = new YList();
131     resetColors(10);
132 
133     //Init GUI components:
134     final JPanel propertiesPanel = new JPanel(new BorderLayout());
135     optionHandler = createOptionHandler();
136     propertiesPanel.add(createOptionTable(optionHandler), BorderLayout.NORTH);
137 
138     if (helpFilePath != null) {
139       final URL url = getResource(helpFilePath);
140       if (url == null) {
141         System.err.println("Could not locate help file: " + helpFilePath);
142       } else {
143         final JComponent helpPane = createHelpPane(url);
144         if (helpPane != null) {
145           propertiesPanel.add(helpPane);
146         }
147       }
148     }
149 
150     final JSplitPane splitPane = new JSplitPane(JSplitPane.HORIZONTAL_SPLIT, propertiesPanel, view);
151     splitPane.setBorder(null);
152     splitPane.setResizeWeight(0.05);
153     splitPane.setContinuousLayout(false);
154     contentPane.add(splitPane, BorderLayout.CENTER);
155 
156     // show bridges
157     BridgeCalculator bridgeCalculator = new BridgeCalculator();
158     bridgeCalculator.setCrossingMode(BridgeCalculator.CROSSING_MODE_HORIZONTAL_CROSSES_VERTICAL);
159     ((DefaultGraph2DRenderer) view.getGraph2DRenderer()).setBridgeCalculator(bridgeCalculator);
160 
161     //load initial graph
162     EventQueue.invokeLater(new Runnable() {
163       public void run() {
164         loadInitialGraph();
165       }
166     });
167   }
168 
169   private void resetColors(int colorCount) {
170     groupId2Color.clear();
171     groupColors = BusDyer.Colors.getColors(colorCount);
172     availableColors.clear();
173     availableColors.addAll(Arrays.asList(groupColors));
174     availableColors.remove(Color.BLACK);
175   }
176 
177   /** Releases colors that are not longer required */
178   private void releaseUnusedColors() {
179     final Graph2D graph = view.getGraph2D();
180     availableColors.addAll(Arrays.asList(groupColors));
181     availableColors.remove(Color.BLACK);
182     for (EdgeCursor cur = graph.edges(); cur.ok() && !availableColors.isEmpty(); cur.next()) {
183       final Edge edge = cur.edge();
184       final Object edgeGroupID = (sourceGroupID.get(edge) != null) ? sourceGroupID.get(edge) : targetGroupID.get(edge);
185       final Color edgeGroupColor = (Color) groupId2Color.get(edgeGroupID);
186       if (availableColors.contains(edgeGroupColor)) {
187         availableColors.remove(edgeGroupColor);
188       }
189     }
190   }
191 
192   /** Assign colors to edge groups, i.e., each edge group has a unique color. Non-grouped edges are drawn black */
193   private void colorizeGroups(final EdgeCursor ec) {
194     final Graph2D graph = view.getGraph2D();
195     for(; ec.ok(); ec.next()) {
196       final Edge e = ec.edge();
197       final EdgeRealizer eRealizer = graph.getRealizer(e);
198       final Object eGroupID = (sourceGroupID.get(e) != null) ? sourceGroupID.get(e) : targetGroupID.get(e);
199       if(eGroupID != null) {
200         Color groupColor = (Color) groupId2Color.get(eGroupID);
201         if(groupColor == null) {
202           if (availableColors.isEmpty()) {
203             releaseUnusedColors();
204             if (availableColors.isEmpty()) {
205               //still empty => not enough colors => we first add new colors and then re-assign the edge group colors
206               resetColors(groupColors.length * 2);
207               colorizeGroups(graph.edges());
208               return;
209             }
210           }
211           groupColor = (Color) availableColors.pop();
212           groupId2Color.put(eGroupID, groupColor);
213         }
214         eRealizer.setLineColor(groupColor);
215       } else {
216         eRealizer.setLineColor(Color.BLACK);
217       }
218     }
219     view.updateView();
220   }
221 
222   /** Creates a table editor component for the specified option handler. */
223   private JComponent createOptionTable(OptionHandler oh) {
224     oh.setAttribute(TableEditorFactory.ATTRIBUTE_INFO_POSITION, TableEditorFactory.InfoPosition.NONE);
225 
226     TableEditorFactory tef = new TableEditorFactory();
227     Editor editor = tef.createEditor(oh);
228 
229     JComponent optionComponent = editor.getComponent();
230     optionComponent.setPreferredSize(new Dimension(330, 150));
231     optionComponent.setMaximumSize(new Dimension(330, 150));
232     return optionComponent;
233   }
234 
235   /** Creates an option handler. */
236   protected OptionHandler createOptionHandler() {
237     final OptionHandler layoutOptionHandler = new OptionHandler("Option Table");
238 
239     layoutOptionHandler.useSection("Edge Routing");
240     final OptionItem automaticRoutingItem = layoutOptionHandler.addBool("Automatic Routing", true);
241     automaticRoutingItem.addPropertyChangeListener("value", new PropertyChangeListener() {
242       public void propertyChange(PropertyChangeEvent evt) {
243         automaticRoutingEnabled = layoutOptionHandler.getBool("Automatic Routing");
244       }
245     });
246     layoutOptionHandler.addBool("Octilinear Routing", true);
247     layoutOptionHandler.addInt("Preferred Octilinear Segment Length", 30);
248 
249     layoutOptionHandler.useSection("Edge Grouping");
250     layoutOptionHandler.addBool("Ignore Edge Groups", false);
251 
252     layoutOptionHandler.useSection("Minimum Distances");
253     layoutOptionHandler.addInt("Minimum Edge Distance", 3);
254     layoutOptionHandler.addInt("Minimum Node Distance", 5);
255 
256     return layoutOptionHandler;
257   }
258 
259   protected void loadInitialGraph() {
260     loadGraph("resource/octilinearEdgeRouting.graphml");
261   }
262 
263   /** Does the edge routing. */
264   protected void routeEdges() {
265     routeEdges(MODE_ROUTE_ALL_EDGES, null);
266   }
267 
268   /**
269    * Does the edge routing.
270    *
271    * @param mode             specifies which edges should be routed. Possible values are {@link #MODE_ROUTE_ALL_EDGES},
272    *                         {@link #MODE_ROUTE_EDGES_OF_SELECTED_NODES} and {@link #MODE_ROUTE_SELECTED_EDGES}.
273    * @param selectedElements a DataProvider that returns true for each selected element.
274    */
275   protected void routeEdges(final byte mode, final DataProvider selectedElements) {
276     final Graph2D graph = view.getGraph2D();
277 
278     //configure the edge router
279     final EdgeRouter edgeRouter = new EdgeRouter();
280     edgeRouter.setReroutingEnabled(false);
281     edgeRouter.setPolylineRoutingEnabled(optionHandler.getBool("Octilinear Routing"));
282     edgeRouter.setPreferredPolylineSegmentLength(optionHandler.getInt("Preferred Octilinear Segment Length"));
283     edgeRouter.getDefaultEdgeLayoutDescriptor().setMinimalEdgeToEdgeDistance(optionHandler.getInt("Minimum Edge Distance"));
284     edgeRouter.setMinimalNodeToEdgeDistance(optionHandler.getInt("Minimum Node Distance"));
285 
286     //if edge groups should be ignored, we temporarily remove the corresponding data providers
287     final boolean ignoreEdgeGroups = optionHandler.getBool("Ignore Edge Groups");
288     if (!ignoreEdgeGroups) {
289       graph.addDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY, sourceGroupID);
290       graph.addDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY, targetGroupID);
291     }
292 
293     //configure edge router, if only a subset of edges should be routed
294     final Object selectionEdgesKey = edgeRouter.getSelectedEdgesDpKey();
295     if (mode == MODE_ROUTE_SELECTED_EDGES) {
296       edgeRouter.setSphereOfAction(EdgeRouter.ROUTE_SELECTED_EDGES);
297       final DataProvider selectedElementsDP = addFixedGroupMembersToSelection(selectedElements);
298       graph.addDataProvider(selectionEdgesKey, selectedElementsDP);
299     } else if (mode == MODE_ROUTE_EDGES_OF_SELECTED_NODES) {
300       edgeRouter.setSphereOfAction(EdgeRouter.ROUTE_SELECTED_EDGES);
301       final DataProvider selectedElementsDP = addFixedGroupMembersToSelection(selectedElements);
302       graph.addDataProvider(selectionEdgesKey, new DataProviderAdapter() {
303         public boolean getBool(Object dataHolder) {
304           return selectedElementsDP.getBool((((Edge) dataHolder).source()))
305               || selectedElementsDP.getBool(((Edge) dataHolder).target());
306         }
307       });
308     }
309 
310     //do the layout
311     final Cursor oldCursor = view.getCanvasComponent().getCursor();
312     try {
313       contentPane.setCursor(Cursor.getPredefinedCursor(Cursor.WAIT_CURSOR));
314       view.applyLayoutAnimated(edgeRouter);
315     } finally {
316       contentPane.setCursor(oldCursor);
317     }
318 
319     if (mode == MODE_ROUTE_SELECTED_EDGES || mode == MODE_ROUTE_EDGES_OF_SELECTED_NODES) {
320       edgeRouter.setSphereOfAction(EdgeRouter.ROUTE_ALL_EDGES);
321       graph.removeDataProvider(selectionEdgesKey);
322     }
323 
324     //restore the original data providers
325     if (!ignoreEdgeGroups) {
326       graph.removeDataProvider(PortConstraintKeys.SOURCE_GROUPID_KEY);
327       graph.removeDataProvider(PortConstraintKeys.TARGET_GROUPID_KEY);
328     }
329   }
330 
331   /** Adds all edges to the selected elements that are are assigned to the same edge group as a selected element */
332   private DataProvider addFixedGroupMembersToSelection(final DataProvider selectedElements) {
333     if(selectedElements == null) {
334       return null;
335     }
336 
337     final List selectedEdges = new ArrayList();
338     final List fixedEdges = new ArrayList();
339     final Set groupIDs = new HashSet();
340     final Graph2D graph = view.getGraph2D();
341     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
342       final Edge edge = ec.edge();
343       if (selectedElements.getBool(edge)) {
344         selectedEdges.add(edge);
345         if (sourceGroupID.get(edge) != null) {
346           groupIDs.add(sourceGroupID.get(edge));
347         } else if (targetGroupID.get(edge) != null) {
348           groupIDs.add(targetGroupID.get(edge));
349         }
350       } else {
351         fixedEdges.add(edge);
352       }
353     }
354 
355     final int numberOfSelectedEdges = selectedEdges.size();
356     for (Iterator it = fixedEdges.iterator(); it.hasNext(); ) {
357       final Edge fixedEdge = (Edge) it.next();
358       if (sourceGroupID.get(fixedEdge) != null && groupIDs.contains(sourceGroupID.get(fixedEdge))) {
359         selectedEdges.add(fixedEdge);
360       } else if (targetGroupID.get(fixedEdge) != null && groupIDs.contains(targetGroupID.get(fixedEdge))) {
361         selectedEdges.add(fixedEdge);
362       }
363     }
364 
365     if (selectedEdges.size() > numberOfSelectedEdges) {
366       final EdgeMap selectedElementsDP = Maps.createHashedEdgeMap();
367       for (Iterator iterator = selectedEdges.iterator(); iterator.hasNext(); ) {
368         final Edge selectedEdge = (Edge) iterator.next();
369         selectedElementsDP.set(selectedEdge, Boolean.TRUE);
370       }
371       return selectedElementsDP;
372     }
373 
374     return selectedElements;
375   }
376 
377   /**
378    * Adds a specially configured EditMode that will automatically route all newly created edges orthogonally. The edge
379    * router will also be activated on some edges, when nodes get resized or a node selection gets moved.
380    */
381   protected void registerViewModes() {
382     final EditMode mode = createEditMode();
383     mode.allowBendCreation(false);
384     mode.setMoveSelectionMode(new MyMoveSelectionMode());
385     mode.setCreateEdgeMode(new MyCreateEdgeMode());
386     mode.setHotSpotMode(new MyHotSpotMode());
387     mode.setPopupMode(new MyPopupMode());
388     mode.setMovePortMode(new MyMovePortMode());
389     view.addViewMode(mode);
390   }
391 
392   /** Provides popup menus for all kinds of actions */
393   final class MyPopupMode extends PopupMode {
394     public JPopupMenu getNodePopup(final Node v) {
395       JPopupMenu pm = new JPopupMenu();
396       addNodeActions(pm, new NodeList(v).nodes());
397       return pm;
398     }
399 
400     private void addNodeActions(JPopupMenu pm, NodeCursor nc) {
401       pm.add(new GroupEdgesOnNodeAction("Group In-Edges", nc, true));
402       pm.add(new UngroupEdgesOnNodeAction("Ungroup In-Edges", nc, true));
403       pm.addSeparator();
404       pm.add(new GroupEdgesOnNodeAction("Group Out-Edges", nc, false));
405       pm.add(new UngroupEdgesOnNodeAction("Ungroup Out-Edges", nc, false));
406     }
407 
408     public JPopupMenu getSelectionPopup(double x, double y) {
409       final JPopupMenu pm = new JPopupMenu();
410       final NodeCursor snc = getGraph2D().selectedNodes();
411       if (snc.ok()) {
412         addNodeActions(pm, snc);
413       } else {
414         final EdgeCursor sec = getGraph2D().selectedEdges();
415         if (sec.ok()) {
416           addEdgeActions(pm, sec);
417         } else {
418           return null;
419         }
420       }
421       return pm;
422     }
423 
424     public JPopupMenu getEdgePopup(Edge e) {
425       final JPopupMenu pm = new JPopupMenu();
426       pm.add(new UngroupSelectedEdgesAction("Ungroup Selected Edges", new EdgeList(e).edges()));
427       return pm;
428     }
429 
430     private void addEdgeActions(JPopupMenu pm, EdgeCursor sec) {
431       pm.add(new GroupSelectedEdgesAction("Group Selected Edges", sec));
432       pm.add(new UngroupSelectedEdgesAction("Ungroup Selected Edges", sec));
433     }
434   }
435 
436   /** Provides an action to ungroup all selected edges. */
437   final class UngroupSelectedEdgesAction extends AbstractAction {
438       private EdgeCursor sec;
439 
440       public UngroupSelectedEdgesAction(String name, EdgeCursor sec) {
441         super(name);
442         this.sec = sec;
443       }
444 
445       public void actionPerformed(ActionEvent ae) {
446         if(sec == null || !sec.ok()) {
447           return;
448         }
449 
450         final EdgeMap edge2IsUngrouped = Maps.createHashedEdgeMap();
451         final EdgeList ungroupedEdges = new EdgeList();
452         for(; sec.ok(); sec.next()) {
453           final Edge e = sec.edge();
454           ungroupedEdges.add(e);
455           edge2IsUngrouped.setBool(e, true);
456           sourceGroupID.set(e, null);
457           targetGroupID.set(e, null);
458         }
459         colorizeGroups(ungroupedEdges.edges());
460         routeEdges(MODE_ROUTE_SELECTED_EDGES, edge2IsUngrouped);
461       }
462   }
463 
464   /** Provides an action to group all selected edges. */
465   final class GroupSelectedEdgesAction extends AbstractAction {
466     private EdgeCursor sec;
467 
468     public GroupSelectedEdgesAction(String name, EdgeCursor sec) {
469       super(name);
470       this.sec = sec;
471     }
472 
473     public void actionPerformed(ActionEvent ae) {
474       if(sec == null || !sec.ok()) {
475         return;
476       }
477 
478       //we construct the subgraph that contains all selected edges and split each original node into one node
479       //for incoming edges and one node for outgoing edges
480       final Graph2D origGraph = view.getGraph2D();
481       final Graph subgraph = new Graph();
482       final NodeMap origNode2SubgraphIncomingNode = Maps.createHashedNodeMap();
483       final NodeMap origNode2SubgraphOutgoingNode = Maps.createHashedNodeMap();
484       for (NodeCursor nc = origGraph.nodes(); nc.ok(); nc.next()) {
485         final Node origNode = nc.node();
486 
487         //create the two nodes of the subgraph (one for incoming and one for outgoing edges)
488         final Node subgraphIncomingNode = subgraph.createNode();
489         origNode2SubgraphIncomingNode.set(origNode, subgraphIncomingNode);
490         final Node subgraphOutgoingNode = subgraph.createNode();
491         origNode2SubgraphOutgoingNode.set(origNode, subgraphOutgoingNode);
492       }
493       final EdgeMap subgraphEdge2OrigEdge = Maps.createHashedEdgeMap();
494       for(; sec.ok(); sec.next()) {
495         final Edge origEdge = sec.edge();
496 
497         //insert edge into the subgraph
498         final Node subgraphSource = (Node) origNode2SubgraphOutgoingNode.get(origEdge.source());
499         final Node subgraphTarget = (Node) origNode2SubgraphIncomingNode.get(origEdge.target());
500         final Edge copy = subgraph.createEdge(subgraphSource, subgraphTarget);
501         subgraphEdge2OrigEdge.set(copy, origEdge);
502       }
503 
504       final int MAX_DEGREE = origGraph.edgeCount();
505       final BHeapIntNodePQ pq = new BHeapIntNodePQ(subgraph);
506       for (NodeCursor nc = subgraph.nodes(); nc.ok(); nc.next()) {
507         final Node node = nc.node();
508         pq.add(node, MAX_DEGREE - node.degree()); //nodes with high degree should be processed first
509       }
510 
511       //we iteratively take the node with highest degree and assign group ids to its edges
512       final EdgeList groupedEdges = new EdgeList();
513       final EdgeMap edge2IsGrouped = Maps.createHashedEdgeMap();
514       while(!pq.isEmpty()) {
515         final Node node = pq.removeMin();
516         final boolean incomingNode = node.inDegree() > 0;
517         final Object groupId = new Tuple(node, node.edges().edge());
518         for(EdgeCursor ec = node.edges(); ec.ok(); ec.next()) {
519           final Edge subgraphEdge = ec.edge();
520 
521           //assign group id to original edge
522           final Edge origEdge = (Edge) subgraphEdge2OrigEdge.get(subgraphEdge);
523           groupedEdges.add(origEdge);
524           edge2IsGrouped.setBool(origEdge, true);
525           sourceGroupID.set(origEdge, incomingNode ? null : groupId);
526           targetGroupID.set(origEdge, incomingNode ? groupId : null);
527 
528           //remove the edge from the subgraph and decrease the degree of the neighbor by one (i.e., increase the priority by one)
529           final Node neighbor = subgraphEdge.opposite(node);
530           subgraph.removeEdge(subgraphEdge);
531           pq.increasePriority(neighbor, pq.getPriority(neighbor) + 1);
532         }
533       }
534       colorizeGroups(groupedEdges.edges());
535       routeEdges(MODE_ROUTE_SELECTED_EDGES, edge2IsGrouped);
536     }
537   }
538 
539   /** Provides an action to ungroup all in-/out-edges of a node. */
540   final class UngroupEdgesOnNodeAction extends AbstractAction {
541     private NodeCursor nc;
542     private boolean incomingEdges;
543 
544     public UngroupEdgesOnNodeAction(String name, NodeCursor nc, boolean incomingEdges) {
545       super(name);
546       this.nc = nc;
547       this.incomingEdges = incomingEdges;
548     }
549 
550     public void actionPerformed(ActionEvent ae) {
551       final EdgeList ungroupedEdges = new EdgeList();
552       final EdgeMap edge2IsUngrouped = Maps.createHashedEdgeMap();
553       for (; nc.ok(); nc.next()) {
554         final Node node = nc.node();
555         if(incomingEdges) {
556           for(EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
557             final Edge e = ec.edge();
558             if(targetGroupID.get(e) != null) {
559               targetGroupID.set(e, null);
560               ungroupedEdges.add(e);
561               edge2IsUngrouped.setBool(e, true);
562             }
563           }
564         } else {
565           for(EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
566             final Edge e = ec.edge();
567             if(sourceGroupID.get(e) != null) {
568               sourceGroupID.set(e, null);
569               ungroupedEdges.add(e);
570               edge2IsUngrouped.setBool(e, true);
571             }
572           }
573         }
574       }
575       colorizeGroups(ungroupedEdges.edges());
576       routeEdges(MODE_ROUTE_SELECTED_EDGES, edge2IsUngrouped);
577     }
578   }
579 
580   /** Provides an action to group all in-/out-edges of a node. */
581   final class GroupEdgesOnNodeAction extends AbstractAction {
582     private NodeCursor nc;
583     private boolean inEdges;
584 
585     public GroupEdgesOnNodeAction(String name, NodeCursor nc, boolean inEdges) {
586       super(name);
587       this.nc = nc;
588       this.inEdges = inEdges;
589     }
590 
591     public void actionPerformed(ActionEvent ae) {
592       final EdgeList groupedEdges = new EdgeList();
593       final EdgeMap edge2IsGrouped = Maps.createHashedEdgeMap();
594       for (; nc.ok(); nc.next()) {
595         final Node node = nc.node();
596         
597         //group all in-edges (out-edges) of the given node
598         final EdgeCursor groupedEdgesCur = inEdges ? node.inEdges() : node.outEdges();
599         if (groupedEdgesCur.ok()) {
600           final Edge firstEdge = groupedEdgesCur.edge();
601           final Object groupId = new Tuple(inEdges ? firstEdge.target() : firstEdge.source(), firstEdge);
602           for (; groupedEdgesCur.ok(); groupedEdgesCur.next()) {
603             final Edge e = groupedEdgesCur.edge();
604             groupedEdges.add(e);
605             edge2IsGrouped.setBool(e, true);
606             targetGroupID.set(e, inEdges ? groupId : null);
607             sourceGroupID.set(e, inEdges ? null : groupId);
608           }
609         }
610       }
611       colorizeGroups(groupedEdges.edges());
612       routeEdges(MODE_ROUTE_SELECTED_EDGES, edge2IsGrouped);
613     }
614   }
615 
616   /** A special mode for creating edges. */
617   class MyCreateEdgeMode extends CreateEdgeMode {
618     MyCreateEdgeMode() {
619       super();
620       allowSelfloopCreation(false);
621     }
622 
623     protected Edge createEdge(Graph2D graph, Node startNode, Node targetNode, EdgeRealizer realizer) {
624       graph.firePreEvent();
625       return super.createEdge(graph, startNode, targetNode, realizer);
626     }
627 
628     protected void edgeCreated(final Edge e) {
629       super.edgeCreated(e);
630 
631       if (automaticRoutingEnabled) {
632         //trigger layout
633         final DataProvider activeEdges = new DataProviderAdapter() {
634           public boolean getBool(Object o) {
635             return e == o;
636           }
637         };
638         routeEdges(MODE_ROUTE_SELECTED_EDGES, activeEdges);
639       }
640 
641       view.getGraph2D().firePostEvent();
642     }
643   }
644 
645   /** A special mode for moving edge ports. */
646   class MyMovePortMode extends MovePortMode {
647     MyMovePortMode() {
648       setChangeEdgeEnabled(true);
649       setIndicatingTargetNode(true);
650     }
651 
652     protected void portMoved(Port port, double x, double y) {
653       super.portMoved(port, x, y);
654 
655       if (automaticRoutingEnabled) {
656         //trigger layout
657         final Edge edge = port.getOwner().getEdge();
658         final DataProvider activeEdges = new DataProviderAdapter() {
659           public boolean getBool(Object o) {
660             return edge == o;
661           }
662         };
663         routeEdges(MODE_ROUTE_SELECTED_EDGES, activeEdges);
664       }
665     }
666   }
667 
668   /** A special mode for moving a selection of the graph. */
669   class MyMoveSelectionMode extends PortAssignmentMoveSelectionMode {
670     MyMoveSelectionMode() {
671       super(null, null);
672     }
673 
674     protected void selectionMovedAction(double dx, double dy, double x, double y) {
675       super.selectionMovedAction(dx, dy, x, y);
676 
677       final Graph2D graph = view.getGraph2D();
678       if (automaticRoutingEnabled && (graph.selectedNodes().ok() || graph.selectedBends().ok())) {
679         //trigger layout
680         final EdgeMap selectedEdges = Maps.createHashedEdgeMap();
681         for (BendCursor bc = graph.selectedBends(); bc.ok(); bc.next()) {
682           final Bend bend = bc.bend();
683           selectedEdges.setBool(bend.getEdge(), true);
684         }
685         for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
686           final Edge edge = ec.edge();
687           if (graph.isSelected(edge.source()) ^ graph.isSelected(edge.target())) {
688             selectedEdges.setBool(edge, true);
689           }
690         }
691         routeEdges(MODE_ROUTE_SELECTED_EDGES, selectedEdges);
692       }
693     }
694   }
695 
696   /** A special mode for resizing nodes. */
697   class MyHotSpotMode extends HotSpotMode {
698     public void mouseReleasedLeft(double x, double y) {
699       super.mouseReleasedLeft(x, y);
700 
701       if (automaticRoutingEnabled) {
702         //trigger layout
703         final DataProvider selectedNodesDP = Selections.createSelectionDataProvider(view.getGraph2D());
704         routeEdges(MODE_ROUTE_EDGES_OF_SELECTED_NODES, selectedNodesDP);
705       }
706     }
707   }
708 
709   /** Creates the default toolbar and adds the routing actions. */
710   protected JToolBar createToolBar() {
711     JToolBar toolBar = super.createToolBar();
712     toolBar.setFloatable(false);
713 
714     toolBar.addSeparator();
715 
716     // add edge router to toolbar
717     Action routeAllAction = new AbstractAction("Route") {
718       public void actionPerformed(ActionEvent e) {
719         routeEdges();
720       }
721     };
722     routeAllAction.putValue(Action.SHORT_DESCRIPTION, "Route all edges");
723     routeAllAction.putValue(Action.SMALL_ICON, SHARED_LAYOUT_ICON);
724     toolBar.add(createActionControl(routeAllAction));
725 
726     return toolBar;
727   }
728 
729   /** Call-back for loading a graph. Overwritten to reset the undo queue. */
730   protected void loadGraph(URL resource) {
731     sourceGroupID = Maps.createHashedEdgeMap();
732     targetGroupID = Maps.createHashedEdgeMap();
733     super.loadGraph(resource);
734     defineGroupsFromSketch(view.getGraph2D());
735   }
736 
737   /** Defines source/target groups for edges with same source/target port */
738   private void defineGroupsFromSketch(final LayoutGraph graph) {
739     //fill providers
740     final Map port2EdgeMap = new HashMap();
741     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
742       final Node node = nc.node();
743       port2EdgeMap.clear();
744       for (EdgeCursor ec = node.outEdges(); ec.ok(); ec.next()) {
745         final Edge e = ec.edge();
746         final YPoint p = graph.getSourcePointRel(e);
747         if (!p.equals(YPoint.ORIGIN)) {
748           final Edge prevEdge = (Edge) port2EdgeMap.get(p);
749           if (prevEdge != null) {
750             final Object groupId = new Tuple(node, p);
751             sourceGroupID.set(prevEdge, groupId);
752             sourceGroupID.set(e, groupId);
753           }
754           port2EdgeMap.put(p, e);
755         }
756       }
757       port2EdgeMap.clear();
758       for (EdgeCursor ec = node.inEdges(); ec.ok(); ec.next()) {
759         final Edge e = ec.edge();
760         final YPoint p = graph.getTargetPointRel(e);
761         if (!p.equals(YPoint.ORIGIN)) {
762           final Edge prevEdge = (Edge) port2EdgeMap.get(p);
763           if (prevEdge != null) {
764             final Object groupId = new Tuple(node, p);
765             targetGroupID.set(prevEdge, groupId);
766             targetGroupID.set(e, groupId);
767           }
768           port2EdgeMap.put(p, e);
769         }
770       }
771     }
772     colorizeGroups(graph.edges());
773   }
774 
775   /** Runs this demo. */
776   public static void main(String[] args) {
777     EventQueue.invokeLater(new Runnable() {
778       public void run() {
779         Locale.setDefault(Locale.ENGLISH);
780         initLnF();
781         new OctilinearEdgeRouterDemo("resource/octilinearedgerouterhelp.html").start("Octilinear Edge Router Demo");
782       }
783     });
784   }
785 }
786