transitive_closure_dag#

transitive_closure_dag(G, topo_order=None)[source]#

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

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

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

参数:
GNetworkX 有向图

一个有向无环图 (DAG)

topo_order: list 或 tuple，可选

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

返回:
NetworkX 有向图

图 G 的传递闭包

引发:
NetworkXNotImplemented

如果图 G 不是有向图

NetworkXUnfeasible

如果图 G 包含环

说明

这个算法可能简单到众所周知，但我没有在文献中找到提及。

示例

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