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

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.Arrays;`
13 |  | ``
14 |  | `import edu.uci.ics.jung.graph.ArchetypeGraph;`
15 |  | `import edu.uci.ics.jung.graph.Graph;`
16 |  | `import edu.uci.ics.jung.graph.Vertex;`
17 |  | `import edu.uci.ics.jung.graph.decorators.Indexer;`
18 |  | `import edu.uci.ics.jung.utils.GraphUtils;`
19 |  | ``
20 |  | `/**`
21 |  | `* Graph generator that produces a random graph with small world properties. The underlying model is`
22 |  | `* an nxn toroidal lattice. Each node u has four local connections, one to each of its neighbors, and`
23 |  | `* in addition one long range connection to some node v where v is chosen randomly according to`
24 |  | `* probability proportional to d^-alpha where d is the lattice distance between u and v and alpha`
25 |  | `* is the clustering expononent.`
26 |  | `* @see "Navigation in a small world J. Kleinberg, Nature 406(2000), 845."`
27 |  | `* @author Scott White`
28 |  | `*/`
29 |  | `public class KleinbergSmallWorldGenerator extends Lattice2DGenerator {`
30 |  | `//private int mNumNodes;`
31 |  | `private double mClusteringExponent;`
32 |  | `private int mLongRangeDistanceDistributionsSize;`
33 |  | `private int[] mLongRangeDistanceDistributions;`
34 |  | ``
35 |  | `/**`
36 |  | `* Constructs the small world graph generator.`
37 |  | `* @param latticeSize the lattice size (length of row or column dimension)`
38 |  | `* @param clusteringExponent the clustering exponent parameter (somewhere around 2 is a good choice)`
39 |  | `*/`
40 |  | `public KleinbergSmallWorldGenerator(int latticeSize, double clusteringExponent) {`
41 | 10 | `super(latticeSize,true);`
42 |  | ``
43 | 10 | `mLongRangeDistanceDistributionsSize = getLatticeSize() * 1000;`
44 | 10 | `mClusteringExponent = clusteringExponent;`
45 | 10 | `}`
46 |  | ``
47 |  | `/**`
48 |  | `* Generates a random small world network according to the parameters given`
49 |  | `* @return a random small world graph`
50 |  | `*/`
51 |  | `public ArchetypeGraph generateGraph() {`
52 |  | ``
53 | 10 | `Lattice2DGenerator generator = new Lattice2DGenerator(getLatticeSize(),true);`
54 | 10 | `Graph graph = (Graph) generator.generateGraph();`
55 |  | ``
56 | 10 | `Indexer id = Indexer.getIndexer( graph ) ;`
57 |  | ``
58 | 10 | `computeLongDistanceEdgeDistributionSample();`
59 |  | ``
60 | 10 | `int numNodes = (int) Math.pow(getLatticeSize(), 2);`
61 |  | ``
62 |  | `//Add long range connections`
63 | 260 | `for (int i = 0; i < numNodes; i++) {`
64 |  | ``
65 |  | `//choose random distance`
66 | 250 | `int sampleNodeIndex = (int) (Math.random() * mLongRangeDistanceDistributionsSize);`
67 | 250 | `int randomDistance = mLongRangeDistanceDistributions[sampleNodeIndex];`
68 |  | `while (true) {`
69 | 251 | `int randomNodeIndex = simulatePath(i, randomDistance);`
70 |  | ``
71 | 251 | `Vertex source = (Vertex) id.getVertex(i);`
72 | 251 | `Vertex target = (Vertex) id.getVertex(randomNodeIndex);`
73 |  | ``
74 | 251 | `if (!target.isSuccessorOf(source)) {`
75 | 250 | `GraphUtils.addEdge( graph, source, target);`
76 | 250 | `break;`
77 |  | `}`
78 |  | ``
79 |  | `}`
80 |  | `}`
81 |  | ``
82 | 10 | `return graph;`
83 |  | `}`
84 |  | ``
85 |  | `private static int pickValue(boolean[] choices) {`
86 |  | ``
87 | 659 | `int totalNumChoicesLeft= 0;`
88 | 3295 | `for (int x =0;x<choices.length;x++) {`
89 | 2636 | `if (choices[x]) {`
90 | 2109 | `totalNumChoicesLeft++;`
91 |  | `}`
92 |  | `}`
93 |  | ``
94 | 659 | `double randValue = Math.random();`
95 | 659 | `int i = 1;`
96 |  | ``
97 | 2211 | `for (;i<=totalNumChoicesLeft; i++) {`
98 | 1435 | `if (randValue < (double) i/ (double) totalNumChoicesLeft) {`
99 | 659 | `break;`
100 |  | `}`
101 |  | `}`
102 |  | ``
103 | 659 | `int currentChoice = 1;`
104 | 1492 | `for (int j=0;i<choices.length;j++) {`
105 | 1419 | `if (choices[j]) {`
106 | 1143 | `if (currentChoice == i) {`
107 | 586 | `return j+1;`
108 |  | `}`
109 | 557 | `currentChoice++;`
110 |  | `}`
111 |  | `}`
112 |  | ``
113 | 73 | `return currentChoice;`
114 |  | `}`
115 |  | ``
116 |  | `private int simulatePath(int index, int distance) {`
117 |  | ``
118 |  | `//1 = up,2 = down,3 = left, 4 = right`
119 | 251 | `boolean[] currentChoices = new boolean[4];`
120 | 251 | `Arrays.fill(currentChoices, true);`
121 |  | ``
122 | 251 | `int numSteps = 0;`
123 | 251 | `int currentChoice = 0;`
124 | 251 | `int newIndex = 0;`
125 | 251 | `int xCoordinate = index / getLatticeSize();`
126 | 251 | `int yCoordinate = index % getLatticeSize();`
127 |  | ``
128 |  | ``
129 | 910 | `while (numSteps < distance) {`
130 |  | ``
131 | 659 | `currentChoice = pickValue(currentChoices);`
132 |  | ``
133 | 659 | `switch (currentChoice) {`
134 |  | `case 1:`
135 |  | `{`
136 | 230 | `currentChoices[1] = false;`
137 | 230 | `newIndex = upIndex(xCoordinate, yCoordinate);`
138 | 230 | `break;`
139 |  | `}`
140 |  | `case 2:`
141 |  | `{`
142 | 126 | `currentChoices[0] = false;`
143 | 126 | `newIndex = downIndex(xCoordinate, yCoordinate);`
144 | 126 | `break;`
145 |  | `}`
146 |  | `case 3:`
147 |  | `{`
148 | 202 | `currentChoices[3] = false;`
149 | 202 | `newIndex = leftIndex(xCoordinate, yCoordinate);`
150 | 202 | `break;`
151 |  | `}`
152 |  | `case 4:`
153 |  | `{`
154 | 101 | `currentChoices[2] = false;`
155 | 101 | `newIndex = rightIndex(xCoordinate, yCoordinate);`
156 |  | `break;`
157 |  | `}`
158 |  | `}`
159 | 659 | `xCoordinate = newIndex / getLatticeSize();`
160 | 659 | `yCoordinate = newIndex % getLatticeSize();`
161 |  | ``
162 | 659 | `numSteps++;`
163 |  | `}`
164 |  | ``
165 | 251 | `return newIndex;`
166 |  | `}`
167 |  | ``
168 |  | ``
169 |  | `public double getClusteringExponent() {`
170 | 0 | `return mClusteringExponent;`
171 |  | `}`
172 |  | ``
173 |  | `public void setClusteringExponent(double clusteringExponent) {`
174 | 0 | `this.mClusteringExponent = clusteringExponent;`
175 | 0 | `}`
176 |  | ``
177 |  | `private void computeLongDistanceEdgeDistributionSample() {`
178 | 10 | `int numLongRangeLevels = getLatticeSize() - 2;`
179 | 10 | `if ((getLatticeSize() % 2) == 0) {`
180 | 0 | `numLongRangeLevels = getLatticeSize() - 1;`
181 |  | `}`
182 |  | ``
183 | 10 | `double[] probDists = new double[numLongRangeLevels];`
184 | 10 | `double normalizingFactor = 0;`
185 | 10 | `int currentDistance = 2;`
186 | 40 | `for (int i = 0; i < numLongRangeLevels; i++) {`
187 | 30 | `probDists[i] = Math.pow(currentDistance, -1 * mClusteringExponent);`
188 | 30 | `normalizingFactor += probDists[i];`
189 | 30 | `currentDistance++;`
190 |  | `}`
191 |  | ``
192 | 40 | `for (int i = 0; i < numLongRangeLevels; i++) {`
193 | 30 | `probDists[i] /= normalizingFactor;`
194 |  | `}`
195 |  | ``
196 | 10 | `mLongRangeDistanceDistributions = new int[mLongRangeDistanceDistributionsSize];`
197 |  | ``
198 |  | ``
199 | 50010 | `for (int i = 0; i < mLongRangeDistanceDistributionsSize; i++) {`
200 | 50000 | `currentDistance = 2;`
201 | 50000 | `double currentCumProb = 0;`
202 | 50000 | `double randomVal = Math.random();`
203 |  | ``
204 | 78306 | `for (int j = 0; j < numLongRangeLevels; j++) {`
205 | 78306 | `currentCumProb += probDists[j];`
206 | 78306 | `if (randomVal < currentCumProb) {`
207 | 50000 | `mLongRangeDistanceDistributions[i] = currentDistance;`
208 | 50000 | `break;`
209 |  | `}`
210 | 28306 | `currentDistance += 1;`
211 |  | `}`
212 |  | `}`
213 | 10 | `}`
214 |  | `}`

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.