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:
Create an instance of the TopologicalSorter with an initial graph.
While is_active() is True, iterate over the nodes returned by get_ready() and process them.
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 raiseDAGHasCycle
if any cycle is detected. If it’s set toFalse
, topological sorter will output as many nodes as possible until cycles block more progress. By default isTrue
.reverse (bool) – If
False
(the default), perform a regular topological ordering. IfTrue
, 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 theinitial
set will be in the ordering. Notably, the first return fromget_ready()
will be the same set of values asinitial
, and any node that has a natural in degree of zero will not be in the output ordering ifinitial
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 todone()
.check_args (bool) – If
True
(the default), then all arguments todone()
are checked for validity, and aValueError
is raised if any were not ready, already done, or not indices of the circuit. IfFalse
, 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