Package com.jgalgo.gen

Class GnmBipartiteGraphGenerator<V,E>

java.lang.Object
com.jgalgo.gen.GnmBipartiteGraphGenerator<V,E>
Type Parameters:
V - the vertices type
E - the edges type
All Implemented Interfaces:
GraphGenerator<V,E>
public class GnmBipartiteGraphGenerator<V,E> extends Object implements GraphGenerator<V,E>
Generates a uniformly random bipartite graph among all graphs with \(n\) vertices and \(m\) edges.

A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. The generator uses the \(G(n_1,n_2,m)\) model to generate a uniformly random bipartite graph among all graphs with \(n_1\) left vertices, \(n_2\) right vertices and \(m\) edges.

Both undirected and directed graphs can be generated. If the graph is directed, there are three options for the considered edges between each pair of left and right vertices: edges in both directions, edge(s) from the left vertex to the right vertex, or edge(s) from the right vertex to the left vertex. If no parallel edges are generated (parallelEdges(boolean)) than at most a single edge is generated from the left to right vertex, and another one from right to left. See directedAll(), directedLeftToRight() and directedRightToLeft() for more details.

The generated graph(s) will have vertex boolean weights with key BipartiteGraphs.VertexBiPartitionWeightKey which is the partition of the vertices into the left and right set of vertices. The weight is set to true for vertices in the left set, and false for vertices in the right set. The VertexBiPartition can be created later using BipartiteGraphs.getExistingPartition(Graph).

By default, the generated graph(s) will be undirected without parallel edges. Self edges are never generated.

In the following example, a bipartite graph with four left vertices and six right vertices is generated. The graph will have ten edges, and will be undirected without parallel edges. The seed of the generator is set to ensure deterministic behavior. 

 
 Graph<Integer, Integer> g = new GnmBipartiteGraphGenerator<>(IntGraphFactory.undirected())
 		.undirected()
 		.vertices(4, 6)
 		.edges(10)
 		.parallelEdges(false)
 		.seed(0x7d0c16fa09e05751L)
 		.generate();

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

This generator is the bipartite version of GnmGraphGenerator.

Author:
Barak Ugav
See Also:

  • Constructor Details

    • GnmBipartiteGraphGenerator

      public GnmBipartiteGraphGenerator()
      Create a new \(G(n_1,n_2,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, int) and edges(int), the vertex and edge builders must be set explicitly using graphFactory().setVertexBuilder(...) and graphFactory().setEdgeBuilder(...). Alternatively, the methods vertices(int, 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, Collection).

    • GnmBipartiteGraphGenerator

      public GnmBipartiteGraphGenerator(GraphFactory<V,E> factory)
      Create a new \(G(n_1,n_2,m)\) 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, 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. If parallel edges are generated (see parallelEdges(boolean)), the method GraphFactory.allowParallelEdges() will also be 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 Details

    • 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, 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. If parallel edges are generated (see parallelEdges(boolean)), the method GraphFactory.allowParallelEdges() will also be called.

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

    • vertices

      public GnmBipartiteGraphGenerator<V,E> vertices(Collection<? extends V> leftVertices, Collection<? extends V> rightVertices)
      Set the vertices of the generated graph(s).

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. This method sets these two sets.

      If the generator is used to generate multiple graphs, the same vertex sets will be used for all of them. This method override all previous calls to any of vertices(Collection, Collection), vertices(int, int) or vertices(int, int, IdBuilder).

      Parameters:
      leftVertices - the set of left vertices of the generated graph(s)
      rightVertices - the set of right vertices of the generated graph(s)
      Returns:
      this generator

    • vertices

      public GnmBipartiteGraphGenerator<V,E> vertices(int leftVerticesNum, int rightVerticesNum)
      Set the number of vertices that will be generated for each graph.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. This method sets these two sets.

      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, 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, Collection), vertices(int, int) or vertices(int, int, IdBuilder).

      Parameters:
      leftVerticesNum - the number of vertices that will be generated in the left set for each graph
      rightVerticesNum - the number of vertices that will be generated in the right set for each graph
      Returns:
      this generator
      Throws:
      IllegalArgumentException - if leftVerticesNum or rightVerticesNum are negative

    • vertices

      public GnmBipartiteGraphGenerator<V,E> vertices(int leftVerticesNum, int rightVerticesNum, 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.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. This method sets these two sets.

      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, Collection), vertices(int, int) or vertices(int, int, IdBuilder).

      Parameters:
      leftVerticesNum - the number of vertices that will be generated in the left set for each graph
      rightVerticesNum - the number of vertices that will be generated in the right set for each graph
      vertexBuilder - the vertex builder, or null to use the vertex builder of the graph factory
      Returns:
      this generator
      Throws:
      IllegalArgumentException - if leftVerticesNum or rightVerticesNum are negative

    • edges

      public GnmBipartiteGraphGenerator<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_1 \cdot n_2\) for undirected graphs and directed graphs in which only one direction is allowed (left to right, or right to left), and at most \(2 \cdot n_1 \cdot n_2\) for directed graphs in which both directions are allowed (all directions).

      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 GnmBipartiteGraphGenerator<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_1 \cdot n_2\) for undirected graphs and directed graphs in which only one direction is allowed (left to right, or right to left), and at most \(2 \cdot n_1 \cdot n_2\) for directed graphs in which both directions are allowed (all directions).

      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

    • undirected

      public GnmBipartiteGraphGenerator<V,E> undirected()
      Sets the generated graph(s) to be undirected.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. Calling this method will cause the generated graph(s) to be undirected, and a single edge between each pair of left and right vertices will considered and generated with probability \(p\). The maximum number of edges will be \(|U| \cdot |V|\).

      By default, the generated graph(s) is undirected.

      Returns:
      this generator
      See Also:

    • directedAll

      public GnmBipartiteGraphGenerator<V,E> directedAll()
      Sets the generated graph(s) to be directed with edges in both directions.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. Calling this method will cause the generated graph(s) to be directed, and edges in both directions (from left vertices to right vertices and visa versa) may be generated. In case parallel edges are not allowed, the maximum number of edges will be \(2 \cdot |U| \cdot |V|\).

      By default, the generated graph(s) is undirected.

      Returns:
      this generator
      See Also:

    • directedLeftToRight

      public GnmBipartiteGraphGenerator<V,E> directedLeftToRight()
      Sets the generated graph(s) to be directed with edges from left to right.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. Calling this method will cause the generated graph(s) to be directed, and only edges from left vertices to right vertices may be generated. In case parallel edges are not allowed, the maximum number of edges will be \(|U| \cdot |V|\).

      By default, the generated graph(s) is undirected.

      Returns:
      this generator
      See Also:

    • directedRightToLeft

      public GnmBipartiteGraphGenerator<V,E> directedRightToLeft()
      Sets the generated graph(s) to be directed with edges from right to left.

      A bipartite graph is a graph whose vertices can be divided into two disjoint sets \(U\) and \(V\) such that every edge connects a vertex in \(U\) to one in \(V\). The two sets are usually called the left and right vertices. Calling this method will cause the generated graph(s) to be directed, and only edges from right vertices to left vertices may be generated. In case parallel edges are not allowed, the maximum number of edges will be \(|U| \cdot |V|\).

      By default, the generated graph(s) is undirected.

      Returns:
      this generator
      See Also:

    • parallelEdges

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