给定一个图,需要生成 所有 拓扑排序。例如,给定以下图:
我想要生成所有的拓扑排序,其中包括:
- 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
如何使算法成为尾递归但仍然是惰性的?
done(...)
之前添加println("found an ordering")
就可以看到。在我的解决方案中,如果我只想要两个排序,allTopologicalSorts(graph) take(2) foreach println
将只打印两次found an ordering
。在提出的解决方案中,它们将打印与解决方案数量相同的次数。因此,提出的解决方案不是lazy的。 - Kevin