immediate_dominators#

immediate_dominators(G, start)[source]#

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

参数:

GDiGraph 或 MultiDiGraph: 要计算支配关系的图。
start节点: 支配计算的起始节点。

返回:

idom以节点为键的字典: 一个字典，包含从 start 可达的每个节点的直接支配者。

抛出:

NetworkXNotImplemented: 如果 G 是无向图。
NetworkXError: 如果 start 不在 G 中。

注意

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

参考资料

[1]

Cooper, Keith D., Harvey, Timothy J. and Kennedy, Ken. “A simple, fast dominance algorithm.” (2006). https://hdl.handle.net/1911/96345

示例

>>> 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)]