001package algs41; 002import stdlib.*; 003import algs13.Stack; 004/* *********************************************************************** 005 * Compilation: javac Bipartite.java 006 * Dependencies: Graph.java 007 * 008 * Given a graph, find either (i) a bipartition or (ii) an odd-length cycle. 009 * Runs in O(E + V) time. 010 * 011 * 012 *************************************************************************/ 013 014public class Bipartite { 015 private boolean isBipartite; // is the graph bipartite? 016 private final boolean[] color; // color[v] gives vertices on one side of bipartition 017 private final boolean[] marked; // marked[v] = true if v has been visited in DFS 018 private final int[] edgeTo; // edgeTo[v] = last edge on path to v 019 private Stack<Integer> cycle; // odd-length cycle 020 021 public Bipartite(Graph G) { 022 isBipartite = true; 023 color = new boolean[G.V()]; 024 marked = new boolean[G.V()]; 025 edgeTo = new int[G.V()]; 026 027 for (int v = 0; v < G.V(); v++) { 028 if (!marked[v]) { 029 // color[v] = false; 030 dfs(G, v); 031 } 032 } 033 assert check(G); 034 } 035 036 private void dfs(Graph G, int v) { 037 marked[v] = true; 038 for (int w : G.adj(v)) { 039 040 // short circuit if odd-length cycle found 041 if (cycle != null) return; 042 043 // found uncolored vertex, so recur 044 if (!marked[w]) { 045 edgeTo[w] = v; 046 color[w] = !color[v]; 047 dfs(G, w); 048 } 049 050 // if v-w create an odd-length cycle, find it 051 else if (color[w] == color[v]) { 052 isBipartite = false; 053 cycle = new Stack<>(); 054 cycle.push(w); // don't need this unless you want to include start vertex twice 055 for (int x = v; x != w; x = edgeTo[x]) { 056 cycle.push(x); 057 } 058 cycle.push(w); 059 } 060 } 061 } 062 063 boolean isBipartite() { return isBipartite; } 064 boolean color(int v) { return color[v]; } 065 public Iterable<Integer> cycle() { return cycle; } 066 067 private boolean check(Graph G) { 068 // graph is bipartite 069 if (isBipartite) { 070 for (int v = 0; v < G.V(); v++) { 071 for (int w : G.adj(v)) { 072 if (color[v] == color[w]) { 073 System.err.format("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w); 074 return false; 075 } 076 } 077 } 078 } 079 080 // graph has an odd-length cycle 081 else { 082 // verify cycle 083 int first = -1, last = -1; 084 for (int v : cycle()) { 085 if (first == -1) first = v; 086 last = v; 087 } 088 if (first != last) { 089 System.err.format("cycle begins with %d and ends with %d\n", first, last); 090 return false; 091 } 092 } 093 094 return true; 095 } 096 097 public static void main(String[] args) { 098 // create random bipartite graph with V vertices and E edges; then add F random edges 099 args = new String [] { "200", "100", "20" }; 100 int V = Integer.parseInt(args[0]); 101 int E = Integer.parseInt(args[1]); 102 int F = Integer.parseInt(args[2]); 103 104 Graph G = new Graph(V); 105 int[] vertices = new int[V]; 106 for (int i = 0; i < V; i++) vertices[i] = i; 107 StdRandom.shuffle(vertices); 108 for (int i = 0; i < E; i++) { 109 int v = StdRandom.uniform(V/2); 110 int w = StdRandom.uniform(V/2); 111 G.addEdge(vertices[v], vertices[V/2 + w]); 112 } 113 114 // add F extra edges 115 for (int i = 0; i < F; i++) { 116 int v = (int) (Math.random() * V); 117 int w = (int) (Math.random() * V); 118 G.addEdge(v, w); 119 } 120 121 StdOut.println(G); 122 123 124 Bipartite b = new Bipartite(G); 125 if (b.isBipartite()) { 126 StdOut.println("Graph is bipartite"); 127 for (int v = 0; v < G.V(); v++) { 128 StdOut.println(v + ": " + b.color(v)); 129 } 130 } 131 else { 132 StdOut.print("Graph has an odd-length cycle: "); 133 for (int x : b.cycle()) { 134 StdOut.print(x + " "); 135 } 136 StdOut.println(); 137 } 138 } 139 140 141}