## 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 !