hedgepigdaniel
commented
2 years ago 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?
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