Circular dependency checker can be slow

[vbraun]

Angular runs circular-dependency-plugin on each incremental build, so speed is somewhat important

On a largeish hybrid app with complicate imports (in particular, the angularjs part doesn't use modules / barrel files, so the import graph is pretty complicated) a no-change incremental build is about 8s with and 3s without circular dependency checking on a state of the art desktop.

Initially reported at https://github.com/angular/angular-cli/issues/19794

There is a PR languishing at #49, but Tarjan's algorithm is also suboptimal for detecting whether there is a cycle (however it is a good algorithm for enumerating all cycles).

See also: https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

[hedgepigdaniel]

Tarjan's algorithm is also suboptimal for detecting whether there is a cycle (however it is a good algorithm for enumerating all cycles).

It's linear in the number of modules + dependencies. Can you do better than that to find if a cycle exists?