Added BFS bipartiteness algorithm

kopiro · kopiro · commit 0925eb622a91 · 2017-06-04T14:34:41.000+02:00
AKA: Graph is 2-colorable.
diff --git a/algorithm/graph_search/bfs/desc.json b/algorithm/graph_search/bfs/desc.json
@@ -18,6 +18,7 @@
   ],
   "files": {
     "tree": "Searching a tree",
-    "shortest_path": "Finding the shortest path"
+    "shortest_path": "Finding the shortest path",
+    "test_bipartiteness": "Test if graph is biparted (or 2-colorable)"
   }
 }
diff --git a/algorithm/graph_search/bfs/test_bipartiteness/code.js b/algorithm/graph_search/bfs/test_bipartiteness/code.js
@@ -0,0 +1,41 @@
+function BFSCheckBipartiteness(s) {
+    var Q = [];
+
+    // Create a new matrix to set colors (0,1)
+    var Colors = [];
+    for (var _i = 0; _i < G.length; _i++) Colors[_i] = -1;
+    colorsTracer._setData(Colors);
+
+    Colors[s] = 1;
+    colorsTracer._notify(s, 1);
+
+    Q.push(s); // add start node to queue
+
+    while (Q.length > 0) {
+        var node = Q.shift(); // dequeue
+        tracer._visit(node)._wait();
+
+        for (var i = 0; i < G[node].length; i++) {
+        	if (G[node][i]) {
+
+        		if (Colors[i] === -1) {
+
+        			Colors[i] = 1 - Colors[node];
+        			colorsTracer._notify(i, 1 - Colors[node]);
+
+        			Q.push(i);
+        			tracer._visit(i, node)._wait();
+
+        		} else if (Colors[i] == Colors[node]) {
+        			logger._print('Graph is not biparted');
+        			return false;
+        		}
+        	}
+        }
+    }
+    
+    logger._print('Graph is biparted');
+    return true;
+}
+
+BFSCheckBipartiteness(0);
diff --git a/algorithm/graph_search/bfs/test_bipartiteness/data.js b/algorithm/graph_search/bfs/test_bipartiteness/data.js
@@ -0,0 +1,14 @@
+var tracer = new UndirectedGraphTracer();
+var logger = new LogTracer();
+tracer.attach(logger);
+
+var G =[
+[0, 1, 0, 1, 1],
+[1, 0, 1, 0, 0],
+[0, 1, 0, 1, 0],
+[1, 0, 1, 0, 0], // <-- replace latest 0 with 1 to make G not biparted
+[1, 0, 0, 0, 0],
+];
+tracer._setData(G, 0);
+
+var colorsTracer = new Array1DTracer('Colors');

Original file line number	Diff line number	Diff line change
`@@ -18,6 +18,7 @@`
`18`	`18`	`],`
`19`	`19`	`"files": {`
`20`	`20`	`"tree": "Searching a tree",`
`21`		`- "shortest_path": "Finding the shortest path"`
	`21`	`+ "shortest_path": "Finding the shortest path",`
	`22`	`+ "test_bipartiteness": "Test if graph is biparted (or 2-colorable)"`
`22`	`23`	`}`
`23`	`24`	`}`