graphlib-backport

1.1.0 · active · verified Wed Apr 15

Backport of the Python 3.9 `graphlib` module for Python 3.6+. It provides the `TopologicalSorter` class for performing topological sorting on directed acyclic graphs (DAGs). The library is currently at version 1.1.0 and is actively maintained, with releases tied to updates on its GitHub repository.

Warnings

gotcha When installed on Python versions 3.9 or higher, the native `graphlib` module (which includes `TopologicalSorter`) will take precedence if you try to import directly as `import graphlib`. It is generally recommended to limit installation of `graphlib-backport` to Python versions `<3.9` and use the standard library's `graphlib` for Python `>=3.9`.
Fix: For Python 3.9+, prefer `from graphlib import TopologicalSorter`. If you must use the backport on 3.9+, ensure your imports are explicitly `from graphlib_backport import TopologicalSorter`. Utilize environment markers or poetry's `python` dependency specifier to conditionally install the backport only on older Python versions.
deprecated Explicit support for Python 3.6 and 3.7 is considered 'somewhat experimental' and is slated to be dropped, as these Python versions have reached their official end-of-life status.
Fix: Migrate your project to Python 3.8 or newer. For Python 3.9+, use the standard library's `graphlib` module.
gotcha The PyPI package name for installation is `graphlib-backport` (with a hyphen), but the Python import name within your code is `graphlib_backport` (with an underscore). Attempting `import graphlib-backport` will result in a `ModuleNotFoundError`.
Fix: Use `pip install graphlib-backport` for installation and `from graphlib_backport import TopologicalSorter` (or `import graphlib_backport`) for importing in your Python code.

Install

pip install graphlib-backport Install stable version

Imports

TopologicalSorter
wrong:
```
from graphlib import TopologicalSorter
```
correct:
```
from graphlib_backport import TopologicalSorter
```
The backport uses 'graphlib_backport' as its top-level package name. 'graphlib' would refer to the standard library module, which only exists in Python 3.9+.

Quickstart

This quickstart demonstrates the core functionality of `TopologicalSorter` to process a graph. It shows both obtaining a full static order and processing nodes dynamically, which is useful for parallel execution patterns. Nodes are represented as hashable objects (e.g., strings), and dependencies are defined by providing a set of predecessors for each node.

from graphlib_backport import TopologicalSorter

# Example graph: keys are nodes, values are sets of predecessors
graph = {"D": {"B", "C"}, "C": {"A"}, "B": {"A"}, "A": set()}

ts = TopologicalSorter(graph)

# Get the nodes in topological order using static_order (convenience method)
order = list(ts.static_order())
print(f"Topological order (static): {order}")

# Example with dynamic processing (simulating parallel work)
print("\nProcessing nodes dynamically:")
ts_dynamic = TopologicalSorter(graph)
ts_dynamic.prepare() # Must be called before is_active, get_ready, or done

processed_nodes = []
while ts_dynamic.is_active():
    ready_nodes = ts_dynamic.get_ready()
    if ready_nodes:
        print(f"  Ready to process: {ready_nodes}")
        # Simulate processing for each ready node
        for node in ready_nodes:
            processed_nodes.append(node)
        ts_dynamic.done(*ready_nodes) # Mark nodes as done to unblock successors
    else:
        # This branch should not be reached in a valid DAG if is_active is true
        # unless there's an unexpected state (e.g., cycle detected after prepare, or bug).
        print("  No nodes ready, but sorter is active. Potential issue or cycle?")
        break

print(f"Dynamic processing complete. Order: {processed_nodes}")

view raw JSON →