Breadth first search implementation (also includes functions for finding shortest path and number of connected components)

Question

I've been practicing my algorithms using The Algorithm Design Manual. I've decided to implement the breadth first search section (5.7) using javascript. I also have a findShortestPath and a connectedComponents function that utilize my BFS. My BFS function accepts an adjacency list.

/* A Queue object for queue-like functionality over JavaScript arrays. */
var Queue = function() {
 this.items = [];
};
Queue.prototype.enqueue = function(obj) {
 this.items.push(obj);
};
Queue.prototype.dequeue = function() {
 return this.items.shift();
};
Queue.prototype.isEmpty = function() {
 return this.items.length === 0;
};
/*
 * Performs a breadth-first search on a graph
 * @param {array} graph - Graph, represented as adjacency lists.
 * @param {number} source - The index of the source vertex.
 * @returns {array} Array of objects describing each vertex, like
 * [{distance: _, predecessor: _ }]
 */
var doBFS = function(graph, source, processVertexEarly, processVertexLate, processEdge, logOff) {
 if (typeof logOff === 'undefined') logOff = false;
 if (!logOff) console.log();
 if (!logOff) console.log('*****************************');
 if (!logOff) console.log('bfs starting at', source, 'for adjacency list:');
 if (!logOff) console.log(graph);
 var bfsInfo = [];
 for (var i = 0; i < graph.length; i++) {
 bfsInfo[i] = {
 distance: null,
 predecessor: null,
 processed: false,
 discovered: false
 };
 }
 bfsInfo[source].distance = 0;
 var queue = new Queue();
 queue.enqueue(source);
 // Traverse the graph
 // As long as the queue is not empty:
 // Repeatedly dequeue a vertex u from the queue.
 // 
 // For each neighbor v of u that has not been visited:
 // Set distance to 1 greater than u's distance
 // Set predecessor to u
 // Enqueue v
 //
 var u, v, adjList;
 while (!queue.isEmpty()) {
 u = queue.dequeue();
 processVertexEarly(u, logOff);
 bfsInfo[u].processed = true;
 adjList = graph[u];
 for (var j = 0; j < adjList.length; j++) {
 v = adjList[j];
 /* A vertex is considered processed after we have traversed 
 * all outgoing edges from it. */
 if (!bfsInfo[v].processed) {
 processEdge(u, v, logOff);
 }
 if (!bfsInfo[v].discovered) {
 bfsInfo[v].discovered = true;
 bfsInfo[v].predecessor = u;
 bfsInfo[v].distance = bfsInfo[u].distance + 1;
 queue.enqueue(v);
 }
 }
 processVertexLate(u, logOff);
 }
 if (!logOff) console.log('##############################');
 if (!logOff) console.log();
 return bfsInfo;
};
var PVE = function(v, logOff) {
 if (!logOff) console.log('Early processed vertex:', v);
};
var PVL = function(v, logOff) {
 if (!logOff) console.log('Late processed vertex:', v);
 if (!logOff) console.log('----------------------------');
};
var PE = function(u, v, logOff) {
 if (!logOff) console.log('Processed edge:', '(' + u + ', ' + v + ')');
};
var findShortestPath = function(start, end, bfsInfo) {
 if (start === end || end === null) {
 console.log(start);
 } else {
 findShortestPath(start, bfsInfo[end].predecessor, bfsInfo);
 console.log(end);
 }
};
var connectedComponents = function(adjList, processVertexEarly, processVertexLate, processEdge) {
 console.log();
 console.log('**************************');
 console.log('Finding number of connected components...');
 var count = 1;
 var bfsInfo = doBFS(adjList, 0, processVertexEarly, processVertexLate, processEdge, true);
 for (var i = 0; i < adjList.length; i++) {
 if (!bfsInfo[i].discovered) {
 count++;
 bfsInfo = doBFS(adjList, i, processVertexEarly, processVertexLate, processEdge, true);
 }
 }
 console.log('there are', count, 'connected components');
 console.log('################################');
 console.log();
 return count;
};
var adjList = [
 [1],
 [0, 4, 5],
 [3, 4, 5],
 [2, 6],
 [1, 2],
 [1, 2, 6],
 [3, 5],
 [8],
 [],
 []
];
var bfsInfo = doBFS(adjList, 3, PVE, PVL, PE);
connectedComponents(adjList, PVE, PVL, PE);
var start = 0;
var end = 3;
findShortestPath(start, end, doBFS(adjList, start, PVE, PVL, PE));

• Joseph: Can you provide a JSBin sample? It appears that the code doesn't seem to work.
• Daniel Jacobson: It was written with Node.js. You can execute it on this site tutorialspoint.com/execute_nodejs_online.php

Answer 1

First, Queue is an unnecessary abstraction. JS arrays already provide methods to make it act like a queue. Use them directly instead.

Next is that your logic is peppered with console.log calls, especially the visually annoying ######### lines. I suggest you make a helper function that accepts a message. That helper message can then do the formatting, saving your logic from unnecessary presentation code.

I'm also wondering why you need to pass in functions. Why can't you call them straight away? Especially when PVL PVE and PE are, again, for presentation only.

I suggest you break down your operation into little functions. doBFS is quite large and at first glance, we don't really know what it's doing (other than the fact that you said its a breadth-first search, we'll take your word for that).

One neat trick so your functions don't get cluttered with logging is monkey-patching. It's a crude form of what other languages call annotations/decorators. It's just creating a function that wraps your original function along with some other functions, and calling that function instead.

function patch(patchFn, origFn){
 return function(){
 patchFn.apply(this, arguments);
 origFn.apply(this, arguments);
 }
}
function logger(){/* You get everything that was passed via arguments */}
function yourFunction(foo, bar, baz){/* your function remains clean */}
var patchedFunction = patch(logger, yourFunction);
// call patchedFunction instead.