The function clojure.tools.namespace.dependency/transitive 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).

None

Show:

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.

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).

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 ?

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

September 19, 2014, 3:08 PM

Included in release 0.2.6

Completed

None

None

Code

Major