Package com.jgalgo.alg.bipartite

Class BipartiteGraphs

java.lang.Object
com.jgalgo.alg.bipartite.BipartiteGraphs
public class BipartiteGraphs extends Object
Static class with functions for bipartite graphs.

A bipartite graph is a graph in which the vertices can be partitioned into two sets \(V_1,V_2\) such that 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 is expected to be vertices boolean weights 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 vertices boolean weights 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 vertices weights, and if it does exists, assume the graph is bipartite and use the partition. If the graph is modified after the bipartite partition was computed and added, it might be invalid, so consider removing the vertices weights to avoid misleading algorithms.

Author:
Barak Ugav

  • Field Details

    • 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 vertices weights with this key. When an algorithm accept a graph to operate on, it may check for such vertices weights, and if they exists it may assume the graph is bipartite and use them.

      If a graph contains vertices 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 vertices weights were added. Consider removing the vertices weights to avoid misleading algorithms.

      See Also:

  • Method Details

    • 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 vertices 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 vertices weights. To add the partition as vertices weights, use findPartition(Graph, boolean).

      If an IntGraph is passed as an argument, an optional of IVertexBiPartition will be returned.

      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 addPartitionWeights)
      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, an optional of IVertexBiPartition will be returned.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - the graph
      addPartitionWeights - if true, add the partition (if exist) will be added to the graph as vertices weights. If no valid bipartite partition is found, the graph will not be modified. If vertices 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 addPartitionWeights is true and the graph already has a non boolean vertices 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 from the vertices weights.

      If a bipartite partition was computed on the graph and boolean vertices 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, an optional of IVertexBiPartition will be returned.

      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 vertices weights with key VertexBiPartitionWeightKey

    • getExistingPartition

      public static Optional<IVertexBiPartition> getExistingPartition(IntGraph g)
      Get the existing bipartite partition of the given IntGraph from the vertices weights.

      If a bipartite partition was computed on the graph and boolean vertices 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 vertices weights with key VertexBiPartitionWeightKey