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(graph, /, check_cycle=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.

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.