Javascript: DFS traversal of a directed tree with I / O involved

Question

Given a directional T tree with a variable number of children per node, I would like to find a path of size PATH_SIZE from the "good" nodes, starting with root.

each node has an isGood() method and a getChildren() method, which works as expected.

Simple recursive DFS solutions are as follows: (please correct me if I am wrong)

 function findGoodPath(node, depth){ if(!node.isGood()){ return null; } else if (depth==PATH_SIZE){ return [node]; } var children = node.getChildren(); for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth+1); if (result){ return result.concat([node]); } } return null; } 

The call to findGoodPath(root, 1) should find the result, if it exists.

Now for the problem : the getChildren() method of the node object is actually an asynchronous method that performs I / O operations behind the scenes. it returns nothing and expects a single callback argument to handle the returned children.

A modified code solution ( WRONG ) might look like this:

 function findGoodPath(node, depth){ if(!node.isGood()){ return null; } else if (depth==PATH_SIZE){ return [node]; } node.getChildren(function(children){ for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth+1); if (result){ return result.concat([node]); } } }); } 

This solution will not work: all getChildren methods of one child node will be called immediately, so it will actually execute BFS. and, even worse, return statements are associated with an anonymous callback function and will execute after the close function completes.

Clearly, there is a need for some kind of flow control mechanism. What is a simple and elegant solution to this problem?

UPDATE: I accepted Sebastian's answer as it solves this problem with recursion, this is how I presented the question. I also posted an answer that uses the whilst asynchronous library, this is what I used. Sebastian was kind enough to compare the two methods here . (spoiler: identical performance)

Answer 1

first, I think you need to call findGoodPath (children [i], depth + 1) if you want the depth to equal PATH_SIZE.

then you have a closing problem. With your asynchronous call, you always agree with the node instance, which is not the one you need.

One way to do this is to:

 node.getChildren((function(_node) { return function(children){ for (var i=0; i<children.length; i++){ var result = findGoodPath(children[i], depth); if (result){ return result.concat([_node]); } } }); })(node)); 

But I think this is part of the problem as you mix the synchronization function with the async function. Line:

 var result = findGoodPath(children[i], depth) 

is written as a synchronization call, whereas findGoodPath is an asynchronous function, so it must also be written with callbacks.

Hope this helps

ps: this will help get jsfiddle ...

UPDATE: just try it. Since I cannot verify, it does not work, but it is an idea. I can't figure out if I need to create another scope in the second findGoodPath call, like in the getChildren call

 function findGoodPath(node, depth, callback){ if(!node.isGood()){ return callback(null); } else if (depth==PATH_SIZE){ return callback([node]); } node.getChildren((function(_node, _callback) { return function(children){ var node = _node, callback = _callback; for (var i=0; i<children.length; i++){ findGoodPath(children[i], depth, function(result) { if (result){ return callback(result.concat([node])); } }); } }); })(node, callback)); } 

Answer 2

Now I'm not 100% focused, but I'm pretty sure Async.js seriestasks is the right solution for you (if there is no seriestasks, I bet there is another control flow in Async.js that will do the trick.

Answer 3

OK, so there are several ways to achieve asynchronous DFS bypass. Since asynchronous recursions tend to become somewhat ugly, I decided to get rid of recursion.

First, I re-executed the synchronous version of the function using the while loop instead of recursion:

 function findGoodPathLoop(root){ var nodesToVisit = [{data: root, path:[]}]; while (nodesToVisit.length>0){ var currentNode = nodesToVisit.pop(); if (currentNode.data.isGood()){ var newPath = currentNode.path.concat(currentNode.data); if (newPath.length==PATH_SIZE){ return newPath; } else { var childrenNodes = currentNode.data.getChildren().map(function(child){ return {data: child, path: newPath}; }); nodesToVisit = nodesToVisit.concat(childrenNodes); } } } return null; } 

Note I saved the whole path for each node, this is not a necessity, you can just keep the depth and keep an array of the current path, although this is a bit messy.

Then I used the async library to convert this function to asynchronous, replacing the standard while() function with async whilst() :

 function findGoodPathAsync(root, pathCallback){ var result = null; var nodesToVisit = [{data: root, path:[]}]; async.whilst( function(){ return nodesToVisit.length>0 && result==null ; }, function(next) { var currentNode = nodesToVisit.pop(); if (currentNode.data.isGood()){ var newPath = currentNode.path.concat(currentNode); if(newPath.length==PATH_SIZE){ result = newPath; next(); } else { currentNode.data.getChildren(function(children){ var childrenNodes = children.map(function(child){ return {data: child, path: newPath}; }); nodesToVisit = nodesToVisit.concat(childrenNodes); next(); }); } } else { next(); } }, function(err) { //error first style callback pathCallback(err, result); } ); } 

Not very beautiful, but he reads and does the job.