y.algo
Class Bipartitions

java.lang.Object
  y.algo.Bipartitions

public class Bipartitions
extends Object

Responsible for graph bipartition problems.

A bipartite graph is a graph whose node set can be partitioned into two sets in such a way that all edges in the graph connect nodes that belong to different partitions. In other words, there are no edges connecting nodes that belong to the same partition.

Field Summary

static Object	BLUE Marker for a node that belongs to the blue partition
static Object	RED Marker for a node that belongs to the red partition

Constructor Summary

Bipartitions()

Method Summary

static boolean	getBipartition(Graph graph, NodeMap markMap) Calculates a bipartition of the given graph if one exists.
static boolean	isBipartite(Graph graph) Tests 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 Object RED

Marker for a node that belongs to the red partition

BLUE

public static final Object BLUE

Marker for a node that belongs to the blue partition

Constructor Detail

Bipartitions

public Bipartitions()

Method Detail

isBipartite

public static boolean isBipartite(Graph graph)

Tests whether or not the given graph is bipartite.

Complexity:

O(nodeCount()+edgeCount())

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 put in the given node map, depending on the partition the node belongs to.

Returns:

isBipartite(graph)

Complexity:

O(nodeCount()+edgeCount())