diff options
author | Li Haoyi <haoyi.sg@gmail.com> | 2018-12-19 19:04:55 +0800 |
---|---|---|
committer | Li Haoyi <haoyi.sg@gmail.com> | 2018-12-19 19:04:55 +0800 |
commit | 497f044545d8a8299c963e8e3dd5241882270362 (patch) | |
tree | d4e2fa124983377df9c2f8631ee4804a97cd74db /main/core/src/eval/Tarjans.scala | |
parent | b44fe2753c62349b3b133d1da0e41a19178233a1 (diff) | |
parent | de175e69977082e35539097a54d381e465dddf8e (diff) | |
download | mill-497f044545d8a8299c963e8e3dd5241882270362.tar.gz mill-497f044545d8a8299c963e8e3dd5241882270362.tar.bz2 mill-497f044545d8a8299c963e8e3dd5241882270362.zip |
Merge branch 'master' into bump-zinc
Diffstat (limited to 'main/core/src/eval/Tarjans.scala')
-rw-r--r-- | main/core/src/eval/Tarjans.scala | 51 |
1 files changed, 51 insertions, 0 deletions
diff --git a/main/core/src/eval/Tarjans.scala b/main/core/src/eval/Tarjans.scala new file mode 100644 index 00000000..ade335a9 --- /dev/null +++ b/main/core/src/eval/Tarjans.scala @@ -0,0 +1,51 @@ +package mill.eval + +import scala.collection.mutable + +// Adapted from +// https://github.com/indy256/codelibrary/blob/c52247216258e84aac442a23273b7d8306ef757b/java/src/SCCTarjan.java +object Tarjans { + def apply(graph0: TraversableOnce[TraversableOnce[Int]]): Seq[Seq[Int]] = { + val graph = graph0.map(_.toArray).toArray + val n = graph.length + val visited = new Array[Boolean](n) + val stack = mutable.ArrayBuffer.empty[Integer] + var time = 0 + val lowlink = new Array[Int](n) + val components = mutable.ArrayBuffer.empty[Seq[Int]] + + + for (u <- 0 until n) { + if (!visited(u)) dfs(u) + } + + def dfs(u: Int): Unit = { + lowlink(u) = time + time += 1 + visited(u) = true + stack.append(u) + var isComponentRoot = true + for (v <- graph(u)) { + if (!visited(v)) dfs(v) + if (lowlink(u) > lowlink(v)) { + lowlink(u) = lowlink(v) + isComponentRoot = false + } + } + if (isComponentRoot) { + val component = mutable.Buffer.empty[Int] + + var done = false + while (!done) { + val x = stack.last + stack.remove(stack.length - 1) + component.append(x) + lowlink(x) = Integer.MAX_VALUE + if (x == u) done = true + } + components.append(component) + } + } + components + } +} |