third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/EppsteinPowerLawGenerator.java

   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.algorithms.generators.random;
  11
  12 import java.util.ArrayList;
  13 import java.util.List;
  14 import java.util.Random;
  15
  16 import org.apache.commons.collections15.Factory;
  17
  18 import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
  19 import edu.uci.ics.jung.graph.Graph;
  20
  21 /**
  22  * Graph generator that generates undirected graphs with power-law degree distributions.
  23  * @author Scott White
  24  * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang"
  25  */
  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;
  35
  36     /**
  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
  45      */
  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;
  53         mNumEdges = numEdges;
  54         mNumIterations = r;
  55         mRandom = new Random();
  56     }
  57
  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());
  63         }
  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);
  70             }
  71         }
  72
  73         double maxDegree = 0;
  74         for (V v : graph.getVertices()) {
  75             maxDegree = Math.max(graph.degree(v),maxDegree);
  76         }
  77         mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;
  78
  79         return graph;
  80     }
  81
  82     /**
  83      * Generates a graph whose degree distribution approximates a power-law.
  84      * @return the generated graph
  85      */
  86     public Graph<V,E> create() {
  87         Graph<V,E> graph = initializeGraph();
  88
  89         List<V> vertices = new ArrayList<V>(graph.getVertices());
  90         for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {
  91
  92             V v = null;
  93             int degree = 0;
  94             do {
  95                 v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
  96                 degree = graph.degree(v);
  97
  98             } while (degree == 0);
  99
 100             List<E> edges = new ArrayList<E>(graph.getIncidentEdges(v));
 101             E randomExistingEdge = edges.get((int) (mRandom.nextDouble()*degree));
 102
 103             // FIXME: look at email thread on a more efficient RNG for arbitrary distributions
 104
 105             V x = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
 106             V y = null;
 107             do {
 108                 y = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
 109
 110             } while (mRandom.nextDouble() > ((graph.degree(y)+1)/mMaxDegree));
 111
 112             if (!graph.isSuccessor(y,x) && x != y) {
 113                 graph.removeEdge(randomExistingEdge);
 114                 graph.addEdge(edgeFactory.create(), x, y);
 115             }
 116         }
 117
 118         return graph;
 119     }
 120
 121     /**
 122      * Sets the seed for the random number generator.
 123      * @param seed input to the random number generator.
 124      */
 125     public void setSeed(long seed) {
 126         mRandom.setSeed(seed);
 127     }
 128 }