y.algo
Class Bipartitions

java.lang.Object
  y.algo.Bipartitions

public class Bipartitions
extends java.lang.Object

This class provides methods to determine whether a graph is bipartite and to obtain the corresponding partitions.

A bipartite graph is a graph whose nodes can be partitioned into two sets such that each edges connects two nodes of different sets. In other words, there are no edges connecting nodes that belong to the same partition.

The two sets/partitions are represented by two Object constants i.e., RED or BLUE.

Example of a bipartite graph. Circular and rectangular nodes represent the two partitions.

Field Summary

static java.lang.Object	BLUE A constant for marking a node that belongs to the blue partition.
static java.lang.Object	RED A constant for marking a node that belongs to the red partition.

Method Summary

static boolean	getBipartition(Graph graph, NodeMap markMap) Calculates a bipartition of the given graph, if one exists.
static boolean	isBipartite(Graph graph) Determines whether or not the given graph is bipartite.

Methods inherited from class java.lang.Object

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

Field Detail

RED

public static final java.lang.Object RED

A constant for marking a node that belongs to the red partition.

BLUE

public static final java.lang.Object BLUE

A constant for marking a node that belongs to the blue partition.

Method Detail

isBipartite

public static boolean isBipartite(Graph graph)

Determines whether or not the given graph is bipartite.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the given graph

Returns:

true if the graph is bipartite, false otherwise

getBipartition

public static boolean getBipartition(Graph graph,
                                     NodeMap markMap)

Calculates a bipartition of the given graph, if one exists.

If the graph is bipartite, then for all nodes of the given graph either RED or BLUE objects will be set in the given NodeMap, depending on the partition to which each node belongs.

Complexity:

O(graph.N() + graph.E())

Parameters:

graph - the given graph

markMap - the NodeMap that will be filled during the BFS execution and returns the partition (either RED or BLUE) to which each node belongs

Returns:

true if the graph is bipartite, false otherwise