networkx中的传递闭包
networkx中的传递闭包
提问于 2018-10-09 05:41:46
考虑以下示例：
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。我预计会使用不同的定义，但它是什么呢？
回答 1
Stack Overflow用户
发布于 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.]]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52710488
复制相关文章
相似问题