Class GnmRandomBipartiteGraphGenerator<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type
    All Implemented Interfaces:
    GraphGenerator<V,​E,​V>

    public class GnmRandomBipartiteGraphGenerator<V,​E>
    extends java.lang.Object
    implements GraphGenerator<V,​E,​V>
    Create a random bipartite graph based on the $G(n, M)$ Erdős–Rényi model. See the Wikipedia article for details and references about Random Graphs and the Erdős–Rényi model . The user provides the sizes $n_1$ and $n_2$ of the two partitions $(n_1+n_2=n)$ and a number $m$ which is the total number of edges to create. The generator supports both directed and undirected graphs.
    Author:
    Michael Behrisch, Dimitrios Michail
    See Also:
    GnpRandomBipartiteGraphGenerator
    • Constructor Detail

      • GnmRandomBipartiteGraphGenerator

        public GnmRandomBipartiteGraphGenerator​(int n1,
                                                int n2,
                                                int m)
        Create a new random bipartite graph generator. The generator uses the $G(n, m)$ model when $n = n1 + n2$ and the bipartite graph has one partition with size $n_1$ and one partition with size $n_2$. In this model a graph is chosen uniformly at random from the collection of bipartite graphs whose partitions have sizes $n_1$ and $n_2$ respectively and $m$ edges.
        Parameters:
        n1 - number of vertices of the first partition
        n2 - number of vertices of the second partition
        m - the number of edges
      • GnmRandomBipartiteGraphGenerator

        public GnmRandomBipartiteGraphGenerator​(int n1,
                                                int n2,
                                                int m,
                                                long seed)
        Create a new random bipartite graph generator. The generator uses the $G(n, m)$ model when $n = n1 + n2$ and the bipartite graph has one partition with size $n_1$ and one partition with size $n_2$. In this model a graph is chosen uniformly at random from the collection of bipartite graphs whose partitions have sizes $n_1$ and $n_2$ respectively and m edges.
        Parameters:
        n1 - number of vertices of the first partition
        n2 - number of vertices of the second partition
        m - the number of edges
        seed - seed for the random number generator
      • GnmRandomBipartiteGraphGenerator

        public GnmRandomBipartiteGraphGenerator​(int n1,
                                                int n2,
                                                int m,
                                                java.util.Random rng)
        Create a new random bipartite graph generator. The generator uses the $G(n, m)$ model when $n = n_1 + n_2$ and the bipartite graph has one partition with size $n_1$ and one partition with size $n_2$. In this model a graph is chosen uniformly at random from the collection of bipartite graphs whose partitions have sizes $n_1$ and $n_2$ respectively and $m$ edges.
        Parameters:
        n1 - number of vertices of the first partition
        n2 - number of vertices of the second partition
        m - the number of edges
        rng - random number generator
    • Method Detail

      • generateGraph

        public void generateGraph​(Graph<V,​E> target,
                                  java.util.Map<java.lang.String,​V> resultMap)
        Generates a random bipartite graph.
        Specified by:
        generateGraph in interface GraphGenerator<V,​E,​V>
        Parameters:
        target - the target graph
        resultMap - not used by this generator, can be null
      • getFirstPartition

        public java.util.Set<V> getFirstPartition()
        Returns the first partition of vertices in the bipartite graph. This partition is guaranteed to be smaller than or equal in size to the second partition.
        Returns:
        one partition of the bipartite graph
      • getSecondPartition

        public java.util.Set<V> getSecondPartition()
        Returns the second partitions of vertices in the bipartite graph. This partition is guaranteed to be larger than or equal in size to the first partition.
        Returns:
        one partition of the bipartite graph