Python Detect Cycles in Dependency Graphs

Detect invalid dependency cycles before trying to schedule tasks.

What You Will Learn

A dependency graph is a directed graph: an edge from task A to B can mean B must happen before A. graphlib.TopologicalSorter yields a valid dependency order for acyclic graphs and raises CycleError for cycles. Choose and document the direction of your edges because reversing it changes execution order.

Time complexity assumes a specific input structure. Include setup work such as sorting or building a lookup table when comparing complete solutions.

Step-by-Step Example

The example below makes the behavior visible with small input values that you can change safely.

from graphlib import CycleError, TopologicalSorter

dependencies = {"build": {"test"}, "test": {"build"}}
try:
    print(list(TopologicalSorter(dependencies).static_order()))
except CycleError:
    print("A dependency cycle was found")

How the Example Works

The imports provide the standard-library tools used in the demonstration: graphlib.
The variable dependencies holds the result of {'build': {'test'}, 'test': {'build'}}. Later lines use that value or inspect how it changes.
The control-flow block demonstrates when each value is processed or when cleanup and exception handling take effect.
The print() calls make the return values or state visible so you can compare them with the explanation and check your prediction.

Expected output from the example:

A dependency cycle was found

When You Would Use This

This technique matters when a program handles larger queues, sorted records, or repeated lookups. Choose the data structure based on actual operations and the preconditions the algorithm requires. Verify boundary inputs before optimizing for speed.

Practice: Modify the Code

Remove the circular edge and print the new task order.

Verify the changed output against the behavior described above, including the relevant invalid or boundary case.

For complete parameters and version details, consult the official Python documentation.

Common Beginner Mistakes

Mistaking the dependency dictionary for a list of outgoing edges without checking its semantics.
Silently ignoring CycleError and assuming a partial order is a valid full schedule.

Key Takeaways

Detect invalid dependency cycles before trying to schedule tasks.
A dependency graph is a directed graph: an edge from task A to B can mean B must happen before A. graphlib.TopologicalSorter yields a valid dependency order for acyclic graphs and raises CycleError for cycles.
Apply this operation only after checking the assumptions and input conditions shown in the example.