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}