# Coverage details for edu.uci.ics.jung.random.generators.WattsBetaSmallWorldGenerator

Line | Hits | Source
--- | --- | ---
1 |  | `/*`
2 |  | `* Copyright (c) 2003, the JUNG Project and the Regents of the University`
3 |  | `* of California`
4 |  | `* All rights reserved.`
5 |  | `*`
6 |  | `* This software is open-source under the BSD license; see either`
7 |  | `* "license.txt" or`
8 |  | `* http://jung.sourceforge.net/license.txt for a description.`
9 |  | `*/`
10 |  | `package edu.uci.ics.jung.random.generators;`
11 |  | ``
12 |  | `import java.util.Random;`
13 |  | ``
14 |  | `import edu.uci.ics.jung.graph.ArchetypeGraph;`
15 |  | `import edu.uci.ics.jung.graph.Edge;`
16 |  | `import edu.uci.ics.jung.graph.Graph;`
17 |  | `import edu.uci.ics.jung.graph.Vertex;`
18 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
19 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;`
20 |  | `import edu.uci.ics.jung.utils.GraphUtils;`
21 |  | ``
22 |  | `/**`
23 |  | `* WattsBetaSmallWorldGenerator is a graph generator that produces a small`
24 |  | `* world network using the beta-model as proposed by Duncan Watts. The basic ideas is`
25 |  | `* to start with a one-dimensional ring lattice in which each vertex has k-neighbors and then randomly`
26 |  | `* rewire the edges, with probability beta, in such a way that a small world networks can be created for`
27 |  | `* certain values of beta and k that exhibit low charachteristic path lengths and high clustering coefficient.`
28 |  | `* @see "Small Worlds:The Dynamics of Networks between Order and Randomness by D.J. Watts"`
29 |  | `* @author Christopher Brooks, Scott White`
30 |  | `*`
31 |  | `*/`
32 |  | `public class WattsBetaSmallWorldGenerator extends Lattice1DGenerator {`
33 | 61 | `private int numNodes = 0;`
34 | 61 | `private double beta = 0;`
35 | 61 | `private int degree = 0;`
36 | 61 | `private Random random = new Random();`
37 |  | ``
38 |  | `/**`
39 |  | `* Constructs the small world graph generator.`
40 |  | `* @param numNodes the number of nodes in the ring lattice`
41 |  | `* @param beta the probability of an edge being rewired randomly; the proportion of randomly rewired edges in a graph.`
42 |  | `* @param degree the number of edges connected to each vertex; the local neighborhood size.`
43 |  | `*/`
44 |  | `public WattsBetaSmallWorldGenerator(int numNodes, double beta, int degree) {`
45 | 61 | `super(numNodes,true);`
46 |  | ``
47 | 61 | `if (numNodes < 10) {`
48 | 0 | `throw new IllegalArgumentException("Lattice must contain at least 10 vertices.");`
49 |  | `}`
50 | 61 | `if (degree % 2 != 0) {`
51 | 0 | `throw new IllegalArgumentException("All nodes must have an even degree.");`
52 |  | `}`
53 | 61 | `if (beta > 1.0 || beta < 0.0) {`
54 | 0 | `throw new IllegalArgumentException("Beta must be between 0 and 1.");`
55 |  | `}`
56 | 61 | `this.numNodes = numNodes;`
57 | 61 | `this.beta = beta;`
58 | 61 | `this.degree = degree;`
59 |  | ``
60 |  | `//System.out.println("Creating a lattice with n="+nodes+", k="+degree+", and beta="+beta+".");`
61 | 61 | `}`
62 |  | ``
63 |  | `/**`
64 |  | `* Generates a beta-network from a 1-lattice according to the parameters given.`
65 |  | `* @return a beta-network model that is potentially a small-world`
66 |  | `*/`
67 |  | `public ArchetypeGraph generateGraph() {`
68 | 61 | `Graph g = new UndirectedSparseGraph();`
69 | 61 | `GraphUtils.addVertices(g, numNodes);`
70 | 61 | `int upI = 0;//, downI = 0;`
71 | 61 | `Indexer id = Indexer.getIndexer(g);`
72 |  | ``
73 | 61 | `int numKNeighbors = (degree / 2);`
74 |  | ``
75 |  | `//create lattice structure`
76 | 4986 | `for (int i = 0; i < numNodes; i++) {`
77 | 14775 | `for (int s = 1; s <= numKNeighbors; s++) {`
78 | 9850 | `Vertex ithVertex = (Vertex) id.getVertex(i);`
79 | 9850 | `upI = upIndex(i, s);`
80 |  | `// downI = downIndex(i, s);`
81 | 9850 | `GraphUtils.addEdge(g, ithVertex, (Vertex) id.getVertex(upI));`
82 |  | `//GraphUtils.addEdge((Graph) g, ithVertex, id.getVertex(downI));`
83 |  | `}`
84 |  | `}`
85 |  | ``
86 |  | `//rewire edges`
87 | 4986 | `for (int i = 0; i < numNodes; i++) {`
88 | 14775 | `for (int s = 1; s <= numKNeighbors; s++) {`
89 |  | ``
90 |  | `while (true) {`
91 |  | `// randomly rewire a proportion, beta, of the edges in the graph.`
92 | 9909 | `double r = random.nextDouble();`
93 | 9909 | `if (r < beta) {`
94 | 1340 | `int v = (int) random.nextInt(numNodes);`
95 |  | ``
96 | 1340 | `Vertex vthVertex = (Vertex) id.getVertex(v);`
97 | 1340 | `Vertex ithVertex = (Vertex) id.getVertex(i);`
98 | 1340 | `Vertex kthVertex = (Vertex) id.getVertex(upIndex(i, s));`
99 | 1340 | `Edge e = ithVertex.findEdge(kthVertex);`
100 |  | ``
101 | 1340 | `if (!kthVertex.isNeighborOf(vthVertex) && kthVertex != vthVertex) {`
102 | 1281 | `g.removeEdge(e);`
103 | 1281 | `GraphUtils.addEdge(g, kthVertex, vthVertex);`
104 | 1281 | `break;`
105 |  | `}`
106 |  | `} else {`
107 | 59 | `break;`
108 |  | `}`
109 |  | `}`
110 |  | `}`
111 |  | `}`
112 |  | ``
113 | 61 | `return g;`
114 |  | `}`
115 |  | `}`

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.