Package com.jgalgo.gen

Class RecursiveMatrixGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class RecursiveMatrixGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generates a random graph using the R-MAT model.

    The R-MAT model generates a graph by recursively partitioning the adjacency matrix into four quadrants and assigning edges to each quadrant with different probabilities \((a,b,c,d)\). The generator accept as an input how many edges to generate, and it generate them one by one: each edge is assigned to a quadrant according to the probabilities \((a,b,c,d)\), and then the quadrant is recursively partitioned until a single cell is reached. The cell is then assigned the edge. The process is repeated until the required number of edges is generated. Except the vertices set and the number of edges to generate, the model has four parameters: the probabilities \((a,b,c,d)\). The generated graphs may be either directed or undirected, but parallel edges are never created.

    The probabilities \((a,b,c,d)\) must be in \([0,1]\) and sum to \(1\). If the graph is undirected, the probabilities \(b\) and \(c\) must be equal. By default, the values of \((a,b,c,d)\) are \((0.57,0.21,0.17,0.05)\) for directed graphs and \((0.57,0.19,0.19,0.05)\) for undirected graphs. The generator will generate undirected graphs by default.

    In the following example, a graph with \(9\) vertices and \(23\) edges is generated using the R-MAT model. The probabilities \((a,b,c,d)\) are \((0.52,0.26,0.17,0.5)\), and the seed of the random number generator is set to some fixed value to get deterministic behavior. 

     
 Graph<Integer, Integer> g = new RecursiveMatrixGraphGenerator<>(IntGraphFactory.directed())
 		.directed(true)
 		.vertices(9)
 		.edges(23)
 		.edgeProbabilities(0.52, 0.26, 0.17, 0.5)
 		.seed(0x7d0c16fa09e05751L)
 		.generate();

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

    Based on 'R-MAT: A Recursive Model for Graph Mining' by Chakrabarti et al.

    Author:
    Barak Ugav

    • Constructor Detail

      • RecursiveMatrixGraphGenerator

        public RecursiveMatrixGraphGenerator()
        Create a new R-MAT 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).

      • RecursiveMatrixGraphGenerator

        public RecursiveMatrixGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new R-MAT generator that will use the given graph factory.

        If the factory has vertex and/or edge builders, they will be used to generate the vertices and edges of the generated graph(s) if only the number of vertices or edges is set using vertices(int) or edges(int).

        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. The method GraphFactory.allowSelfEdges() is always 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. The vertex and edge builders will be used to generate the vertices and edges of the generated graph(s) if only the number of vertices or edges is set using vertices(int) or edges(int). Set the vertex/edge builder of the factory to use these functions.

        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. The method GraphFactory.allowSelfEdges() is always called.

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

      • vertices

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

      • edgeProbabilities

        public RecursiveMatrixGraphGenerator<V,​E> edgeProbabilities​(double a,
                                                                  double b,
                                                                  double c,
                                                                  double d)
        Set the edge probabilities of the generated graph(s).

        The generator accept as an input how many edges to generate, and it generate them one by one: each edge is assigned to a quadrant according to the probabilities \((a,b,c,d)\), and then the quadrant is recursively partitioned until a single cell is reached. The cell is then assigned the edge. The process is repeated until the required number of edges is generated.

        The probabilities \((a,b,c,d)\) are corresponding to the four quadrants of the adjacency matrix, and they must be in \([0,1]\) and sum to \(1\). If the graph is undirected, the probabilities \(b\) and \(c\) must be equal. By default, the values of \((a,b,c,d)\) are \((0.57,0.21,0.17,0.05)\) for directed graphs and \((0.57,0.19,0.19,0.05)\) for undirected graphs.

        Parameters:
        a - the probability of the edge to be in the first quadrant
        b - the probability of the edge to be in the second quadrant
        c - the probability of the edge to be in the third quadrant
        d - the probability of the edge to be in the fourth quadrant
        Returns:
        this generator
        Throws:
        IllegalArgumentException - if the probabilities are not in the range \([0,1]\) or do not sum to \(1\)

      • seed

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