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.

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

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

    Author:
    Barak Ugav

    • Method Detail

      • newInstance

        public static <V,​E> RecursiveMatrixGraphGenerator<V,​E> newInstance()
        Creates a new R-MAT generator.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Returns:
        a new R-MAT generator

      • setVertices

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

        If the generator is used to generate multiple graphs, the same vertices set is 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​(int m,
                     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:
        m - the number of edges to generate
        edgeSupplier - the edge supplier

      • setEdges

        public void setEdges​(int m,
                     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:
        m - the number of edges to generate
        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

      • setEdgeProbabilities

        public void setEdgeProbabilities​(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

      • 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