# Coverage details for edu.uci.ics.jung.utils.TestGraphs

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. visit www.jcoverage.com for updates. | copyright © 2003, jcoverage ltd. all rights reserved. Java is a trademark of Sun Microsystems, Inc. in the United States and other countries.