Преобразование рекурсии дерева в хвостовую рекурсию вручную с использованием стека

Question

Я реализую вариант топологической сортировки (поверх scala-graph ), который возвращает все топологические порядки вместо одного.У меня есть рекурсивная реализация дерева, которую я хочу сделать рекурсивным хвостом.Я не хочу использовать трамплины, вместо этого я хочу имитировать стек вызовов, как описано в этот ответ .

Это рекурсивная версия моего алгоритма в виде дерева:

import scalax.collection.Graph
import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._
import scala.collection.Set

def allTopologicalSorts[T](graph: Graph[T, DiEdge]): Unit = {
  val indegree: Map[graph.NodeT, Int] = graph.nodes.map(node => (node, node.inDegree)).toMap

  def isSource(node: graph.NodeT): Boolean = indegree.get(node).get == 0

  def getSources(): Set[graph.NodeT] = graph.nodes.filter(node => isSource(node))

  processSources(getSources(), indegree, List[graph.NodeT](), 0)

  def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int): Unit = {
    if (sources.nonEmpty) {
      // `sources` contain all the nodes we can pick
      // --> generate all possibilities
      for (src <- sources) {
        val newTopOrder = src :: topOrder
        var newSources = sources - src

        // Decrease the in-degree of all adjacent nodes
        var newIndegrees = indegrees
        for (adjacent <- src.diSuccessors) {
          val newIndeg = newIndegrees.get(adjacent).get - 1
          newIndegrees = newIndegrees.updated(adjacent, newIndeg)
          // If in-degree becomes zero, add to sources
          if (newIndeg == 0) {
            newSources = newSources + adjacent
          }
        }

        processSources(newSources, newIndegrees, newTopOrder, cnt + 1)
      }
    }
    else if (cnt != graph.nodes.size) {
      println("There is a cycle in the graph.")
    }
    else {
      println(topOrder.reverse)
    }
  }
}

И мы можем запустить алгоритм следующим образом

val graph: Graph[Int, DiEdge] = Graph(2 ~> 4, 2 ~> 7, 4 ~> 5)
allTopologicalSorts(graph)

, который правильно возвращает

• Список (2, 7, 4, 5)
• List (2, 4, 7, 5)
• List (2, 4, 5, 7)

Теперь я попытался реализовать хвостовую рекурсивную версию, вручную сохранив стек

import scalax.collection.Graph
import scalax.collection.GraphPredef._
import scalax.collection.GraphEdge._
import scala.collection.Set

def allTopologicalSorts[T](graph: Graph[T, DiEdge]): Unit = { 
  val indegree: Map[graph.NodeT, Int] = graph.nodes.map(node => (node, node.inDegree)).toMap

  def isSource(node: graph.NodeT): Boolean = indegree.get(node).get == 0

  def getSources(): Set[graph.NodeT] = graph.nodes.filter(node => isSource(node))

  def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int]): Unit = {
    type Order = List[graph.NodeT]
    case class Frame(sources: List[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: Order, cnt: Int)

    def step(stack: List[Frame]): Unit = {
      stack match {
        case Frame(src :: rest, indegrees, topOrder, cnt) :: tail => {
          val onBacktrackingFrame = Frame(rest, indegrees, topOrder, cnt)

          // Process src now and remember to do the rest later
          val newTopOrder = src :: topOrder
          var newSources = rest

          // Decrease the in-degree of all adjacent nodes
          var newIndegrees = indegrees
          for (adjacent <- src.diSuccessors) {
            val newIndeg = newIndegrees.get(adjacent).get - 1
            newIndegrees = newIndegrees.updated(adjacent, newIndeg)
            // If in-degree becomes zero, add to sources
            if (newIndeg == 0) {
              newSources = adjacent :: newSources
            }
          }

          val recursionFrame = Frame(newSources, newIndegrees, newTopOrder, cnt + 1)
          step(recursionFrame :: onBacktrackingFrame :: tail)
        }
        case Frame(Nil, indegrees, topOrder, cnt) :: tail => {
          println(topOrder.reverse)
          step(tail)
        }
        case Nil =>
      }
    }

    step(List(Frame(sources.toList, indegrees, List[graph.NodeT](), 0)))
  }

  processSources(getSources(), indegree)
}

Однако это не работает, так как в результате получается

• Список (2, 4, 5, 7)
• Список (2, 4, 5)
• Список (2, 4, 7)
• Список (2, 4)
• Список (2, 7)
• Список (2)
• List ()

Что-то не так со стеком, но я не смог найти проблему.

Связанный вопрос: Хвостовой рекурсивный алгоритм генерациивсе топологические упорядочения в графе

Answer 1

Это решение является хвостово-рекурсивным AFAICT и работает, когда я его запускаю, хотя я изменил его части обратно на первую версию, в частности, изменив некоторые типы с List на Set, чтобы сохранить изменения отпервоначально маленький (я полагаю, что изменение его обратно на List снова должно быть относительно простым):

