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

## Description

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

## Environment

## Activity

Included in release 0.2.6

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.

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 ?

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

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