Tarjan强连通组件算法的功能实现

Question

我继续在Scala中实现了Tarjan的SCC算法的教科书版本.但是,我不喜欢代码 - 这是非常必要/程序化的,有很多变异的状态和簿记索引.是否有更多"功能"版本的算法？我相信算法的命令式版本隐藏了算法背后的核心思想,而不像功能版本.我发现其他人遇到了与此特定算法相同的问题,但我无法将他的Clojure代码转换为idomatic Sc​​ala.

注意:如果有人想要试验,我有一个很好的设置,可以生成随机图并测试你的SCC算法与运行Floyd-Warshall

Answer 1

请参阅David King和John Launchbury 在Haskell中的Lazy Depth-First Search和Linear Graph Algorithms.它以功能样式描述了许多图算法,包括SCC.

Answer 2

以下功能性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|)版本.