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

Advertisements
1 comment
  1. fa said:

    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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: