The other day I finally implemented a feature in Ledger which I’d avoided doing for a full half-year. The reason? Every time I thought about it, my brain kept shutting down. It seems my brain doesn’t care for math much, or for mathy problems, so it always seemed as if something better needed doing…
The problem turned out to be a fairly straightforward one, it just required sitting down and mapping it out for a couple of hours before the coding began. Here’s the synopsis:
You have a network of N nodes, each of which can be connected to N-1 other nodes. There can be multiple connections between any two nodes, where each connection has a date — but no two connections between the same nodes can have the same date.
Given a start node, a query date, and a set of target nodes (which may be zero, one or many), find the shortest and youngest path that is not older than the query date, from the start node to each of the target nodes.
Ledger uses this algorithm to record price conversions between commodities, and to later render each commodity into a market value relative to another known commodity. Sometimes such renderings are not possible, or sometimes they require multiple conversion steps before a value can be found.
For example, if I bought 10 shares of AAPL for $30.00, and later exchanged $10.00 for 9.83 CAD, and at one point exchanged 80 EUR for 100 CAD, then how many EUR are my shares of AAPL worth?
Previously Ledger could only render AAPL in terms of dollars, but now it can finally report any commodity in terms of any other, provided there exists a path of traversal between the two nodes which is older than or equal to the query date.
If you enjoyed this article, please consider sharing it!
The problem itself sounds pretty interesting. Can you give some details on the algorithm you used?
The data storage is as follows: Each node maintains N binary trees, where each tree records the historical prices for that node in terms of another node. So if the price for AAPL is known in both EUR and CAD, then the AAPL nodes will have two binary trees with each of those price histories.
When looking for a price, I do a recursive traversal of the nodes. I look at each binary tree for its most current price relative to the query date. I think traverse the node relating to that price’s commodity, and so on. As I traverse each node, I mark it with a flag to note that it’s currently being traversed, so that I don’t end up in an infinite loop. Once the recursion for that leg of the algorithm completes, I clear the flag.
It’s possible that a particular node will get visited in this way multiple times, but it’s also possible that the “oldest acceptable date” value will change on each iteration. Because I’m not just looking for a price before the query date, but the price which is nearest to it, no matter how long that path may be.
At each step where I find a suitable conversion, I must multiply that conversion factor with every price in the recursion stack, to arrive at a final conversion that can turn the source value into the target value.
The code for the algorithm is located here: http://tinyurl.com/dkkxnc