gpt4 book ai didi

python - 有效地枚举 networkx 中 DiGraph 的所有简单路径

转载 作者:太空狗 更新时间:2023-10-30 01:38:16 44 4
gpt4 key购买 nike

我正在尝试对杜威十进制分类法进行一些图形分析,以便我可以在两本书之间划清界限。 DDC有几个关系:“hierarchy”,“see-also”,“class-elsewhere”,这里我用不同的颜色来表示。由于这些关系不是对称的,您会注意到我们有一个有向图。下图是距离 394.1 最多 4 条边的所有顶点的图形。

Sample Graph

分类 A 和 B 之间的距离度量应该是 A 和 B 之间的最短路径。但是颜色没有固有的加权值或偏好。但是用户会给提供一个。所以给定一个权重字典,例如:

weights_dict_test = {'notational_hiearchy':1,
'see_reference':0.5,
'class_elsewhere':2}

我想返回加权最短路径。我认为如果我可以预处理两个节点之间的所有简单路径,然后找到给定权重指令的最短路径,那将不是问题。但是,由于该图包含 >50,000 个节点。计算 nx.all_simple_paths(G, a, b) 在计算 24 小时后仍未返回。是否有任何关于并行查找 all_simple_paths 的建议。还是在给定 weights_dict 的情况下计算最短路径的技术不涉及计算 all_simple_paths

最佳答案

感谢@CorleyBrigman。解决方案是从 G 创建一个新的图 W,用你想要的权重替换 G 的颜色。然后,您可以高效地使用 nx.shortest_pathnx.shortest_path_length,因为它们通常运行速度很快。

In [23]:

def update_weights(G, weights_dict):
W = nx.DiGraph()

for m in G.nodes():
for n in G[m].iterkeys():
relation = G[m][n]['rel']
weight = weights_dict[relation]
W.add_edge(m, n, rel=weights_dict[relation])
return W

In [41]:

weights_dict_test = {'notational_hiearchy':50,
'see_reference':0.6,
'class_elsewhere':1}

In [42]:

W = update_weights(G, weights_dict_test)

In [43]:

print len(W)
print len(G)

43241
43241

In [45]:

nx.shortest_path_length(W, '394.1', '341.33',weight='rel')

Out[45]:

52.2

关于python - 有效地枚举 networkx 中 DiGraph 的所有简单路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21414046/

44 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com