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 Summary

Fields

Modifier and Type	Field	Description
static String	VertexBiPartitionWeightKey	The vertices weight key of the bipartite property.

Method Summary

Modifier and Type	Method	Description
static <V,E> Optional<VertexBiPartition<V,E>>	findPartition(Graph<V,E> g)	Find a bipartite partition of the given graph (if one exists).
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.
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.
static Optional<IVertexBiPartition>	getExistingPartition(IntGraph g)	Get the existing bipartite partition of the given IntGraph from the vertices weights.
static <V,E> boolean	isBipartite(Graph<V,E> g)	Check whether the given graph is bipartite or not.

Methods inherited from class java.lang.Object

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

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 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:

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