功能实现tarjan算法的(Functional implementation of Tarjan&

我继续实现了的Tarjan的SCC算法的教科书版本 Scala中。但是，我不喜欢的代码 - 这是非常必要/程序，有很多变异的状态和簿记指数。有算法更“实用”的版本？我相信算法势在必行版本隐藏不同功能版本的算法背后的核心思想。我发现，别人遇到了同样的问题与此特定的算法，但我一直没能到他的Clojure代码翻译成idomatic斯卡拉。

注意：如果有人想尝试，我有一个很好的设置，生成随机图和测试您的SCC算法VS运行弗洛伊德，沃肖尔

Answer 1:

以下功能Scala代码生成的地图分配给图的每个节点代表。每个代表识别一个强连通分量。该代码是基于的Tarjan的算法强连通分量。

为了了解该算法可能足以理解褶皱和合同dfs功能。

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

我测试过的代码只对维基百科页面上找到的例子图。

差异势在必行版本

相较于原来的实现，我的版本避免明确地释放堆栈和简单的使用适当的（非tail-）递归函数。堆栈是由称为持续映射表示path代替。在我的第一个版本，我用一个List作为堆栈; 但是这是低效率的，因为它必须被搜索的包含元素。

效率

该代码是相当有效的。对于每个边缘，则必须更新和/或访问不可变的映射path ，费用O(log|N|)总共O(|E| log|N|) 这是相对于O(|E|)由势在必行版本来实现的。

线性时间实现

在克里斯·奥卡萨基的答案给出了在Haskell的线性时间的解决方案寻找强连通分量。它们的实现是基于kosaraju算法寻找的SCC，这基本上需要两个深度优先遍历。论文的主要贡献似乎是在Haskell懒，线性时间DFS实现。

它们需要以达到溶液具有一组具有一个线性时间什么O(1)单加和成员资格测试。这基本上是同样的问题，使得在这个答案给出的解决方案具有比势在必行解决方案更高的复杂性。他们与国家的线程在Haskell，也可在斯卡拉（见Scalaz）进行解决。所以，如果有人愿意让代码相当复杂，它是可以实现的Tarjan的SCC算法的功能O(|E|)版本。

Answer 2:

见懒惰深度优先搜索和线性图算法在Haskell由大卫国王和约翰Launchbury。它描述了一个实用的风格很多图形算法，包括鳞状细胞癌。

Answer 3:

看看https://github.com/jordanlewis/data.union-find ，一个Clojure的实现算法。它八九不离十伪装成一个数据结构，但算法都在那里。而且它的纯功能性的，当然。