KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > jgrapht > experimental > PartiteRandomGraphGenerator


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  * PartiteRandomGraphGenerator.java
27  * -------------------
28  * (C) Copyright 2003-2006, by Michael Behrisch and Contributors.
29  *
30  * Original Author: Michael Behrisch
31  * Contributor(s): -
32  *
33  * $Id: PartiteRandomGraphGenerator.java 504 2006-07-03 02:37:26Z perfecthash $
34  *
35  * Changes
36  * -------
37  * 13-Sep-2004 : Initial revision (MB);
38  *
39  */
40 // package org.jgrapht.generate;
41 package org.jgrapht.experimental;
42
43 import java.util.*;
44
45 import org.jgrapht.*;
46 import org.jgrapht.generate.*;
47
48
49 /**
50  * PartiteRandomGraphGenerator generates a <a
51  * HREF="http://mathworld.wolfram.com/RandomGraph.html">partite uniform random
52  * graph</a> of any size. A partite uniform random graph contains edges chosen
53  * independently uniformly at random from the set of possible edges between
54  * partition classes.
55  *
56  * @author Michael Behrisch
57  * @since Sep 13, 2004
58  */
59 public class PartiteRandomGraphGenerator<V, E>
60     implements GraphGenerator<V, E, Object JavaDoc []>
61 {
62
63     //~ Instance fields -------------------------------------------------------
64
65     private final int [] numVertices;
66     private final int numEdges;
67
68     //~ Constructors ----------------------------------------------------------
69
70     /**
71      * Construct a new PartiteRandomGraphGenerator for a bipartite graph.
72      *
73      * @param numVertices1 number of vertices in the first partition
74      * @param numVertices2 number of vertices in the second partition
75      * @param numEdges number of edges to be generated
76      *
77      * @throws IllegalArgumentException
78      */
79     public PartiteRandomGraphGenerator(
80         int numVertices1,
81         int numVertices2,
82         int numEdges)
83     {
84         if ((numVertices1 < 0) || (numVertices2 < 0)) {
85             throw new IllegalArgumentException JavaDoc("must be non-negative");
86         }
87
88         if ((numEdges < 0) || (numEdges > (numVertices1 * numVertices2))) {
89             throw new IllegalArgumentException JavaDoc("illegal number of edges");
90         }
91
92         final int [] numVertices = {
93                 numVertices1,
94                 numVertices2
95             };
96         this.numVertices = numVertices;
97         this.numEdges = numEdges;
98     }
99
100     /**
101      * Construct a new PartiteRandomGraphGenerator for a k-partite graph.
102      *
103      * @param numVertices number of vertices in the k partitions
104      * @param numEdges number of edges to be generated between any two
105      * partitions
106      *
107      * @throws IllegalArgumentException
108      */
109     public PartiteRandomGraphGenerator(int [] numVertices, int numEdges)
110     {
111         if (numEdges < 0) {
112             throw new IllegalArgumentException JavaDoc("illegal number of edges");
113         }
114
115         for (int i = 0; i < numVertices.length; i++) {
116             if (numVertices[i] < 0) {
117                 throw new IllegalArgumentException JavaDoc("must be non-negative");
118             }
119
120             for (int j = 0; j < i; j++) {
121                 if (numEdges > (numVertices[i] * numVertices[j])) {
122                     throw new IllegalArgumentException JavaDoc(
123                         "illegal number of edges");
124                 }
125             }
126         }
127
128         this.numVertices = numVertices;
129         this.numEdges = numEdges;
130     }
131
132     //~ Methods ---------------------------------------------------------------
133
134     /**
135      * TODO hb 30-nov-05: document me
136      *
137      * @param target
138      * @param vertexFactory
139      * @param resultMap some array of vertices
140      *
141      * @see GraphGenerator#generateGraph
142      */
143     public void generateGraph(
144         Graph<V, E> target,
145         VertexFactory<V> vertexFactory,
146         Map<String JavaDoc, Object JavaDoc []> resultMap)
147     {
148         Object JavaDoc [][] vertices = new Object JavaDoc [numVertices.length][];
149
150         for (int i = 0; i < numVertices.length; i++) {
151             vertices[i] =
152                 RandomGraphHelper.addVertices(
153                     target,
154                     vertexFactory,
155                     numVertices[i]);
156
157             if (resultMap != null) {
158                 resultMap.put(Integer.toString(i), vertices[i]);
159             }
160
161             for (int j = 0; j < i; j++) {
162                 RandomGraphHelper.addEdges(
163                     target,
164                     Arrays.asList(vertices[i]),
165                     Arrays.asList(vertices[j]),
166                     numEdges);
167             }
168         }
169     }
170 }
171
Popular Tags