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:

	algorithm tarjan is
	input: graph G = (V, E)
	output: set of strongly connected components (sets of vertices)
	index := 0
	S := empty
	for each v in V do
	if (v.index is undefined) then
	strongconnect(v)
	end if
	repeat
	function strongconnect(v)
	// Set the depth index for v to the smallest unused index
	v.index := index
	v.lowlink := index
	index := index + 1
	S.push(v)
	// Consider successors of v
	for each (v, w) in E do
	if (w.index is undefined) then
	// Successor w has not yet been visited; recurse on it
	strongconnect(w)
	v.lowlink := min(v.lowlink, w.lowlink)
	else if (w is in S) then
	// Successor w is in stack S and hence in the current SCC
	v.lowlink := min(v.lowlink, w.index)
	end if
	repeat
	// If v is a root node, pop the stack and generate an SCC
	if (v.lowlink = v.index) then
	start a new strongly connected component
	repeat
	w := S.pop()
	add w to current strongly connected component
	until (w = v)
	output the current strongly connected component
	end if
	end function

view raw

TarjanCssAlgoPseudocode.txt

hosted with ❤ by GitHub

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:

Matching Engine – Market Orders (Best Limit Rule)

In the previous post I integrated a new order type – market – into the order book, implemented price and time priority rules for market orders, and started matching them. I tested and implemented the simplest case – matching incoming market order against outstanding limit order. In this post I am going to continue using Cucumber to test-drive the implementation of another use case: matching incoming limit order to outstanding market one.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Crossing Limit Order with Outstanding Market Orders

What happens when an incoming limit order crosses with a market order in the opposite book? At what price should they cross? The actual rule is a bit involved:

• If the opposite book does not have outstanding limit orders, then the trade settles at the incoming order’s limit price
• “Best limit” price improvement rule: if the opposite book does have limit orders, the trade settles at the better of two prices – the incoming order’s limit or the best limit from the opposite book – the term “better of two prices” is from the point of view of the incoming limit order. In other words, if incoming limit order would have crossed with outstanding opposite “best limit” order in the absence of market order, then trade at that, potentially improved, “best limit” price.

To implement this logic it is useful to have OrderBook class maintain the notion of “best limit” price at any time. Lets capture the different possible scenarios in a Cucumber script:

Matching Engine – Market Orders (Core)

In the first two posts in this series, Prototyping a Matching Engine with Scala and Cucumber and Matching Engine – Crossing Limit Orders, we built a simple limit order book and a matching algorithm that crosses limit orders of opposite sides. In this post I am going to continue using Cucumber to test-drive the implementation of order book and matching engine – this time we are going to add support for another fundamental order type – market order.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Maintaining Market Orders in the Order Book

First of all lets model market order as a case class:

case class MarketOrder(broker: String, side: Side, qty: Double) extends Order

view raw

Order.scala

hosted with ❤ by GitHub

	sealed trait PriceLevel
	case class LimitPrice(limit: Double) extends PriceLevel
	case object MarketPrice extends PriceLevel

view raw

PriceLevel.scala

hosted with ❤ by GitHub

	object OrderType {
	def all(): PartialFunction[Order, OrderType] = {
	// Unmodified code omitted
	// …
	case self@MarketOrder(_, _, _) => new OrderType {
	def bookDisplay: String = "MO"
	def price: PriceLevel = MarketPrice
	def crossesAt(price: Double): Boolean = true
	def decreasedBy(qty: Double): MarketOrder = self.copy(qty = self.qty – qty)
	}
	}
	}

view raw

OrderType.scala

hosted with ❤ by GitHub

By definition market orders cross at any price level (line 13). “MO” (line 9) is the code we use to display outstanding market orders in the book.

Since market orders are ready to cross at any price level they sort higher than any limit orders in the order book (they have a higher price priority). Among different market orders time priority is maintained – the orders that enter the order book earlier are closer to the top. Let capture these rules in a form of Cucumber scenarios (Buy and Sell tests are very similar, so I’m using an outline for brevity):

Matching Engine – Crossing Limit Orders

In the first post in this series, Prototyping a Matching Engine with Scala and Cucumber, we built a simple limit order book that properly maintains price and time priority for incoming Buy or Sell orders. In this post I am going to continue using Cucumber to test-drive the implementation of an algorithm that matches incoming limit orders against the opposite side order book.  The complete source code for this and other posts in the series is available from my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

Introducing Matching Engine

So far we have dealt with two independent order books, one for Buy orders and one for Sell orders. Now when we are going to match opposite side orders, it is useful to introduce a concept of matching engine – an algorithm that operates on both order books and matches and determines the prices at which orders are matched:

	sealed trait OrderBookEvent
	case class Trade(buyingBroker: String, sellingBroker: String,
	price: Double, qty: Double) extends OrderBookEvent

view raw

OrderBookEvent.scala

hosted with ❤ by GitHub

	class MatchingEngine(buy: OrderBook, sell: OrderBook, orderTypes: (Order => OrderType))
	extends mutable.Publisher[OrderBookEvent] {
	def acceptOrder(order: Order) = throw new NotImplementedError()
	}

view raw

MatchingEngine.scala

hosted with ❤ by GitHub

Prototyping a Matching Engine with Scala and Cucumber

Implementing matching engine correctly can be tricky when you consider variety of order types offered by real exchanges. In addition to core limit and market orders exchanges offer additional execution strategies: market-to-limit, various types of pegged orders, stop orders, and others. Matching different order types is non-trivial, and there are many edge cases. In addition there are different rules for matching orders when session opens (i.e. auction mode) vs. continuous trading.

The resulting complexity strongly suggests a test driven approach for developing correctly working engine. In the following series of posts I’m going to gradually build a prototype of a functionally rich equity matching engine. To make things interesting I’m going to model the functionality based on a real, publicly available specs from Euronext: https://europeanequities.nyx.com/trading/order-types

The complete source code for every posts in the series is available in my GitHub repo: https://github.com/prystupa/scala-cucumber-matching-engine

The foundation – limit order book

Implementing a matching engine inevitably requires maintaining buy and sell order books. In this first post I am going to test drive the implementation of a simple limit order book using Scala and Cucumber.

First lets start defining the domain model. All orders are created by brokers, are either to sell or to buy a given instrument, and have a known size and quantity. Limit orders, in addition, define a limit price, and will not execute if market conditions are inferior to the limit price:

	trait Side
	case object Buy extends Side
	case object Sell extends Side

view raw

Side.scala

hosted with ❤ by GitHub

	trait Order {
	val broker: String
	val qty: Double
	val side: Side
	}
	case class LimitOrder(broker: String, side: Side, qty: Double, limit: Double) extends Order

view raw

Order.scala

hosted with ❤ by GitHub

	sealed trait PriceLevel
	case class LimitPrice(limit: Double) extends PriceLevel

view raw

PriceLevel.scala

hosted with ❤ by GitHub

	trait OrderType {
	def bookDisplay: String
	def price: PriceLevel
	}
	object OrderType {
	def all(): PartialFunction[Order, OrderType] = {
	case LimitOrder(_, _, _, limit) => new OrderType {
	def bookDisplay: String = limit.toString
	def price: PriceLevel = LimitPrice(limit)
	}
	}
	}

view raw

OrderType.scala

hosted with ❤ by GitHub