Алгоритмы направленного циклического обхода графа (JavaScript)

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

Вы можете предположить, что я уже знаю, с какого узла начать, чтобы достичь всех точек ориентированного графа, и что для каждого узла у меня есть функция, которая будет возвращать узлы, на которые он направляет. Есть ли известный алгоритм поиска всех узлов?

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

Если вам нужны дополнительные сведения, актуальная задача состоит в том, чтобы получить список каждой именованной функции в JavaScript, включая функции, которые являются свойствами других объектов. Поэтому я попробовал что-то вроде следующего, так как думал, что ссылки объектов JS друг на друга образуют дерево (но, конечно, это не так):

function __findFunctions(obj){
  for (var f in obj){
    // for special case of edge with self
    if (obj === obj[f]){
      continue
    }
    if (typeof obj[f] === 'function' &&
        obj.hasOwnProperty(f) &&
          // exclude native functions, we only want user-defined ones
        !(/\[(native\scode|object\sfunction)\]/i).test(obj[f].toString()) &&
          // exclude functions with __ prefix
        !(/^\s*function\s*__/).test(obj[f].toString())
       ){
      document.write(f + "<br/>" + obj[f].toString() + "<hr/>");
    }
    //alert(typeof obj[f] + "\n" + obj + "\n" + obj[f] + "\n" + f)
    __findFunctions(obj[f]);
  }
}
__findFunctions(window);

Проблема с этим кодом в том, что он зацикливается.


javascript graph traversal language-agnostic
person ehsanul    schedule 08.07.2010    source источник
comment
Пожалуйста, игнорируйте регулярное выражение, не слишком важное в контексте этого вопроса. Хотя мне бы хотелось узнать, есть ли лучший способ отличить пользовательские функции от собственных.   -  person ehsanul    schedule 08.07.2010

Ответы (2)


arrow_upward
5
arrow_downward

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

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

// psuedo
id=0;
for each node
    node.id = id++;

и Т. Д.

Затем вы можете добавить идентификатор каждого узла в хэш во время обхода:

var alreadyTraversed = {};

// Traversing a node:
alreadyTraversed[node.id] = true;

И позже, когда вам нужно проверить, был ли он уже пройден:

if (node.id in alreadyTraversed) // It's already been traversed...

Или, для действительно элементарного решения, просто установите какое-либо свойство для каждого объекта, который вы проходите:

node._traversed = true;

// Later:
if (someNode._traversed) // already traversed.
person James    schedule 08.07.2010
comment
К сожалению, ваш псевдокод не сработает, потому что for each node на самом деле является алгоритмом обхода графа, который я ищу. Однако это дает мне представление, если JS позволяет: использовать сами объекты узлов в качестве идентификаторов вместо целого числа. Я делал такие вещи в Ruby, попробую на JS. Спасибо! - person ehsanul; 08.07.2010
comment
@ehsanul: См. мое второе предложенное решение :) - person James; 08.07.2010
comment
Угу, отличная идея. Это не только элементарно, но и правильное решение. Теперь я могу спать, зная, что есть разумное решение для меня, чтобы проснуться. - person ehsanul; 08.07.2010
comment
Вы бы случайно не узнали, какие объекты JS, кроме строк, не могут иметь свойств, не так ли? - person ehsanul; 08.07.2010
comment
Null, Undefined, String, Boolean, Number ... Хотя последние три могут иметь свойства, технически, но они не сохранят их, поскольку они не упакованы (попробуйте вместо этого new String() ...) - person James; 08.07.2010

arrow_upward
0
arrow_downward

Вам нужно будет вести список уже посещенных узлов, если вы хотите избежать циклов.

E.g.

__findFunctions(obj, visited) as your signature
at start do an "in array" test for current obj and return if so.
at start add obj to the visited for subsequent traversals.
person Matt Mitchell    schedule 08.07.2010