def allTopologicalSortsNew[T](graph: Graph[T, DiEdge]): Unit = { 
  type Order = List[graph.NodeT]
  case class Frame(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: Order, cnt: Int)
  val indegree: Map[graph.NodeT, Int] = graph.nodes.map(node => (node, node.inDegree)).toMap

  def isSource(node: graph.NodeT): Boolean = indegree.get(node).get == 0

  def getSources(): Set[graph.NodeT] = graph.nodes.filter(node => isSource(node))

  def processSources(initialSources: Set[graph.NodeT], initialIndegrees: Map[graph.NodeT, Int]): Unit = {

    def step(stack: List[Frame]): Unit = {
      stack match {
        case Frame(sources, indegrees, topOrder, cnt) :: tail if !sources.isEmpty => {

          val futureFrames = for (src <- sources) yield {
            val newTopOrder = src :: topOrder
            var newSources = sources - src

            // Decrease the in-degree of all adjacent nodes
            var newIndegrees = indegrees
            for (adjacent <- src.diSuccessors) {
              val newIndeg = newIndegrees.get(adjacent).get - 1
              newIndegrees = newIndegrees.updated(adjacent, newIndeg)
              // If in-degree becomes zero, add to sources
              if (newIndeg == 0) {
                newSources = newSources + adjacent
              }
            }

            Frame(newSources, newIndegrees, newTopOrder, cnt + 1)
          }

          step(futureFrames.toList ::: tail)
        }
        case Frame(sources, indegrees, topOrder, cnt) :: tail if sources.isEmpty => {
          println(topOrder.reverse)
          step(tail)
        }
        case Nil =>
      }
    }

    step(List(Frame(initialSources, initialIndegrees, List[graph.NodeT](), 0)))
  }

  processSources(getSources(), indegree)
}

Answer 2

Попробуйте

  def allTopologicalSorts[T](graph: Graph[T, DiEdge]): Stream[List[graph.NodeT]] = {
    val indegree: Map[graph.NodeT, Int] = graph.nodes.map(node => (node, node.inDegree)).toMap

    def isSource(node: graph.NodeT): Boolean = indegree.get(node).get == 0
    def getSources(): Set[graph.NodeT] = graph.nodes.filter(node => isSource(node))

    case class Frame(arg: Argument, parentArg: Option[Argument], res: Result)

    case class Argument(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int)

    sealed trait Result
    case object NotExpanded extends Result
    case object Expanded extends Result
    case class Calculated(value: Output) extends Result

    type Output = Stream[List[graph.NodeT]]

    // extract result from final state of stack
    def processSources(arg: Argument): Output =
      step1(List(Frame(arg, None, NotExpanded))) match {
        case Frame(`arg`, None, Calculated(res)) :: Nil => res
      }

    @tailrec
    // process stack as long as necessary
    def step1(stack: List[Frame]): List[Frame] = {
      val x = step(stack, Nil)
      x match {
        case Frame(arg, None, Calculated(res)) :: Nil => x
        case _ => step1(x)
      }
    }

    // helper method for handling "recursion backward" case in "step"
    def calcFromChildren(stack: List[Frame], parentArg: Argument): Option[(List[Frame], Frame)] = {
      val (childFrames, rest) = stack.span {
        case Frame(_, Some(`parentArg`), Calculated(_)) => true
        case _ => false
      }

      val output: Output = childFrames.map {
        case Frame(arg, Some(`parentArg`), Calculated(res)) => res
      }.toStream.flatten

      rest match {
        case Frame(`parentArg`, parentArg1, Expanded) :: rest1 if parentArg.sources.nonEmpty =>
          Some(rest1, Frame(parentArg, parentArg1, Calculated(output)))
        case _ => None
      }
    }

    @tailrec
    // process stack once
    def step(stack: List[Frame], acc: List[Frame]): List[Frame] = {
      stack match {
          // recursion backward
        case Frame(arg, Some(parentArg), Calculated(res)) :: frames if calcFromChildren(stack, parentArg).isDefined =>
          val (rest1, parentFrame) = calcFromChildren(stack, parentArg).get
          step(rest1, parentFrame :: acc)

          // base
        case Frame(arg, parentArg, _) :: frames if arg.sources.isEmpty && arg.cnt != graph.nodes.size =>
          throw new Error("There is a cycle in the graph.")
        case Frame(arg, parentArg, _) :: frames if arg.sources.isEmpty =>
          val res = arg.topOrder.reverse #:: Stream.empty[List[graph.NodeT]]
          step(frames, Frame(arg, parentArg, Calculated(res)) :: acc)

          // recursion forward
        case Frame(arg, parentArg, NotExpanded) :: frames =>

          val childFrames = arg.sources.toList.map(src => {
            val newTopOrder = src :: arg.topOrder
            var newSources = arg.sources - src

            var newIndegrees = arg.indegrees
            for (adjacent <- src.diSuccessors) {
              val newIndeg = newIndegrees.get(adjacent).get - 1
              newIndegrees = newIndegrees.updated(adjacent, newIndeg)
              if (newIndeg == 0) {
                newSources = newSources + adjacent
              }
            }

            val newArg = Argument(newSources, newIndegrees, newTopOrder, arg.cnt + 1)
            Frame(newArg, Some(arg), NotExpanded)
          })

          step(frames, Frame(arg, parentArg, Expanded) :: childFrames.reverse ::: acc)

          // ignore if not "recursion backward" case
        case Frame(arg, parentArg, Expanded) :: frames => step(frames, Frame(arg, parentArg, Expanded) :: acc)
        case Frame(arg, parentArg, Calculated(res)) :: frames => step(frames, Frame(arg, parentArg, Calculated(res)) :: acc)

          // stack is processed once
        case Nil => acc.reverse
      }
    }

    processSources(Argument(getSources(), indegree, List[graph.NodeT](), 0))
  }