Javascript: обход DFS для направленного дерева с участием ввода-вывода

Question

Учитывая направленное дерево T с переменным числом дочерних элементов на узел, я хотел бы найти путь размером PATH_SIZE из «хороших» узлов, начиная с root.

у каждого узла есть метод isGood() и метод getChildren(), который работает должным образом.

Простой DFS рекурсивные решения будет выглядеть следующим образом: (пожалуйста, поправьте меня, если я ошибаюсь)

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; 
} 

Вызов findGoodPath(root, 1) должен найти результат, если таковой существует.

В настоящее время для проблема: метод объекта узла - это, по сути, метод асинхронного ввода-вывода за кулисами. он ничего не возвращает и ожидает один аргумент обратного вызова для обработки возвращенных детей.

Модифицированный раствор кода (который НЕПРАВИЛЬНО) может выглядеть следующим образом:

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]); 
      } 
     } 
    }); 
} 

Это решение не будет работать: все методы GetChildren детей одного узла будет называться сразу, так он фактически выполнит BFS. и, что еще хуже, операторы return связаны с анонимной функцией обратного вызова и будут выполняться после завершения функции закрытия.

Понятно, что существует необходимость в каком-то механизме управления потоком. Какое простое и элегантное решение этой проблемы?

ОБНОВЛЕНИЕ: Я принял ответ Себастьяна, так как он решает эту проблему с рекурсией, вот как я представил вопрос. Я также опубликовал ответ, в котором используется цикл async'swhilst, это то, что я использовал. Себастьян был достаточно любезен, чтобы сравнить эти два метода: here.(спойлер: производительность одинакова)

Answer 1

первый, я думаю, вы должны вызвать findGoodPath (дети [I], глубина + 1), если вы хотите, чтобы глубина равна PATH_SIZE.

тогда вы У вас есть проблема с закрытием. С вашим асинхронным вызовом вы всегда соглашаетесь с экземпляром узла, который не тот, который вам нужен.

Один из способов вы можете сделать это может быть:

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)); 

Но я думаю, что это только часть проблемы, как вы смешиваете синхронизации функции с функцией асинхронной. Линия:

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

записывается в виде синхронизации вызова, тогда как findGoodPath является функцией асинхронной, поэтому он должен быть написан с обратными вызовами тоже!

Надеется, что это помогает

псу: это помогло бы иметь jsfiddle ...

UPDATE: просто попробовать. Поскольку я не могу проверить, он не работает, но это идея. Я не могу понять, если вам нужно создать еще одну сферу во втором findGoodPath вызова, так же, как в GetChildren называют

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

Я не 100% в центре внимания сейчас, но я почти уверен, что Async.js seriestasks является правильным решением для вас (если не seriestasks я готов поспорить, есть еще один контроль поток в Async.js, что будет делать трюк.

Answer 3

ОК, так что есть несколько способов достижения в обход асинхронной DFS. Поскольку асинхронные рекурсии имеют тенденцию становиться несколько уродливыми, я решил избавиться от рекурсии.

я сначала повторно реализован синхронный вариант функции, используя время цикла вместо рекурсии:

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; 
} 

Примечание: я сохранил весь путь для каждого узла, это не является необходимостью , вы можете просто сохранить глубину и сохранить массив текущего пути, хотя это немного грязнее.

Затем я использовал async библиотеку, чтобы преобразовать эту функцию в асинхронном одной, заменяя стандартный while() функцию с асинхронной-х 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); 
     } 
    ); 
} 

Не хорошенькая, но это читается и это делает работу.