/*****************************************************************************
* File: BipartiteVerify.java
* Author: Keith Schwarz (htiek@cs.stanford.edu)
*
* A function for determining whether or not a given graph is bipartite. The
* algorithm works by using a rather famous result about bipartite graphs:
*
* A graph G is bipartite iff it contains no odd cycles.
*
* We can prove this claim as follows. To prove the forward direction, we
* prove the contrapositive; that if G contains an odd cycle, it cannot be
* bipartite. The proof is by contradiction. Suppose that G is bipartite;
* then there is a way of partitioning the nodes in G into two groups A and B
* such that there is no edge between nods in A or nodes in B. Now, let
* C = (v0, v1, v2, ..., v_{2n}, v0) be the odd cycle in G and assume without
* loss of generality that v0 \in A. This means that v1 \in B (since
* otherwise there would be an edge between two nodes in A), and so v2 \in A,
* etc. In general, this means that v_{2i} \in A and v_{2i+1} \in B. But
* there is an edge from v0 to v_{2n}, both of which are in A, contradicting
* that there are no edges between nodes in A or nodes in B, and so G is not
* bipartite.
*
* To prove the other direction of the claim, that if G has no odd cycles it is
* bipartite, we similarly prove the contrapositive - that if G is not
* bipartite, it contains an odd cycle. Consider any non-bipartite graph G and
* let F be any spanning forest of G. For each tree T in F, pick an arbitrary
* node of the tree to use as the root, then label each node with its distance
* from the root. Some nodes will have odd depth; others will have even depth.
* Now, partition the nodes into nodes of odd depth and nodes of even depth.
* Since the graph is not bipartite, there must be at least one edge between
* nodes of even depth or of odd depth; call it e = (u, v). Now consider the
* least common ancestor w of u and v in the tree T. Then the parity of the
* lengths of the paths from u to w and from w to v in T must be the same,
* since each path is either a path between two even nodes, two odd nodes, or
* an even node and an odd node. This means that the length of the path from
* u to w and then from w to v in tree T is even. But this gives us our odd
* cycle - we can take this path, then cross edge e = (u, v) to end up back
* where we started after following an odd number of edges.
*
* The algorithm implemented here works by choosing as its spanning forest a
* depth-first search tree in the graph G. As it explores nodes in a DFS
* fashion, it marks the parity of the distance of each node from the root of
* the particular tree it resides in. We can then check every edge and see if
* any runs between two nodes of even parity or of odd parity to check whether
* the odd cycle exists. As an optimization, though, we combine this logic
* with the logic to actually perform the depth-first search. Whenever we
* expand a node for the first time, we mark its parity, then explore all
* outgoing arcs with the assumption that the endpoints of those arcs are at a
* different parity than the current node. If we ever explore an arc where
* both nodes are known to have the same parity, we have found an arc between
* two nodes of the same parity and have detected an odd cycle. Since the DFS
* considers each arc in the graph twice (once in each direction), we're
* guaranteed that we will locate such an edge if it exists.
*
* The runtime of this algorithm is surprisingly good - it takes a single DFS,
* which runs in linear (O(|V| + |E|)) time.
*/
import java.util.*; // For HashMap
public final class BipartiteVerify {
/**
* Returns whether the input graph is bipartite.
*
* @param g The graph to examine.
* @return Whether the graph is bipartite.
*/
public static <T> boolean isBipartite(UndirectedGraph<T> g) {
/* We'll associate each node in the graph with its parity in the DFS
* search. This map will hold this association.
*/
Map<T, Boolean> parityTable = new HashMap<T, Boolean>();
/* Start off a DFS from each node in the graph, unless we've already
* visited it. We hoist the check for whether the node has been
* explored before out of the recursion, since if the node has been
* explored previously we don't care what parity it has.
*/
for (T node: g)
if (!parityTable.containsKey(node) &&
!dfsExplore(node, g, parityTable, true))
return false;
/* If we got here, it means that the graph contains no odd cycles and
* is therefore bipartite.
*/
return true;
}
/**
* Recursively explores outward from the given node in the DFS, labeling
* it with the appropriate parity. If a contradiction is detected in the
* parity assignment, this returns false.
*
* @param node The node to explore.
* @param g The graph in which to perform the DFS.
* @param parityTable A map from nodes to their parities.
* @param parity The expected parity of this node.
*/
private static <T> boolean dfsExplore(T node, UndirectedGraph<T> g,
Map<T, Boolean> parityTable,
boolean parity) {
/* If we've visited this node, return whether the parity matches the
* expected parity.
*/
if (parityTable.containsKey(node))
return parityTable.get(node).equals(parity);
/* Otherwise, mark that this node has the indicated parity. */
parityTable.put(node, parity);
/* Continue exploring outward from this node. If we find a
* contradiction, immediately abort and report failure.
*/
for (T endpoint: g.edgesFrom(node))
/* Note that we use the opposite parity for all child nodes, since
* we alternate between odd and even in the DFS tree.
*/
if (!dfsExplore(endpoint, g, parityTable, !parity))
return false;
/* If we made it here, everything in this subtree worked out. */
return true;
}
}