从Python到s的Tarjan算法

Question

我正在尝试将递归python code for tarjan algorithm转换为scala，尤其是这一部分：

def tarjan_recursive(g):
        S = []
        S_set = set()
        index = {}
        lowlink = {}
        ret = []
        def visit(v):
                index[v] = len(index)
                lowlink[v] = index[v]
                S.append(v)
                S_set.add(v)

                for w in g.get(v,()):
                        print(w)
                        if w not in index:
                                visit(w)
                                lowlink[v] = min(lowlink[w], lowlink[v])
                        elif w in S_set:
                                lowlink[v] = min(lowlink[v], index[w])
                if lowlink[v] == index[v]:
                        scc = []
                        w = None
                        while v != w:
                                w = S.pop()
                                scc.append(w)
                                S_set.remove(w)
                        ret.append(scc)

        for v in g:
                print(index)
                if not v in index:
                        visit(v)
        return ret

我知道scala中有tarjan算法here或{a3}，但它没有返回好的结果，并从python中翻译它来帮助我理解它。在

以下是我所拥有的：

^{pr2}$

我知道这根本不是scala的方式（而且不干净…），但我计划在第一个版本开始工作时，慢慢地将它改为更具功能性的风格。在

现在，我得到了一个错误：

type mismatch;  found   : Unit  required: Int

在这条线上

if(lowlink(v)==index(v)){ 

我想是从这条线传来的，但我不确定：

if( !(index.contains(w)) 

但调试起来真的很难，因为我不能直接打印我的错误。。。在

谢谢！在

Answer 1

这是一个迭代版本。它是Wikipedia中算法的递归版本的翻译。在

case class Arc[A](from:A, to:A)

class SparseDG[A](src: Iterable[Arc[A]]) {

  val verts = (src.map(_.from) ++ src.map(_.to)).toSet.toIndexedSeq
  val qVert = verts.size
  val vertMap = verts.zipWithIndex.toMap
  val indexedSrc = src.map{ arc => Arc(vertMap(arc.from), vertMap(arc.to)) }

  val exit  = (0 until qVert)
              .map(v => indexedSrc.filter(_.from == v).map(_.to).toIndexedSeq)


  lazy val tarjan_iterative: Seq[Seq[A]] = {
    trait Step
    case object SetDepth           extends Step
    case object ConsiderSuccessors extends Step
    case object CalcLowlink        extends Step
    case object PopIfRoot          extends Step
    case class StackFrame(v:Int, next:Step)

    val result = Buffer[Seq[A]]()
    val index = new Array[Int](qVert).map(_ => -1)   // -1 = undefined
    val lowlink = new Array[Int](qVert).map(_ => -1) // -1 = undefined
    val wIndex = new Array[Int](qVert)               // used to iterate w nodes
    var _index = 0
    val s = Stack[Int]()
    val isRemoved = BitSet()
    val strongconnect = Stack[StackFrame]()

    (0 until qVert).foreach { v_idx =>
      if(index(v_idx) == -1) {
        strongconnect.push(StackFrame(v_idx, SetDepth))
        while(!strongconnect.isEmpty) {
          val StackFrame(v, step) = strongconnect.pop()
          step match {
            case SetDepth =>
              index(v) = _index
              lowlink(v) = _index
              _index += 1
              s.push(v)
              isRemoved.remove(v)
              strongconnect.push(StackFrame(v, ConsiderSuccessors))

            case ConsiderSuccessors =>
              if(wIndex(v) < exit(v).size){
                val w = exit(v)(wIndex(v))
                if(index(w) == -1){
                  strongconnect.push(StackFrame(v, CalcLowlink))
                  strongconnect.push(StackFrame(w, SetDepth))
                }
                else{
                  if(!isRemoved.contains(w)){
                    if(lowlink(v) > lowlink(w)) lowlink(v) = index(w)
                  }
                  wIndex(v) += 1
                  strongconnect.push(StackFrame(v, ConsiderSuccessors))
                }
              }
              else{
                strongconnect.push(StackFrame(v, PopIfRoot))
              }

            case CalcLowlink =>
              val w = exit(v)(wIndex(v))
              if(lowlink(v) > lowlink(w)) lowlink(v) = lowlink(w)
              wIndex(v) += 1
              strongconnect.push(StackFrame(v, ConsiderSuccessors))

            case PopIfRoot =>
              if(index(v) == lowlink(v)){
                val buf = Buffer[A]()
                var w = 0
                do{
                  w = s.pop()
                  isRemoved += w
                  buf += verts(w)
                }
                while(w != v)
                result += buf.toSeq
              }
          }
        }
      }
    }
    result.toSeq
  }

  lazy val hasCycle = tarjan_iterative.find(_.size >= 2).isDefined

  lazy val topologicalSort =
    if(hasCycle) None
    else         Some(tarjan_iterative.flatten.reverse)

}

运行维基百科文章中的示例图：

^{pr2}$

退货：

ArrayBuffer(ArrayBuffer(1, 3, 2), ArrayBuffer(7, 6), ArrayBuffer(4, 5), ArrayBuffer(8))

Answer 2

以下是Python的直译：

def tj_recursive(g: Map[Int, List[Int]])= {
  val s = mutable.Buffer.empty[Int]
  val s_set = mutable.Set.empty[Int]
  val index = mutable.Map.empty[Int, Int]
  val lowlink = mutable.Map.empty[Int, Int]
  val ret = mutable.Buffer.empty[mutable.Buffer[Int]]

  def visit(v: Int): Unit = {
    index(v) = index.size
    lowlink(v) = index(v)
    s += v
    s_set += v

    for (w <- g(v)) {
      if (!index.contains(w)) {
        visit(w)
        lowlink(v) = math.min(lowlink(w), lowlink(v))
      } else if (s_set(w)) {
        lowlink(v) = math.min(lowlink(v), index(w))
      }
    }

    if (lowlink(v) == index(v)) {
      val scc = mutable.Buffer.empty[Int]
      var w = -1

      while(v != w) {
        w = s.remove(s.size - 1)
        scc += w
        s_set -= w
      }

      ret += scc
    }
  }

  for (v <- g.keys) if (!index.contains(v)) visit(v)
  ret
}

它在以下方面产生相同的输出：

^{pr2}$

实现中最大的问题是返回类型visit（应该是Unit，而不是{}），并且在最后的for-理解中，迭代了图的项而不是图的键，但为了风格和清晰度，我做了一些其他的编辑（同时仍然保持基本形状）。在