Include Tarjan's algorithm, for doing a topological sort which elegantly handles cycles

1 files changed, 61 insertions, 0 deletions

diff --git a/src/main/scala/hbt/Tarjans.scala b/src/main/scala/hbt/Tarjans.scala
new file mode 100644
index 00000000..dc95b02f
--- /dev/null
+++ b/src/main/scala/hbt/Tarjans.scala
@@ -0,0 +1,61 @@
+package hbt
+
+import collection.mutable
+// Adapted from
+// https://github.com/indy256/codelibrary/blob/c52247216258e84aac442a23273b7d8306ef757b/java/src/SCCTarjan.java
+object Tarjans {
+  def main(args: Array[String]) = {
+    val components = Tarjans(
+      Vector(
+        Vector(1),
+        Vector(0),
+        Vector(0, 1)
+      )
+    )
+    println(components)
+  }
+
+  def apply(graph0: Seq[Seq[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
+  }
+}
\ No newline at end of file