Sunday, May 22, 2011

Circular dependency detection revisited

In last blog post I mentioned the much more efficient SCC detection algorithm by Tarjan. As it turns out, SWI-PROLOG's clpfd library contains an implementation of the SCC algorithm.
The predicates that implement it are not exposed by the clpfd library though. I got help from the author of the library, Markus Triska, to use the scc algorithm outside the library, and the results are incorporated in pycdep's latest source code.

Cycle detection now is as simple as typing

With this better algorithm, the cycle detection on the 2800+ files and 19000 include dependencies program I mentioned in the previous blog post now only takes 6 seconds.

Thanks again, Markus Triska.

No comments:

Post a Comment