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) {
69251                int randomNodeIndex = simulatePath(i, randomDistance);
70  
71251                Vertex source = (Vertex) id.getVertex(i);
72251                Vertex target = (Vertex) id.getVertex(randomNodeIndex);
73  
74251                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  
87659        int totalNumChoicesLeft= 0;
883295        for (int x =0;x<choices.length;x++) {
892636            if (choices[x]) {
902109                  totalNumChoicesLeft++;
91             }
92         }
93  
94659        double randValue = Math.random();
95659        int i = 1;
96  
972211        for (;i<=totalNumChoicesLeft; i++) {
981435            if (randValue < (double) i/ (double) totalNumChoicesLeft) {
99659                break;
100             }
101         }
102  
103659        int currentChoice = 1;
1041492        for (int j=0;i<choices.length;j++) {
1051419            if (choices[j]) {
1061143                if (currentChoice == i) {
107586                    return j+1;
108                 }
109557                currentChoice++;
110             }
111         }
112  
11373        return currentChoice;
114     }
115  
116     private int simulatePath(int index, int distance) {
117  
118         //1 = up,2 = down,3 = left, 4 = right
119251        boolean[] currentChoices = new boolean[4];
120251        Arrays.fill(currentChoices, true);
121  
122251        int numSteps = 0;
123251        int currentChoice = 0;
124251        int newIndex = 0;
125251        int xCoordinate = index / getLatticeSize();
126251        int yCoordinate = index % getLatticeSize();
127  
128  
129910        while (numSteps < distance) {
130  
131659            currentChoice = pickValue(currentChoices);
132  
133659            switch (currentChoice) {
134                 case 1:
135                     {
136230                        currentChoices[1] = false;
137230                        newIndex = upIndex(xCoordinate, yCoordinate);
138230                        break;
139                     }
140                 case 2:
141                     {
142126                        currentChoices[0] = false;
143126                        newIndex = downIndex(xCoordinate, yCoordinate);
144126                        break;
145                     }
146                 case 3:
147                     {
148202                        currentChoices[3] = false;
149202                        newIndex = leftIndex(xCoordinate, yCoordinate);
150202                        break;
151                     }
152                 case 4:
153                     {
154101                        currentChoices[2] = false;
155101                        newIndex = rightIndex(xCoordinate, yCoordinate);
156                         break;
157                     }
158             }
159659            xCoordinate = newIndex / getLatticeSize();
160659            yCoordinate = newIndex % getLatticeSize();
161  
162659            numSteps++;
163         }
164  
165251        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  
20478306            for (int j = 0; j < numLongRangeLevels; j++) {
20578306                currentCumProb += probDists[j];
20678306                if (randomVal < currentCumProb) {
20750000                    mLongRangeDistanceDistributions[i] = currentDistance;
20850000                    break;
209                 }
21028306                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.