transitive_closure_dag

transitive_closure_dag(G, topo_order=None)

返回有向无环图的传递闭包。

此函数比 transitive_closure 函数更快，但如果图中有环则会失败。

G = (V,E)的传递闭包是图G+ = (V,E+)，使得对于所有v, w in V，当且仅当G中存在从v到w的非空路径时，E+中存在边(v, w)。

Parameters:

GNetworkX DiGraph

一个有向无环图（DAG）

topo_order: 列表或元组, 可选

G的一个拓扑顺序（如果为None，函数将计算一个）

Returns:

NetworkX DiGraph

G 的传递闭包

Raises:

NetworkXNotImplemented

如果 G 不是有向的

NetworkXUnfeasible

如果 G 有环

Notes

此算法可能足够简单以至于广为人知，但我没有在文献中找到提及。

Examples

>>> DG = nx.DiGraph([(1, 2), (2, 3)])
>>> TC = nx.transitive_closure_dag(DG)
>>> TC.edges()
OutEdgeView([(1, 2), (1, 3), (2, 3)])