Search⌘ K
Home
Courses
Building a Machine Learning Pipeline from Scratch

Topological Sorting

Understand how the topological sorting algorithm works.

We'll cover the following...

Consider the following configuration:

YAML
tasks:
    task_a:
      next:
        - task_b
    task_e:
      next: []
    task_c:
      next:
        - task_e
    task_d:
      next:
        - task_e
    task_b:
      next:
        - task_c
        - task_d

This is the same config we saw previously, with one difference: tasks are ordered randomly here. This should have no effect on how the DAG is built when we read this config. A config is user-supplied and prone to human error, so it’s the developer’s responsibility to make sure it defines a valid DAG and sort its vertices appropriately.

Topological sorting

When the config file is read, tasks are loaded into memory in the order that they are encountered in the file: task_a first, then task_e, then task_c, and so on. We can perform task_a without any problem because it’s the first task and it appears first in the config file. However, the next task in the config, task_e, ...