Class Bipartite

java.lang.Object

Bipartite

public class Bipartite
extends java.lang.Object

The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. The isBipartite operation determines whether the graph is bipartite. If so, the color operation determines a bipartition; if not, the oddCycle operation determines a cycle with an odd number of edges.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the isBipartite and color operations take constant time; the oddCycle operation takes time proportional to the length of the cycle.

For additional documentation, see Section 4.1 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
Bipartite(Graph G) Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.

Method Summary

Methods

Modifier and Type	Method and Description
boolean	color(int v) Returns the side of the bipartite that vertex v is on.
boolean	isBipartite() Is the graph bipartite?
static void	main(java.lang.String[] args) Unit tests the Bipartite data type.
java.lang.Iterable<java.lang.Integer>	oddCycle() Returns an odd-length cycle if the graph is not bipartite, and null otherwise.

Methods inherited from class java.lang.Object

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

Constructor Detail

Bipartite

public Bipartite(Graph G)

Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.

Parameters:

G - the graph

Method Detail

isBipartite

public boolean isBipartite()

Is the graph bipartite?

Returns:

true if the graph is bipartite, false otherwise

color

public boolean color(int v)

Returns the side of the bipartite that vertex v is on. param v the vertex

Returns:

the side of the bipartition that vertex v is on; two vertices are in the same side of the bipartition if and only if they have the same color

Throws:

java.lang.UnsupportedOperationException - if this method is called when the graph is not bipartite

oddCycle

public java.lang.Iterable<java.lang.Integer> oddCycle()

Returns an odd-length cycle if the graph is not bipartite, and null otherwise.

Returns:

an odd-length cycle (as an iterable) if the graph is not bipartite (and hence has an odd-length cycle), and null otherwise

main

public static void main(java.lang.String[] args)

Unit tests the Bipartite data type.