Package com.jgalgo.gen

Class GnpGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class GnpGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generates a random graph using the G(n,p) model.

    The G(n,p) model generates a graph by connecting nodes randomly. Each edge is included in the graph with probability \(p\) independent from every other edge. The model has only two parameters: the vertices set and the probability \(p\). The generated graphs may be either directed or undirected, and may or may not allow self-loops. Parallel edges are never created.

    By default, the value of \(p\) is \(0.1\) and the graph is undirected and does not generate self-loops.

    For deterministic behavior, set the seed of the generator using setSeed(long).

    Based on 'On random graphs' by Erdős and Rényi.

    Author:
    Barak Ugav

    • Method Detail

      • newInstance

        public static <V,​E> GnpGraphGenerator<V,​E> newInstance()
        Creates a new G(n,p) generator.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Returns:
        a new G(n,p) generator

      • setVertices

        public void setVertices​(Collection<V> vertices)
        Set the vertices set of the generated graph(s).

        If the generator is used to generate multiple graphs, the same vertex set will be used for all of them.

        Parameters:
        vertices - the vertices set

      • setVertices

        public void setVertices​(int verticesNum,
                        Supplier<V> vertexSupplier)
        Set the vertices set of the generated graph(s) from a supplier.

        The supplier will be called exactly verticesNum times, and the same set of vertices created will be used for multiple graphs if GraphGenerator.generate() is called multiple times.

        Parameters:
        verticesNum - the number of vertices
        vertexSupplier - the supplier of vertices

      • setEdges

        public void setEdges​(Supplier<E> edgeSupplier)
        Set the edge supplier of the generated graph(s).

        The supplier will be called for any edge created, for any graph generated. This behavior is different from setVertices(int, Supplier), where the supplier is used to generate a set of vertices which is reused for any generated graph.

        Parameters:
        edgeSupplier - the edge supplier

      • setEdges

        public void setEdges​(BiFunction<V,​V,​E> edgeBuilder)
        Set the edge builder function of the generated graph(s).

        The function will be called for any edge created, for any graph generated. This behavior is different from setVertices(int, Supplier), where the supplier is used to generate a set of vertices which is reused for any generated graph.

        Parameters:
        edgeBuilder - the edge builder function

      • setDirected

        public void setDirected​(boolean directed)
        Determine if the generated graph(s) is directed or undirected.

        By default, the generated graph(s) is undirected.

        Parameters:
        directed - true if the generated graph(s) will be directed, false if undirected

      • setSelfEdges

        public void setSelfEdges​(boolean selfEdges)
        Determine if the generated graph(s) will contain self-loops.

        By default, the generated graph(s) will not contain self-loops.

        Parameters:
        selfEdges - true if the generated graph(s) will contain self-loops, false otherwise

      • setEdgeProbability

        public void setEdgeProbability​(double p)
        Set the probability each edge will exists in the generated graph(s).

        First the set of vertices is determined. Then, for each pair of vertices, an edge is created with probability \(p\). If the graph is directed, both directions of the edge are created or not created independently with probability \(p\). If the graph allows self-loops, each vertex is connected to itself with probability \(p\).

        By default, the probability is \(0.1\).

        Parameters:
        p - the probability each edge will exists in the generated graph(s)

      • setSeed

        public void setSeed​(long seed)
        Set the seed of the random number generator used to generate the graph(s).

        By default, a random seed is used. For deterministic behavior, set the seed of the generator.

        Parameters:
        seed - the seed of the random number generator

      • generateIntoBuilder

        public GraphBuilder<V,​E> generateIntoBuilder()
        Description copied from interface: GraphGenerator
        Generates a graph into a builder.

        This is the a more flexible way to generate a graph. The builder can be used to generate a mutable or immutable graph, or to add additional vertices or edges on top of the generated ones.

        Specified by:
        generateIntoBuilder in interface GraphGenerator<V,​E>
        Returns:
        a new graph builder populated by the generator with the generator parameters