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

Question

Учитывая график, мне нужно сгенерировать все топологические упорядочения. Например, учитывая следующий график:

Я хочу сгенерировать все топологические заказы, которые:

• 2 4 7 5
• 2 7 4 5
• 2 4 5 7

Поскольку может существовать много топологических порядков, мне нужно генерировать их лениво. В настоящее время у меня есть рабочая реализация, которая является рекурсивной и работает поверх библиотеки scala-graph:

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

import scala.collection.mutable.ArrayStack
import scala.collection.Set

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))

  def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int): Stream[List[graph.NodeT]] = {
    if (sources.nonEmpty) {
      // `sources` contain all the nodes we can pick
      // --> generate all possibilities
      sources.toStream.flatMap(src => {
        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) {
      throw new Error("There is a cycle in the graph.")
    }
    else {
      topOrder.reverse #:: Stream.empty[List[graph.NodeT]]
    }
  }

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

Теперь я могу сгенерировать все (или только несколько) топологических порядков следующим образом:

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

Как я могу сделать алгоритм хвостом рекурсивным, но все еще ленивым?

Answer 1

Как сделать хвостовое отображение дерева рекурсивным?

Метод хвостовой рекурсивной максимальной глубины двоичного дерева в Scala

Попробуйте использовать scala.util.control.TailCalls

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

import scala.collection.Set
import scala.util.control.TailCalls.{TailRec, done, tailcall}

import cats.Monad
import cats.instances.stream._
import cats.syntax.traverse._

object App {

  implicit val tailRecMonad: Monad[TailRec] = new Monad[TailRec] {
    override def pure[A](x: A): TailRec[A] = done(x)
    override def flatMap[A, B](fa: TailRec[A])(f: A => TailRec[B]): TailRec[B] = fa.flatMap(f)
    override def tailRecM[A, B](a: A)(f: A => TailRec[Either[A, B]]): TailRec[B] = ???
  }

  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))

    def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int): TailRec[Stream[List[graph.NodeT]]] = {
      if (sources.nonEmpty) {
        // `sources` contain all the nodes we can pick
        // --> generate all possibilities
        sources.toStream.flatTraverse/*flatMap*/(src => {
          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
            }
          }

          tailcall(processSources(newSources, newIndegrees, newTopOrder, cnt + 1))
        })
      }
      else if (cnt != graph.nodes.size) {
        done(throw new Error("There is a cycle in the graph."))
      }
      else {
        done(topOrder.reverse #:: Stream.empty[List[graph.NodeT]])
      }
    }

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

  def main(args: Array[String]): Unit = {
    val graph: Graph[Int, DiEdge] = Graph(2 ~> 4, 2 ~> 7, 4 ~> 5)
    allTopologicalSorts(graph) foreach println
  }
}

---

Или вы можете использовать cats.free.Trampoline

http://eed3si9n.com/herding-cats/stackless-scala-with-free-monads.html

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

import cats.free.Trampoline
import cats.free.Trampoline.{done, defer}
import cats.instances.stream._
import cats.instances.function._
import cats.syntax.traverse._

import scala.collection.Set

object App {

  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))

    def processSources(sources: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], topOrder: List[graph.NodeT], cnt: Int): Trampoline[Stream[List[graph.NodeT]]] = {
      if (sources.nonEmpty) {
        // `sources` contain all the nodes we can pick
        // --> generate all possibilities
        sources.toStream.flatTraverse(src => {
          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
            }
          }

          defer(processSources(newSources, newIndegrees, newTopOrder, cnt + 1))
        })
      }
      else if (cnt != graph.nodes.size) {
        done(throw new Error("There is a cycle in the graph."))
      }
      else {
        done(topOrder.reverse #:: Stream.empty[List[graph.NodeT]])
      }
    }

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

  def main(args: Array[String]): Unit = {
    val graph: Graph[Int, DiEdge] = Graph(2 ~> 4, 2 ~> 7, 4 ~> 5)
    allTopologicalSorts(graph) foreach println
  }
}

Answer 2

Реализация этого варианта топологической сортировки без разрыва стека и без одновременного вычисления всех возможностей была болезненной. Я закончил со следующей реализацией:

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

object test extends App {

  class TopSorter[T](val graph: Graph[T, DiEdge]) extends Iterator[List[T]] {

    final case class State[Node](indegrees: Map[Node, Int], topo: List[Node])

    sealed trait TopoRes
    final case class Res(order: List[graph.NodeT], sorter: Set[State[graph.NodeT]]) extends TopoRes
    final case object Nil extends TopoRes

    private[this] val indegs: Map[graph.NodeT, Int] = graph.nodes.map(node => (node, node.inDegree)).toMap
    private[this] var nextOrder = nextTopo(Set(State(indegs, List[graph.NodeT]())))

    override def hasNext: Boolean = nextOrder.isInstanceOf[Res]

    override def next(): List[T] = nextOrder match {
      case Res(order, sorter) => {
        nextOrder = nextTopo(sorter)
        order.map(_.value)
      }
      case Nil => throw new NoSuchElementException("next on empty iterator")
    }

    private def nextTopo(w: Set[State[graph.NodeT]]): TopoRes = {
      if (w.isEmpty) {
        Nil
      }
      else {
        w.head match {
          case State(indegrees, topo) => {
            val sources = indegrees.keySet.filter(indegrees.get(_).get == 0)
            if (sources.isEmpty) {
              Res(topo.reverse, w.tail) // The result is the order + state to compute the next order
            }
            else {
              sourcesLoop(sources, w.tail, topo, indegrees)
            }
          }
        }
      }
    }

    private def sourcesLoop(sources: Set[graph.NodeT], w: Set[State[graph.NodeT]], topo: List[graph.NodeT], indegrees: Map[graph.NodeT, Int]): TopoRes = {
      if (sources.isEmpty) {
        nextTopo(w)
      }
      else {
        val source = sources.head
        succLoop(source.diSuccessors, indegrees - source, sources, w, source, topo, indegrees)
      }
    }

    private def succLoop(succs: Set[graph.NodeT], indegrees: Map[graph.NodeT, Int], sources: Set[graph.NodeT], w: Set[State[graph.NodeT]], source: graph.NodeT, topo: List[graph.NodeT], oldIndegrees: Map[graph.NodeT, Int]): TopoRes = {
      if (succs.isEmpty) {
        sourcesLoop(sources.tail, w + State(indegrees, source :: topo), topo, oldIndegrees)
      }
      else {
        val succ = succs.head
        succLoop(succs.tail, indegrees.updated(succ, indegrees.get(succ).get - 1), sources, w, source, topo, oldIndegrees)
      }
    }
  }

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

  while (it.hasNext)
    println(it.next())
}