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.base.DataMap;
31  import y.base.DataProvider;
32  import y.base.Edge;
33  import y.base.EdgeCursor;
34  import y.base.EdgeList;
35  import y.base.GraphEvent;
36  import y.base.GraphListener;
37  import y.base.Node;
38  import y.base.NodeCursor;
39  import y.base.NodeList;
40  import y.layout.LayoutGraph;
41  import y.layout.router.BusRepresentations;
42  import y.util.Maps;
43  import y.util.pq.IntObjectPQ;
44  import y.view.Graph2D;
45  import y.view.NodeRealizer;
46  
47  import java.awt.Color;
48  import java.util.Random;
49  
50  /**
51   * Governs the coloring of the buses. It maintains a list of predefined nice colors and reclaims colors which are no
52   * longer in use.
53   */
54  public class BusDyer implements GraphListener {
55    private final Graph2D graph;
56    private final DataProvider hubMarker;
57    private final IntObjectPQ availableColorsPQ;
58    private final int predefinedColorsCount;
59    private int eventCount;
60  
61    /**
62     * Creates a new instance for the given graph and its hubs.
63     *
64     * @param graph the graph
65     */
66    public BusDyer(Graph2D graph) {
67      this.graph = graph;
68      this.hubMarker = graph.getDataProvider(BusRouterDemo.HUB_MARKER_DPKEY);
69  
70      this.eventCount = 0;
71      this.predefinedColorsCount = 50;
72      DataMap backingStore = Maps.createHashedDataMap();
73      this.availableColorsPQ = new IntObjectPQ(predefinedColorsCount, backingStore, backingStore);
74      resetColors();
75    }
76  
77    /**
78     * Restores a valid bus coloring for the graph with respect to the current appearence.
79     */
80    public void colorize() {
81      colorize(null);
82    }
83  
84    /**
85     * Restores a valid bus coloring for the graph with respect to the specified color provider and the current
86     * appearance. First, to each bus is assigned any color provided for one of its edges. If no such color exists, a
87     * color from the current appearance is chosen.
88     *
89     * @param colorProvider a data provider which provides the color of an edge
90     */
91    public void colorize(DataProvider colorProvider) {
92      resetColors();
93  
94      // store the isolated hubs since they are not covered by the edge lists below
95      final NodeList isolatedHubList = new NodeList();
96      for (NodeCursor nc = graph.nodes(); nc.ok(); nc.next()) {
97        final Node node = nc.node();
98        if (node.degree() == 0 && hubMarker.getBool(node)) {
99          isolatedHubList.add(node);
100       }
101     }
102     final Node[] isolatedHubs = isolatedHubList.toNodeArray();
103 
104     // get an edge list for each bus and check if a valid bus color is already set
105     final EdgeList[] edgeLists = calculateBusComponents(graph);
106     final Color[] busColors = new Color[edgeLists.length + isolatedHubs.length];
107     for (int i = 0; i < edgeLists.length; i++) {
108       final EdgeList edgeList = edgeLists[i];
109       Color descriptorColor = null;
110       Color presentColor = null;
111       for (EdgeCursor ec = edgeList.edges(); ec.ok(); ec.next()) {
112         final Edge edge = ec.edge();
113         if (colorProvider != null && colorProvider.get(edge) != null) {
114           descriptorColor = (Color) colorProvider.get(edge);
115           break;
116         }
117         final Color lineColor = graph.getRealizer(edge).getLineColor();
118         if (presentColor == null && !lineColor.equals(Color.BLACK)) {
119           presentColor = lineColor;
120         }
121         Color sourceFill = graph.getRealizer(edge.source()).getFillColor();
122         if (presentColor == null && !sourceFill.equals(Color.BLACK)) {
123           presentColor = sourceFill;
124         }
125         Color targetFill = graph.getRealizer(edge.target()).getFillColor();
126         if (presentColor == null && !targetFill.equals(Color.BLACK)) {
127           presentColor = targetFill;
128         }
129         if (presentColor != null && colorProvider == null) {
130           break;
131         }
132       }
133 
134       if (descriptorColor != null && isAvailable(descriptorColor)) {
135         busColors[i] = descriptorColor;
136         use(descriptorColor);
137       } else if (presentColor != null && isAvailable(presentColor)) {
138         busColors[i] = presentColor;
139         use(presentColor);
140       }
141     }
142 
143     // check for each isolated hub if a valid bus color is already set
144     for (int i = 0; i < isolatedHubs.length; i++) {
145       final Node isolatedHub = isolatedHubs[i];
146       final Color fillColor = graph.getRealizer(isolatedHub).getFillColor();
147       if (!fillColor.equals(Color.BLACK) && isAvailable(fillColor)) {
148         busColors[edgeLists.length + i] = fillColor;
149         use(fillColor);
150       }
151     }
152 
153     // get colors for all uncolored buses and isolated hubs
154     for (int i = 0; i < busColors.length; i++) {
155       if (busColors[i] == null) {
156         busColors[i] = useNextColor();
157       }
158     }
159 
160     // set the colors to the buses
161     for (int i = 0; i < edgeLists.length; i++) {
162       final EdgeList edgeList = edgeLists[i];
163       final Color color = busColors[i];
164       for (EdgeCursor ec = edgeList.edges(); ec.ok(); ec.next()) {
165         final Edge edge = ec.edge();
166         graph.getRealizer(edge).setLineColor(color);
167         colorizeHub(edge.source(), color);
168         colorizeHub(edge.target(), color);
169       }
170     }
171 
172     // set the colors to the isolated hubs
173     for (int i = 0; i < isolatedHubs.length; i++) {
174       colorizeHub(isolatedHubs[i], busColors[edgeLists.length + i]);
175     }
176   }
177 
178   /**
179    * Listens to node and edge creation and removal and executes the coloring if not inside of a pre-post-block. Note
180    * that this implementation does a coloring of the complete graph which is not recommended for larger graphs.
181    */
182   public void onGraphEvent(GraphEvent e) {
183     switch (e.getType()) {
184       case GraphEvent.PRE_EVENT:
185         eventCount++;
186         break;
187       case GraphEvent.POST_EVENT:
188         eventCount--;
189         break;
190       case GraphEvent.NODE_CREATION:
191       case GraphEvent.NODE_REINSERTION:
192       case GraphEvent.PRE_NODE_REMOVAL:
193       case GraphEvent.POST_NODE_REMOVAL:
194         return; // the coloring can only change on edge events
195       default:
196     }
197 
198     if (eventCount == 0) {
199       colorize();
200     }
201   }
202 
203   /**
204    * Call-back which provides the collection of the bus edges of each bus.
205    */
206   protected EdgeList[] calculateBusComponents(LayoutGraph graph) {
207     return BusRepresentations.toEdgeLists(graph, graph.getDataProvider(BusRouterDemo.HUB_MARKER_DPKEY));
208   }
209 
210   /**
211    * Sets the color of the given node.
212    *
213    * @param node     the node
214    * @param newColor the color to set
215    */
216   private void colorizeHub(Node node, Color newColor) {
217     if (!hubMarker.getBool(node)) {
218       return;
219     }
220     final NodeRealizer realizer = graph.getRealizer(node);
221     realizer.setFillColor(newColor);
222     realizer.setLineColor(newColor);
223   }
224 
225   /**
226    * Sets all colors to unused.
227    */
228   private void resetColors() {
229     availableColorsPQ.clear();
230 
231     Color[] colors = Colors.getColors(predefinedColorsCount + 1);
232     for (int i = 1; i < colors.length; i++) { // discard black
233       final Color color = colors[i];
234       availableColorsPQ.add(color, i - 1);
235     }
236   }
237 
238   /**
239    * Returns the next available color and marks it as used.
240    *
241    * @return the next unused color
242    */
243   private Color useNextColor() {
244     if (availableColorsPQ.isEmpty()) {
245       return Colors.getRandomColor();
246     } else {
247       return (Color) availableColorsPQ.removeMin();
248     }
249   }
250 
251   /**
252    * Sets the color to <code>used</code>.
253    *
254    * @param color the color
255    */
256   private void use(final Color color) {
257     if (isAvailable(color)) {
258       availableColorsPQ.remove(color);
259     }
260   }
261 
262   /**
263    * Returns whether the color is available or not.
264    *
265    * @param color the color
266    * @return <true> if the color is not in use.
267    */
268   private boolean isAvailable(final Color color) {
269     return availableColorsPQ.contains(color);
270   }
271 
272   /**
273    * Provides sets of distinct colors.
274    */
275   static class Colors {
276 
277     // some nice predefined colors
278     private static final Color[] COLORS = {new Color(0x000000), new Color(0xBF0404), new Color(0x009EFF),
279         new Color(0x1B8C48), new Color(0xB300C2), new Color(0xFF6405), new Color(0x2B4BFA), new Color(0x8C6048),
280         new Color(0xFAAFE8), new Color(0xB1D95B), new Color(0xBBB082), new Color(0xFAEE00), new Color(0xAAAAAA),
281         new Color(0x00FFC9), new Color(0x5B519C), new Color(0x666666)};
282 
283     private static final Random RANDOM = new Random(1234L);
284 
285     /**
286      * Do not instantiate this class
287      */
288     private Colors() {
289     }
290 
291     /**
292      * Returns an array of distinct colors. The first 16 colors are predefined and span the complete color range. If
293      * more colors are required, these are created as intermediate shades of the predefined colors.
294      *
295      * @param count the number of colors to return
296      * @return an array of colors
297      */
298     static Color[] getColors(int count) {
299       Color[] r = new Color[count];
300       final int numColors = COLORS.length;
301       System.arraycopy(COLORS, 0, r, 0, Math.min(count, numColors));
302       if (count > numColors) {
303         double div = Math.ceil((double) (count / numColors)) + 1.0;
304         for (int i = numColors; i < count; i++) {
305           int j = i % numColors;
306           int k = (j + 1) % numColors;
307           Color c1 = COLORS[j];
308           Color c2 = COLORS[k];
309           double f = 1.0 / div * Math.ceil((double) (i / numColors));
310           r[i] = blendColors(c1, c2, f);
311         }
312       }
313       return r;
314     }
315 
316     /**
317      * Returns a random color.
318      *
319      * @return a random color
320      */
321     static Color getRandomColor() {
322       return new Color(RANDOM.nextFloat(), RANDOM.nextFloat(), RANDOM.nextFloat());
323     }
324 
325     /**
326      * Returns a color that lays between the tow specified colors.
327      *
328      * @return an intermediate color
329      */
330     private static Color blendColors(Color c1, Color c2, double div) {
331       int dr = (int) ((double) (c2.getRed() - c1.getRed()) * div);
332       int dg = (int) ((double) (c2.getGreen() - c1.getGreen()) * div);
333       int db = (int) ((double) (c2.getBlue() - c1.getBlue()) * div);
334       return new Color(c1.getRed() + dr, c1.getGreen() + dg, c1.getBlue() + db);
335     }
336 
337   }
338 
339 }
340