Преобразование рекурсивного тарьяна в итеративное для поиска SCC - PullRequest
Новая
       39

Преобразование рекурсивного тарьяна в итеративное для поиска SCC

1 голос
/ 16 июня 2019

Итак, я успешно реализовал рекурсивный тарджан, который предоставляет мне SCC графика

Моя рекурсивная реализация выглядит следующим образом: 

public void DFSRecursive(long currentNode){
    low[currentNode] = preCount++;
    visited[currentNode] = true;
    stack.Push(currentNode);                                                                                                                 
    long minimum = low[currentNode];    
    foreach(long successorNode in SuccessorMap[currentNode])
    {
        if(!visited[successorNode])
        {
            DFSRecursive(successorNode);                 
        }
        if(low[successorNode] < minimum)
        {
        minimum = low[successorNode];
        }
    }
    if(minimum < low[currentNode])
    {
        low[currentNode] = minimum;
        return;
    }
    List<long> component = new List<long>();
    long stackTop;
    do
    {
        stackTop = stack.Pop();
        component.Add(stackTop);
    } 
    while(stackTop != currentNode);
    SCComponent.Add(component);
}

Теперь мне нужно преобразовать это в итеративное решение. Я уже проверил много ресурсов, чтобы помочь мне, включая очень похожий вопрос SO ( нерекурсивная версия алгоритма Тарьяна ). Я не могу использовать перечислитель, поскольку мне приходится иметь дело с длинными значениями, а индексы преемника текущего состояния хранятся в словаре (SuccessorMap []) (необходимо иметь дело с графами с числом узлов> 5 миллиардов).

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

  1. Заменил рекурсивный вызов на push в локальный стек
  2. Заменены «возвраты» на pop из локального стека

  3. Установите переменные в начале цикла и выскочили из локального стек 

    public void DFSIterative(long currentNode)
{
    var internalStack = new Stack<long>();
    low[currentNode] = preCount++;          
    stack.Push(currentNode);
    long minimum = low[currentNode];
    internalStack.Push(currentNode);

    while(!(internalStack.Count == 0))
    {
      currentNode = internalStack.Pop();
      visited[currentNode] = true;
      foreach(long successorNode in SuccessorMap[currentNode])
      {
        if(!visited[successorNode])
        {
          internalStack.Push(successorNode); 
        }
        if(low[successorNode] < minimum)
        { 
          minimum = low[successorNode];
        }
      }
      if(minimum < low[currentNode])
      {
        low[currentNode] = minimum;
        return;
      }
   }
   List<long> component = new List<long>();
   long stackTop;
   do
   {
     stackTop = stack.Pop();
 component.Add(w);
   }
   while(stackTop != currentNode);

   SCComponent.Add(component);
   }

Я признаю, что цикл do-while в итеративном методе всегда будет выдавать InvalidOperationException(stack empty), но я не знал, как реализовать рекурсивный do-while итеративно.

Был бы очень признателен за любую помощь, чтобы помочь мне.

...