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