Line | Hits | Source |
---|---|---|
1 | /* | |
2 | * Copyright (c) 2003, the JUNG Project and the Regents of the University of | |
3 | * California All rights reserved. | |
4 | * | |
5 | * This software is open-source under the BSD license; see either "license.txt" | |
6 | * or http://jung.sourceforge.net/license.txt for a description. | |
7 | */ | |
8 | /* | |
9 | * Created on Jul 2, 2003 | |
10 | * | |
11 | */ | |
12 | package edu.uci.ics.jung.utils; | |
13 | ||
14 | import java.util.HashSet; | |
15 | import java.util.Iterator; | |
16 | import java.util.Set; | |
17 | ||
18 | import edu.uci.ics.jung.exceptions.FatalException; | |
19 | import edu.uci.ics.jung.graph.DirectedGraph; | |
20 | import edu.uci.ics.jung.graph.Edge; | |
21 | import edu.uci.ics.jung.graph.Graph; | |
22 | import edu.uci.ics.jung.graph.Vertex; | |
23 | import edu.uci.ics.jung.graph.decorators.EdgeWeightLabeller; | |
24 | import edu.uci.ics.jung.graph.decorators.Indexer; | |
25 | import edu.uci.ics.jung.graph.decorators.NumberEdgeValue; | |
26 | import edu.uci.ics.jung.graph.decorators.StringLabeller; | |
27 | import edu.uci.ics.jung.graph.impl.AbstractSparseGraph; | |
28 | import edu.uci.ics.jung.graph.impl.DirectedSparseEdge; | |
29 | import edu.uci.ics.jung.graph.impl.DirectedSparseGraph; | |
30 | import edu.uci.ics.jung.graph.impl.SparseGraph; | |
31 | import edu.uci.ics.jung.graph.impl.SparseVertex; | |
32 | import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge; | |
33 | import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph; | |
34 | import edu.uci.ics.jung.graph.impl.UndirectedSparseVertex; | |
35 | import edu.uci.ics.jung.random.generators.BarabasiAlbertGenerator; | |
36 | ||
37 | /** | |
38 | * | |
39 | * Generates a series of potentially useful test graphs. | |
40 | * | |
41 | * @author danyelf | |
42 | * | |
43 | */ | |
44 | 0 | public class TestGraphs { |
45 | ||
46 | /** | |
47 | * A series of pairs that may be useful for generating graphs. The | |
48 | * miniature graph consists of 8 edges, 10 nodes, and is formed of two | |
49 | * connected components, one of 8 nodes, the other of 2. | |
50 | * | |
51 | */ | |
52 | 3 | public static String[][] pairs = { { "a", "b", "3" }, { |
53 | "a", "c", "4" }, { | |
54 | "a", "d", "5" }, { | |
55 | "d", "c", "6" }, { | |
56 | "d", "e", "7" }, { | |
57 | "e", "f", "8" }, { | |
58 | "f", "g", "9" }, { | |
59 | "h", "i", "1" } | |
60 | }; | |
61 | ||
62 | /** | |
63 | * Creates a small sample graph that can be used for testing purposes. The | |
64 | * graph is as described in the section on {@link #pairs pairs}. If <tt>isDirected</tt>, | |
65 | * the graph is a {@link DirectedSparseGraph DirectedSparseGraph}, | |
66 | * otherwise, it is an {@link UndirectedSparseGraph UndirectedSparseGraph}. | |
67 | * | |
68 | * @param isDirected: | |
69 | * Is the graph directed? | |
70 | * @return a graph consisting of eight edges and ten nodes. | |
71 | */ | |
72 | public static AbstractSparseGraph createTestGraph(boolean isDirected) { | |
73 | AbstractSparseGraph g; | |
74 | 18 | if (isDirected) { |
75 | 14 | g = new DirectedSparseGraph(); |
76 | } else { | |
77 | 4 | g = new UndirectedSparseGraph(); |
78 | } | |
79 | 18 | StringLabeller sl = StringLabeller.getLabeller(g); |
80 | 18 | EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g); |
81 | 162 | for (int i = 0; i < pairs.length; i++) { |
82 | 144 | String[] pair = pairs[i]; |
83 | 144 | createEdge(g, sl, el, pair[0], pair[1], Integer.parseInt(pair[2])); |
84 | } | |
85 | 18 | return g; |
86 | ||
87 | } | |
88 | ||
89 | /** | |
90 | * Returns a graph consisting of a chain of <code>vertex_count - 1</code> vertices | |
91 | * plus one isolated vertex. | |
92 | */ | |
93 | public static Graph createChainPlusIsolates(int chain_length, int isolate_count) | |
94 | { | |
95 | 0 | Graph g = new UndirectedSparseGraph(); |
96 | 0 | if (chain_length > 0) |
97 | { | |
98 | 0 | Vertex[] v = new Vertex[chain_length]; |
99 | 0 | v[0] = g.addVertex(new UndirectedSparseVertex()); |
100 | 0 | for (int i = 1; i < chain_length; i++) |
101 | { | |
102 | 0 | v[i] = g.addVertex(new UndirectedSparseVertex()); |
103 | 0 | g.addEdge(new UndirectedSparseEdge(v[i], v[i-1])); |
104 | } | |
105 | } | |
106 | 0 | for (int i = 0; i < isolate_count; i++) |
107 | 0 | g.addVertex(new UndirectedSparseVertex()); |
108 | ||
109 | 0 | return g; |
110 | } | |
111 | ||
112 | /** | |
113 | * Creates a sample directed acyclic graph by generating several "layers", | |
114 | * and connecting nodes (randomly) to nodes in earlier (but never later) | |
115 | * layers. Each layer has some random number of nodes in it 1 less than n | |
116 | * less than maxNodesPerLayer. | |
117 | * | |
118 | * @return the created graph | |
119 | */ | |
120 | public static Graph createDirectedAcyclicGraph( | |
121 | int layers, | |
122 | int maxNodesPerLayer, | |
123 | double linkprob) { | |
124 | 0 | DirectedGraph dag = new DirectedSparseGraph(); |
125 | 0 | StringLabeller sl = StringLabeller.getLabeller(dag); |
126 | 0 | Set previousLayers = new HashSet(); |
127 | 0 | Set inThisLayer = new HashSet(); |
128 | 0 | for (int i = 0; i < layers; i++) { |
129 | ||
130 | 0 | int nodesThisLayer = (int) (Math.random() * maxNodesPerLayer) + 1; |
131 | 0 | for (int j = 0; j < nodesThisLayer; j++) { |
132 | 0 | Vertex v = dag.addVertex(new SparseVertex()); |
133 | 0 | inThisLayer.add(v); |
134 | try { | |
135 | 0 | sl.setLabel(v, i + ":" + j); |
136 | 0 | } catch (Exception e) { |
137 | 0 | } |
138 | // for each previous node... | |
139 | 0 | for (Iterator iter = previousLayers.iterator(); |
140 | 0 | iter.hasNext(); |
141 | ) { | |
142 | 0 | Vertex v2 = (Vertex) iter.next(); |
143 | 0 | if (Math.random() < linkprob) { |
144 | 0 | GraphUtils.addEdge(dag, v, v2); |
145 | } | |
146 | } | |
147 | } | |
148 | ||
149 | 0 | previousLayers.addAll(inThisLayer); |
150 | 0 | inThisLayer.clear(); |
151 | } | |
152 | 0 | return dag; |
153 | } | |
154 | ||
155 | private static void createEdge( | |
156 | final AbstractSparseGraph g, | |
157 | StringLabeller sl, | |
158 | EdgeWeightLabeller el, | |
159 | String v1Label, | |
160 | String v2Label, | |
161 | int weight) { | |
162 | ||
163 | try { | |
164 | 144 | Vertex v1 = sl.getVertex(v1Label); |
165 | 144 | if (v1 == null) { |
166 | 36 | v1 = g.addVertex(new SparseVertex()); |
167 | 36 | sl.setLabel(v1, v1Label); |
168 | } | |
169 | 144 | Vertex v2 = sl.getVertex(v2Label); |
170 | 144 | if (v2 == null) { |
171 | 126 | v2 = g.addVertex(new SparseVertex()); |
172 | 126 | sl.setLabel(v2, v2Label); |
173 | } | |
174 | 144 | Edge e = GraphUtils.addEdge(g, v1, v2); |
175 | 144 | el.setWeight(e, weight); |
176 | 0 | } catch (StringLabeller.UniqueLabelException e) { |
177 | 0 | throw new FatalException("This should not happen " + e); |
178 | 144 | } |
179 | 144 | } |
180 | ||
181 | /** | |
182 | * Returns a bigger, undirected test graph with a just one component. This | |
183 | * graph consists of a clique of ten edges, a partial clique (randomly | |
184 | * generated, with edges of 0.6 probability), and one series of edges | |
185 | * running from the first node to the last. | |
186 | * | |
187 | * @return the testgraph | |
188 | */ | |
189 | public static Graph getOneComponentGraph() { | |
190 | 0 | UndirectedSparseGraph g = new UndirectedSparseGraph(); |
191 | 0 | StringLabeller sl = StringLabeller.getLabeller(g); |
192 | 0 | EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g); |
193 | ||
194 | // let's throw in a clique, too | |
195 | 0 | for (int i = 1; i <= 10; i++) { |
196 | 0 | for (int j = i + 1; j <= 10; j++) { |
197 | 0 | String i1 = "" + i; |
198 | 0 | String i2 = "" + j; |
199 | 0 | createEdge(g, sl, el, i1, i2, i + j); |
200 | } | |
201 | } | |
202 | ||
203 | // and, last, a partial clique | |
204 | 0 | for (int i = 11; i <= 20; i++) { |
205 | 0 | for (int j = i + 1; j <= 20; j++) { |
206 | 0 | if (Math.random() > 0.6) |
207 | 0 | continue; |
208 | 0 | String i1 = "" + i; |
209 | 0 | String i2 = "" + j; |
210 | 0 | createEdge(g, sl, el, i1, i2, i + j); |
211 | } | |
212 | } | |
213 | ||
214 | // and one edge to connect them all | |
215 | 0 | Indexer ind = Indexer.getIndexer(g); |
216 | 0 | for (int i = 0; i < g.numVertices() - 1; i++) { |
217 | try { | |
218 | 0 | GraphUtils.addEdge(g, (Vertex)ind.getVertex(i), (Vertex) ind.getVertex(i + 1)); |
219 | 0 | } catch (IllegalArgumentException fe) { |
220 | 0 | } |
221 | } | |
222 | ||
223 | 0 | return g; |
224 | } | |
225 | ||
226 | /** | |
227 | * Returns a bigger test graph with a clique, several components, and other | |
228 | * parts. | |
229 | * | |
230 | * @return a demonstration graph of type <tt>UndirectedSparseGraph</tt> | |
231 | * with 28 vertices. | |
232 | */ | |
233 | public static Graph getDemoGraph() { | |
234 | 0 | UndirectedSparseGraph g = new UndirectedSparseGraph(); |
235 | 0 | StringLabeller sl = StringLabeller.getLabeller(g); |
236 | 0 | EdgeWeightLabeller el = EdgeWeightLabeller.getLabeller(g); |
237 | ||
238 | 0 | for (int i = 0; i < pairs.length; i++) { |
239 | 0 | String[] pair = pairs[i]; |
240 | 0 | createEdge(g, sl, el, pair[0], pair[1], Integer.parseInt(pair[2])); |
241 | } | |
242 | ||
243 | // let's throw in a clique, too | |
244 | 0 | for (int i = 1; i <= 10; i++) { |
245 | 0 | for (int j = i + 1; j <= 10; j++) { |
246 | 0 | String i1 = "" + i; |
247 | 0 | String i2 = "" + j; |
248 | 0 | createEdge(g, sl, el, i1, i2, i + j); |
249 | } | |
250 | } | |
251 | ||
252 | // and, last, a partial clique | |
253 | 0 | for (int i = 11; i <= 20; i++) { |
254 | 0 | for (int j = i + 1; j <= 20; j++) { |
255 | 0 | if (Math.random() > 0.6) |
256 | 0 | continue; |
257 | 0 | String i1 = "" + i; |
258 | 0 | String i2 = "" + j; |
259 | 0 | createEdge(g, sl, el, i1, i2, i + j); |
260 | } | |
261 | } | |
262 | 0 | return g; |
263 | } | |
264 | ||
265 | /** | |
266 | * Equivalent to <code>generateMixedRandomGraph(edge_weight, num_vertices, true)</code>. | |
267 | */ | |
268 | public static Graph generateMixedRandomGraph(NumberEdgeValue edge_weight, int num_vertices) | |
269 | { | |
270 | 0 | return generateMixedRandomGraph(edge_weight, num_vertices, true); |
271 | } | |
272 | ||
273 | /** | |
274 | * Returns a random mixed-mode graph. Starts with a randomly generated | |
275 | * Barabasi-Albert (preferential attachment) generator | |
276 | * (4 initial vertices, 3 edges added at each step, and num_vertices - 4 evolution steps). | |
277 | * Then takes the resultant graph, replaces random undirected edges with directed | |
278 | * edges, and assigns random weights to each edge. | |
279 | */ | |
280 | public static Graph generateMixedRandomGraph(NumberEdgeValue edge_weights, int num_vertices, boolean parallel) | |
281 | { | |
282 | 0 | int seed = (int)(Math.random() * 10000); |
283 | 0 | BarabasiAlbertGenerator bag = new BarabasiAlbertGenerator(4, 3, false, parallel, seed); |
284 | 0 | bag.evolveGraph(num_vertices - 4); |
285 | 0 | Graph ug = (Graph)bag.generateGraph(); |
286 | 0 | SettableVertexMapper svm = new HashSettableVertexMapper(); |
287 | ||
288 | // create a SparseGraph version of g | |
289 | 0 | Graph g = new SparseGraph(); |
290 | 0 | for (Iterator iter = ug.getVertices().iterator(); iter.hasNext(); ) |
291 | { | |
292 | 0 | Vertex v = (Vertex)iter.next(); |
293 | 0 | Vertex w = new SparseVertex(); |
294 | 0 | g.addVertex(w); |
295 | 0 | if (v.containsUserDatumKey(BarabasiAlbertGenerator.SEED)) |
296 | 0 | w.addUserDatum(BarabasiAlbertGenerator.SEED, BarabasiAlbertGenerator.SEED, UserData.REMOVE); |
297 | 0 | svm.map(v, w); |
298 | } | |
299 | ||
300 | // randomly replace some of the edges by directed edges to | |
301 | // get a mixed-mode graph, add random weights | |
302 | 0 | for (Iterator iter = ug.getEdges().iterator(); iter.hasNext(); ) |
303 | { | |
304 | 0 | Edge e = (Edge)iter.next(); |
305 | 0 | Vertex v1 = (Vertex)e.getEndpoints().getFirst(); |
306 | 0 | Vertex v2 = (Vertex)e.getEndpoints().getSecond(); |
307 | 0 | Vertex mv1 = (Vertex)svm.getMappedVertex(v1); |
308 | 0 | Vertex mv2 = (Vertex)svm.getMappedVertex(v2); |
309 | Edge me; | |
310 | 0 | if (Math.random() < 0.5) |
311 | 0 | me = new DirectedSparseEdge(mv1, mv2); |
312 | else | |
313 | 0 | me = new UndirectedSparseEdge(mv1, mv2); |
314 | 0 | g.addEdge(me); |
315 | 0 | edge_weights.setNumber(me, new Double(Math.random())); |
316 | } | |
317 | ||
318 | 0 | return g; |
319 | } | |
320 | ||
321 | ||
322 | } |
this report was generated by version 1.0.5 of jcoverage. |
copyright © 2003, jcoverage ltd. all rights reserved. |