DAGs: topological order and dependencies

Build systems, task schedulers, course prerequisites and data pipelines are all DAGs.

A directed acyclic graph (DAG) is a DiGraph with no directed cycles. Use edges prerequisite -> dependent and many questions become one-liners:

nx.is_directed_acyclic_graph(G) checks the property.
list(nx.topological_sort(G)) returns an order in which every node comes after all its prerequisites. It raises nx.NetworkXUnfeasible if there's a cycle.
nx.topological_generations(G) groups nodes into layers that can run in parallel, generation by generation.
nx.ancestors(G, n) returns everything n depends on, directly or indirectly; nx.descendants(G, n) everything that depends on n.
nx.find_cycle(G) returns one offending cycle; nx.simple_cycles(G) enumerates them all, which can be exponential.
nx.dag_longest_path(G, weight="hours") gives the critical path: the chain that determines minimum total duration.
nx.transitive_reduction(G) removes edges implied by others, leaving only direct prerequisites.
nx.lexicographical_topological_sort(G) gives a deterministic order when ties exist.

Topological order isn't unique; don't depend on one particular valid order unless you use the lexicographic version. And keep validating when graphs are edited, because a single back edge makes the whole thing cyclic.

Example

import networkx as nx

course = nx.DiGraph([
    ("python", "numpy"), ("numpy", "pandas"), ("python", "pandas"),
    ("sql", "pandas"), ("pandas", "dask"), ("numpy", "dask"),
])
print(nx.is_directed_acyclic_graph(course))         # True
print(list(nx.lexicographical_topological_sort(course)))
# ['python', 'numpy', 'sql', 'pandas', 'dask']
print([sorted(g) for g in nx.topological_generations(course)])
# [['python', 'sql'], ['numpy'], ['pandas'], ['dask']]
print(sorted(nx.ancestors(course, "dask")))         # ['numpy', 'pandas', 'python', 'sql']

reduced = nx.transitive_reduction(course)
print(reduced.has_edge("python", "pandas"))         # False (implied via numpy)

course.add_edge("dask", "python")                   # oops: a cycle
try:
    list(nx.topological_sort(course))
except nx.NetworkXUnfeasible:
    print(nx.find_cycle(course)[0])                 # ('python', 'numpy')

Remember

Edges point from prerequisite to dependent
topological_sort orders; topological_generations gives parallel layers
ancestors, transitive_reduction and dag_longest_path answer dependency questions

Watch out for

Relying on one specific topological order when several are valid.

Check yourself

What does nx.transitive_reduction remove from a DAG?

Official docs: networkx.org/documentation/stable/reference/algorithms/dag.html

Example

Remember

Watch out for

Check yourself

Builds on

Unlocks