JointJs Cycle Detection

Question

Я пытаюсь реализовать алгоритм обнаружения циклов в ориентированном графе (только исходящие соединения) с использованием JointJS. Я написал следующий код, который не работает должным образом.

 var _elements = graph.getElements(); 
     var visited = []; 
     var level = 0; 
     var isCycleExists; 
     for (var i = 0; i < _elements.length; i++) { 
      var elem = _elements[i]; 
      //only checking nodes which do have predecessors 
      if ((graph.getPredecessors(elem).length > 0) && !elem.isLink() 
        && hasCycle(elem, visited, level)) { 
       isCycleExists = true; 
       break; 
      } 
     } 

    function hasCycle(comp, visited, level) { 
     var successors = graph.getSuccessors(comp); 
     visited.push(comp.id); 
     for (var i = 0; i < successors.length; i++) { 
      var c = successors[i]; 
      var _successors = graph.getSuccessors(c); 
      if (_successors.length == 0) { 
       continue; 
      } 
      if (visited.indexOf(c.id) > -1) { 
       return true; 
      } 
      visited.push(c.id); 
      if (hasCycle(c, visited.slice(), ++level)) { 
       return true; 
      } 
     } 
     return false; 
    } 

Было бы очень полезно, если бы кто-нибудь мог мне помочь в этом.

Answer 1

Проблема преемника - это не то же самое, что прямой преемник. Проверьте значение graph.getSuccessors(comp): если lib использует согласованные имена функций, которые должны содержать B, C, D и E для первого запуска. Таким образом, вы отмечаете те, которые были посещены, но также запускаете hasCycle(c, visited.slice(), ++level), где вы снова проверяете узлы, начиная с D (я думаю, что D является первым, для которого вы получаете «уже посещенный» случай).

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

function hasCycle(comp, visited, level) { 
    var successors = graph.getSuccessors(comp), i; 

    if (visited.indexOf(comp.id) > -1) 
     return true; 
    visited.push(comp.id); 

    for (i = 0; i < successors.length; i++) 
     if (hasCycle(successors[i], visited.slice(), ++level)) 
      return true; 

    return false; 
} 

И второе, что более важно, попробуйте graph.getNeighbors метод вместо graph.getSuccessors (не забудьте проверить только соседей в одном направлении).

Answer 2

Я считаю, что я нашел основную причину такого неустойчивого поведения, используя этот алгоритм.

На самом деле метод JointJS API getElements() возвращает массив элементов в порядке ввода в ячейках графа. Это означает, что если вы создаете 3 элемента A, B, C, чтобы создать граф вроде A-->B-->C, но вы добавили эти элементы в заказ A сначала, C второй и B в конце. Теперь, согласно условию if (graph.getPredecessors(elem).length > 0) && !elem.isLink() && hasCycle(elem, visited, level), обнаружение цикла фактически начинается с C. В этом случае C не имеет исходящего соседа и помечен как посещенный. Теперь, на следующей итерации, проверяется B (поскольку он вводится в График после C), и он имеет C в качестве исходящего соседа. Теперь C снова оценивается, но C уже отмечен как посетивший. Следовательно, это показывает существование цикла.

Итак, мы считаем, что наш поиск на графике должен начинаться с узлов, у которых нет предшественников. Например, в предыдущем примере наш поиск должен начинаться всегда с A. График также может содержать один или несколько узлов, которые не имеют предшественника. В этом сценарии мы также должны начать поиск с узлов, у которых нет предшественника. Например, A1-->B, A1-->C, A2-->B, A2-->C вот так. Наше обнаружение должно начинаться с A1 и A2.

Я изменил методы следующим которая соответствует предыдущей стратегии:

function checkForCycleExistence() { 
    var visited = []; 
    var level = 0; 
    var isCycleExists; 
    var _elements = graph.getElements(); 
    for (var i = 0; i < _elements.length; i++) { 
     var elem = _elements[i]; 
     if ((graph.getPredecessors(elem).length == 0) 
       && hasCycle(elem, visited, level)) { 
      isCycleExists = true; 
      break; 
     } 
    } 
    if (isCycleExists) { 
     console.log("Cycle Exists"); 
    } 
    return isCycleExists; 
} 

function hasCycle(comp, visited, level) { 
    var neighbors = graph.getNeighbors(comp, { 
     outbound : true 
    }), i; 

    if (visited.indexOf(comp.id) > -1) 
     return true; 

    visited.push(comp.id); 

    for (i = 0; i < neighbors.length; i++) 
     if (hasCycle(neighbors[i], visited.slice(), ++level)) 
      return true; 

    return false; 
}