# Tarjan’s strongly connected components algorithm in Scala

Recently I have been researching a matching algorithm for a certain sector of a swap market. This turned into a graph problem requiring finding strongly connected components of the graph (and then cycles) to generate possible multi-broker trades. I turned to Wikipedia for help and found this nice Tarjan’s algorithm:

I quickly coded it up as-is in Scala, my language of choice currently. All worked fine, but it did not feel right in Scala, relying so heavily on mutable state. It took me a bit but I managed to rework the algorithm into a purely functional style. Here is the code:

Of course, I had to cover the implementation with tests – how else would I know Tarjan was right :-)? Below are my unit tests in Cucumber:

The whole project is available in my GitHub repo: https://github.com/prystupa/scala-graph-algo

Hi Eugene,

Thanks for sharing !

I got one question since I wasn’t able to run your code.

I suppose the process to run it is :

val scc = new StronglyConnectedComponentsAlgo

scc.compute(Vector[Set[Int])

But I don’t understand what’s your input because, for me, it’s suppose to be (for input AND output) a Vector[Map[Int,Set[Int]]] .

I tried to go to your unit test but that wasn’t a success :-)

Thanks again !

F