尾递归算法，用于生成图中的所有拓扑顺序

本文介绍了尾递归算法，用于生成图中的所有拓扑顺序的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给出一个图，我需要生成所有拓扑顺序. 例如，给定下图:

Given a graph i need to generate all topological orderings. For instance, given the following graph:

我要生成所有拓扑顺序，这些顺序是:

i want to generate all topological orderings, which are:

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

因为可能存在许多拓扑顺序，所以我需要延迟生成它们.当前，我有一个递归的有效实现，并且可以在scala-graph库的顶部进行工作:

Because many topological orderings may exist, I need to generate them lazily. Currently, I have a working implementation that is recursive and works on top of the scala-graph library:

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

现在，我可以生成所有(或仅几个)拓扑顺序，如下所示:

Now, i can generate all (or only a few) topological orderings as follows:

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

如何使算法尾部递归，但仍然很懒?

推荐答案

在拓扑排序上实现这种变化而不会炸毁堆栈，也不会立即计算所有可能性，这是很痛苦的.我完成了以下实现:

Implementing this variation on topological sort without blowing up the stack and without computing all possibilities at once has been painful. I ended up with the following implementation:

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