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 y.algo.Trees;
31  import y.base.DataAcceptor;
32  import y.base.DataProvider;
33  import y.base.Edge;
34  import y.base.EdgeCursor;
35  import y.base.EdgeList;
36  import y.base.EdgeMap;
37  import y.base.Graph;
38  import y.base.Node;
39  import y.base.NodeCursor;
40  import y.base.NodeList;
41  import y.base.YList;
42  import y.geom.YPoint;
43  import y.layout.LayoutGraph;
44  import y.layout.router.BusDescriptor;
45  import y.layout.router.BusRepresentations;
46  import y.layout.router.BusRouter;
47  import y.util.DataProviderAdapter;
48  import y.util.DataProviders;
49  import y.util.GraphHider;
50  import y.util.Maps;
51  import y.view.Graph2D;
52  
53  import javax.swing.JOptionPane;
54  import java.awt.Color;
55  import java.awt.Component;
56  import java.util.HashMap;
57  import java.util.Iterator;
58  import java.util.List;
59  import java.util.Map;
60  
61  /**
62   * Bus Routing for graphs with hubs. The {@link BusRouter} requires a graph without hubs but with edges connecting
63   * regular nodes. This class provides methods to calculate this intermediate graph for BusRouter from the original graph
64   * and to restore hubs and the original edges of regular nodes after the routing. Note that since the hubs and inner
65   * edges of the buses depend on the routing, it is not possible the restore these elements as well.
66   */
67  public class HubRoutingSupport {
68    private final BusRouterDemoModule module;
69  
70    public HubRoutingSupport() {
71      // a slightly customized router module for this demo
72      module = new BusRouterDemoModule();
73      module.getLayoutExecutor().setLockingView(true);
74      module.getLayoutExecutor().getNodePortConfigurator().setAutomaticPortConstraintsEnabled(true);
75      // the backup of the realizers is done before the placement of the hubs in method {@link BusRouterDemo#doLayout}
76      module.getLayoutExecutor().setBackupRealizersEnabled(false);
77    }
78  
79    BusRouterDemoModule getModule() {
80      return module;
81    }
82  
83    /**
84     * Does the bus routing. This requires three steps: first, create the intermediate graph in which the hubs of each
85     * effected bus are replaced by a complete subgraph; secondly, do the routing of the resulting graph; and finally,
86     * convert the intermediate graph back to hub representation.
87     */
88    public void doLayout(final Graph2D graph, final int mode) {
89      graph.firePreEvent();
90      try {
91        doLayoutImpl(graph, mode);
92      } finally {
93        graph.firePostEvent();
94      }
95    }
96  
97    /**
98     * Does the actual bus routing.
99     *
100    * @see #doLayout(y.view.Graph2D, int)
101    */
102   protected void doLayoutImpl(final Graph2D graph, final int mode) {
103     final EdgeMap edgeDescriptors = graph.createEdgeMap();
104     final EdgeMap edgeIdMap = graph.createEdgeMap();
105 
106     //noinspection CatchGenericClass
107     try {
108       storeOriginalEdges(graph);
109 
110       // 1) Replace the hubs of each bus in scope by an intermediate complete subgraph.
111       EdgeList scopeList;
112       try {
113         scopeList = replaceHubs(graph, edgeDescriptors, mode);
114       } catch (IllegalArgumentException e) {
115         String message = "Warning: " + e.getMessage() + "\n" +
116             "The routing of only the moved or new elements failed since the remainder is\n" +
117             "not a valid bus. All selected buses will be routed completely anew instead.";
118         JOptionPane.showMessageDialog((Component) graph.getCurrentView(), message, "Automatic Routing",
119             JOptionPane.INFORMATION_MESSAGE);
120         doLayoutImpl(graph, BusRouterDemo.MODE_SELECTED);
121         return;
122       }
123 
124       // 2) Do the layout on the intermediate graph. Create required data providers first.
125       switch (mode) {
126         case BusRouterDemo.MODE_SELECTED:
127         case BusRouterDemo.MODE_PARTIAL:
128           module.setScope(BusRouter.SCOPE_SUBSET);
129           graph.addDataProvider(BusRouter.EDGE_SUBSET_DPKEY, new DataProviderAdapter() {
130             public boolean getBool(Object dataHolder) {
131               return edgeDescriptors.get(dataHolder) != null;
132             }
133           });
134           break;
135         case BusRouterDemo.MODE_ALL:
136         default:
137           module.setScope(BusRouter.SCOPE_ALL);
138           break;
139       }
140       graph.addDataProvider(BusRouter.EDGE_DESCRIPTOR_DPKEY, edgeDescriptors);
141       module.start(graph);
142 
143       // 3) Restore the hubs and the original edges of regular nodes for the new layout.
144       BusRepresentations.replaceSubgraphByHubs(graph, scopeList.edges(), edgeDescriptors, edgeIdMap);
145       restoreOriginalEdges(graph);
146     } finally {
147       graph.removeDataProvider(BusRouter.EDGE_DESCRIPTOR_DPKEY);
148       graph.removeDataProvider(BusRouter.EDGE_SUBSET_DPKEY);
149 
150       graph.disposeEdgeMap(edgeDescriptors);
151       graph.disposeEdgeMap(edgeIdMap);
152     }
153   }
154 
155   /**
156    * Sets the Id data provider of class {@link BusRepresentations#SOURCE_ID_DPKEY BusRepresentations} for each edge that
157    * is connected to a regular node to this edge. This allows to restore the original edges of the regular nodes after
158    * the routing.
159    *
160    * @see #restoreOriginalEdges(y.layout.LayoutGraph)
161    */
162   protected void storeOriginalEdges(Graph graph) {
163     EdgeMap sourcePointIdMap = Maps.createHashedEdgeMap();
164     graph.addDataProvider(BusRepresentations.SOURCE_ID_DPKEY, sourcePointIdMap);
165     EdgeMap targetPointIdMap = Maps.createHashedEdgeMap();
166     graph.addDataProvider(BusRepresentations.TARGET_ID_DPKEY, targetPointIdMap);
167 
168     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
169       final Edge edge = ec.edge();
170       if (!BusRouterDemo.isHub(edge.source())) {
171         sourcePointIdMap.set(edge, edge);
172       }
173       if (!BusRouterDemo.isHub(edge.target())) {
174         targetPointIdMap.set(edge, edge);
175       }
176     }
177   }
178 
179   /**
180    * Restores the original edges of each regular node from its associated Id data provider of class {@link
181    * BusRepresentations#SOURCE_ID_DPKEY BusRepresentations}. Takes care to set the new edge path to the restored edges.
182    * Finally, removes the said data providers.
183    */
184   protected void restoreOriginalEdges(LayoutGraph graph) {
185     final DataProvider sourceDataProvider = graph.getDataProvider(BusRepresentations.SOURCE_ID_DPKEY);
186     final DataProvider targetDataProvider = graph.getDataProvider(BusRepresentations.TARGET_ID_DPKEY);
187 
188     try {
189       // iterate over a new list since the graph is modified
190       for (EdgeCursor ec = new EdgeList(graph.edges()).edges(); ec.ok(); ec.next()) {
191         final Edge edge = ec.edge();
192         final Edge sourceEdge = (Edge) sourceDataProvider.get(edge);
193         final Edge targetEdge = (Edge) targetDataProvider.get(edge);
194         if (sourceEdge != null && sourceEdge.getGraph() == null && !BusRouterDemo.isHub(edge.source())) {
195           // if sourceEdge is already in the graph, the related bus was not part of the routing
196           graph.changeEdge(sourceEdge, edge.source(), edge.target());
197           graph.reInsertEdge(sourceEdge);
198           graph.setPath(sourceEdge, graph.getPath(edge));
199           graph.removeEdge(edge);
200         }
201         if (targetEdge != null && targetEdge.getGraph() == null && !BusRouterDemo.isHub(edge.target())) {
202           // if targetEdge is already in the graph, the related bus was not part of the routing
203           graph.changeEdge(targetEdge, edge.source(), edge.target());
204           graph.reInsertEdge(targetEdge);
205           graph.setPath(targetEdge, graph.getPath(edge));
206           graph.removeEdge(edge);
207         }
208       }
209     } finally {
210       graph.removeDataProvider(BusRepresentations.SOURCE_ID_DPKEY);
211       graph.removeDataProvider(BusRepresentations.TARGET_ID_DPKEY);
212     }
213   }
214 
215   /**
216    * Converts the buses defined by the hub nodes into the respective complete subgraph in which there are only
217    * connections between the regular bus nodes as required by the {@link y.layout.router.BusRouter}. Also, creates
218    * appropriate {@link y.layout.router.BusDescriptor}s. If the mode is set to MODE_SELECTED, only buses which contain
219    * at least one selected edge or hub are converted. If the mode is set to MODE_SELECTED_PARTS, only buses which
220    * contain at least one moveable edge are converted.
221    * <p/>
222    * This method sets the bus IDs of all edges to the bus color. This is not required for the conversion of the layout
223    * but simplifies the restoration of the correct bus color after the layout execution.
224    *
225    * @param busDescriptors an edge map that will be filled with {@link y.layout.router.BusDescriptor}s
226    * @param mode           the mode to use
227    * @throws IllegalArgumentException if the fixed subgraph is not a connected orthogonal tree
228    */
229   protected EdgeList replaceHubs(Graph2D graph, EdgeMap busDescriptors, final int mode) {
230     final DataProvider hubDP = graph.getDataProvider(BusRouterDemo.HUB_MARKER_DPKEY);
231 
232     // a map which marks fixed and movable edges
233     EdgeMap movableMarker = graph.createEdgeMap();
234 
235     // 1.) Identify the buses which belong to the scope of the given mode.
236     //     Therefore, check for selected edges and end-nodes.
237     GraphHider hider = new GraphHider(graph);
238     List selectedBuses = new YList();
239 
240     //noinspection CatchGenericClass
241     try {
242       final EdgeList[] busEdgesArray = calculateBusComponents(graph);
243       hider.hideAll();
244 
245       // iteratively un-hide one bus and its connected nodes
246       for (int i = 0; i < busEdgesArray.length; i++) {
247         final EdgeList busEdges = busEdgesArray[i];
248         final NodeList busNodes = new NodeList();
249         for (EdgeCursor ec = busEdges.edges(); ec.ok(); ec.next()) {
250           busNodes.add(ec.edge().source());
251           busNodes.add(ec.edge().target());
252         }
253         hider.unhideNodes(busNodes, false);
254         hider.unhideEdges(busEdges);
255 
256         if (mode == BusRouterDemo.MODE_SELECTED) {
257           for (EdgeCursor ec = busEdges.edges(); ec.ok(); ec.next()) {
258             final Edge edge = ec.edge();
259             if (graph.isSelected(edge) || graph.isSelected(edge.source()) || graph.isSelected(edge.target())) {
260               selectedBuses.add(busEdges);
261               break;
262             }
263           }
264         } else if (mode == BusRouterDemo.MODE_PARTIAL) {
265           if (markMoveableEdges(graph, movableMarker)) {
266             selectedBuses.add(busEdges);
267           }
268         } else {
269           selectedBuses.add(busEdges);
270         }
271 
272         hider.hideAll();
273       }
274     } catch (RuntimeException e) {
275       //noinspection CallToPrintStackTrace
276       e.printStackTrace();
277     } finally {
278       hider.unhideAll();
279     }
280 
281     // Store the bus color of the original edges to set it to the intermediate edges.
282     // This is not required but looks good during the layout animation.
283     Map idToColor = new HashMap();
284     for (Iterator listIter = selectedBuses.iterator(); listIter.hasNext(); ) {
285       final EdgeList edgeList = (EdgeList) listIter.next();
286       idToColor.put(new Integer(idToColor.size()), graph.getRealizer(edgeList.firstEdge()).getLineColor());
287     }
288 
289     // 2.a) Remove singleton hubs since they are not handled by BusRepresentations.replaceHubsBySubgraph(..)
290     NodeList singletonHubs = new NodeList();
291     for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
292       final Node node = nc.node();
293       if (hubDP.getBool(node) && node.degree() == 0) {
294         singletonHubs.add(node);
295       }
296     }
297     for (NodeCursor nc = singletonHubs.nodes(); nc.ok(); nc.next()) {
298       graph.removeNode(nc.node());
299     }
300 
301     // 2.b) Replace the hubs by intermediate edges
302     final EdgeList[] selectedBusesArray = (EdgeList[]) selectedBuses.toArray(new EdgeList[selectedBuses.size()]);
303     final EdgeList subGraphEdges = BusRepresentations.replaceHubsBySubgraph(graph, selectedBusesArray,
304         hubDP,
305         mode == BusRouterDemo.MODE_PARTIAL ?
306             DataProviders.createNegatedDataProvider(movableMarker) :
307             DataProviders.createConstantDataProvider(Boolean.FALSE),
308         busDescriptors);
309 
310     // Set the bus color to the intermediate edges.
311     // This is not required but looks good during the layout animation.
312     for (EdgeCursor ec = subGraphEdges.edges(); ec.ok(); ec.next()) {
313       final Edge edge = ec.edge();
314       final BusDescriptor descriptor = (BusDescriptor) busDescriptors.get(edge);
315       graph.getRealizer(edge).setLineColor((Color) idToColor.get(descriptor.getID()));
316     }
317 
318     return subGraphEdges;
319   }
320 
321   /**
322    * Returns whether there is at least one moveable edge in the bus and marks all moveable edges in the provided edge
323    * map. This is required only for MODE_SELECTED_PARTS.
324    * <p/>
325    * This method expects that the graph contains only edges that belong to a common bus. All other edges must be removed
326    * or hidden before calling this method.
327    *
328    * @param moveableMarker a data acceptor in which the movable edges are marked
329    * @return <code>true</code> if the bus contains a movable edge
330    * @throws IllegalArgumentException if a bus contains movable edges and its fixed subgraph is not a connected
331    *                                  orthogonal tree
332    */
333   protected boolean markMoveableEdges(Graph2D graph, DataAcceptor moveableMarker) {
334     final DataProvider hubDP = graph.getDataProvider(BusRouterDemo.HUB_MARKER_DPKEY);
335 
336     boolean containsMoveable = false;
337 
338     // Iteratively, do a search starting from each selected regular node along paths of degree-2 hubs
339     // and hide the discovered edges. These edges are moveable.
340     GraphHider hider = new GraphHider(graph);
341     for (EdgeCursor ec = new EdgeList(graph.edges()).edges(); ec.ok(); ec.next()) {
342       final Edge edge = ec.edge();
343       if (!graph.contains(edge) || (hubDP.getBool(edge.source()) && hubDP.getBool(edge.target()))
344           || !(graph.isSelected(edge) || (graph.isSelected(edge.source()) && !hubDP.getBool(edge.source()))
345           || (graph.isSelected(edge.target()) && !hubDP.getBool(edge.target())))) {
346         // start a search at a regular node either if it is selected by itself or if its edge is selected
347         continue;
348       }
349 
350       containsMoveable = true;
351       moveableMarker.setBool(edge, true);
352       Node node = hubDP.getBool(edge.source()) ? edge.source() : edge.target();
353       hider.hide(edge);
354 
355       while (node != null && node.degree() == 1) {
356         final Edge chainEdge = node.inDegree() > 0 ? node.firstInEdge() : node.firstOutEdge();
357         final Node opposite = chainEdge.opposite(node);
358 
359         if (hubDP.getBool(opposite)) {
360           moveableMarker.setBool(chainEdge, true);
361           hider.hide(chainEdge);
362           node = opposite;
363         } else {
364           node = null;
365         }
366       }
367     }
368 
369     if (!containsMoveable) {
370       hider.unhideAll();
371       return false;
372     }
373 
374     // Everything that is not hidden is fixed and should be a tree and orthogonal.
375     // Find (multi-)edges to regular nodes and hide them for the tree check.
376     EdgeList nodeLinks = new EdgeList();
377     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
378       final Edge edge = ec.edge();
379       if (!hubDP.getBool(edge.source()) || !hubDP.getBool(edge.target())) {
380         nodeLinks.add(edge);
381       }
382     }
383     hider.hide(nodeLinks);
384     if (!Trees.isForest(graph)) {
385       hider.unhideAll();
386       throw new IllegalArgumentException("Fixed subgraph is not a connected tree.");
387     }
388     hider.unhideEdges(nodeLinks);
389 
390     if (!isOrthogonal(graph)) {
391       hider.unhideAll();
392       throw new IllegalArgumentException("Fixed subgraph is not orthogonal.");
393     }
394 
395     hider.unhideAll();
396     return true;
397   }
398 
399   /**
400    * Call-back which provides the collection of the bus edges of each bus.
401    */
402   protected EdgeList[] calculateBusComponents(LayoutGraph graph) {
403     return BusRepresentations.toEdgeLists(graph, graph.getDataProvider(BusRouterDemo.HUB_MARKER_DPKEY));
404   }
405 
406   /**
407    * Checks whether all edge paths of a graph are orthogonal.
408    *
409    * @param graph the graph
410    * @return <code>true</code> if all paths are orthogonal.
411    */
412   private static boolean isOrthogonal(final LayoutGraph graph) {
413     for (EdgeCursor ec = graph.edges(); ec.ok(); ec.next()) {
414       final YPoint[] path = graph.getPath(ec.edge()).toArray();
415       for (int i = 1; i < path.length; i++) {
416         final YPoint p1 = path[i - 1];
417         final YPoint p2 = path[i];
418         if (Math.abs(p1.x - p2.x) > 1.0e-5 && Math.abs(p1.y - p2.y) > 1.0e-5) {
419           return false;
420         }
421       }
422     }
423     return true;
424   }
425 }
426