Bipartite (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.Bipartite

```
public class Bipartite
extends Object
```
The Bipartite class represents a data type for determining whether an undirected graph is bipartite or whether it has an odd-length cycle. A graph is bipartite if and only if it has no 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 Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the graph). See BipartiteX for a nonrecursive version that uses breadth-first search.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors
Constructor Description

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

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method	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(String[] args)`	Unit tests the `Bipartite` data type.
`Iterable<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, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - Bipartite
```
public Bipartite(Graph graph)
```
    Determines whether an undirected graph is bipartite and finds either a bipartition or an odd-length cycle.
    
    Parameters:
    
    graph - 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:
    
    IllegalArgumentException - unless 0 <= v < V
    
    UnsupportedOperationException - if this method is called when the graph is not bipartite
  - oddCycle
```
public Iterable<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(String[] args)
```
    Unit tests the Bipartite data type.
    
    Parameters:
    
    args - the command-line arguments