Home

Motivation

This code was inspired by an interview question. In order to explain a loop detection algorithm in a directed graph I tried to come up with a quick and dirty piece of code during that interview, but it proved to be more time consuming than I thought. I worked for a while on applying the Quartz platform at Bank of America Merrill Lynch and the question was to test my understanding of one of the cornerstone components of it, the DAG, a.k.a. directed acyclic graph. So, I decided to write a naive dependency graph to test my understanding (and refresh the memory) of DAG.

Except for some syntactic resemblance due to use of decorators this has nothing in common with the actual Quartz code, and it is both my intent and obligation to keep it this way. See also Prior Art section below.

Example

The code below shows a single traced-enabled class with interdependent attributes being evaluated in the context of a graph.

class Diamond(traced.Traceable):
    @traced.Cell
    def X(self):
        return 6

    @traced.Cell
    def Y1(self):
        return self.X() * 2

    @traced.Cell
    def Y2(self):
        return self.X() // 2

    @traced.Cell
    def Z(self):
        return self.Y1() + self.Y2()

class SimpleTest(unittest.TestCase):
    def test_diamond(self):
        with traced.Graph():
            diamond = Diamond()
            self.assertEqual(15, diamond.Z())

Name: traced

The code allows one to trace dependencies between cells in a directed graph, hence traced. It's also short enough for a Python package name.

License: LGPL v3

This is more of a learning exercise and the industrial-strength implementations of DAG in Python already exist. Commercial use of this code, still perfectly acceptable and legal under LGPL, is therefore taking a back seat to the desire to expose the implementation and keep any modifications open.

Prior Art

While [tiny part of] Quartz served as inspiration behind this code, there are other precedents. Cellulose and more traditional spreadsheet PySpread would have similar functionality. This Coding the Markets blog post on Python DAGs pointed me to Man Systematic Strategies Data-flow (MDF) package (see also MDF documentation). A new (as of this writing) player to watch in this space is Washington Square Technologies.