rustworkx.lexicographical_topological_sort#

lexicographical_topological_sort(dag, /, key, *, reverse=False, initial=None)#

Get the lexicographical topological sorted nodes from the provided DAG

This function returns a list of nodes data in a graph lexicographically topologically sorted using the provided key function. A topological sort is a linear ordering of vertices such that for every directed edge from node \(u\) to node \(v\), \(u\) comes before \(v\) in the ordering. If reverse is set to False, the edges are treated as if they pointed in the opposite direction.

This function differs from topological_sort() because when there are ties between nodes in the sort order this function will use the string returned by the key argument to determine the output order used. The reverse argument does not affect the ordering of keys from this function, only the edges of the graph.

Parameters:

  • dag (PyDiGraph) – The DAG to get the topological sorted nodes from

  • key (callable) – key is a python function or other callable that gets passed a single argument the node data from the graph and is expected to return a string which will be used for resolving ties in the sorting order.

  • reverse (bool) – If False (the default), perform a regular topological ordering. If True, return the lexicographical topological order that would have been found if all the edges in the graph were reversed. This does not affect the comparisons from the key.

  • 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, 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.

Returns:

A list of node’s data lexicographically topologically sorted.

Return type:

list