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

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.HashMap;`
13 |  | `import java.util.HashSet;`
14 |  | `import java.util.Iterator;`
15 |  | `import java.util.LinkedList;`
16 |  | `import java.util.List;`
17 |  | `import java.util.Map;`
18 |  | `import java.util.Random;`
19 |  | `import java.util.Set;`
20 |  | `import java.util.Vector;`
21 |  | ``
22 |  | `import edu.uci.ics.jung.graph.ArchetypeGraph;`
23 |  | `import edu.uci.ics.jung.graph.Edge;`
24 |  | `import edu.uci.ics.jung.graph.Graph;`
25 |  | `import edu.uci.ics.jung.graph.Vertex;`
26 |  | `import edu.uci.ics.jung.graph.impl.DirectedSparseEdge;`
27 |  | `import edu.uci.ics.jung.graph.impl.DirectedSparseGraph;`
28 |  | `import edu.uci.ics.jung.graph.impl.DirectedSparseVertex;`
29 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseEdge;`
30 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseGraph;`
31 |  | `import edu.uci.ics.jung.graph.impl.UndirectedSparseVertex;`
32 |  | `import edu.uci.ics.jung.utils.Pair;`
33 |  | `import edu.uci.ics.jung.utils.UserData;`
34 |  | ``
35 |  | `/**`
36 |  | `* <p>Simple evolving scale-free random graph generator. At each time`
37 |  | `* step, a new vertex is created and is connected to existing vertices`
38 |  | `* according to the principle of "preferential attachment", whereby`
39 |  | `* vertices with higher degree have a higher probability of being`
40 |  | `* selected for attachment.</p>`
41 |  | `*`
42 |  | `* <p>At a given timestep, the probability <code>p</code> of creating an edge`
43 |  | `* between an existing vertex <code>v</code> and the newly added vertex is`
44 |  | `* <pre>`
45 |  | `* p = (degree(v) + 1) / (|E| + |V|);`
46 |  | `* </pre>`
47 |  | `*`
48 |  | `* <p>where <code>|E|</code> and <code>|V|</code> are, respectively, the number`
49 |  | `* of edges and vertices currently in the network (counting neither the new`
50 |  | `* vertex nor the other edges that are being attached to it).</p>`
51 |  | `*`
52 |  | `* <p>Note that the formula specified in the original paper`
53 |  | `* (cited below) was`
54 |  | `* <pre>`
55 |  | `* p = degree(v) / |E|`
56 |  | `* </pre>`
57 |  | `* </p>`
58 |  | `*`
59 |  | `* <p>However, this would have meant that the probability of attachment for any existing`
60 |  | `* isolated vertex would be 0. This version uses Lagrangian smoothing to give`
61 |  | `* each existing vertex a positive attachment probability.</p>`
62 |  | `*`
63 |  | `* <p>The graph created may be either directed or undirected (controlled by a constructor`
64 |  | `* parameter); the default is undirected.`
65 |  | `* If the graph is specified to be directed, then the edges added will be directed`
66 |  | `* from the newly added vertex u to the existing vertex v, with probability proportional to the`
67 |  | `* indegree of v (number of edges directed towards v). If the graph is specified to be undirected,`
68 |  | `* then the (undirected) edges added will connect u to v, with probability proportional to the`
69 |  | `* degree of v.</p>`
70 |  | `*`
71 |  | `* <p>The <code>parallel</code> constructor parameter specifies whether parallel edges`
72 |  | `* may be created.</p>`
73 |  | `*`
74 |  | `* @see "A.-L. Barabasi and R. Albert, Emergence of scaling in random networks, Science 286, 1999."`
75 |  | `* @author Scott White`
76 |  | `* @author Joshua O'Madadhain`
77 |  | `*/`
78 |  | `public class BarabasiAlbertGenerator implements EvolvingGraphGenerator`
79 |  | `{`
80 | 1 | `private Graph mGraph = null;`
81 |  | `private int mNumEdgesToAttachPerStep;`
82 |  | `private int mElapsedTimeSteps;`
83 |  | `private Random mRandom;`
84 |  | `protected Vector vertex_index;`
85 |  | `protected int init_vertices;`
86 |  | `protected Map index_vertex;`
87 |  | `protected boolean directed;`
88 |  | `protected boolean parallel;`
89 |  | ``
90 |  | `/**`
91 |  | `* Tags the initial "seed" vertices that the graph starts with`
92 |  | `*/`
93 | 1 | `public final static Object SEED = "edu.uci.ics.jung.random.generators.BarabasiAlbertGenerator.SEED";`
94 |  | ``
95 |  | `/**`
96 |  | `* Constructs a new instance of the generator.`
97 |  | `* @param init_vertices number of unconnected 'seed' vertices that the graph should start with`
98 |  | `* @param numEdgesToAttach the number of edges that should be attached from the`
99 |  | `* new vertex to pre-existing vertices at each time step`
100 |  | `* @param directed specifies whether the graph and edges to be created should be directed or not`
101 |  | `* @param parallel specifies whether the algorithm permits parallel edges`
102 |  | `* @param seed random number seed`
103 |  | `*/`
104 |  | `public BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, boolean directed, boolean parallel, int seed)`
105 | 1 | `{`
106 | 1 | `if (init_vertices <= 0)`
107 | 0 | `throw new IllegalArgumentException("Number of initial unconnected 'seed' vertices " +`
108 |  | `"must be positive");`
109 | 1 | `if (numEdgesToAttach <= 0)`
110 | 0 | `throw new IllegalArgumentException("Number of edges to attach " +`
111 |  | `"at each time step must be positive");`
112 |  | ``
113 | 1 | `if (!parallel && init_vertices < numEdgesToAttach)`
114 | 0 | `throw new IllegalArgumentException("If parallel edges disallowed, initial" +`
115 |  | `"number of vertices must be >= number of edges to attach at each time step");`
116 | 1 | `mNumEdgesToAttachPerStep = numEdgesToAttach;`
117 | 1 | `mRandom = new Random(seed);`
118 | 1 | `this.init_vertices = init_vertices;`
119 | 1 | `this.directed = directed;`
120 | 1 | `this.parallel = parallel;`
121 | 1 | `initialize();`
122 | 1 | `}`
123 |  | ``
124 |  | `/**`
125 |  | `* Constructs a new instance of the generator, whose output will be an undirected graph.`
126 |  | `* @param init_vertices number of unconnected 'seed' vertices that the graph should start with`
127 |  | `* @param numEdgesToAttach the number of edges that should be attached from the`
128 |  | `* new vertex to pre-existing vertices at each time step`
129 |  | `* @param seed random number seed`
130 |  | `*/`
131 |  | `public BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach, int seed)`
132 |  | `{`
133 | 1 | `this(init_vertices, numEdgesToAttach, false, false, seed);`
134 | 1 | `}`
135 |  | ``
136 |  | `/**`
137 |  | `* Constructs a new instance of the generator, whose output will be an undirected graph,`
138 |  | `* and which will use the current time as a seed for the random number generation.`
139 |  | `* @param init_vertices number of vertices that the graph should start with`
140 |  | `* @param numEdgesToAttach the number of edges that should be attached from the`
141 |  | `* new vertex to pre-existing vertices at each time step`
142 |  | `*/`
143 |  | `public BarabasiAlbertGenerator(int init_vertices, int numEdgesToAttach) {`
144 | 0 | `this(init_vertices, numEdgesToAttach, (int) System.currentTimeMillis());`
145 | 0 | `}`
146 |  | ``
147 |  | `private void initialize()`
148 |  | `{`
149 | 1 | `if (directed)`
150 | 0 | `mGraph = new DirectedSparseGraph();`
151 |  | `else`
152 | 1 | `mGraph = new UndirectedSparseGraph();`
153 | 1 | `if (parallel)`
154 | 0 | `mGraph.getEdgeConstraints().remove(Graph.NOT_PARALLEL_EDGE);`
155 | 1 | `vertex_index = new Vector(2*init_vertices);`
156 | 1 | `index_vertex = new HashMap(2*init_vertices);`
157 | 2 | `for (int i = 0; i < init_vertices; i++)`
158 |  | `{`
159 | 1 | `Vertex v = new UndirectedSparseVertex();`
160 | 1 | `mGraph.addVertex(v);`
161 | 1 | `vertex_index.add(v);`
162 | 1 | `index_vertex.put(v, new Integer(i));`
163 | 1 | `v.addUserDatum(SEED, SEED, UserData.REMOVE);`
164 |  | `}`
165 |  | ``
166 | 1 | `mElapsedTimeSteps = 0;`
167 | 1 | `}`
168 |  | ``
169 |  | `private Edge createRandomEdge(Set preexistingNodes, Vertex newVertex, Set added_pairs)`
170 |  | `{`
171 |  | `Vertex attach_point;`
172 | 100 | `boolean created_edge = false;`
173 |  | `Pair endpoints;`
174 |  | `do`
175 |  | `{`
176 | 3166 | `attach_point = (Vertex)vertex_index.elementAt(mRandom.nextInt(vertex_index.size()));`
177 |  | ``
178 | 3166 | `endpoints = new Pair(newVertex, attach_point);`
179 |  | ``
180 |  | `// if parallel edges are not allowed, skip attach_point if <newVertex, attach_point>`
181 |  | `// already exists; note that because of the way edges are added, we only need to check`
182 |  | `// the list of candidate edges for duplicates.`
183 | 3166 | `if (!parallel && added_pairs.contains(endpoints))`
184 | 0 | `continue;`
185 |  | ``
186 | 3166 | `double degree = directed ? attach_point.inDegree() : attach_point.degree();`
187 |  | ``
188 |  | `// subtract 1 from numVertices because we don't want to count newVertex`
189 |  | `// (which has already been added to the graph, but not to vertex_index)`
190 | 3166 | `double attach_prob = (degree + 1) / (mGraph.numEdges() + mGraph.numVertices() - 1);`
191 | 3166 | `if (attach_prob >= mRandom.nextDouble())`
192 | 100 | `created_edge = true;`
193 |  | `}`
194 | 3166 | `while (!created_edge);`
195 |  | ``
196 |  | `Edge to_add;`
197 |  | ``
198 | 100 | `if (directed)`
199 |  | `{`
200 | 0 | `to_add = new DirectedSparseEdge(newVertex, attach_point);`
201 | 0 | `added_pairs.add(endpoints);`
202 |  | `}`
203 |  | `else`
204 |  | `{`
205 | 100 | `to_add = new UndirectedSparseEdge(newVertex, attach_point);`
206 | 100 | `added_pairs.add(endpoints);`
207 | 100 | `added_pairs.add(new Pair(attach_point, newVertex));`
208 |  | `}`
209 |  | ``
210 | 100 | `return to_add;`
211 |  | `}`
212 |  | ``
213 |  | `public void evolveGraph(int numTimeSteps) {`
214 |  | ``
215 | 110 | `for (int i = 0; i < numTimeSteps; i++) {`
216 | 100 | `evolveGraph();`
217 | 100 | `mElapsedTimeSteps++;`
218 |  | `}`
219 | 10 | `}`
220 |  | ``
221 |  | `private void evolveGraph()`
222 |  | `{`
223 | 100 | `Set preexistingNodes = mGraph.getVertices();`
224 |  | `Vertex newVertex;`
225 | 100 | `if (directed)`
226 | 0 | `newVertex = new DirectedSparseVertex();`
227 |  | `else`
228 | 100 | `newVertex = new UndirectedSparseVertex();`
229 | 100 | `mGraph.addVertex(newVertex);`
230 |  | ``
231 |  | `// generate and store the new edges; don't add them to the graph`
232 |  | `// yet because we don't want to bias the degree calculations`
233 |  | `// (all new edges in a timestep should be added in parallel)`
234 | 100 | `List edges = new LinkedList();`
235 | 100 | `HashSet added_pairs = new HashSet(mNumEdgesToAttachPerStep*3);`
236 | 200 | `for (int i = 0; i < mNumEdgesToAttachPerStep; i++)`
237 | 100 | `edges.add(createRandomEdge(preexistingNodes, newVertex, added_pairs));`
238 |  | ``
239 |  | `// add edges to graph, now that we have them all`
240 | 100 | `for (Iterator iter = edges.iterator(); iter.hasNext(); )`
241 | 100 | `mGraph.addEdge((Edge)iter.next());`
242 |  | ``
243 |  | `// now that we're done attaching edges to this new vertex,`
244 |  | `// add it to the index`
245 | 100 | `vertex_index.add(newVertex);`
246 | 100 | `index_vertex.put(newVertex, new Integer(vertex_index.size() - 1));`
247 | 100 | `}`
248 |  | ``
249 |  | `public int getIndex(Vertex v)`
250 |  | `{`
251 | 0 | `return ((Integer)index_vertex.get(v)).intValue();`
252 |  | `}`
253 |  | ``
254 |  | `public int getNumElapsedTimeSteps() {`
255 | 0 | `return mElapsedTimeSteps;`
256 |  | `}`
257 |  | ``
258 |  | `public ArchetypeGraph generateGraph() {`
259 | 10 | `return mGraph;`
260 |  | `}`
261 |  | ``
262 |  | `public void reset() {`
263 | 0 | `initialize();`
264 | 0 | `}`
265 |  | `}`

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.