Module org.jgrapht.core
Package org.jgrapht.generate

Class GnmRandomBipartiteGraphGenerator<V,​E>

java.lang.Object
org.jgrapht.generate.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 Summary

    Constructors 
    Constructor Description
    GnmRandomBipartiteGraphGenerator​(int n1, int n2, int m)
    Create a new random bipartite graph generator.
    GnmRandomBipartiteGraphGenerator​(int n1, int n2, int m, long seed)
    Create a new random bipartite graph generator.
    GnmRandomBipartiteGraphGenerator​(int n1, int n2, int m, java.util.Random rng)
    Create a new random bipartite graph generator.

  • Method Summary

    Modifier and Type Method Description
    void generateGraph​(Graph<V,​E> target, java.util.Map<java.lang.String,​V> resultMap)
    Generates a random bipartite graph.
    java.util.Set<V> getFirstPartition()
    Returns the first partition of vertices in the bipartite graph.
    java.util.Set<V> getSecondPartition()
    Returns the second partitions of vertices in the bipartite graph.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    Methods inherited from interface org.jgrapht.generate.GraphGenerator

    generateGraph

  • Constructor Details

    • 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 Details

    • 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