KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > generate > RandomGraphGenerator


1 /* ==========================================
2  * JGraphT : a free Java graph-theory library
3  * ==========================================
4  *
5  * Project Info: http://jgrapht.sourceforge.net/
6  * Project Creator: Barak Naveh (http://sourceforge.net/users/barak_naveh)
7  *
8  * (C) Copyright 2003-2006, by Barak Naveh and Contributors.
9  *
10  * This library is free software; you can redistribute it and/or modify it
11  * under the terms of the GNU Lesser General Public License as published by
12  * the Free Software Foundation; either version 2.1 of the License, or
13  * (at your option) any later version.
14  *
15  * This library is distributed in the hope that it will be useful, but
16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17  * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18  * License for more details.
19  *
20  * You should have received a copy of the GNU Lesser General Public License
21  * along with this library; if not, write to the Free Software Foundation,
22  * Inc.,
23  * 59 Temple Place, Suite 330, Boston, MA 02111-1307, USA.
24  */
25 /* -----------------
26  * RandomGraphGenerator.java
27  * -----------------
28  * (C) Copyright 2005-2006, by Assaf Lehr and Contributors.
29  *
30  * Original Author: Assaf Lehr
31  * Contributor(s): -
32  *
33  * $Id: RandomGraphGenerator.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  */
38 package org.jgrapht.generate;
39
40 import java.util.*;
41
42 import org.jgrapht.*;
43 import org.jgrapht.graph.*;
44
45
46 /**
47  * This Generator creates a random-topology graph of a specified number of
48  * vertexes and edges. An instance of this generator will always return the same
49  * graph-topology in calls to generateGraph(). The vertexes can be different
50  * (depends on the VertexFactory implementation)
51  *
52  * <p>However, two instances which use the same constructor parameters will
53  * produce two different random graphs (note: as with any random generator,
54  * there is always a small possibility that two instances will create the same
55  * results).
56  *
57  * @author Assaf Lehr
58  * @since Aug 6, 2005
59  */
60 public class RandomGraphGenerator<V, E>
61     implements GraphGenerator<V, E, V>
62 {
63
64     //~ Static fields/initializers --------------------------------------------
65
66     private static long seedUniquifier = 8682522807148012L;
67
68     //~ Instance fields -------------------------------------------------------
69
70     protected int numOfVertexes;
71     protected int numOfEdges;
72     protected Random randomizer;
73     private long randomizerSeed;
74
75     //~ Constructors ----------------------------------------------------------
76
77     public RandomGraphGenerator(int aNumOfVertexes, int aNumOfEdges)
78     {
79         if ((numOfVertexes < 0) || (numOfEdges < 0)) {
80             throw new IllegalArgumentException JavaDoc("must be non-negative");
81         }
82         this.numOfVertexes = aNumOfVertexes;
83         this.numOfEdges = aNumOfEdges;
84
85         this.randomizerSeed = chooseRandomSeedOnce();
86         this.randomizer = new Random(this.randomizerSeed);
87     }
88
89     //~ Methods ---------------------------------------------------------------
90
91     /**
92      * Should be called only once on creation. Chooses a seed which can be used
93      * later to reset the randomizer before each method call. This
94      * implementation copies the java.util.Random constructor because there is
95      * no getSeed() there, and seed is protected.
96      *
97      * @author Assaf
98      * @since Aug 6, 2005
99      */
100     private synchronized static long chooseRandomSeedOnce()
101     {
102         return (++seedUniquifier + System.nanoTime());
103     }
104
105     /**
106      * Resets seed to generate the same random stream.
107      */
108     private void resetRandomSeed()
109     {
110         this.randomizer.setSeed(this.randomizerSeed);
111     }
112
113     /**
114      * (non-Javadoc)
115      *
116      * @throws IllegalArgumentException if the aNumOfEdges passed in the
117      * constructor, cannot be created on a
118      * graph of the concrete type with
119      * aNumOfVertexes.
120      *
121      * org.jgrapht.generate.RandomGraphGenerator.DefaultEdgeTopologyFactory#isNumberOfEdgesValid(org.jgrapht.Graph,
122      * int)
123      *
124      * @see GraphGenerator#generateGraph(Graph, VertexFactory, Map)
125      */
126     public void generateGraph(
127         Graph<V, E> target,
128         VertexFactory<V> vertexFactory,
129         Map<String JavaDoc, V> resultMap)
130     {
131         resetRandomSeed();
132
133         // key = generation order (1st,2nd,3rd,...) value=vertex Object
134 // will be used later
135 Map<Integer JavaDoc, V> orderToVertexMap =
136             new HashMap<Integer JavaDoc, V>(this.numOfVertexes);
137
138         for (int i = 0; i < this.numOfVertexes; i++) {
139             V currVertex = vertexFactory.createVertex();
140             target.addVertex(currVertex);
141             orderToVertexMap.put(Integer.valueOf(i), currVertex);
142         }
143
144         // use specific type of edge factory, depending of the graph type
145 // and edge density
146 EdgeTopologyFactory<V, E> edgesFactory =
147             edgeTopologyFactoryChooser(target, numOfEdges);
148         if (!edgesFactory.isNumberOfEdgesValid(target, numOfEdges)) {
149             throw new IllegalArgumentException JavaDoc(
150                 "numOfEdges is not valid for the graph type "
151                 + "\n-> Invalid number Of Edges=" + numOfEdges + " for:"
152                 + " graph type=" + target.getClass()
153                 + " ,number Of Vertexes=" + this.numOfVertexes
154                 + "\n-> Advice: For the Max value , check the javadoc for"
155                 + " org.jgrapht.generate.RandomGraphGenerator.DefaultEdgeTopologyFactory");
156         }
157
158         edgesFactory.createEdges(
159             target,
160             orderToVertexMap,
161             this.numOfEdges,
162             this.randomizer);
163     }
164
165     /**
166      * Returns a concrete EdgeTopologyFactory, depending on graph type and
167      * numOfEdges
168      *
169      * @param target
170      *
171      * @return
172      */
173     private EdgeTopologyFactory<V, E> edgeTopologyFactoryChooser(
174         Graph<V, E> target,
175         int numOfEdges)
176     {
177         return new DefaultEdgeTopologyFactory<V, E>();
178     }
179
180     //~ Inner Interfaces ------------------------------------------------------
181
182     /**
183      * This class is used to generate the edge topology for a graph.
184      *
185      * @author Assaf
186      * @since Aug 6, 2005
187      */
188     public interface EdgeTopologyFactory<VV, EE>
189     {
190         /**
191          * Two different calls to the createEdges() with the same parameters
192          * must result in the generation of the same. But if the randomizer is
193          * different, it should, usually, create different edge topology.
194          *
195          * @param targetGraph - guranteed to start with zero edges.
196          * @param orderToVertexMap - key=Integer of vertex order . between zero
197          * to numOfVertexes (exclusive). value = vertex
198          * from the graph. unique.
199          * @param numberOfEdges - to create in the graph
200          * @param randomizer
201          */
202         public void createEdges(
203             Graph<VV, EE> targetGraph,
204             Map<Integer JavaDoc, VV> orderToVertexMap,
205             int numberOfEdges,
206             Random randomizer);
207
208         /**
209          * Checks if the graph can contain the givven numberOfEdges according to
210          * the graph type restrictions. For example: <i>#V means number of
211          * vertexes in graph
212          * <li>a Simple Graph, can have max of #V*(#V-1)/2 edges. etc
213          *
214          * @param targetGraph guranteed to start with zero edges.
215          * @param numberOfEdges
216          */
217         public boolean isNumberOfEdgesValid(
218             Graph<VV, EE> targetGraph,
219             int numberOfEdges);
220     }
221
222     //~ Inner Classes ---------------------------------------------------------
223
224     /**
225      * Default implementation of the EdgeTopologyFactory interface. randomly
226      * chooses an edge and tries to add it. If the add fails from any reason
227      * (like: self edge / multiple edges in unpermitted graph type) it will
228      * just choose another and try again. Performance:
229      * <li>when the number of possible edges becomes slim , this class will have
230      * a very poor performance , cause it will not use gready methods to choose
231      * them. for example : In simple graph , if #V = N (#x = number Of x) and we
232      * want full mesh #edges= N*(N-1)/2 , the first added edges will do so
233      * quickly (O(1) , the last will take O(N^2). So , do not use it in this
234      * kind of graphs.
235      * <li>If the numberOfEdges is bigger than what the graph can add, there
236      * will be an infinite loop here. It is not tested.
237      *
238      * @author Assaf
239      * @since Aug 6, 2005
240      */
241     public class DefaultEdgeTopologyFactory<VV, EE>
242         implements EdgeTopologyFactory<VV, EE>
243     {
244         public void createEdges(
245             Graph<VV, EE> targetGraph,
246             Map<Integer JavaDoc, VV> orderToVertexMap,
247             int numberOfEdges,
248             Random randomizer)
249         {
250             int iterationsCounter = 0;
251             int edgesCounter = 0;
252             while (edgesCounter < numberOfEdges) {
253                 // randomizer.nextInt(int n) return a number between zero
254 // (includsive) and n(exclusive)
255 VV startVertex =
256                     orderToVertexMap.get(
257                         Integer.valueOf(randomizer.nextInt(numOfVertexes)));
258                 VV endVertex =
259                     orderToVertexMap.get(
260                         Integer.valueOf(randomizer.nextInt(numOfVertexes)));
261                 try {
262                     EE resultEdge = targetGraph.addEdge(startVertex, endVertex);
263                     if (resultEdge != null) {
264                         edgesCounter++;
265                     }
266                 } catch (Exception JavaDoc e) {
267                     // do nothing.just ignore the edge
268 }
269
270                 iterationsCounter++;
271             }
272         }
273
274         /**
275          * checks if the numOfEdges is smaller than the Max edges according to
276          * the following table:
277          *
278          * <p>
279          * <table border=1 cellpadding=5>
280          * <tr align="center">
281          * <th>Graph Type</th>
282          * <th><i>Directed / UnDirected</i></th>
283          * <th><i>multiple edges</i></th>
284          * <th><i>loops</i></th>
285          * <th><i>Max Edges</i></th>
286          * </tr>
287          * <tr align="center">
288          * <td>SimpleGraph</td>
289          * <td>UnDirected</td>
290          * <td>-</td>
291          * <td>-</td>
292          * <td>N(N-1)/2</td>
293          * </tr>
294          * <tr align="center">
295          * <td>Multigraph</td>
296          * <td>UnDirected</td>
297          * <td>+</td>
298          * <td>-</td>
299          * <td>Infinite</td>
300          * </tr>
301          * <tr align="center">
302          * <td>Pseudograph</td>
303          * <td>UnDirected</td>
304          * <td>+</td>
305          * <td>+</td>
306          * <td>Infinite</td>
307          * </tr>
308          * <tr align="center">
309          * <td>SimpleDirectedGraph</td>
310          * <td>Directed</td>
311          * <td>-</td>
312          * <td>-</td>
313          * <td>N (N-1)</td>
314          * </tr>
315          * <tr align="center">
316          * <td>DefaultDirectedGraph</td>
317          * <td>Directed</td>
318          * <td>-</td>
319          * <td>+</td>
320          * <td>N*(N-1)+ N = N^2</td>
321          * </tr>
322          * <tr align="center">
323          * <td>DirectedMultigraph</td>
324          * <td>Directed</td>
325          * <td>+</td>
326          * <td>+</td>
327          * <td>Infinite</td>
328          * </tr>
329          * </table>
330          *
331          * @see RandomGraphGenerator.EdgeTopologyFactory#isNumberOfEdgesValid(Graph,
332          * int)
333          */
334         public boolean isNumberOfEdgesValid(
335             Graph<VV, EE> targetGraph,
336             int numberOfEdges)
337         {
338             boolean result;
339
340             boolean infinite = false;
341             int maxAllowedEdges = getMaxEdgesForVertexNum(targetGraph);
342             if (maxAllowedEdges == -1) {
343                 infinite = true;
344             }
345
346             if (true == infinite) {
347                 result = true;
348             } else if (numberOfEdges <= maxAllowedEdges) {
349                 result = true;
350             } else {
351                 result = false;
352             }
353             return result;
354         }
355
356         /**
357          * Return max edges for that graph. If it is infinite return -1 instead.
358          */
359         public int getMaxEdgesForVertexNum(Graph<VV, EE> targetGraph)
360         {
361             int maxAllowedEdges = 0;
362             if (targetGraph instanceof SimpleGraph) {
363                 maxAllowedEdges = numOfVertexes * (numOfVertexes - 1) / 2;
364             } else if (targetGraph instanceof SimpleDirectedGraph) {
365                 maxAllowedEdges = numOfVertexes * (numOfVertexes - 1);
366             } else if (targetGraph instanceof DefaultDirectedGraph) {
367                 maxAllowedEdges = numOfVertexes * numOfVertexes;
368             } else if (
369                 (targetGraph instanceof Multigraph)
370                 || (targetGraph instanceof Pseudograph)
371                 || (targetGraph instanceof DirectedMultigraph)) {
372                 maxAllowedEdges = -1; // infinite
373 } else {
374                 throw new ClassCastException JavaDoc(
375                     "cannot find the appropriate graph type");
376             }
377             return maxAllowedEdges;
378         }
379     }
380 }
381
Popular Tags