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 in which every edge exists with probability \(p\).

    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-edges. Parallel edges are never created.

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

    In the following example, a graph with nine vertices is generated. Each edge is included in the graph with probability \(0.15\). The graph is directed and self-edges are allowed. The seed of the random number generator is set to some fixed value to get deterministic behavior. 

     
 Graph<Integer, Integer> g = new GnpGraphGenerator<>(IntGraphFactory.directed())
 		.directed(true)
 		.vertices(9)
 		.edgeProbability(0.15)
 		.selfEdges(true)
 		.seed(0x7d0c16fa09e05751L)
 		.generate();

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

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

    Author:
    Barak Ugav

    • Constructor Detail

      • GnpGraphGenerator

        public GnpGraphGenerator()
        Create a new \(G(n,p)\) graph generator that will use the default graph factory.

        The default graph factory does not have vertex builder, so if only the number of vertices is set using vertices(int), the vertex builder must be set explicitly using graphFactory().setVertexBuilder(...). Alternatively, the method vertices(int, IdBuilder) can be used to set the number of vertices and provide a vertex builder that will override the (maybe non existing) vertex builder of the graph factory. The vertex set can also be set explicitly using vertices(Collection). For edges, the number of them is not fixed, therefore an edge builder is mandatory. It can be set using edges(IdBuilder).

      • GnpGraphGenerator

        public GnpGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new \(G(n,p)\) graph generator that will use the given graph factory.

        If the factory has a vertex builder it will be used to generate the vertices of the generated graph(s) if only the number of vertices is set using vertices(int). If the factory has an edge builder it will be used to generate the edges of the generated graph(s) if it will not be overridden by edges(IdBuilder).

        During the graph(s) generation, the method GraphFactory.setDirected(boolean) of the given factory will be called to align the created graph with the generator configuration. If self edges are generated (see selfEdges(boolean)), the method GraphFactory.allowSelfEdges() will also be called.

        To generate int graphs, pass an instance of IntGraphFactory to this constructor.

        Parameters:
        factory - the graph factory that will be used to create the generated graph(s)

    • Method Detail

      • graphFactory

        public GraphFactory<V,​E> graphFactory()
        Get the graph factory that will be used to create the generated graph(s).

        It's possible to customize the factory before generating the graph(s), for example by using GraphFactory.addHint(GraphFactory.Hint) to optimize the generated graph(s) for a specific algorithm. If the factory has a vertex builder it will be used to generate the vertices of the generated graph(s) if only the number of vertices is set using vertices(int). If the factory has an edge builder it will be used to generate the edges of the generated graph(s) if it will not be overridden by edges(IdBuilder).

        During the graph(s) generation, the method GraphFactory.setDirected(boolean) of the given factory will be called to align the created graph with the generator configuration. If self edges are generated (see selfEdges(boolean)), the method GraphFactory.allowSelfEdges() will also be called.

        Returns:
        the graph factory that will be used to create the generated graph(s)

      • vertices

        public GnpGraphGenerator<V,​E> vertices​(int verticesNum)
        Set the number of vertices that will be generated for each graph.

        The vertices will be generated using the vertex builder of the graph factory, see GraphFactory.setVertexBuilder(IdBuilder). The default graph factory does not have a vertex builder, so it must be set explicitly, or IntGraphFactory, which does have such builder, should be passed in the constructor. Another alternative is to use vertices(int, IdBuilder) which set the number of vertices and provide a vertex builder that will override the (maybe non existing) vertex builder of the graph factory. The generation will happen independently for each graph generated. If there is no vertex builder, an exception will be thrown during generation. This method override all previous calls to any of vertices(Collection), vertices(int) or vertices(int, IdBuilder).

        Parameters:
        verticesNum - the number of vertices that will be generated for each graph
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if verticesNum is negative

      • vertices

        public GnpGraphGenerator<V,​E> vertices​(int verticesNum,
                                             IdBuilder<V> vertexBuilder)
        Set the number of vertices that will be generated for each graph, and the vertex builder that will be used to generate them.

        The vertices will be generated using the provided vertex builder, and the vertex generator provided by the graph factory (if exists) will be ignored. The generation will happen independently for each graph generated. This method override all previous calls to any of vertices(Collection), vertices(int) or vertices(int, IdBuilder).

        Parameters:
        verticesNum - the number of vertices that will be generated for each graph
        vertexBuilder - the vertex builder, or null to use the vertex builder of the graph factory
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if verticesNum is negative

      • edges

        public GnpGraphGenerator<V,​E> edges​(IdBuilder<E> edgeBuilder)
        Set the edge builder that will be used to generate edges.

        The edges will be generated using the provided edge builder, and the edge generator provided by the graph factory (if exists) will be ignored. The generation will happen independently for each graph generated. If this method is not called, or called with a null argument, the edge builder of the graph factory will be used. If the graph factory does not have an edge builder, an exception will be thrown during generation.

        Parameters:
        edgeBuilder - the edge builder, or null to use the edge builder of the graph factory
        Returns:
        this generator

      • directed

        public GnpGraphGenerator<V,​E> directed​(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
        Returns:
        this generator

      • selfEdges

        public GnpGraphGenerator<V,​E> selfEdges​(boolean selfEdges)
        Determine if the generated graph(s) will contain self-edges.

        Self edges are edges with the same source and target vertex. By default, the generated graph(s) will not contain self-edges.

        Parameters:
        selfEdges - true if the generated graph(s) will contain self-edges, false otherwise
        Returns:
        this generator

      • edgeProbability

        public GnpGraphGenerator<V,​E> edgeProbability​(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-edges, 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)
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if the probability is not in the range \([0,1]\)

      • seed

        public GnpGraphGenerator<V,​E> seed​(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
        Returns:
        this 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