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.immediate_dominators#

immediate_dominators(graph, start_node, /)#

Determine the immediate dominators of all nodes in a directed graph.

The dominance computation uses the algorithm published in 2006 by Cooper, Harvey, and Kennedy (https://hdl.handle.net/1911/96345). The time complexity is quadratic in the number of vertices.

Parameters:

  • graph (PyDiGraph) – directed graph

  • start_node (int) – the start node for the dominance computation

Returns:

a mapping of node indices to their immediate dominators

Return type:

dict[int, int]

Raises: