考虑以下示例:
import numpy as np
import networkx as nx
a = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
G = nx.from_numpy_matrix(a, create_using=nx.MultiDiGraph())
T = nx.transitive_closure(G)
print(nx.to_numpy_matrix(T))
传递闭包缺少预期的自循环。为什么?(文档链接不起作用。)我所说的“预期”是指“根据标准定义”,例如Wikipedia definition。我预计会使用不同的定义,但它是什么呢?
发布于 2018-10-09 07:56:57
看起来像是实现错误。文档字符串在定义上是明确的:“图G+ = (V,E+)使得对于V中的所有v,w,当且仅当在G中存在从v到w的非空路径时,E+中存在边(v,w)。”在这个定义下,自循环是合格的。
该算法归结为,在使TC成为给定G的副本之后,
for v in G:
TC.add_edges_from((v, u) for u in nx.dfs_preorder_nodes(G, source=v)
if v != u)
因此,由于if v != u
,自循环永远不会被添加。排除的原因是dfs_preorder_nodes
的输出将以v
(源)开始,而不管有什么边,当然我们不想仅仅因为这个原因添加一个循环(v, v)
。但是,依赖dfs_preorder_nodes
的一个副作用是,该算法永远无法确定v
本身是否可以通过v
通过非空路径到达。
因此,为了获得通常意义上的传递闭包,我们需要为位于循环上的每个节点v
添加循环(v, v)
。如下所示:
T = nx.transitive_closure(G)
for cycle in nx.simple_cycles(G):
T.add_edges_from((v, v) for v in cycle)
在矩阵形式中,T
现在是
[[4. 2. 2.]
[2. 4. 2.]
[2. 2. 4.]]
循环被添加了多次。如果你关心重数(尽管我真的看不出传递闭包应该有什么边的重数),可以这样做,以防止边的多次添加:
cycles = frozenset().union(*[frozenset(cycle) for cycle in nx.simple_cycles(G)])
T.add_edges_from((v, v) for v in cycles)
那么T
就是
[[1. 2. 2.]
[2. 1. 2.]
[2. 2. 1.]]
https://stackoverflow.com/questions/52710488
复制相似问题