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

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.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 {
801    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      */
931    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)
1051    {
1061        if (init_vertices <= 0)
1070            throw new IllegalArgumentException("Number of initial unconnected 'seed' vertices " +
108                     "must be positive");
1091        if (numEdgesToAttach <= 0)
1100            throw new IllegalArgumentException("Number of edges to attach " +
111                     "at each time step must be positive");
112         
1131        if (!parallel && init_vertices < numEdgesToAttach)
1140            throw new IllegalArgumentException("If parallel edges disallowed, initial" +
115                     "number of vertices must be >= number of edges to attach at each time step");
1161        mNumEdgesToAttachPerStep = numEdgesToAttach;
1171        mRandom = new Random(seed);
1181        this.init_vertices = init_vertices;
1191        this.directed = directed;
1201        this.parallel = parallel;
1211        initialize();
1221    }
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     {
1331        this(init_vertices, numEdgesToAttach, false, false, seed);
1341    }
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) {
1440        this(init_vertices, numEdgesToAttach, (int) System.currentTimeMillis());
1450    }
146     
147     private void initialize()
148     {
1491        if (directed)
1500            mGraph = new DirectedSparseGraph();
151         else
1521            mGraph = new UndirectedSparseGraph();
1531        if (parallel)
1540            mGraph.getEdgeConstraints().remove(Graph.NOT_PARALLEL_EDGE);
1551        vertex_index = new Vector(2*init_vertices);
1561        index_vertex = new HashMap(2*init_vertices);
1572        for (int i = 0; i < init_vertices; i++)
158         {
1591            Vertex v = new UndirectedSparseVertex();
1601            mGraph.addVertex(v);
1611            vertex_index.add(v);
1621            index_vertex.put(v, new Integer(i));
1631            v.addUserDatum(SEED, SEED, UserData.REMOVE);
164         }
165             
1661        mElapsedTimeSteps = 0;
1671    }
168  
169     private Edge createRandomEdge(Set preexistingNodes, Vertex newVertex, Set added_pairs)
170     {
171         Vertex attach_point;
172100        boolean created_edge = false;
173         Pair endpoints;
174         do
175         {
1763166            attach_point = (Vertex)vertex_index.elementAt(mRandom.nextInt(vertex_index.size()));
177             
1783166            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.
1833166            if (!parallel && added_pairs.contains(endpoints))
1840                continue;
185             
1863166            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)
1903166            double attach_prob = (degree + 1) / (mGraph.numEdges() + mGraph.numVertices() - 1);
1913166            if (attach_prob >= mRandom.nextDouble())
192100                created_edge = true;
193         }
1943166        while (!created_edge);
195  
196         Edge to_add;
197         
198100        if (directed)
199         {
2000            to_add = new DirectedSparseEdge(newVertex, attach_point);
2010            added_pairs.add(endpoints);
202         }
203         else
204         {
205100            to_add = new UndirectedSparseEdge(newVertex, attach_point);
206100            added_pairs.add(endpoints);
207100            added_pairs.add(new Pair(attach_point, newVertex));
208         }
209         
210100        return to_add;
211     }
212  
213     public void evolveGraph(int numTimeSteps) {
214  
215110        for (int i = 0; i < numTimeSteps; i++) {
216100            evolveGraph();
217100            mElapsedTimeSteps++;
218         }
21910    }
220  
221     private void evolveGraph()
222     {
223100        Set preexistingNodes = mGraph.getVertices();
224         Vertex newVertex;
225100        if (directed)
2260            newVertex = new DirectedSparseVertex();
227         else
228100            newVertex = new UndirectedSparseVertex();
229100        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)
234100        List edges = new LinkedList();
235100        HashSet added_pairs = new HashSet(mNumEdgesToAttachPerStep*3);
236200        for (int i = 0; i < mNumEdgesToAttachPerStep; i++)
237100            edges.add(createRandomEdge(preexistingNodes, newVertex, added_pairs));
238         
239         // add edges to graph, now that we have them all
240100        for (Iterator iter = edges.iterator(); iter.hasNext(); )
241100            mGraph.addEdge((Edge)iter.next());
242         
243         // now that we're done attaching edges to this new vertex,
244         // add it to the index
245100        vertex_index.add(newVertex);
246100        index_vertex.put(newVertex, new Integer(vertex_index.size() - 1));
247100    }
248  
249     public int getIndex(Vertex v)
250     {
2510        return ((Integer)index_vertex.get(v)).intValue();
252     }
253     
254     public int getNumElapsedTimeSteps() {
2550        return mElapsedTimeSteps;
256     }
257  
258     public ArchetypeGraph generateGraph() {
25910        return mGraph;
260     }
261  
262     public void reset() {
2630        initialize();
2640    }
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.