Resolving dependencies in a directed acyclic graph with a topological sort
In this recipe, we will show an application of a well-known graph algorithm: topological sorting. Let's consider a directed graph describing dependencies between items. For example, in a package manager, before we can install a given package P, we may need to install dependent packages.
The set of dependencies forms a directed graph. With topological sorting, the package manager can resolve the dependencies and find the right installation order of the packages.
Topological sorting has many other applications. Here, we will illustrate this notion on real data from the Debian package manager. We will find the installation order of the required packages for IPython.
Getting ready ...
Get IPython Interactive Computing and Visualization Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
