Tarjan algorithm - Python to scala

I'm trying to translate the recursive python code for tarjan algorithm to scala and especially this part :

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

I know that there's tarjan algorithm in scala here or here but it doesn't return good result and translate it from python help me understand it.

Here's what I have :

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
}

I know this isn't the scala way at all (and not clean ...) but I'm planning to slowly change it to a more functional style when I get the first version working.

For now, I got this error :

type mismatch;  found   : Unit  required: Int

at this line

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

I think it's coming from this line but I'm not sure :

if( !(index.contains(w)) 

But it's really hard to debug it since I can't just println my mistakes ...

Thanks !

Here's a fairly literal translation of the 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
}

It produces the same output on e.g.:

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

The biggest problem with your implementation was the return type of visit (which should have been Unit, not Int) and the fact that you were iterating over the graph's items instead of the graph's keys in the final for-comprehension, but I've made a number of other edits for style and clarity (while still keeping the basic shape).

Tarjan's algorithm for Scala � GitHub, import scala.collection.mutable. // See python version: https://github.com/ bwesterb/py-tarjan. /**. * Tarjan's algorithm is an algorithm in graph theory for finding the� We have discussed Kosaraju’s algorithm for strongly connected components. The previously discussed algorithm requires two DFS traversals of a Graph. In this post, Tarjan’s algorithm is discussed that requires only one DFS traversal. Tarjan Algorithm is based on following facts: 1. DFS search produces a DFS tree/forest 2.

Here is an iterative version. It is a translation from the recursive version of the algorithm in 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)

}

Running the example graph in the Wikipedia article:

val g = new SparseDG(Seq(
        Arc("1","2"),
        Arc("2","3"),
        Arc("3","1"),
        Arc("4","2"),
        Arc("4","3"),
        Arc("6","3"),
        Arc("6","7"),
        Arc("7","6"),
        Arc("4","5"),
        Arc("5","4"),
        Arc("5","6"),
        Arc("8","5"),
        Arc("8","8"),
        Arc("8","7")
      ))

g.tarjan_iterative

returns:

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

Tarjan algorithm - Python to scala - - Diya, i'm trying translate recursive python code tarjan algorithm scala , part : def tarjan_recursive(g): s = [] s_set = set() index = {} lowlink = {} ret = [] def visit(v): index[v]� Using Tarjan’s algorithm, one can efficiently compute the transitive closure of a graph. (Given a graph G, the transitive closure of G is a graph that contains the same vertices and contains an edge from v to w if and only if there is a path from v to w in G.) The transitive closure is implemented in tarjan.tc:

I know this post is old, but I have lately been working with the implementation of Tarjans algorithm in Scala. In the implementation of the code, I was looking at this post and it occurred to me, that it could be done in a simpler way:

case class Edge[A](from: A, to: Set[A])

class TarjanGraph[A](src: Iterable[Edge[A]]) {
  lazy val trajan: mutable.Buffer[mutable.Buffer[A]] = {
    var s = mutable.Buffer.empty[A] //Stack to keep track of nodes reachable from current node
    val index = mutable.Map.empty[A, Int] //index of each node
    val lowLink = mutable.Map.empty[A, Int] //The smallest index reachable from the node
    val ret = mutable.Buffer.empty[mutable.Buffer[A]] //Keep track of SCC in graph
def visit(v: A): Unit = {
  //Set index and lowlink of node on first visit
  index(v) = index.size
  lowLink(v) = index(v)
  //Add to stack
  s += v
  if (src.exists(_.from == v)) {
    for (w <- src.find(e => e.from == v).head.to) {
      if (!index.contains(w)) { //Node is not explored yet
        //Perform DFS from node W
        visit(w)
        //Update the lowlink value of v so it has the value of the lowest node reachable from itself and from node w
        lowLink(v) = math.min(lowLink(w), lowLink(v))
      } else if (s.contains(w)) {
        // Node w is on the stack meaning - it means there is a path from w to v
        // and since node w is a neighbor to node v there is also a path from v to w
        lowLink(v) = math.min(lowLink(v), index(w))
      }
    }
  }
  //The lowlink value haven't been updated meaning it is the root of a cycle/SCC
  if (lowLink(v) == index(v)) {
    //Add the elements to the cycle that has been added to the stack and whose lowlink has been updated by node v's lowlink
    //This is the elements on the stack that is placed behind v
    val n = s.length - s.indexOf(v)
    ret += s.takeRight(n)
    //Remove these elements from the stack
    s.dropRightInPlace(n)
  }
}

//Perform a DFS from  all no nodes that hasn't been explored
src.foreach(v => if (!index.contains(v.from)) visit(v.from))
ret
  }

  // A cycle exist if there is a SCC with at least two components
  lazy val hasCycle: Boolean = trajan.exists(_.size >= 2)
  lazy val trajanCycle: Iterable[Seq[A]] = trajan.filter(_.size >= 2).distinct.map(_.toSeq).toSeq
  lazy val topologicalSortedEdges: Seq[Edge[A]] =
    if (hasCycle) Seq[Edge[A]]()
    else trajan.flatten.reverse.flatMap(x => src.find(_.from == x)).toSeq
}

Tarjan's Algorithm to find Strongly Connected Components , Following is implementation of Tarjan's algorithm to print all SCCs. C/C++; Python. C/C++. tarjan's algorithm python (2) I went ahead and implemented the textbook version of Tarjan's SCC algorithm in Scala. However, I dislike the code - it is very

Tarjan, Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a graph. It runs in linear time,� Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected components of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. Tarjan's algorithm is named for its inventor, Robert Tarjan.

Tarjan's strongly connected components algorithm, Tarjan's algorithm is an algorithm in graph theory for finding the strongly connected "Robust topological sorting and Tarjan's algorithm in Python". Retrieved 9� Tarjan's algorithm is a procedure for finding strongly connected components of a directed graph. A strongly connected component is a maximum set of vertices, in which exists at least one oriented path between every two vertices. Description. Tarjan's algorithm is based on depth first search (DFS).

Tarjan's Algorithm for Strongly Connected Components, Tarjan's Algorithm is used to find strongly connected components of a directed graph. It requires only one DFS traversal to implement this� Tarjan's algorithm takes as input a directed (possibly cyclic!) graph and returns as output its strongly connected components in a topological order. In various cases, dependencies might be cyclic and a group of interdependant actions must be executed simultaneously. It is not uncommon that the

Comments
  • Hey Travis, Thank you for your help. I though I had resolve the problem with the graph's items but no :/ I'm gonna check Buffer now. Thank you again !