transitive_reduction

transitive_reduction(G)

返回有向图的传递归约

G = (V,E) 的传递归约是一个图 G- = (V,E-)，其中对于所有 V 中的 v,w，当且仅当 (v,w) 在 E 中且在 G 中不存在从 v 到 w 的长度大于 1 的路径时，E- 中存在边 (v,w)。

参数:

GNetworkX DiGraph

一个有向无环图 (DAG)

返回:

NetworkX DiGraph

G 的传递归约

抛出:

NetworkXError

如果 G 不是有向无环图 (DAG)，则传递归约没有唯一定义，将抛出 NetworkXError 异常。

参考

https://en.wikipedia.org/wiki/Transitive_reduction

示例

对有向图执行传递归约

>>> DG = nx.DiGraph([(1, 2), (2, 3), (1, 3)])
>>> TR = nx.transitive_reduction(DG)
>>> list(TR.edges)
[(1, 2), (2, 3)]

为避免不必要的数据复制，此实现不返回包含节点/边数据的有向图。要对有向图执行传递归约并转移节点/边数据，请执行以下操作：

>>> DG = nx.DiGraph()
>>> DG.add_edges_from([(1, 2), (2, 3), (1, 3)], color="red")
>>> TR = nx.transitive_reduction(DG)
>>> TR.add_nodes_from(DG.nodes(data=True))
>>> TR.add_edges_from((u, v, DG.edges[u, v]) for u, v in TR.edges)
>>> list(TR.edges(data=True))
[(1, 2, {'color': 'red'}), (2, 3, {'color': 'red'})]