Package com.jgalgo.alg

Class BipartiteGraphs

  • public class BipartiteGraphs
extends Object
    Static class for bipartite graphs.

    A bipartite graph is a graph in which the vertices can be partitioned into two sets V1,V2 and there are no edges between two vertices u,v if they are both in V1 or both in V2. Some algorithms expect a bipartite graph as an input, and the partition V1,V2 is expected to be a vertex boolean weight keyed by VertexBiPartitionWeightKey. See the static field documentation for more details.

    This class provides functions to check whether a graph is bipartite, and to find a bipartite partition of a graph. These functions can add the bipartite partition as a vertex boolean weight as an option, but the default is to treat the graph as immutable.

    Note that algorithms might test for the existent of a bipartite partition as vertex weights, and if it does exists, to assume the graph is bipartite and use it. If the graph is modified after the bipartite partition was computed and added, it might be invalid, so consider removing the vertex weights to avoid misleading algorithms.

    Author:
    Barak Ugav

    • Field Detail

      • VertexBiPartitionWeightKey

        public static final String VertexBiPartitionWeightKey
        The vertices weight key of the bipartite property.

        The bipartite partition is usually represented as a vertex boolean weight keyed by this key. The weight of each vertex indicates to which of the two partitions it belongs to. Functions such as findPartition(Graph, boolean) may attempt to find a valid bipartition of a graph, and if one is found, to store it as vertex weights with this key. When an algorithm accept a graph to operate on, it may check for such vertex weights, and if they exists it may assume the graph is bipartite and use them.

        If a graph contains vertex weights with this key, the partition can be retrieved by getExistingPartition(Graph). But note that a bipartite partition may become invalid if the graph is modified after the vertex weights were added. Consider removing the vertex weights to avoid misleading algorithms.

        See Also:
        Constant Field Values

    • Method Detail

      • isBipartite

        public static <V,​E> boolean isBipartite​(Graph<V,​E> g)
        Check whether the given graph is bipartite or not.

        If the computed partition is needed, use findPartition(Graph). This function does not have any side effects on the graph object itself, namely it does not add the partition (if one exist) as vertex weights.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        Returns:
        true if the graph is bipartite, false otherwise

      • findPartition

        public static <V,​E> Optional<VertexBiPartition<V,​E>> findPartition​(Graph<V,​E> g)
        Find a bipartite partition of the given graph (if one exists).

        This function does not have any side effects on the graph object itself, namely it does not add the partition (if one exist) as vertex weights. To add the partition as vertex weights, use findPartition(Graph, boolean).

        If an IntGraph is passed as an argument, IVertexBiPartition will be returned (if a partition exist).

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        Returns:
        the bipartite partition of the graph if one exists

      • findPartition

        public static <V,​E> Optional<VertexBiPartition<V,​E>> findPartition​(Graph<V,​E> g,
                                                                               boolean addPartitionWeight)
        Find a bipartite partition of the given graph (if one exists), and optionally add the partition as vertex weights.

        If an IntGraph is passed as an argument, IVertexBiPartition will be returned (if a partition exist).

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        addPartitionWeight - if true, add the partition (if exist) will be added to the graph as vertex weights. If no valid bipartite partition is found, the graph will not be modified. If vertex weights already exists in the graph with the key VertexBiPartitionWeightKey, they will be used as the partition.
        Returns:
        the bipartite partition of the graph if one exists
        Throws:
        IllegalArgumentException - if addPartitionWeight is true and the graph already has a non boolean vertex weights with key VertexBiPartitionWeightKey

      • getExistingPartition

        public static <V,​E> Optional<VertexBiPartition<V,​E>> getExistingPartition​(Graph<V,​E> g)
        Get the existing bipartite partition of the given graph (if one exists).

        If a bipartite partition was computed on the graph and boolean vertex weights were added to it, the partition will be returned. Otherwise, an empty optional will be returned. This function does not compute a partition if it doesn't find an existing one.

        Note that if the graph was modified after the bipartite partition was computed and added, it might be invalid and no checks are performed in this function to verify that it is still valid.

        If an IntGraph is passed as an argument, IVertexBiPartition will be returned (if a partition exist).

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        Returns:
        the bipartite partition of the graph if one exists
        Throws:
        IllegalArgumentException - if the graph has a non boolean vertex weights with key VertexBiPartitionWeightKey

      • getExistingPartition

        public static Optional<IVertexBiPartition> getExistingPartition​(IntGraph g)
        Get the existing bipartite partition of the given IntGraph (if one exists).

        If a bipartite partition was computed on the graph and boolean vertex weights were added to it, the partition will be returned. Otherwise, an empty optional will be returned. This function does not compute a partition if it doesn't find an existing one.

        Note that if the graph was modified after the bipartite partition was computed and added, it might be invalid and no checks are performed in this function to verify that it is still valid.

        Parameters:
        g - the graph
        Returns:
        the bipartite partition of the graph if one exists
        Throws:
        IllegalArgumentException - if the graph has a non boolean vertex weights with key VertexBiPartitionWeightKey