Use linear time algorithm to calculate transitive dependencies, instead of current exponential time algorithm


The function takes exponential time for cases where there are an exponential number of paths in the DAG (directed acyclic graph) of dependencies. I discovered this when using tools.namespace on the namespaces of project core.typed, where the total time for finding a topological order was several minutes on a reasonably fast machine.

It is easy to calculate transitive dependents/dependencies in linear time in the worst case (linear in the number of dependency arcs in the DAG).




Stuart Sierra
September 19, 2014, 3:08 PM

Included in release 0.2.6

Stuart Sierra
July 11, 2014, 10:42 PM

Merged on master as of commit 3f946380. Will be in release 0.2.5.

New functions are named transitive-dependencies-set and transitive-dependents-set.

Stuart Sierra
June 6, 2014, 4:27 PM

This is a valuable improvement — thanks, Andy!

I don't want to add more methods to the protocol, but I don't see any way to avoid it right now. Ideally, transitive-dependencies would change to take a set, but that breaks backwards-compatibility.

I'll give it a week or so to think about naming:

  • transitive-dependencies-of-node-set is too long

  • transitive-dependencies-all ?

  • transitive-dependencies-set ?

  • all-transitive-dependencies ?

Andy Fingerhut
June 3, 2014, 9:20 PM

Patch linear-time-no-debug.patch is one way to implement transitive dependencies in linear time. It also introduces additional protocol functions, which may not be desired. I am definitely open to suggestions on what kind of change you would like to see here (assuming you want any changes at all).

Andy Fingerhut
June 3, 2014, 9:18 PM

Patch demo-exponential-algo.patch only adds some test cases that demonstrate the exponential running time of the current algorithm for calculating transitive dependencies.

Your pinned fields
Click on the next to a field label to start pinning.


Stuart Sierra


Andy Fingerhut