- java.lang.Object
-
- org.jgrapht.generate.GnmRandomGraphGenerator<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
GraphGenerator<V,E,V>
public class GnmRandomGraphGenerator<V,E> extends java.lang.Object implements GraphGenerator<V,E,V>
Create a random graph based on the $G(n, M)$ 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, M)$ model, a graph is chosen uniformly at random from the collection of all graphs which have $n$ nodes and $M$ edges. For example, in the $G(3, 2)$ model, each of the three possible graphs on three vertices and two edges are included with probability $\frac{1}{3}$.
The implementation creates the vertices and then randomly chooses an edge and tries to add it. If the add fails for any reason (an edge already exists and multiple (parallel) edges are not allowed) it will just choose another and try again. The performance therefore varies significantly based on the probability of successfully constructing an acceptable edge.
The implementation tries to guess the number of allowed edges based on the following. If self-loops or multiple edges are allowed and requested, the maximum number of edges is
Integer.MAX_VALUE
. Otherwise the maximum for undirected graphs with n vertices is $\frac{n(n-1)}{2}$ while for directed $n(n-1)$.For the $G(n, p)$ model please see
GnpRandomGraphGenerator
.- See Also:
GnpRandomGraphGenerator
-
-
Field Summary
Fields Modifier and Type Field Description private static boolean
DEFAULT_ALLOW_LOOPS
private static boolean
DEFAULT_ALLOW_MULTIPLE_EDGES
private boolean
loops
private int
m
private boolean
multipleEdges
private int
n
private java.util.Random
rng
-
Constructor Summary
Constructors Constructor Description GnmRandomGraphGenerator(int n, int m)
Create a new $G(n, M)$ random graph generator.GnmRandomGraphGenerator(int n, int m, long seed)
Create a new $G(n, M)$ random graph generator.GnmRandomGraphGenerator(int n, int m, long seed, boolean loops, boolean multipleEdges)
Create a new $G(n, M)$ random graph generatorGnmRandomGraphGenerator(int n, int m, java.util.Random rng, boolean loops, boolean multipleEdges)
Create a new $G(n, M)$ random graph generator
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description (package private) static int
computeMaximumAllowedEdges(int n, boolean isDirected, boolean createLoops, boolean createMultipleEdges)
Return the number of allowed edges based on the graph type.void
generateGraph(Graph<V,E> target, java.util.Map<java.lang.String,V> resultMap)
Generates a random graph based on the $G(n, M)$ 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
-
-
-
-
Field Detail
-
DEFAULT_ALLOW_LOOPS
private static final boolean DEFAULT_ALLOW_LOOPS
- See Also:
- Constant Field Values
-
DEFAULT_ALLOW_MULTIPLE_EDGES
private static final boolean DEFAULT_ALLOW_MULTIPLE_EDGES
- See Also:
- Constant Field Values
-
rng
private final java.util.Random rng
-
n
private final int n
-
m
private final int m
-
loops
private final boolean loops
-
multipleEdges
private final boolean multipleEdges
-
-
Constructor Detail
-
GnmRandomGraphGenerator
public GnmRandomGraphGenerator(int n, int m)
Create a new $G(n, M)$ random graph generator. The generator does not create self-loops or multiple (parallel) edges between the same two vertices.- Parameters:
n
- the number of nodesm
- the number of edges
-
GnmRandomGraphGenerator
public GnmRandomGraphGenerator(int n, int m, long seed)
Create a new $G(n, M)$ random graph generator. The generator does not create self-loops or multiple (parallel) edges between the same two vertices.- Parameters:
n
- the number of nodesm
- the number of edgesseed
- seed for the random number generator
-
GnmRandomGraphGenerator
public GnmRandomGraphGenerator(int n, int m, long seed, boolean loops, boolean multipleEdges)
Create a new $G(n, M)$ random graph generator- Parameters:
n
- the number of nodesm
- the number of edgesseed
- seed for the random number generatorloops
- whether the generated graph may contain loopsmultipleEdges
- whether the generated graph many contain multiple (parallel) edges between the same two vertices
-
GnmRandomGraphGenerator
public GnmRandomGraphGenerator(int n, int m, java.util.Random rng, boolean loops, boolean multipleEdges)
Create a new $G(n, M)$ random graph generator- Parameters:
n
- the number of nodesm
- the number of edgesrng
- the random number generatorloops
- whether the generated graph may contain loopsmultipleEdges
- whether the generated graph many contain multiple (parallel) edges between the same two vertices
-
-
Method Detail
-
generateGraph
public void generateGraph(Graph<V,E> target, java.util.Map<java.lang.String,V> resultMap)
Generates a random graph based on the $G(n, M)$ model- Specified by:
generateGraph
in interfaceGraphGenerator<V,E,V>
- Parameters:
target
- the target graphresultMap
- not used by this generator, can be null- Throws:
java.lang.IllegalArgumentException
- if the number of edges, passed in the constructor, cannot be created on a graph of the concrete type with the specified number of verticesjava.lang.IllegalArgumentException
- if the graph does not support a requested feature such as self-loops or multiple (parallel) edges
-
computeMaximumAllowedEdges
static int computeMaximumAllowedEdges(int n, boolean isDirected, boolean createLoops, boolean createMultipleEdges)
Return the number of allowed edges based on the graph type.- Parameters:
n
- number of nodesisDirected
- whether the graph is directed or notcreateLoops
- if loops are allowedcreateMultipleEdges
- if multiple (parallel) edges are allowed- Returns:
- the number of maximum edges
-
-