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

我正在尝试对杜威十进分类进行一些图分析，以便我可以在两本书之间制作一段距离。 DDC有几个关系：“层次结构”，“另见”，“别处的类别”，在这里我用不同的颜色表示它们。由于这些关系不对称，您会注意到我们有一个有向图。以下是距离394.1最远4个边的所有顶点图的图片。有效枚举网络中DiGraph的所有简单路径x

Sample Graph

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

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

我想返回加权的最短路径。我认为如果我可以预处理两个节点之间的所有简单路径，然后找到权重字典中最短的路径，这不会成为问题。但由于该图包含> 50,000个节点。在计算24小时后，计算nx.all_simple_paths(G, a, b)还没有返回。是否有任何建议可以并行查找all_simple_paths。或者是一种计算给定weights_dict的最短路径的技术，它不涉及计算all_simple_paths？

来源

2014-01-28 notconfusing

您的问题的答案是：是的，有这方面的技术，但范围太宽了，没有一个好的答案在这里。尝试从这里开始：http：//en.wikipedia.org/wiki/Shortest_path – jonrsharpe

我想也更具体一点，它将实施[有非负权的有向图]之一（http://en.wikipedia.org/wiki/） Shortest_path＃Directed_graphs_with_nonnegative_weights）。 – notconfusing

你怎么代表不同的关系？这只是如果边缘有这个属性？根据属性和输入字典更新边缘属性'weight'可能不需要太长时间，然后只需使用内置的'shortest_path'，它已经支持加权。此外，networkx是纯粹的python，并且最短路径的代码是可用的，如果您需要修改它以适应这种特殊情况。 –

感谢@CorleyBrigman。解决方案是从G创建一个新的图W，用您想要的权重代替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

来源

2014-01-28 22:22:05 notconfusing

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

回答

相关问题