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.

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

graph = rx.generators.directed_path_graph(5)
sorter = rx.TopologicalSorter(graph)
while sorter.is_active():
    nodes = sorter.get_ready()
    print(nodes)
    sorter.done(nodes)

[0]
[1]
[2]
[3]
[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, 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. By default is True.

• reverse (bool) – If False (the default), perform a regular topological ordering. If True, the ordering will be a reversed topological ordering; that is, a topological order if all the edges had their directions flipped, such that the first nodes returned are the ones that have only incoming edges in the DAG.

• initial (Iterable[int]) –

  If given, the initial node indices to start the topological ordering from. If not given, the topological ordering will certainly contain every node in the graph. If given, only the initial nodes and nodes that are dominated by the initial set will be in the ordering. Notably, the first return from get_ready() will be the same set of values as initial, and any node that has a natural in degree of zero will not be in the output ordering if initial is given and the zero-in-degree node is not in it.

  It is a ValueError to give an initial set where the nodes have even a partial topological order between themselves, though this might not appear until some 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.