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

BipartiteX(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
BipartiteX data type. 
Iterable<Integer> 
oddCycle()
Returns an oddlength cycle if the graph is not bipartite, and
null otherwise. 
public BipartiteX(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)
BipartiteX
data type.args
 the commandline arguments