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

Topological Sorting

Explore how topological sorting organizes tasks in directed acyclic graphs (DAGs) to ensure correct execution order in machine learning pipelines. Understand key concepts like node indegree and cycle detection, and learn an iterative algorithm for sorting graph vertices properly.

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, ...