c# - 再帰的 Tarjan を反復型に変換して SCC を見つける

Question

これで、グラフの SCC を提供する再帰的な tarjan の実装に成功しました。

私の再帰的な実装は次のとおりです。

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の質問（ Tarjanのアルゴリズムの非再帰バージョン）を含む多くのリソースをすでにチェックしています。長い値を処理する必要があり、現在の状態の後継インデックスが Dictionary(SuccessorMap[]) に格納されているため、列挙子を使用できません (ノード数が 50 億を超えるグラフを処理する必要があります)。

再帰的なソリューションを反復的なソリューションに変換するために利用できる一般的なガイドラインに従いました。

1. 再帰呼び出しをローカル スタックへのプッシュに置き換えました
2. 「リターン」をローカルスタックからのポップに置き換えました

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 を繰り返し実装する方法を理解していません。

私を助けるためのあらゆる種類の助けを本当に感謝します。