python - Tarjan 算法 - Python 到 scala

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或here但它没有返回好的结果并从 python 翻译它帮助我理解它。

这是我所拥有的:

def tj_recursive(g: Map[Int,List[Int]])= {
        var s : mutable.ListBuffer[Int] = new mutable.ListBuffer()
        var s_set : mutable.Set[Int] = mutable.Set()
        var index : mutable.Map[Int,Int] =  mutable.Map()
        var lowlink : mutable.Map[Int,Int]=  mutable.Map()
        var ret : mutable.Map[Int,mutable.ListBuffer[Int]]= mutable.Map()

        def visit(v: Int):Int = {
                 index(v) = index.size
               lowlink(v) = index(v)
               var zz :List[Int]= gg.get(v).toList(0)
                            for( w <- zz) {
                  if( !(index.contains(w)) ){
                     visit(w)
                     lowlink(v) = List(lowlink(w),lowlink(v)).min
                   }else if(s_set.contains(w)){
                     lowlink(v)=List(lowlink(v),index(w)).min
                   }
               }

               if(lowlink(v)==index(v)){
                  var scc:mutable.ListBuffer[Int] = new mutable.ListBuffer()
                  var w:Int=null.asInstanceOf[Int]
                  while(v!=w){
                    w= s.last
                    scc+=w
                    s_set-=w
                  }
           ret+=scc
        }
        }

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

我知道这根本不是 scala 方式(而且不干净......)，但我计划在第一个版本运行时慢慢将其更改为更实用的样式.

目前，我收到此错误:

type mismatch;  found   : Unit  required: Int

在这一行

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

我认为它来自这条线，但我不确定:

if( !(index.contains(w)) 

但是调试它真的很难，因为我不能只打印我的错误......

谢谢!

Answer 1

这是 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
}

它会产生相同的输出，例如:

tj_recursive(Map(
  1 -> List(2),    2 -> List(1, 5), 3 -> List(4),
  4 -> List(3, 5), 5 -> List(6),    6 -> List(7),
  7 -> List(8),    8 -> List(6, 9), 9 -> Nil
))

您的实现中最大的问题是 visit 的返回类型(应该是 Unit，而不是 Int)，而且事实上您在最终的for理解中迭代了图表的项目而不是图表的键，但为了风格和清晰度，我进行了许多其他编辑(同时仍然保持基本形状)。