Package com.jgalgo.gen

Class CompleteBipartiteGraphGenerator<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Implemented Interfaces:
    GraphGenerator<V,​E>
    public class CompleteBipartiteGraphGenerator<V,​E>
extends Object
implements GraphGenerator<V,​E>
    Generates a complete bipartite 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. A complete bipartite graph is a bipartite graph in which each pair of left and right vertices is connected by an edge.

    Both undirected and directed graphs can be generated. If the graph is directed, there are three options for the generated edges between each pair of left and right vertices: generate two edges in both directions, generate one edge from the left vertex to the right vertex, or generate one edge from the right vertex to the left vertex. 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).

    In the following example, a complete bipartite graph with four left and six right vertices is generated: 

     
 Graph<Integer, Integer> g = new CompleteBipartiteGraphGenerator<>(IntGraphFactory.directed())
 		.directedAll()
 		.vertices(4, 6)
 		.edges(IdBuilderInt.defaultBuilder())
 		.generate();

    By default, the generated graph(s) is undirected. Self and parallel edges are never created.

    This generator is the bipartite version of CompleteGraphGenerator.

    Author:
    Barak Ugav
    See Also:
    BipartiteGraphs

    • Constructor Detail

      • CompleteBipartiteGraphGenerator

        public CompleteBipartiteGraphGenerator()
        Create a new complete bipartite graph generator that will use the default graph factory.

        The default graph factory does not have vertex builder, so if only the number of vertices is set using vertices(int, int), the vertex builder must be set explicitly using graphFactory().setVertexBuilder(...). Same holds for edges, for which the number of them is determine by the number of vertices and the direction of the generated edges. Alternatively, the methods vertices(int, int, IdBuilder) and edges(IdBuilder) can be used to set the number of vertices 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).

      • CompleteBipartiteGraphGenerator

        public CompleteBipartiteGraphGenerator​(GraphFactory<V,​E> factory)
        Create a new complete bipartite graph generator that will use the given graph factory.

        If the factory has a vertex builder it will be used to generate the vertices of the generated graph(s) if only the number of vertices is set using vertices(int, int). If the factory has an edge builder it will be used to generate the edges of the generated graph(s) if it will not be overridden by edges(IdBuilder).

        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.

        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. If the factory has a vertex builder it will be used to generate the vertices of the generated graph(s) if only the number of vertices is set using vertices(int, int). If the factory has an edge builder it will be used to generate the edges of the generated graph(s) if it will not be overridden by edges(IdBuilder).

        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.

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

      • vertices

        public CompleteBipartiteGraphGenerator<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 CompleteBipartiteGraphGenerator<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 CompleteBipartiteGraphGenerator<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 CompleteBipartiteGraphGenerator<V,​E> edges​(IdBuilder<E> edgeBuilder)
        Set the edge builder that will be used to generate edges.

        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. If this method is not called, or called with a null argument, the edge builder of the graph factory will be used. If the graph factory does not have an edge builder, an exception will be thrown during generation.

        Parameters:
        edgeBuilder - the edge builder, or null to use the edge builder of the graph factory
        Returns:
        this generator

      • undirected

        public CompleteBipartiteGraphGenerator<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, all a single edge will be generated for each pair of left and right vertices. The number of edges will be \(|U| \cdot |V|\).

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

        Returns:
        this generator
        See Also:
        directedAll(), directedLeftToRight(), directedRightToLeft()

      • directedAll

        public CompleteBipartiteGraphGenerator<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 all edges from the left vertices set to the right vertices set will be generated, and also from the right vertices set to the left vertices set. The number of edges will be \(2 \cdot |U| \cdot |V|\).

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

        Returns:
        this generator
        See Also:
        undirected(), directedLeftToRight(), directedRightToLeft()

      • directedLeftToRight

        public CompleteBipartiteGraphGenerator<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 all edges will be directed from the left vertices set to the right vertices set. The number of edges will be \(|U| \cdot |V|\).

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

        Returns:
        this generator
        See Also:
        undirected(), directedAll(), directedRightToLeft()

      • directedRightToLeft

        public CompleteBipartiteGraphGenerator<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 all edges will be directed from the right vertices set to the left vertices set. The number of edges will be \(|U| \cdot |V|\).

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

        Returns:
        this generator
        See Also:
        undirected(), directedAll(), directedLeftToRight()

      • 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