immediate_dominators#

immediate_dominators(G, start)[source]#

返回有向图中所有节点的直接支配者。

Parameters:
GDiGraph 或 MultiDiGraph

要计算支配关系的图。

start节点

支配关系计算的起始节点。

Returns:
idom以节点为键的字典

包含从 start 可达的每个节点的直接支配者的字典。

Raises:
NetworkXNotImplemented

如果 G 是无向图。

NetworkXError

如果 start 不在 G 中。

Notes

除了 start 之外，直接支配者是其对应节点在支配树中的父节点。

References

[1]

Cooper, Keith D., Harvey, Timothy J. 和 Kennedy, Ken. “一个简单快速的支配算法.” (2006). https://hdl.handle.net/1911/96345

Examples

>>> G = nx.DiGraph([(1, 2), (1, 3), (2, 5), (3, 4), (4, 5)])
>>> sorted(nx.immediate_dominators(G, 1).items())
[(1, 1), (2, 1), (3, 1), (4, 3), (5, 1)]
On this page