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

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.ArrayList;
13 import java.util.Iterator;
14 import java.util.List;
15 import java.util.Random;
16  
17 import edu.uci.ics.jung.graph.ArchetypeGraph;
18 import edu.uci.ics.jung.graph.Edge;
19 import edu.uci.ics.jung.graph.Graph;
20 import edu.uci.ics.jung.graph.Vertex;
21 import edu.uci.ics.jung.graph.decorators.Indexer;
22 import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;
23 import edu.uci.ics.jung.utils.GraphUtils;
24  
25 /**
26  * Graph generator that generates undirected sparse graphs with power-law distributions.
27  * @author Scott White
28  * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang"
29  */
30 public class EppsteinPowerLawGenerator implements GraphGenerator {
31     private int mNumVertices;
32     private int mNumEdges;
33     private int mNumIterations;
34     private double mMaxDegree;
35     private Random mRandom;
36  
37     /**
38      * Constructor which specifies the parameters of the generator
39      * @param numVertices the number of vertices for the generated graph
40      * @param numEdges the number of edges the generated graph will have, should be Theta(numVertices)
41      * @param r the model parameter. The larger the value for this parameter the better the graph's degree
42      * distribution will approximate a power-law.
43      */
4430    public EppsteinPowerLawGenerator(int numVertices, int numEdges,int r) {
4530        mNumVertices = numVertices;
4630        mNumEdges = numEdges;
4730        mNumIterations = r;
4830        mRandom = new Random();
4930    }
50  
51     protected Graph initializeGraph() {
5230        Graph graph = null;
5330        graph = new UndirectedSparseGraph();
5430        GraphUtils.addVertices(graph,mNumVertices);
55  
5630        Indexer id = Indexer.getIndexer(graph);
57  
5815131        while (graph.numEdges() < mNumEdges) {
5915101            Vertex u = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));
6015101            Vertex v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));
6115101            if (!v.isSuccessorOf(u)) {
6212400                GraphUtils.addEdge(graph,u,v);
63             }
64         }
65  
6630        double maxDegree = 0;
6730        for (Iterator vIt=graph.getVertices().iterator(); vIt.hasNext();) {
682000            Vertex v = (Vertex) vIt.next();
692000            maxDegree = Math.max(v.degree(),maxDegree);
70         }
7130        mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;
72  
7330        return graph;
74     }
75  
76     /**
77      * Generates a graph whose degree distribution approximates a power-law.
78      * @return the generated graph
79      */
80     public ArchetypeGraph generateGraph() {
8130        Graph graph = initializeGraph();
82  
8330        Indexer id = Indexer.getIndexer(graph);
84118075        for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {
85  
86118045            Vertex v = null;
87118045            int degree = 0;
88             do {
89130793                v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));
90130793                degree = v.degree();
91  
92130793            } while (degree == 0);
93  
94118045            List edges = new ArrayList(v.getIncidentEdges());
95118045            Edge randomExistingEdge = (Edge) edges.get((int) (mRandom.nextDouble()*degree));
96  
97118045            Vertex x = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));
98118045            Vertex y = null;
99             do {
100233766                y = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));
101  
102233766            } while (mRandom.nextDouble() > ((double) (y.degree()+1)/mMaxDegree));
103  
104118045            if (!y.isSuccessorOf(x) && x != y) {
105108113                graph.removeEdge(randomExistingEdge);
106108113                GraphUtils.addEdge(graph,x,y);
107             }
108         }
109  
11030        return graph;
111     }
112  
113     public void setSeed(long seed) {
11411        mRandom.setSeed(seed);
11511    }
116 }

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.