transitive_reduction#

transitive_reduction(G)[源代码]#

返回有向图的传递约简

g=（v，e）的传递约简是一个图g-=（v，e-）这样对于v中的所有v，w，在e-if中都有一个边（v，w），并且只有当（v，w）在e中并且g中没有从v到w的路径长度大于1时。

参数

G网络X有向图: 有向无环图(DAG)

返回

网络X有向图: 传递约简 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)]

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

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