/*
* Copyright (c) 2003, The JUNG Authors 
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.generators.random;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import com.google.common.base.Supplier;

import edu.uci.ics.jung.algorithms.generators.GraphGenerator;
import edu.uci.ics.jung.graph.Graph;

/**
 * Graph generator that generates undirected graphs with power-law degree distributions.
 * @author Scott White
 * @see "A Steady State Model for Graph Power Law by David Eppstein and Joseph Wang"
 */
public class EppsteinPowerLawGenerator implements GraphGenerator {
    private int mNumVertices;
    private int mNumEdges;
    private int mNumIterations;
    private double mMaxDegree;
    private Random mRandom;
    private Supplier> graphFactory;
    private Supplier vertexFactory;
    private Supplier edgeFactory;

    /**
     * Creates an instance with the specified factories and specifications.
     * @param graphFactory the Supplier to use to generate the graph
     * @param vertexFactory the Supplier to use to create vertices
     * @param edgeFactory the Supplier to use to create edges
     * @param numVertices the number of vertices for the generated graph
     * @param numEdges the number of edges the generated graph will have, should be Theta(numVertices)
     * @param r the number of iterations to use; the larger the value the better the graph's degree
     * distribution will approximate a power-law
     */
    public EppsteinPowerLawGenerator(Supplier> graphFactory,
    		Supplier vertexFactory, Supplier edgeFactory, 
    		int numVertices, int numEdges, int r) {
    	this.graphFactory = graphFactory;
    	this.vertexFactory = vertexFactory;
    	this.edgeFactory = edgeFactory;
        mNumVertices = numVertices;
        mNumEdges = numEdges;
        mNumIterations = r;
        mRandom = new Random();
    }

    protected Graph initializeGraph() {
        Graph graph = null;
        graph = graphFactory.get();
        for(int i=0; i vertices = new ArrayList(graph.getVertices());
        while (graph.getEdgeCount() < mNumEdges) {
            V u = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
            V v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
            if (!graph.isSuccessor(v,u)) {
            	graph.addEdge(edgeFactory.get(), u, v);
            }
        }

        double maxDegree = 0;
        for (V v : graph.getVertices()) {
            maxDegree = Math.max(graph.degree(v),maxDegree);
        }
        mMaxDegree = maxDegree; //(maxDegree+1)*(maxDegree)/2;

        return graph;
    }

    /**
     * Generates a graph whose degree distribution approximates a power-law.
     * @return the generated graph
     */
    public Graph get() {
        Graph graph = initializeGraph();

        List vertices = new ArrayList(graph.getVertices());
        for (int rIdx = 0; rIdx < mNumIterations; rIdx++) {

            V v = null;
            int degree = 0;
            do {
                v = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
                degree = graph.degree(v);

            } while (degree == 0);

            List edges = new ArrayList(graph.getIncidentEdges(v));
            E randomExistingEdge = edges.get((int) (mRandom.nextDouble()*degree));

            // FIXME: look at email thread on a more efficient RNG for arbitrary distributions
            
            V x = vertices.get((int) (mRandom.nextDouble() * mNumVertices));
            V y = null;
            do {
                y = vertices.get((int) (mRandom.nextDouble() * mNumVertices));

            } while (mRandom.nextDouble() > ((graph.degree(y)+1)/mMaxDegree));

            if (!graph.isSuccessor(y,x) && x != y) {
                graph.removeEdge(randomExistingEdge);
                graph.addEdge(edgeFactory.get(), x, y);
            }
        }

        return graph;
    }

    /**
     * Sets the seed for the random number generator.
     * @param seed input to the random number generator.
     */
    public void setSeed(long seed) {
        mRandom.setSeed(seed);
    }
}

 

Ads help maintain this website.