Useful Code Part 1: Dependency Resolution Via Topological Sorting

A short post detailing how the Networkx topological sort method can be used to solve dependency resolution problems.

Sept. 27, 2021

Share with:

In software development, we often find ourselves dealing with dependency resolution of one sort or another. This can come in many flavors, but the prototypical example consists of a set of tasks which need to be executed serially, due to some tasks depending upon the output of other tasks. The extensibility challenge in this situation becomes how to add tasks in the future in a painless manner, without requiring the developer to perform any mental gymnastics about where in the ordering they need to be placed, or worse, need to do dramatic reordering of the existing tasks to accomodate them. In short, what one needs here is a algorithm to dynamically order the tasks on demand while respecting the dependency relationships between them. 

To accomplish this, we may represent the task set as a Directed Acyclic Graph and apply a Topological Sort algorithm to it. In Python this is quite easy to accomplish by utilizing the Networkx module. For instance, suppose we were to represent the dependency requirements on a set of tasks as a python dictionary, with the keys the tasks and the values as lists of dependent tasks. Then the following function will sort the dependency graph with $ \mathcal{O}(e + v) $ complexity, where $ e $ and $ v $ are the number of edges and vertices in the graph, respectively.

from typing import Callable
import networkx as nx

def sort_tasks(tasks: dict[Callable: list[Callable]]) -> list[Callable]:
    graph = nx.DiGraph()
    for task, deps in tasks.items():
        graph.add_node(task)
        for dep in deps:
            graph.add_node(dep) # idempotent
            graph.add_edge(dep, task)
    assert nx.is_directed_acyclic_graph(G=graph)
    return list(nx.topological_sort(G=graph))

This makes our prospective developer's job much easier, since they only need to know what tasks their new one depends upon to insert it into the set.