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.base;
15  
16  import y.util.YRandom;
17  import y.base.Graph;
18  import y.base.Edge;
19  import y.base.EdgeCursor;
20  import y.base.Node;
21  
22  /**
23   * A class that creates random graphs. The size of the graph and other options
24   * may be specified. These options influence the properties of the created
25   * graph.
26   *
27   *
28   * @see <a href="http://docs.yworks.com/yfiles/doc/developers-guide/base.html#Creating Graphs and Graph Elements">Section Creating Graphs and Graph Elements</a> in the yFiles for Java Developer's Guide
29   */
30  public class RandomGraphGenerator 
31  {
32    private int nodeCount;
33    private int edgeCount;
34    private boolean allowCycles;
35    private boolean allowSelfLoops;
36    private boolean allowMultipleEdges;
37    
38    private YRandom random;
39    
40    /** Constructs a new random graph generator */
41    public RandomGraphGenerator()
42    {
43      this(System.currentTimeMillis());
44    }
45    
46    /** 
47     * Constructs a new random graph generator that uses
48     * the given random seed to initialize.
49     */
50    public RandomGraphGenerator(long seed)
51    {
52      random = new YRandom(seed);
53      nodeCount = 30;
54      edgeCount = 40;
55      allowSelfLoops = false;
56      allowCycles    = true;
57      allowMultipleEdges = false;
58    }
59    
60    /**
61     * Sets the random seed for this generator.
62     */
63    public void setSeed(long seed)
64    {
65      random.setSeed(seed);
66    }
67    
68    /**
69     * Sets the node count of the graph to be generated.
70     * The default value is 30.
71     */
72    public void setNodeCount(int nodeCount)
73    {
74      this.nodeCount = nodeCount;
75    }
76    
77    /**
78     * Sets the edge count of the graph to be generated.
79     * The default value is 40. If the edge count is 
80     * higher than it is theoretically possible by the 
81     * generator options set, then the highest possible
82     * edge count is applied instead.
83     */
84    public void setEdgeCount(int edgeCount)
85    {
86      this.edgeCount = edgeCount;
87    }
88    
89    /**
90     * Returns the edge count of the graph to be generated.
91     */
92    public int getEdgeCount()
93    {
94      return edgeCount;
95    }
96    
97    /**
98     * Returns the node count of the graph to be generated.
99     */
100   public int getNodeCount()
101   {
102     return nodeCount;
103   }
104   
105   /**
106    * Whether or not to allow the generation of cyclic graphs, i.e. 
107    * graphs that contain directed cyclic paths. If allowed 
108    * it still could happen by chance that the generated
109    * graph is acyclic. By default allowed.
110    */
111   public void allowCycles(boolean allow)
112   {
113     this.allowCycles = allow;
114   }
115   
116   /**
117    * Returns whether or not to allow the generation of cyclic graphs.
118    */
119   public boolean allowCycles()
120   {
121     return allowCycles;
122   }
123   
124   /**
125    * Whether or not to allow the generation of selfloops, i.e.
126    * edges with same source and target nodes.
127    * If allowed it still could happen by chance that
128    * the generated graph contains no selfloops.
129    * By default disallowed.
130    */
131   public void allowSelfLoops(boolean allow)
132   {
133     this.allowSelfLoops = allow;
134   }
135   
136   /**
137    * Returns whether or not to allow the generation of selfloops.
138    */  
139   public boolean allowSelfLoops()
140   {
141     return allowSelfLoops;
142   }
143   
144   /**
145    * Whether or not to allow the generation of graphs that contain multiple
146    * edges, i.e. graphs that has more than one edge that connect the same pair
147    * of nodes. If allowed it still could happen by chance that
148    * the generated graph does not contain multiple edges.
149    * By default disallowed.
150    */
151   public void allowMultipleEdges(boolean allow)
152   {
153     this.allowMultipleEdges = allow;
154   }
155   
156   /** 
157    * Returns whether or not to allow the generation of graphs that contain
158    * multiple edges.
159    */
160   public boolean allowMultipleEdges()
161   {
162     return allowMultipleEdges;
163   }
164   
165   /** 
166    * Returns a newly created random graph that obeys the specified settings.
167    */
168   public Graph generate()
169   {
170     Graph graph = new Graph();
171     generate(graph);
172     return graph;
173   }
174   
175   
176   /**
177    * Clears the given graph and generates new nodes and edges for it,
178    * so that the specified settings are obeyed.
179    */
180   public void generate(Graph graph)
181   {
182     if(allowMultipleEdges)
183     {
184       generateMultipleGraph(graph);
185     }
186     else if(nodeCount > 1 && edgeCount > 10 && Math.log(nodeCount)*nodeCount < edgeCount)
187     { 
188       generateDenseGraph(graph);
189     }
190     else
191     {
192       generateSparseGraph(graph);
193     }
194   }
195   
196   /**
197    * Random graph generator in case multiple edges are allowed.
198    */
199   private void generateMultipleGraph(Graph G)
200   {
201     
202     int n = nodeCount;
203     int m = edgeCount;
204 
205     int[] deg = new int[n];
206     Node[] V = new Node[n];
207     for(int i = 0; i < n; i++) V[i] = G.createNode();
208     
209     for(int i = 0; i < m; i++) deg[random.nextInt(n)]++;
210     for(int i = 0; i < n; i++)
211     {
212       Node v = V[i];
213       int d = deg[i];
214       while( d > 0 )
215       {
216         int j = random.nextInt(n);
217         if( j == i && (!allowCycles || !allowSelfLoops)) continue;
218         G.createEdge(v,V[j]);
219         d--;
220       }
221     }
222     
223     if(!allowCycles)
224     {
225       for(EdgeCursor ec = G.edges(); ec.ok(); ec.next())
226       {
227         Edge e = ec.edge();
228         if(e.source().index() > e.target().index())
229           G.reverseEdge(e);
230       }
231     }
232   }
233   
234   
235   /**
236    * Random graph generator for dense graphs.
237    */
238   private void generateDenseGraph(Graph g)
239   {
240     g.clear();
241     Node[] nodes = new Node[nodeCount];
242     
243     for(int i = 0; i < nodeCount; i++)
244       nodes[i] = g.createNode();
245     
246     random.permutate(nodes);
247         
248     int m = Math.min(getMaxEdges(),edgeCount);
249     int n = nodeCount;
250     
251     int adder = (allowSelfLoops && allowCycles) ? 0 : 1;
252     
253     boolean[] edgeWanted = random.getBoolArray(getMaxEdges(),m);
254     for(int i = 0, k = 0; i < n; i++)
255       for(int j = i + adder ; j < n; j++, k++)
256       {
257         if(edgeWanted[k])
258         {
259           if(allowCycles && random.nextFloat() > 0.5f)
260             g.createEdge(nodes[j],nodes[i]);
261           else
262             g.createEdge(nodes[i],nodes[j]);
263         }
264       }
265   }
266   
267  
268   /**
269    * Random graph generator for sparse graphs.
270    */
271   private void generateSparseGraph(Graph G)
272   {
273     G.clear();
274     
275     int n = nodeCount;
276     
277     int m = Math.min(getMaxEdges(),edgeCount);
278     
279     Node[] V = new Node[n];
280     
281     for(int i = 0; i < n; i++) 
282     {
283       V[i] = G.createNode();
284     }
285     random.permutate(V);
286 
287     int count = m;
288     while (count > 0)
289     {
290       int vi = random.nextInt(n);
291       Node v = V[vi];
292       Node w = V[random.nextInt(n)];
293       if ( v.getEdge(w) != null || (v == w && (!allowSelfLoops || !allowCycles))) {
294         continue;
295       }
296       G.createEdge(v,w);
297       count--;
298     }
299     
300     if(!allowCycles)
301     {
302       for(EdgeCursor ec = G.edges(); ec.ok(); ec.next())
303       {
304         Edge e = ec.edge();
305         if(e.source().index() > e.target().index())
306           G.reverseEdge(e);
307       }
308     }
309   }
310 
311   /**
312    * Helper method that returns the maximum number of edges
313    * of a graph that still obeys the set structural constraints.
314    */
315   private int getMaxEdges()
316   {
317     if(allowMultipleEdges) return Integer.MAX_VALUE;
318     int maxEdges = nodeCount*(nodeCount-1)/2;
319     if(allowCycles && allowSelfLoops) maxEdges += nodeCount;
320     return maxEdges;
321   }
322   
323   /**
324    * Startup routine. Creates a random graph and outputs
325    * it to the console.
326    */
327   public static void main(String[] args)
328   {
329     RandomGraphGenerator rgg = new RandomGraphGenerator();
330     rgg.setNodeCount(10);
331     rgg.setEdgeCount(20);
332 
333     Graph randomGraph = rgg.generate();
334     System.out.println(randomGraph);
335   }
336 }
337 
338 
339 
340