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;
20 import edu.uci.ics.jung.graph.UndirectedGraph;
23 * Generates a random graph using the Erdos-Renyi binomial model
24 * (each pair of vertices is connected with probability p).
26 * @author William Giordano, Scott White, Joshua O'Madadhain
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;
38 * @param numVertices number of vertices graph should have
39 * @param p Connection's probability between 2 vertices
41 public ErdosRenyiGenerator(Factory<UndirectedGraph<V,E>> graphFactory,
42 Factory<V> vertexFactory, Factory<E> edgeFactory,
43 int numVertices,double p)
45 if (numVertices <= 0) {
46 throw new IllegalArgumentException("A positive # of vertices must be specified.");
48 mNumVertices = numVertices;
50 throw new IllegalArgumentException("p must be between 0 and 1.");
52 this.graphFactory = graphFactory;
53 this.vertexFactory = vertexFactory;
54 this.edgeFactory = edgeFactory;
55 mEdgeConnectionProbability = p;
56 mRandom = new Random();
60 * Returns a graph in which each pair of vertices is connected by
61 * an undirected edge with the probability specified by the constructor.
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());
68 List<V> list = new ArrayList<V>(g.getVertices());
70 for (int i = 0; i < mNumVertices-1; i++) {
72 for (int j = i+1; j < mNumVertices; j++) {
74 if (mRandom.nextDouble() < mEdgeConnectionProbability) {
75 g.addEdge(edgeFactory.create(), v_i, v_j);
83 * Sets the seed of the internal random number generator to {@code seed}.
84 * Enables consistent behavior.
86 public void setSeed(long seed) {
87 mRandom.setSeed(seed);