在网络x中有效地枚举DiGraph的所有简单路径

Question

我试图对杜威十进制分类进行一些图形分析,这样我就可以在两本书之间做一个距离.DDC有几个关系:"层次结构","看也","类别 - 其他",这里我用不同的颜色代表它们.由于这些关系不对称,您会注意到我们有一个有向图.下面是所有顶点距离394.1最多4个边的图的图片.

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

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

我想返回加权最短路径.我认为如果我可以预处理两个节点之间的所有简单路径,然后在给定权重dict的情况下找到最短的路径,那就不会有问题了.但是,因为该图包含> 50,000个节点.计算nx.all_simple_paths(G, a, b)24小时后计算没有返回.是否有任何并行发现的建议all_simple_paths.或者一种计算最短路径的技术weights_dict,但不涉及计算all_simple_paths？

Answer 1

感谢@CorleyBrigman。W解决方案是从 中创建一个新图表G，将 的颜色替换G为您想要的权重。然后，您可以有效地使用nx.shortest_path和nx.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