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