public class Bipartite extends Object
Bipartite
class represents a data type for
determining whether an undirected graph is bipartite or whether
it has an oddlength cycle.
A graph is bipartite if and only if it has no oddlength 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 depthfirst 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 breadthfirst
search.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description 

Bipartite(Graph G)
Determines whether an undirected graph is bipartite and finds either a
bipartition or an oddlength cycle.

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(String[] args)
Unit tests the
Bipartite data type. 
Iterable<Integer> 
oddCycle()
Returns an oddlength cycle if the graph is not bipartite, and
null otherwise. 
public Bipartite(Graph G)
G
 the graphpublic boolean isBipartite()
true
if the graph is bipartite; false
otherwisepublic boolean color(int v)
v
is on.v
 the vertexv
is on; two vertices
are in the same side of the bipartition if and only if they have the
same colorIllegalArgumentException
 unless 0 <= v < V
UnsupportedOperationException
 if this method is called when the graph
is not bipartitepublic Iterable<Integer> oddCycle()
null
otherwise.null
otherwisepublic static void main(String[] args)
Bipartite
data type.args
 the commandline arguments