How does Homebrew resolve dependencies?

Question

How does Homebrew (and other package managers in general) resolve dependencies? What about special cases like circular dependencies? Is there a generalized pattern, algorithm, and/or data structure for this task?

Answer 1

The general algorithm to solve dependency problems in a directed acyclic graph is called topological sorting. I'm pretty sure that's what package managers use too. This doesn't work with circular dependencies however.

For circular (run-time) dependencies you can (at least in RPM) skip checks on one of the packages or install interdependent packages "simultaneously" by specifying them on the same command line. The package manager then knows that the other package will be installed too and thus the dependency is satisfied.

I don't think there is a solution for build-time circular dependencies though.