2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
6 * This software is open-source under the BSD license; see either
8 * http://jung.sourceforge.net/license.txt for a description.
10 package edu.uci.ics.jung.algorithms.generators.random;
12 import java.util.ArrayList;
13 import java.util.List;
14 import java.util.Random;
16 import org.apache.commons.collections15.Factory;
18 import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
19 import edu.uci.ics.jung.graph.Graph;
22 * Graph generator that generates undirected graphs with power-law degree distributions.
24 * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang"
26 public class EppsteinPowerLawGenerator<V,E> implements GraphGenerator<V,E> {
27 private int mNumVertices;
28 private int mNumEdges;
29 private int mNumIterations;
30 private double mMaxDegree;
31 private Random mRandom;
32 private Factory<Graph<V,E>> graphFactory;
33 private Factory<V> vertexFactory;
34 private Factory<E> edgeFactory;
37 * Creates an instance with the specified factories and specifications.
38 * @param graphFactory the factory to use to generate the graph
39 * @param vertexFactory the factory to use to create vertices
40 * @param edgeFactory the factory to use to create edges
41 * @param numVertices the number of vertices for the generated graph
42 * @param numEdges the number of edges the generated graph will have, should be Theta(numVertices)
43 * @param r the number of iterations to use; the larger the value the better the graph's degree
44 * distribution will approximate a power-law
46 public EppsteinPowerLawGenerator(Factory<Graph<V,E>> graphFactory,
47 Factory<V> vertexFactory, Factory<E> edgeFactory,
48 int numVertices, int numEdges, int r) {
49 this.graphFactory = graphFactory;
50 this.vertexFactory = vertexFactory;
51 this.edgeFactory = edgeFactory;
52 mNumVertices = numVertices;
55 mRandom = new Random();
58 protected Graph<V,E> initializeGraph() {
59 Graph<V,E> graph = null;
60 graph = graphFactory.create();
61 for(int i=0; i<mNumVertices; i++) {
62 graph.addVertex(vertexFactory.create());
64 List<V> vertices = new ArrayList<V>(graph.getVertices());
65 while (graph.getEdgeCount() < mNumEdges) {
66 V u = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
67 V v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
68 if (!graph.isSuccessor(v,u)) {
69 graph.addEdge(edgeFactory.create(), u, v);
74 for (V v : graph.getVertices()) {
75 maxDegree = Math.max(graph.degree(v),maxDegree);
77 mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;
83 * Generates a graph whose degree distribution approximates a power-law.
84 * @return the generated graph
86 public Graph<V,E> create() {
87 Graph<V,E> graph = initializeGraph();
89 List<V> vertices = new ArrayList<V>(graph.getVertices());
90 for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {
95 v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
96 degree = graph.degree(v);
98 } while (degree == 0);
100 List<E> edges = new ArrayList<E>(graph.getIncidentEdges(v));
101 E randomExistingEdge = edges.get((int) (mRandom.nextDouble()*degree));
103 // FIXME: look at email thread on a more efficient RNG for arbitrary distributions
105 V x = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
108 y = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
110 } while (mRandom.nextDouble() > ((graph.degree(y)+1)/mMaxDegree));
112 if (!graph.isSuccessor(y,x) && x != y) {
113 graph.removeEdge(randomExistingEdge);
114 graph.addEdge(edgeFactory.create(), x, y);
122 * Sets the seed for the random number generator.
123 * @param seed input to the random number generator.
125 public void setSeed(long seed) {
126 mRandom.setSeed(seed);