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.

rustworkx.lexicographical_topological_sort#

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

Get the lexicographical topological sorted nodes from the provided directed graph.

This function returns a list of node data from the graph, sorted in lexicographical order based on 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 appears before v in the ordering. If reverse is set to False, the edges are treated as if they point in the opposite direction.

Unlike topological_sort(), this function resolves ties between nodes using the string returned by the key argument. The reverse argument only affects the direction of the edges, not the ordering of keys.

>>> G = rx.PyDiGraph()
>>> a, b, c, d, e, f, g = G.add_nodes_from(["A", "B", "C", "D", "E", "F", "G"])
>>> G.add_edges_from_no_data([(a, g), (b, g), (c, g), (d, g), (e, g), (f, g)])
>>> rx.topological_sort(G)
NodeIndices[5, 4, 3, 2, 1, 0, 6]                     # First 6 items in any order
>>> rx.lexicographical_topological_sort(G, key=str)
['A', 'B', 'C', 'D', 'E', 'F', 'G']                  # First 6 items in alphabetical order

For a standard topological sort without lexicographical ordering, see topological_sort().

Parameters:

  • dag (PyDiGraph) – The directed graph to sort.

  • key (callable) – A callable that takes a single argument (node data) and returns a string used to resolve ties in the sorting order.

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

  • 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. Providing an initial set where the nodes have even a partial topological order among themselves will raise a ValueError.

Returns:

A list of node data, lexicographically topologically sorted.

Return type:

list[S]