Class BipartiteX


  • public class BipartiteX
    extends Object
    The BipartiteX 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 breadth-first search and is nonrecursive. The constructor takes Θ(V + E) time in 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 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.

    Author:
    Robert Sedgewick, Kevin Wayne
    • 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:
        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 BipartiteX data type.
        Parameters:
        args - the command-line arguments