third-party/net.sf.jung2/src/main/java/edu/uci/ics/jung/algorithms/generators/random/ErdosRenyiGenerator.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 import edu.uci.ics.jung.graph.UndirectedGraph;
  21
  22 /**
  23  * Generates a random graph using the Erdos-Renyi binomial model
  24  * (each pair of vertices is connected with probability p).
  25  *
  26  *  @author William Giordano, Scott White, Joshua O'Madadhain
  27  */
  28 public class ErdosRenyiGenerator<V,E> implements GraphGenerator<V,E> {
  29     private int mNumVertices;
  30     private double mEdgeConnectionProbability;
  31     private Random mRandom;
  32     Factory<UndirectedGraph<V,E>> graphFactory;
  33     Factory<V> vertexFactory;
  34     Factory<E> edgeFactory;
  35
  36     /**
  37      *
  38      * @param numVertices number of vertices graph should have
  39      * @param p Connection's probability between 2 vertices
  40      */
  41         public ErdosRenyiGenerator(Factory<UndirectedGraph<V,E>> graphFactory,
  42                         Factory<V> vertexFactory, Factory<E> edgeFactory,
  43                         int numVertices,double p)
  44     {
  45         if (numVertices <= 0) {
  46             throw new IllegalArgumentException("A positive # of vertices must be specified.");
  47         }
  48         mNumVertices = numVertices;
  49         if (p < 0 || p > 1) {
  50             throw new IllegalArgumentException("p must be between 0 and 1.");
  51         }
  52         this.graphFactory = graphFactory;
  53         this.vertexFactory = vertexFactory;
  54         this.edgeFactory = edgeFactory;
  55         mEdgeConnectionProbability = p;
  56         mRandom = new Random();
  57         }
  58
  59     /**
  60      * Returns a graph in which each pair of vertices is connected by
  61      * an undirected edge with the probability specified by the constructor.
  62      */
  63         public Graph<V,E> create() {
  64         UndirectedGraph<V,E> g = graphFactory.create();
  65         for(int i=0; i<mNumVertices; i++) {
  66                 g.addVertex(vertexFactory.create());
  67         }
  68         List<V> list = new ArrayList<V>(g.getVertices());
  69
  70                 for (int i = 0; i < mNumVertices-1; i++) {
  71             V v_i = list.get(i);
  72                         for (int j = i+1; j < mNumVertices; j++) {
  73                 V v_j = list.get(j);
  74                                 if (mRandom.nextDouble() < mEdgeConnectionProbability) {
  75                                         g.addEdge(edgeFactory.create(), v_i, v_j);
  76                                 }
  77                         }
  78                 }
  79         return g;
  80     }
  81
  82     /**
  83      * Sets the seed of the internal random number generator to {@code seed}.
  84      * Enables consistent behavior.
  85      */
  86     public void setSeed(long seed) {
  87         mRandom.setSeed(seed);
  88     }
  89 }
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
 100