Tarjan的强连接组件算法的功能实现 [英] Functional implementation of Tarjan's Strongly Connected Components algorithm
问题描述
我进行了实施 Scala中的 Tarjan的SCC算法教科书版本。但是，我不喜欢的代码 - 这是非常必要/程序与大量的突变状态和记账索引。是否有更多的功能版本的算法？我相信命令式版本的算法隐藏的算法背后的核心思想不像功能版本。我发现其他人遇到相同问题使用此特定算法，但我无法将他的Clojure代码翻译成idomatic Scala。
I went ahead and implemented the textbook version of Tarjan's SCC algorithm in Scala. However, I dislike the code - it is very imperative/procedural with lots of mutating states and book-keeping indices. Is there a more "functional" version of the algorithm? I believe imperative versions of algorithms hide the core ideas behind the algorithm unlike the functional versions. I found someone else encountering the same problem with this particular algorithm but I have not been able to translate his Clojure code into idomatic Scala.
注意：如果有人想实验，我有一个很好的设置生成随机图和< a href =https://github.com/pathikrit/scalgos/blob/master/src/test/scala/com/github/pathikrit/scalgos/GraphSpec.scala#L82>测试您的SCC算法与运行Floyd-Warshall
Note: If anyone wants to experiment, I have a good setup that generates random graphs and tests your SCC algorithm vs running Floyd-Warshall
推荐答案
以下函数式Scala代码生成一个将代表分配给图表每个节点的映射。每个代表识别一个强连接分量。该代码基于Tarjan的强连接组件的算法。
The following functional Scala code generates a map that assigns a representative to each node of a graph. Each representative identifies one strongly connected component. The code is based on Tarjan's algorithm for strongly connected components.
为了理解算法，它可能足以理解折叠和 dfs function。
In order to understand the algorithm it might suffice to understand the fold and the contract of the dfs function.
def scc[T](graph:Map[T,Set[T]]): Map[T,T] = {
//`dfs` finds all strongly connected components below `node`
//`path` holds the the depth for all nodes above the current one
//'sccs' holds the representatives found so far; the accumulator
def dfs(node: T, path: Map[T,Int], sccs: Map[T,T]): Map[T,T] = {
//returns the earliest encountered node of both arguments
//for the case both aren't on the path, `old` is returned
def shallowerNode(old: T,candidate: T): T =
(path.get(old),path.get(candidate)) match {
case (_,None) => old
case (None,_) => candidate
case (Some(dOld),Some(dCand)) => if(dCand < dOld) candidate else old
}
//handle the child nodes
val children: Set[T] = graph(node)
//the initially known shallowest back-link is `node` itself
val (newState,shallowestBackNode) = children.foldLeft((sccs,node)){
case ((foldedSCCs,shallowest),child) =>
if(path.contains(child))
(foldedSCCs, shallowerNode(shallowest,child))
else {
val sccWithChildData = dfs(child,path + (node -> path.size),foldedSCCs)
val shallowestForChild = sccWithChildData(child)
(sccWithChildData, shallowerNode(shallowest, shallowestForChild))
}
}
newState + (node -> shallowestBackNode)
}
//run the above function, so every node gets visited
graph.keys.foldLeft(Map[T,T]()){ case (sccs,nextNode) =>
if(sccs.contains(nextNode))
sccs
else
dfs(nextNode,Map(),sccs)
}
}
我只是在维基百科页面上的示例图上测试了代码。
I've tested the code only on the example graph found on the Wikipedia page.
与原始实现相反，我的版本避免了显式解开堆栈，使用一个适当的（非尾）递归函数。该堆栈由 path 的持久性映射表示。在我的第一个版本中，我使用 List 作为堆栈;
In contrast to the original implementation, my version avoids explicitly unwinding the stack and simply uses a proper (non tail-) recursive function. The stack is represented by a persistent map called path instead. In my first version I used a List as stack; but this was less efficient since it had to be searched for containing elements.
代码是而高效。对于每个边，你必须更新和/或访问不可变映射 path ，这会花费 O（log | N |），总计 O（| E | log | N |）。这与命令式版本实现的 O（| E |）形成对比。
The code is rather efficient. For each edge, you have to update and/or access the immutable map path, which costs O(log|N|), for a total of O(|E| log|N|). This is in contrast to O(|E|) achieved by the imperative version.
Chris Okasaki的回答给出了Haskell中的线性时间解，组件。它们的实现是基于Kosaraju的算法来寻找SCC，这基本上需要两个深度优先遍历。本文的主要贡献似乎是一个懒惰的线性时间DFS实现在Haskell。
The paper in Chris Okasaki's answer gives a linear time solution in Haskell for finding strongly connected components. Their implementation is based on Kosaraju's Algorithm for finding SCCs, which basically requires two depth-first traversals. The paper's main contribution appears to be a lazy, linear time DFS implementation in Haskell.
它们实现线性时间解决方案需要一个 O（1）单例添加和成员测试。这基本上是相同的问题，使得该答案中给出的解决方案比命令性解决方案具有更高的复杂性。他们用Haskell中的状态线程解决它，这也可以在Scala中完成（见Scalaz）。所以如果一个人愿意让代码相当复杂，可以实现Tarjan的SCC算法到一个功能 O（| E |）版本。
What they require to achieve a linear time solution is having a set with O(1) singleton add and membership test. This is basically the same problem that makes the solution given in this answer have a higher complexity than the imperative solution. They solve it with state-threads in Haskell, which can also be done in Scala (see Scalaz). So if one is willing to make the code rather complicated, it is possible to implement Tarjan's SCC algorithm to a functional O(|E|) version.
这篇关于Tarjan的强连接组件算法的功能实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
