Package com.jgalgo.gen

Class GnmGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class GnmGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generates a uniformly random graph among all graphs with \(n\) vertices and \(m\) edges.

    The generator uses the \(G(n,m)\) model to generate a uniformly random graph among all graphs with \(n\) vertices and \(m\) edges. Both directed and undirected graphs are supported, as well as self-edges and parallel-edges. By default, the generated graph(s) is undirected, does not contain self-edges and may contain parallel-edges.

    A GraphFactory is used to create the generated graph(s). The factory can be set in the constructor, or a default one will be used, which is still available for customization using graphFactory(). Vertices and edges can either be provided explicitly, or the number of vertices/edges is passed and they are generated using a vertex/edge builder. The vertex and edge builders can be set when the number of vertices or edges is set using vertices(int, IdBuilder) or edges(int, IdBuilder), or the builders of the graph factory will be used. Note that the default graph factory does not have default vertex and edge builders, unless set explicitly. The IntGraph factory does have these builders by default, pass an instance of it to the constructor to use it (and to generate int graphs).

    In the following example, a graph with ten vertices and fourteen edges is generated. The graph is directed, contains self-edges and does not contain parallel-edges. The seed of the generator is set to ensure deterministic behavior. 

     
 Graph<Integer, Integer> g = new GnmGraphGenerator<>(IntGraphFactory.directed())
 		.directed(true)
 		.vertices(10)
 		.edges(14)
 		.selfEdges(true)
 		.parallelEdges(false)
 		.seed(0x7d0c16fa09e05751L)
 		.generate();

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

    Author:
    Barak Ugav

    • Constructor Detail

      • GnmGraphGenerator

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

        The default graph factory does not have default vertex and edge builders, so if only the number of vertices and edges is set using vertices(int) and edges(int), the vertex and edge builders must be set explicitly using graphFactory().setVertexBuilder(...) and graphFactory().setEdgeBuilder(...). Alternatively, the methods vertices(int, IdBuilder) and edges(int, IdBuilder) can be used to set the number of vertices and edges and provide a vertex/edge builder that will override the (maybe non existing) vertex/edge builder of the graph factory. The vertex set can also be set explicitly using vertices(Collection).

    • Method Detail

      • vertices

        public GnmGraphGenerator<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 GnmGraphGenerator<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 GnmGraphGenerator<V,​E> edges​(int edgesNum)
        Set the number of edges what will be generated for each graph.

        The number of edges must be non-negative, and if parallel edges are not allowed, it must be at most \(n(n-1) / 2\) for undirected graphs and \(n(n-1)\) for directed graphs, with addition of \(n\) self-edges if self-edges are allowed.

        The edges will be generated using the edge builder of the graph factory, see GraphFactory.setEdgeBuilder(IdBuilder). The default graph factory does not have an edge 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 edges(int, IdBuilder) which set the number of edges and provide an edge builder that will override the (maybe non existing) edge builder of the graph factory. The generation will happen independently for each graph generated. If there is no edge builder, an exception will be thrown during generation. This method override all previous calls to edges(int) or edges(int, IdBuilder).

        Parameters:
        edgesNum - the number of edges
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if edgesNum is negative

      • edges

        public GnmGraphGenerator<V,​E> edges​(int edgesNum,
                                          IdBuilder<E> edgeBuilder)
        Set the number of edges what will be generated for each graph, and the edge builder that will be used to generate them.

        The number of edges must be non-negative, and if parallel edges are not allowed, it must be at most \(n(n-1) / 2\) for undirected graphs and \(n(n-1)\) for directed graphs, with addition of \(n\) self-edges if self-edges are allowed.

        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. This method override all previous calls to edges(int) or edges(int, IdBuilder).

        Parameters:
        edgesNum - the number of edges
        edgeBuilder - the edge builder, or null to use the edge builder of the graph factory
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if edgesNum is negative

      • directed

        public GnmGraphGenerator<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 GnmGraphGenerator<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

      • parallelEdges

        public GnmGraphGenerator<V,​E> parallelEdges​(boolean parallelEdges)
        Determine if the generated graph(s) will contain parallel-edges.

        Parallel edges are a set of edges that connect the same two vertices. By default, the generated graph(s) will contain parallel-edges.

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

      • seed

        public GnmGraphGenerator<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