Note

This is the documentation for the current state of the development branch of rustworkx. The documentation or APIs here can change prior to being released.

TopologicalSorter

class TopologicalSorter(dag, /, check_cycle=True, *, reverse=False, initial=None, check_args=True)

Bases: object

Provides functionality to topologically sort a directed graph.

A topological sorter is used to arrange the nodes of a directed acyclic graph in a linear order such that for every directed edge from node u to node v, node u` appears before node v in the sequence. This ordering is particularly useful for resolving dependencies in scenarios such as task scheduling, where certain tasks must be completed before others, and in build systems, where files or modules depend on one another. The topological sorting process ensures that all dependencies are satisfied, allowing for efficient execution and processing of tasks or data.

The steps required to perform the sorting of a given graph are as follows:

1. Create an instance of the TopologicalSorter with an initial graph.

2. While is_active() is True, iterate over the nodes returned by get_ready() and process them.

3. Call done() on each node as it finishes processing.

For example:

import rustworkx as rx

G = rx.PyDiGraph()
G.add_nodes_from(["A", "B", "C", "D", "E", "F"])
G.add_edges_from_no_data([(0, 2),(1, 2), (2, 3), (3, 4), (3, 5)])
sorter = rx.TopologicalSorter(G)
while sorter.is_active():
    nodes = sorter.get_ready()
    print(nodes)
    sorter.done(nodes)

[0, 1]
[2]
[3]
[5, 4]

The underlying graph can be mutated and TopologicalSorter will pick-up the modifications but it’s not recommended doing it as it may result in a logical-error.

Parameters:

• graph (PyDiGraph) – The directed graph to be used.

• check_cycle (bool) – When this is set to True (the default), we search for cycles in the graph during initialization of topological sorter and raise DAGHasCycle if any cycle is detected. If it’s set to False, topological sorter will output as many nodes as possible until cycles block more progress.

• reverse (bool) – If False (the default), perform a regular topological ordering, i.e. for a directed edge A -> B the A appears before the B. If True, the ordering will be a reversed topological ordering, i.e. for a directed edge A -> B, the B appears before the A.

• initial (Iterable[int]) – By default, the topological ordering will include all nodes in the graph. If initial node indices are provided, the ordering will only include those nodes and any nodes that are dominated by them. In this case, the first output from get_ready() will match the initial set, and any node with a natural in-degree of zero will be excluded from the output if it is not part of the initial set. Additionally, providing an initial set where the nodes have even a partial topological order among themselves will raise a ValueError, although this may not be detected until a call to done().

• check_args (bool) – If True (the default), then all arguments to done() are checked for validity, and a ValueError is raised if any were not ready, already done, or not indices of the circuit. If False, the tracking for this is disabled, which can provide a meaningful performance and memory improvement, but the results will be undefined if invalid values are given.

Methods

done	Marks a set of nodes returned by get_ready() as processed.
get_ready	Return a list of all the nodes that are ready.
is_active	Return True if more progress can be made and False otherwise.