Package org.jgrapht.generate

Class GnpRandomGraphGenerator<V,E>

java.lang.Object

org.jgrapht.generate.GnpRandomGraphGenerator<V,E>

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

GraphGenerator<V,E,V>

public class GnpRandomGraphGenerator<V,E>
extends Object
implements GraphGenerator<V,E,V>

Create a random graph based on the $G(n, p)$ Erdős–Rényi model. See the Wikipedia article for details and references about Random Graphs and the Erdős–Rényi model .

In the $G(n, p)$ model, a graph is constructed by connecting nodes randomly. Each edge is included in the graph with probability $p$ independent from every other edge. The complexity of the generator is $O(n^2)$ where $n$ is the number of vertices.

For the $G(n, M)$ model please see GnmRandomGraphGenerator.

Author:

Dimitrios Michail

See Also:

GnmRandomGraphGenerator

Constructor Summary

Constructors

Constructor	Description
GnpRandomGraphGenerator(int n, double p)	Create a new $G(n, p)$ random graph generator.
GnpRandomGraphGenerator(int n, double p, long seed)	Create a new $G(n, p)$ random graph generator.
GnpRandomGraphGenerator(int n, double p, long seed, boolean createLoops)	Create a new $G(n, p)$ random graph generator.
GnpRandomGraphGenerator(int n, double p, Random rng, boolean createLoops)	Create a new $G(n, p)$ random graph generator.

Method Summary

Modifier and Type	Method	Description
void	generateGraph(Graph<V,E> target, Map<String,V> resultMap)	Generates a random graph based on the $G(n, p)$ model.

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.jgrapht.generate.GraphGenerator

generateGraph

Constructor Detail

GnpRandomGraphGenerator

public GnpRandomGraphGenerator(int n,
                               double p)

Create a new $G(n, p)$ random graph generator. The generator does not create self-loops.

Parameters:

n - the number of nodes

p - the edge probability

GnpRandomGraphGenerator

public GnpRandomGraphGenerator(int n,
                               double p,
                               long seed)

Create a new $G(n, p)$ random graph generator. The generator does not create self-loops.

Parameters:

n - the number of nodes

p - the edge probability

seed - seed for the random number generator

GnpRandomGraphGenerator

public GnpRandomGraphGenerator(int n,
                               double p,
                               long seed,
                               boolean createLoops)

Create a new $G(n, p)$ random graph generator.

Parameters:

n - the number of nodes

p - the edge probability

seed - seed for the random number generator

createLoops - whether the generated graph may create loops

GnpRandomGraphGenerator

public GnpRandomGraphGenerator(int n,
                               double p,
                               Random rng,
                               boolean createLoops)

Create a new $G(n, p)$ random graph generator.

Parameters:

n - the number of nodes

p - the edge probability

rng - the random number generator to use

createLoops - whether the generated graph may create loops

Method Detail

generateGraph

public void generateGraph(Graph<V,E> target,
                          Map<String,V> resultMap)

Generates a random graph based on the $G(n, p)$ model.

Specified by:

generateGraph in interface GraphGenerator<V,E,V>

Parameters:

target - the target graph

resultMap - not used by this generator, can be null