agape.generators

Class RandGenerator<V,E>

java.lang.Object

agape.generators.RandGenerator<V,E>

public class RandGenerator<V,E>
extends java.lang.Object

This class allows to generate random graphs.

Author:

V. Levorato, P. Berthome, J.-F. Lalande

Constructor Summary

Constructors

Constructor and Description
RandGenerator()

Method Summary

Methods

Modifier and Type	Method and Description
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateBarabasiAlbertGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int n, int e, int steps) This method generates Barabasi-Albert power law graph.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateEppsteinGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int n, int e, int i) This method generates Eppstein power law graph.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateErdosRenyiGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int n, double p)
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateKleinbergSWGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int width, int height, int p, int q, double r)
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateRandomRegularGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int n, int d) This method generates a random regular graph.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	generateWattsStrogatzSWGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory, org.apache.commons.collections15.Factory<V> vertexFactory, org.apache.commons.collections15.Factory<E> edgeFactory, int n, int k, double p)

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

RandGenerator

public RandGenerator()

Method Detail

generateErdosRenyiGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateErdosRenyiGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                              org.apache.commons.collections15.Factory<V> vertexFactory,
                                                              org.apache.commons.collections15.Factory<E> edgeFactory,
                                                              int n,
                                                              double p)

Type Parameters:

V -

E -

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

n - number of vertices

p - probability of connectedness (between 0.0 and 1.0)

Returns:

Erdös-Rényi random graph

See Also:

"Erdös, P. and Rényi, A., 1959. On random graphs. Publ Math Debrecen, 6(290-297), p.290-297."

generateEppsteinGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateEppsteinGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                            org.apache.commons.collections15.Factory<V> vertexFactory,
                                                            org.apache.commons.collections15.Factory<E> edgeFactory,
                                                            int n,
                                                            int e,
                                                            int i)

This method generates Eppstein power law graph. Generator from JUNG library is used in this method.

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

n - number of vertices

e - number of edges

i - the number of iterations to use: the larger the value the better the graph's degree distribution will approximate a power-law

Returns:

Eppstein power law graph

See Also:

"Eppstein, D. and Wang, J., 2002. A steady state model for graph power laws. In 2nd Int. Worksh. Web Dynamics. p. 8."

generateBarabasiAlbertGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateBarabasiAlbertGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                                  org.apache.commons.collections15.Factory<V> vertexFactory,
                                                                  org.apache.commons.collections15.Factory<E> edgeFactory,
                                                                  int n,
                                                                  int e,
                                                                  int steps)
                                                                     throws java.lang.Exception

This method generates Barabasi-Albert power law graph. Generator from JUNG library is used in this method.

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

n - amount of nodes

e - the number of edges that should be attached from the new vertex to pre-existing vertices at each time step

steps - number of steps to iterate

Returns:

Barabasi-Albert power law graph with n+steps vertices and steps * e edges.

Throws:

java.lang.Exception - if too many edges are requested to add

See Also:

"Barabasi, A.-L. and Albert, R., 1999. Emergence of scaling in random networks. Science, 286(5439), p.11."

generateKleinbergSWGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateKleinbergSWGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                               org.apache.commons.collections15.Factory<V> vertexFactory,
                                                               org.apache.commons.collections15.Factory<E> edgeFactory,
                                                               int width,
                                                               int height,
                                                               int p,
                                                               int q,
                                                               double r)

Type Parameters:

V -

E -

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

width - the width of the grid (in number of vertices)

height - the height of the grid (in number of vertices)

p - Manhattan distance of the all nodes to connect to the neighbors of a node v

r - A constant to manage the probability of connecting a node v to a long distance node

q - The number of long distance neighbors of v

Returns:

Kleinberg small-world graph

See Also:

"Kleinberg, J., 2000. The small-world phenomenon. In The thirty-second annual ACM symposium on Theory of computing. New York, New York, USA: ACM Press, pp. 163-170."

generateWattsStrogatzSWGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateWattsStrogatzSWGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                                   org.apache.commons.collections15.Factory<V> vertexFactory,
                                                                   org.apache.commons.collections15.Factory<E> edgeFactory,
                                                                   int n,
                                                                   int k,
                                                                   double p)
                                                                      throws java.lang.Exception

Type Parameters:

V -

E -

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

n - number of vertices

k - mean degree of the graph

p - probability of rewiring an edge

Returns:

Watts-Strogatz small-world graph

Throws:

java.lang.Exception - when the probability is not in [0,1]

See Also:

"Watts, D.J. and Strogatz, S., 1998. Collective dynamics of 'small-world' networks. Nature, 393, p.440-442."

generateRandomRegularGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> generateRandomRegularGraph(org.apache.commons.collections15.Factory<edu.uci.ics.jung.graph.Graph<V,E>> graphFactory,
                                                                 org.apache.commons.collections15.Factory<V> vertexFactory,
                                                                 org.apache.commons.collections15.Factory<E> edgeFactory,
                                                                 int n,
                                                                 int d)

This method generates a random regular graph.

Parameters:

graphFactory - graph factory

vertexFactory - vertex factory

edgeFactory - edge factory

n - number of vertices

d - degree of the graph

Returns:

random regular graph