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