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