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

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.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 |  | `*/`
44 | 30 | `public EppsteinPowerLawGenerator(int numVertices, int numEdges,int r) {`
45 | 30 | `mNumVertices = numVertices;`
46 | 30 | `mNumEdges = numEdges;`
47 | 30 | `mNumIterations = r;`
48 | 30 | `mRandom = new Random();`
49 | 30 | `}`
50 |  | ``
51 |  | `protected Graph initializeGraph() {`
52 | 30 | `Graph graph = null;`
53 | 30 | `graph = new UndirectedSparseGraph();`
54 | 30 | `GraphUtils.addVertices(graph,mNumVertices);`
55 |  | ``
56 | 30 | `Indexer id = Indexer.getIndexer(graph);`
57 |  | ``
58 | 15131 | `while (graph.numEdges() < mNumEdges) {`
59 | 15101 | `Vertex u = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));`
60 | 15101 | `Vertex v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));`
61 | 15101 | `if (!v.isSuccessorOf(u)) {`
62 | 12400 | `GraphUtils.addEdge(graph,u,v);`
63 |  | `}`
64 |  | `}`
65 |  | ``
66 | 30 | `double maxDegree = 0;`
67 | 30 | `for (Iterator vIt=graph.getVertices().iterator(); vIt.hasNext();) {`
68 | 2000 | `Vertex v = (Vertex) vIt.next();`
69 | 2000 | `maxDegree = Math.max(v.degree(),maxDegree);`
70 |  | `}`
71 | 30 | `mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;`
72 |  | ``
73 | 30 | `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() {`
81 | 30 | `Graph graph = initializeGraph();`
82 |  | ``
83 | 30 | `Indexer id = Indexer.getIndexer(graph);`
84 | 118075 | `for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {`
85 |  | ``
86 | 118045 | `Vertex v = null;`
87 | 118045 | `int degree = 0;`
88 |  | `do {`
89 | 130793 | `v = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));`
90 | 130793 | `degree = v.degree();`
91 |  | ``
92 | 130793 | `} while (degree == 0);`
93 |  | ``
94 | 118045 | `List edges = new ArrayList(v.getIncidentEdges());`
95 | 118045 | `Edge randomExistingEdge = (Edge) edges.get((int) (mRandom.nextDouble()*degree));`
96 |  | ``
97 | 118045 | `Vertex x = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));`
98 | 118045 | `Vertex y = null;`
99 |  | `do {`
100 | 233766 | `y = (Vertex) id.getVertex((int) (mRandom.nextDouble() * mNumVertices));`
101 |  | ``
102 | 233766 | `} while (mRandom.nextDouble() > ((double) (y.degree()+1)/mMaxDegree));`
103 |  | ``
104 | 118045 | `if (!y.isSuccessorOf(x) && x != y) {`
105 | 108113 | `graph.removeEdge(randomExistingEdge);`
106 | 108113 | `GraphUtils.addEdge(graph,x,y);`
107 |  | `}`
108 |  | `}`
109 |  | ``
110 | 30 | `return graph;`
111 |  | `}`
112 |  | ``
113 |  | `public void setSeed(long seed) {`
114 | 11 | `mRandom.setSeed(seed);`
115 | 11 | `}`
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.