Module org.jgrapht.core
Package org.jgrapht.generate

Class GnmRandomGraphGenerator<V,​E>

java.lang.Object
org.jgrapht.generate.GnmRandomGraphGenerator<V,​E>
Type Parameters:
V - the graph vertex type
E - 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.

Author:
Assaf Lehr, Dimitrios Michail
See Also:
GnpRandomGraphGenerator

  • 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 generator
    GnmRandomGraphGenerator​(int n, int m, java.util.Random rng, boolean loops, boolean multipleEdges)
    Create a new $G(n, M)$ random graph generator

  • Method Summary

    Modifier and Type Method Description
    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

  • Constructor Details

    • 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 nodes
      m - 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 nodes
      m - the number of edges
      seed - 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 nodes
      m - the number of edges
      seed - seed for the random number generator
      loops - whether the generated graph may contain loops
      multipleEdges - 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 nodes
      m - the number of edges
      rng - the random number generator
      loops - whether the generated graph may contain loops
      multipleEdges - whether the generated graph many contain multiple (parallel) edges between the same two vertices

  • Method Details

    • 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 interface GraphGenerator<V,​E,​V>
      Parameters:
      target - the target graph
      resultMap - 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 vertices
      java.lang.IllegalArgumentException - if the graph does not support a requested feature such as self-loops or multiple (parallel) edges