Can tasks run in parallel?

Some may, but the single returned sequence does not itself decide resource availability or execution timing. Dependency layers can help identify candidates.

Does NetworkX return a list immediately?

Its documented topological_sort interface returns a generator. Errors may arise while that generator is consumed, so partial output is not proof that the entire graph is acyclic.

Does a valid order require an edge between consecutive tasks?

No. The order only requires existing edges to point forward.

AI Glossary / Graphs and symbolic AI / Intermediate

Topological sort

Definition

A topological sort is an ordering of every vertex in a directed acyclic graph such that each directed edge goes from an earlier vertex to a later one. It turns dependency constraints into a valid sequence while preserving their direction.

What it means

Suppose a task depends on another task being completed first. Draw an arrow from the prerequisite to the dependent task. A topological ordering places every prerequisite before the tasks that rely on it.

The ordering is usually not unique. If two tasks have no dependency between them, either may appear first, provided their other requirements are satisfied. Topological sorting therefore differs from arranging names alphabetically or sorting numerical scores.

A directed cycle makes such an ordering impossible: A cannot precede B, B precede C and C precede A in one linear sequence. The graph must be acyclic. Isolated vertices still belong in the result, even though no dependency restricts their position.

How it works

One common procedure is Kahn's algorithm. It begins with vertices that have no incoming edges. It selects one, outputs it and removes its outgoing dependencies from the remaining problem. Any vertex whose remaining incoming-edge count becomes zero becomes eligible next.

If every vertex is output, the sequence is valid. If unprocessed vertices remain but none is eligible, the remaining graph contains a directed cycle. With suitable adjacency lists and a queue, this process takes time proportional to the number of vertices plus edges.

A depth-first-search approach can also obtain a topological order when cycle detection and finishing order are handled correctly. The algorithm's chosen tie-breaking policy affects which valid order is returned. Reproducibility may require an explicit tie-breaker, but that does not change the dependency constraints themselves.

Three practical examples

A data pipeline orders cleaning, feature preparation, training and evaluation steps according to their prerequisites.
A spreadsheet engine uses dependency relationships to determine a valid order for recalculating affected formulas.
A build system arranges compilation tasks so that required generated files exist before dependent steps run.

Think of it this way

Think of a recipe whose instructions include several separate preparations. The dough must be mixed before baking, while a garnish might be prepared at several possible points. A valid instruction sequence respects the required order without insisting that every pair of steps has a dependency.

The analogy stops at ordering. Topological sorting does not calculate cooking times, oven capacity or the shortest completion schedule. Those require durations and resource constraints beyond the dependency graph.

Worked example

Ordering a small pipeline

Let the tasks be A: collect data, B: validate data, C: prepare configuration, D: train and E: evaluate. The dependency edges are A → B, B → D, C → D and D → E.

Initially A and C have no prerequisites. Choosing A makes B eligible. Choosing B next still leaves D waiting for C. After choosing C, D becomes eligible, followed by E. One valid order is therefore A, B, C, D, E.

Another is C, A, B, D, E. Both satisfy all four edges. A, B, D, C, E is invalid because it puts training before configuration. Now add E → B. The cycle B → D → E → B means that no topological ordering of the full graph exists. Removing an arbitrary edge merely to obtain an order would change the specified workflow, so the modeling error needs investigation.

Illustrative case study

Fictional case: Alder Analytics represents a reporting workflow as a dependency graph. Its first implementation sorts task names and happens to work on one demonstration. Renaming a task changes the order and exposes a missing prerequisite.

The team switches to an explicit topological ordering and checks every edge against the resulting positions. A later workflow update introduces a cycle: a validation step requires a report that cannot be generated until validation completes.

Rather than executing the partial list produced before the cycle is encountered, the team reports the conflicting dependencies for review. Independent tasks receive a stable tie-breaker so logs remain easy to compare. The case illustrates correctness and diagnosis, not a measured reduction in execution time.

Common misconceptions and mistakes

Every graph has a topological sort. Directed cycles prevent one; undirected graphs do not carry the required ordering meaning without further modeling.
A different valid order is necessarily wrong. Unconstrained tasks can often move relative to one another.
A topological order is an optimal schedule. It respects dependencies but does not optimize elapsed time or resource use.

Business use

Topological sorting is a useful foundation for AI workflows with explicit prerequisites. It helps separate dependency correctness from decisions about parallel execution, priorities and capacity.

Document what an edge means, since reversing the convention reverses the required order. Include all tasks, check for cycles and decide whether a stable tie-breaker is needed. Treat a cyclic dependency as information about the workflow rather than silently dropping it. Before launching consequential steps, ensure that the complete dependency check has succeeded.

Check your understanding

A graph contains A → C and B → C, with no edge between A and B. Are both A, B, C and B, A, C valid?

Answer: Yes. Both place the two prerequisites before C. Neither edge requires A and B to have a particular relative order.

Related terms

Directed acyclic graph
Scheduling
Critical path
dependency graph
partial order
cycle detection
Kahn's algorithm

Learn next

Read directed acyclic graph and scheduling. Write a five-step workflow, draw prerequisite arrows, and produce two valid orders if possible. Then explain which additional information would be needed to choose the fastest schedule.

Sources

NetworkX, Directed Acyclic Graphs and Topological Sort tutorial: https://networkx.org/nx-guides/content/algorithms/dag/index.html

NetworkX, topological_sort API reference: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dag.topological_sort.html

The algorithm description and documented generator behaviour were read. The pipeline example was checked directly against its edge constraints; no execution of a NetworkX program is claimed.

Previous: Topological deep learning Next: Torus interconnect