Changed the efficient bridge-finding algorithm

jonathanxia · jonathanxia · commit e53fce7741d9 · 2016-05-30T21:52:04.000-07:00
Got rid of the unnecessary visited and parent array to make it more
space efficient. I also used the idea that the low array is the lowest
numbered vertex that can be reached, so a depth first search can
initiate at a connected component by passing the vertex itself in as its
parent.
diff --git a/algorithm/graph_search/bridges/efficient/code.js b/algorithm/graph_search/bridges/efficient/code.js
@@ -4,61 +4,70 @@
 
 var timer = 0, bridges = [], adj = [];	//adj keeps track of the neighbors of each node
 
-var util = function (u, visited, disc, low, parent) {
+var util = function (u, disc, low, parent) {
+	//u is the node that is currently being processed in the DFS (depth-first search)
+	//disc is the numbering of the vertices in the DFS, starting at 0
+	//low[v] is the lowest numbered vertex that can be reached from vertex v along the DFS
+	//parent is the node that u came from 
 	logger._print ('');
 	logger._print ('Visiting node ' + u);
 	graphTracer._visit (u)._wait ();
 	graphTracer._leave (u)._wait ();
 
-	visited [u] = true;
-	disc [u] = low [u] = ++timer;
+	//visited [u] = true;
+	disc [u] = low [u] = timer++;
 
 	logger._print ('Nodes adjacent to ' + u + ' are: [ ' + adj [u] + ' ]');
-	adj [u].forEach (function (v) {
+	/*adj [u].forEach (function (v) {
 		graphTracer._visit (v, u)._wait ();
 		graphTracer._leave (v, u)._wait ();
-	});
+	});*/
+	var trace = function(v) {
+		graphTracer._visit (v, u)._wait ();
+		graphTracer._leave (v, u)._wait ();
+	}
 
 	adj [u].forEach (function (v) {
-		if (visited [v]) {
-			logger._print (u + '\'s neighbor ' + v + ' has already been visited. Not visiting it.');
+		if (disc [v] > -1 && v == parent) {
+			trace(v);
+			logger._print (u + '\'s neighbor ' + v + ' is u\'s parent. Not visiting it.');
+			
+		}
+		else if (disc[v] > -1 && v != parent) {
+			trace(v);
+		    logger._print(u + '\'s neighbor ' + v + ' is not u\'s parent. Comparing low[u] with disc[v]')
+		    if(low[u] > disc[v]) {
+		        logger._print('low[' + u + '] is greater than disc[' + v + ']. Setting low[' + u + '] to disc[' + v + ']')
+		        low[u] = disc[v]
+		    }
 		}
 
-		if (!visited [v]) {
+		if (disc[v] == -1) {
+			trace(v);
 			logger._print (u + '\'s neighbor ' + v + ' has not been visited yet');
-			logger._print ('Setting parent of ' + v + ' to ' + u + ' (parent [v] = u)');
-
-			parent [v] = u;
 
-			logger._print ('recursively calling util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
-			util (v, visited, disc, low, parent);
+			logger._print ('recursively calling util (' + v + ', [' + disc + '], [' + low + '],' + u + ')');
+			util (v, disc, low, u);
 
 			logger._print ('--------------------------------------------------------------------');
-			logger._print ('Returned from util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
-			logger._print ('notice that the values of visited, disc, low and parent might have changed');
 
 			logger._print ('Setting low [' + u + '] to ' + Math.min (low [u], low [v]));
 			low [u] = Math.min (low [u], low [v]);
 
-			if (low [v] > disc [u]) {
-				logger._print ('low [v] > disc [u], v=' + v + ', u=' + u + ', (' + low [v] + ' > ' + low [u] + ')');
-				logger._print (u + ' -> ' + v + ' is a bridge. Adding u->v to the set of bridges found');
+			if (low [v] == disc [v]) {
+				logger._print ('low [' + v + '] == disc [' + v + '], low[' + v + ']=' + low[v] + ', disc[' + v + ']=' + disc[v]);
+				logger._print (u + ' -> ' + v + ' is a bridge. Adding ' + u + '->' + v + 'to the set of bridges found');
 				bridges.push ([u, v]);
 			}
 		}
-		else if (v !== parent [u]) {
-			logger._print (v + ' does not equal parent [' + u + '] (' + parent [u] + ')');
-			logger._print ('Setting low [' + u + '] to ' + Math.min (low [u], disc [v]));
-			low [u] = Math.min (low [u], disc [v]);
-		}
+		
 	});
 };
 
 (function findBridges (graph) {
-	var visited = filledArray (graph.length, 0);
-	var parent = filledArray (graph.length, -1);
-	var disc = filledArray (graph.length, 0);
-	var low = filledArray (graph.length, 0);
+	
+	var disc = filledArray (graph.length, -1);
+	var low = filledArray (graph.length, -1);
 
 	function filledArray (length, value) {
 		return Array.apply (null, Array (length)).map (Number.prototype.valueOf, value);
@@ -75,20 +84,18 @@ var util = function (u, visited, disc, low, parent) {
 		});
 	}) ();
 
-	for (var i = 0; i < visited.length; i++) { visited [i] = false; }
-
-	logger._print ('Initializing <b>visited</b>: ' + visited + ', <b>parent</b>: ' + parent + ', <b>disc</b>: ' + disc + ' <b>low</b>: ' + low);
+	logger._print ('Initializing: <b>disc</b>: ' + disc + ' <b>low</b>: ' + low);
 	logger._print ('');
 	logger._print ('Beginning efficient Bridge Finding');
-	logger._print ('NOTE: call to util () follows pattern: util (nodeToVisit, visited, disc, low, parent). See code for clarity');
+	logger._print ('NOTE: call to util () follows pattern: util (nodeToVisit, disc, low, parent). See code for clarity');
 	logger._print ('');
 
 	logger._print ('Starting the main for loop (for each node)');
 	for (var v = 0; v < graph.length; v++) {
-		if (!visited [v]) {
-			logger._print (v + ' has not been visited yet. Calling util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + ']) from the for loop');
-			util (v, visited, disc, low, parent);
-			logger._print ('Returned in for loop after util (' + v + ', [' + visited + '], [' + disc + '], [' + low + '], [' + parent + '])');
+		if (disc[v] == -1) {
+			logger._print (v + ' has not been visited yet. Calling util (' + v + ',  [' + disc + '], [' + low + '],' + v + ') from the for loop');
+			util (v, disc, low, v);
+			logger._print ('Returned in for loop after util (' + v + ', [' + disc + '], [' + low + '], [' + v + '])');
 		}
 	}
 }) (G);
