在networkx中高效枚举DiGraph的所有简单路径

Question

我试图对杜威十进分类进行一些图形分析，以便我可以计算出两本书之间的距离。 DDC具有几个关系：“层次结构”，“参见”，“其他类别”，我用不同的颜色表示它们。 由于这些关系不是对称的，您会注意到我们有一个有向图。 下面是离394.1最多4条边的所有顶点的图形。

分类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的建议？或者一种不需要计算all_simple_paths就能计算出给定weights_dict的最短路径的技术？

- notconfusing

---

你的问题的答案是：是的，有一些技术可以解决这个问题，但范围太广了，无法在此给出好的答案。可以从这里开始尝试：http://en.wikipedia.org/wiki/Shortest_path - jonrsharpe

我想更具体地说，它将实现具有非负权重的有向图之一。 - notconfusing

你是如何表示不同的关系的？只是通过边缘是否具有该属性吗？根据属性和输入字典更新边缘属性“权重”可能不需要太长时间，然后只需使用内置的shortest_path，它已经支持权重。此外，networkx是纯Python编写的，如果您需要为此特殊情况修改最短路径的代码，则可以获得其代码。 - Corley Brigman

@CorleyBrigman 我刚刚尝试了你的建议 - 它非常有效。谢谢你 - 问题已解决。 - notconfusing

Answer 1

感谢 @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

- notconfusing