Class 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 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 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 n(n-1)/2 while for directed n(n-1). If the graph type cannot be determined (for example using adapter classes or user-created custom graph types) the generator assumes the graph is undirected and therefore uses n(n-1)/2 as the maximum number of edges. If the user requests self-loops and/or multiple edges and the graph type cannot be determined, the corresponding feature is silently ignored.

    For the G(n, p) model please see GnpRandomGraphGenerator.

    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

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) static <V,​E>
      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, VertexFactory<V> vertexFactory, 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
    • Field Detail

      • 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 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 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 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 edges between the same two vertices
    • Method Detail

      • generateGraph

        public void generateGraph​(Graph<V,​E> target,
                                  VertexFactory<V> vertexFactory,
                                  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
        vertexFactory - the vertex factory
        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 edges
      • computeMaximumAllowedEdges

        static <V,​E> 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 nodes
        isDirected - whether the graph is directed or not
        createLoops - if loops are allowed
        createMultipleEdges - if multiple edges are allowed
        Returns:
        the number of maximum edges