toposort

1.10 · active · verified Mon Apr 06

The `toposort` library provides a pure Python implementation of a topological sort algorithm, useful for ordering items based on their dependencies. As of its latest version `1.10`, released on February 25, 2023, it is a stable, production-ready tool. It accepts dependency graphs as dictionaries and efficiently computes a valid processing order. The release cadence appears to be moderate, with updates for compatibility and minor enhancements.

Warnings

breaking Circular dependencies will raise a `toposort.CircularDependencyError` (derived from `ValueError`). The algorithm cannot produce a valid topological sort if a cycle exists in the graph.
Fix: Ensure your dependency graph is a Directed Acyclic Graph (DAG). If cycles are expected or possible, implement logic to detect and handle `CircularDependencyError`.
gotcha The input `data` dictionary expects keys to be dependent nodes and values to be `set`s of nodes that the key depends on. Using lists instead of sets for dependencies, or incorrectly defining the dependency direction (e.g., mapping a node to what it *is depended on by*), are common mistakes.
Fix: Always provide dependencies as `set`s (`{dependency1, dependency2}`) and ensure the mapping is `dependent_node: {its_dependencies}`.
gotcha All nodes (keys and elements within the dependency sets) must be hashable types (e.g., numbers, strings, tuples). Unhashable types like lists or dictionaries cannot be used as nodes.
Fix: Represent your graph nodes using hashable Python types. If you need to use complex objects, consider using a unique identifier (like an ID string or number) as the node in the topological sort, and map it back to your complex object.
gotcha For Python 3.9 and newer, the standard library includes `graphlib.TopologicalSorter` which offers similar topological sorting functionality. Users might consider this built-in alternative to avoid external dependencies.
Fix: Evaluate `graphlib.TopologicalSorter` from the Python standard library as an alternative, especially for new projects or to reduce third-party dependencies. The API differs, so code migration would be required.

Install

pip install toposort Install latest version

Imports

toposort
```
from toposort import toposort
```
The primary function for performing a topological sort, returning an iterator of sets for parallel processing stages.
toposort_flatten
```
from toposort import toposort_flatten
```
A convenience function that returns a single flattened list of topologically sorted items.
CircularDependencyError
```
from toposort import CircularDependencyError
```
The exception raised when a cyclic dependency is detected in the input graph.

Quickstart

This quickstart demonstrates how to use `toposort` with a sample dependency graph. The `data` dictionary maps each dependent node to a set of its direct dependencies. `toposort` yields sets of nodes that can be processed concurrently, while `toposort_flatten` provides a single linear sequence. It also shows how to catch `CircularDependencyError` for graphs containing cycles.

from toposort import toposort, toposort_flatten

data = {
    2: {11},
    9: {11, 8, 10},
    10: {11, 3},
    11: {7, 5},
    8: {7, 3},
    # Nodes 3, 5, 7 have no dependencies, so they can be omitted
    # or explicitly listed with empty sets if they have no outgoing edges
    3: set(),
    5: set(),
    7: set()
}

# Get items in stages (sets of items that can be processed in parallel)
# Example output: [{3, 5, 7}, {8, 11}, {2, 10}, {9}]
for step in toposort(data):
    print(f"Process in parallel: {step}")

# Get a flattened list of items in a valid order
# Example output: [3, 5, 7, 8, 11, 2, 10, 9] (order within sets may vary)
flattened_order = list(toposort_flatten(data))
print(f"Flattened order: {flattened_order}")

# Example of circular dependency handling
cyclic_data = {1: {2}, 2: {1}}
try:
    list(toposort(cyclic_data))
except toposort.CircularDependencyError as e:
    print(f"Caught expected error: {e}")

view raw JSON →