edu.princeton.cs.algs4

Class BipartiteX

java.lang.Object

edu.princeton.cs.algs4.BipartiteX

public class BipartiteX
extends java.lang.Object

The BipartiteX 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 breadth-first search and is nonrecursive. 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. See Bipartite for a recursive version that uses depth-first search.

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

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
boolean	color(int v) Returns the side of the bipartite that vertex v is on.
boolean	isBipartite() Returns true if the graph is bipartite.
static void	main(java.lang.String[] args) Unit tests the BipartiteX 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

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

Constructor Detail

BipartiteX

public BipartiteX(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()

Returns true if the graph is 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.

Parameters:

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.IllegalArgumentException - unless 0 <= v < V

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 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 BipartiteX data type.

Parameters:

args - the command-line arguments