public class BipartiteX extends Object
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 and Description |
---|
BipartiteX(Graph G)
Determines whether an undirected graph is bipartite and finds either a
bipartition or an odd-length 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 odd-length 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 command-line arguments