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

LineHitsSource
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) {
4110        super(latticeSize,true);
42  
4310        mLongRangeDistanceDistributionsSize = getLatticeSize() * 1000;
4410        mClusteringExponent = clusteringExponent;
4510    }
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         
5310        Lattice2DGenerator generator = new Lattice2DGenerator(getLatticeSize(),true);
5410        Graph graph = (Graph) generator.generateGraph();
55         
5610        Indexer id = Indexer.getIndexer( graph ) ;
57         
5810        computeLongDistanceEdgeDistributionSample();
59         
6010        int numNodes = (int) Math.pow(getLatticeSize(), 2);
61         
62         //Add long range connections
63260        for (int i = 0; i < numNodes; i++) {
64  
65             //choose random distance
66250            int sampleNodeIndex = (int) (Math.random() * mLongRangeDistanceDistributionsSize);
67250            int randomDistance = mLongRangeDistanceDistributions[sampleNodeIndex];
68             while (true) {
69250                int randomNodeIndex = simulatePath(i, randomDistance);
70  
71250                Vertex source = (Vertex) id.getVertex(i);
72250                Vertex target = (Vertex) id.getVertex(randomNodeIndex);
73  
74250                if (!target.isSuccessorOf(source)) {
75250                    GraphUtils.addEdge( graph, source, target);
76250                    break;
77                 }
78  
79             }
80         }
81  
8210        return graph;
83     }
84  
85     private static int pickValue(boolean[] choices) {
86  
87619        int totalNumChoicesLeft= 0;
883095        for (int x =0;x<choices.length;x++) {
892476            if (choices[x]) {
902022                  totalNumChoicesLeft++;
91             }
92         }
93  
94619        double randValue = Math.random();
95619        int i = 1;
96  
971977        for (;i<=totalNumChoicesLeft; i++) {
981298            if (randValue < (double) i/ (double) totalNumChoicesLeft) {
99619                break;
100             }
101         }
102  
103619        int currentChoice = 1;
1041359        for (int j=0;i<choices.length;j++) {
1051300            if (choices[j]) {
1061062                if (currentChoice == i) {
107560                    return j+1;
108                 }
109502                currentChoice++;
110             }
111         }
112  
11359        return currentChoice;
114     }
115  
116     private int simulatePath(int index, int distance) {
117  
118         //1 = up,2 = down,3 = left, 4 = right
119250        boolean[] currentChoices = new boolean[4];
120250        Arrays.fill(currentChoices, true);
121  
122250        int numSteps = 0;
123250        int currentChoice = 0;
124250        int newIndex = 0;
125250        int xCoordinate = index / getLatticeSize();
126250        int yCoordinate = index % getLatticeSize();
127  
128  
129869        while (numSteps < distance) {
130  
131619            currentChoice = pickValue(currentChoices);
132  
133619            switch (currentChoice) {
134                 case 1:
135                     {
136221                        currentChoices[1] = false;
137221                        newIndex = upIndex(xCoordinate, yCoordinate);
138221                        break;
139                     }
140                 case 2:
141                     {
142137                        currentChoices[0] = false;
143137                        newIndex = downIndex(xCoordinate, yCoordinate);
144137                        break;
145                     }
146                 case 3:
147                     {
148180                        currentChoices[3] = false;
149180                        newIndex = leftIndex(xCoordinate, yCoordinate);
150180                        break;
151                     }
152                 case 4:
153                     {
15481                        currentChoices[2] = false;
15581                        newIndex = rightIndex(xCoordinate, yCoordinate);
156                         break;
157                     }
158             }
159619            xCoordinate = newIndex / getLatticeSize();
160619            yCoordinate = newIndex % getLatticeSize();
161  
162619            numSteps++;
163         }
164  
165250        return newIndex;
166     }
167  
168  
169     public double getClusteringExponent() {
1700        return mClusteringExponent;
171     }
172  
173     public void setClusteringExponent(double clusteringExponent) {
1740        this.mClusteringExponent = clusteringExponent;
1750    }
176  
177     private void computeLongDistanceEdgeDistributionSample() {
17810        int numLongRangeLevels = getLatticeSize() - 2;
17910        if ((getLatticeSize() % 2) == 0) {
1800            numLongRangeLevels = getLatticeSize() - 1;
181         }
182  
18310        double[] probDists = new double[numLongRangeLevels];
18410        double normalizingFactor = 0;
18510        int currentDistance = 2;
18640        for (int i = 0; i < numLongRangeLevels; i++) {
18730            probDists[i] = Math.pow(currentDistance, -1 * mClusteringExponent);
18830            normalizingFactor += probDists[i];
18930            currentDistance++;
190         }
191  
19240        for (int i = 0; i < numLongRangeLevels; i++) {
19330            probDists[i] /= normalizingFactor;
194         }
195  
19610        mLongRangeDistanceDistributions = new int[mLongRangeDistanceDistributionsSize];
197  
198  
19950010        for (int i = 0; i < mLongRangeDistanceDistributionsSize; i++) {
20050000            currentDistance = 2;
20150000            double currentCumProb = 0;
20250000            double randomVal = Math.random();
203  
20478032            for (int j = 0; j < numLongRangeLevels; j++) {
20578032                currentCumProb += probDists[j];
20678032                if (randomVal < currentCumProb) {
20750000                    mLongRangeDistanceDistributions[i] = currentDistance;
20850000                    break;
209                 }
21028032                currentDistance += 1;
211             }
212         }
21310    }
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.