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