# Bipartite.java

Below is the syntax highlighted version of Bipartite.java from §4.1 Undirected Graphs.

```/*************************************************************************
*  Compilation:  javac Bipartite.java
*  Dependencies: Graph.java
*
*  Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
*  Runs in O(E + V) time.
*
*
*************************************************************************/

public class Bipartite {
private boolean isBipartite;   // is the graph bipartite?
private boolean[] color;       // color[v] gives vertices on one side of bipartition
private boolean[] marked;      // marked[v] = true if v has been visited in DFS
private int[] edgeTo;          // edgeTo[v] = last edge on path to v
private Stack<Integer> cycle;  // odd-length cycle

public Bipartite(Graph G) {
isBipartite = true;
color  = new boolean[G.V()];
marked = new boolean[G.V()];
edgeTo = new int[G.V()];

for (int v = 0; v < G.V(); v++) {
if (!marked[v]) {
//                color[v] = false;
dfs(G, v);
}
}
assert check(G);
}

private void dfs(Graph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {

// short circuit if odd-length cycle found
if (cycle != null) return;

// found uncolored vertex, so recur
if (!marked[w]) {
edgeTo[w] = v;
color[w] = !color[v];
dfs(G, w);
}

// if v-w create an odd-length cycle, find it
else if (color[w] == color[v]) {
isBipartite = false;
cycle = new Stack<Integer>();
cycle.push(w);  // don't need this unless you want to include start vertex twice
for (int x = v; x != w; x = edgeTo[x]) {
cycle.push(x);
}
cycle.push(w);
}
}
}

boolean isBipartite()            { return isBipartite; }
boolean color(int v)             { return color[v];    }
public Iterable<Integer> cycle() { return cycle;       }

private boolean check(Graph G) {
// graph is bipartite
if (isBipartite) {
for (int v = 0; v < G.V(); v++) {
for (int w : G.adj(v)) {
if (color[v] == color[w]) {
System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
return false;
}
}
}
}

// graph has an odd-length cycle
else {
// verify cycle
int first = -1, last = -1;
for (int v : cycle()) {
if (first == -1) first = v;
last = v;
}
if (first != last) {
System.err.printf("cycle begins with %d and ends with %d\n", first, last);
return false;
}
}

return true;
}

public static void main(String[] args) {
// create random bipartite graph with V vertices and E edges; then add F random edges
int V = Integer.parseInt(args[0]);
int E = Integer.parseInt(args[1]);
int F = Integer.parseInt(args[2]);

Graph G = new Graph(V);
int[] vertices = new int[V];
for (int i = 0; i < V; i++) vertices[i] = i;
StdRandom.shuffle(vertices);
for (int i = 0; i < E; i++) {
int v = StdRandom.uniform(V/2);
int w = StdRandom.uniform(V/2);
}

for (int i = 0; i < F; i++) {
int v = (int) (Math.random() * V);
int w = (int) (Math.random() * V);
}

StdOut.println(G);

Bipartite b = new Bipartite(G);
if (b.isBipartite()) {
StdOut.println("Graph is bipartite");
for (int v = 0; v < G.V(); v++) {
StdOut.println(v + ": " + b.color(v));
}
}
else {
StdOut.print("Graph has an odd-length cycle: ");
for (int x : b.cycle()) {
StdOut.print(x + " ");
}
StdOut.println();
}
}

}
```