Tarjan强连通分量算法的函数实现

Question

我继续在Scala中implemented textbook version of Tarjan's SCC algorithm。然而，我不喜欢它的代码--它是非常强制的/过程性的，有很多变化的状态和记账索引。有没有更“功能性”的算法版本？我认为，与函数式版本不同，命令式版本的算法隐藏了算法背后的核心思想。我使用这种特殊的算法找到了someone else encountering the same problem，但是我还不能将他的Clojure代码转换成particular。

注意:如果有人想要实验，我有一个很好的设置，可以生成随机图和tests your SCC algorithm vs running Floyd-Warshall

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

我只在维基百科页面上找到的示例图上测试了代码。

与命令式版本的区别

与最初的实现相比，我的版本避免显式地展开堆栈，而只是使用适当的(非尾部)递归函数。相反，该堆栈由名为path的持久映射表示。在我的第一个版本中，我使用List作为堆栈；但效率较低，因为必须搜索包含元素的堆栈。

效率

代码是相当高效的。对于每条边，您必须更新和/或访问不可变的映射path，这会耗费O(log|N|)，总共需要O(|E| log|N|)。这与命令式版本实现的O(|E|)形成了鲜明对比。

线性时间实现

Chris Okasaki的答案中的论文在Haskell中给出了寻找强连接分量的线性时间解决方案。它们的实现基于Kosaraju的查找SCC的算法，该算法基本上需要两次深度优先遍历。这篇论文的主要贡献似乎是在Haskell中实现了一个惰性的线性时间DFS。

要实现线性时间解决方案，他们需要的是具有O(1)单例添加和成员资格测试的集合。这基本上是同一个问题，使得这个答案中给出的解决方案比命令式解决方案具有更高的复杂性。他们在Haskell中使用状态线程来解决这个问题，这也可以在Scala中完成(参见Scalaz)。因此，如果愿意让代码变得相当复杂，可以将Tarjan的SCC算法实现为一个功能强大的O(|E|)版本。

Answer 2

请参阅大卫·金和约翰·兰奇伯里的Lazy Depth-First Search and Linear Graph Algorithms in Haskell。它以函数式风格描述了许多图形算法，包括SCC。

Answer 3

看看https://github.com/jordanlewis/data.union-find，它是该算法的Clojure实现。它有点伪装成一种数据结构，但算法都在那里。当然，它是纯功能的。