python - 输入图形进行 scipy 图形搜索

Question

根据我可以为scipy graph_search找到的示例，输入图似乎采用 NxN 的形式，其中图的索引对等于该值。

所以一个矩阵

G = [ [0,5,2],
      [3,0,8],
      [12,7,0] ]  

表示 的边权重2->1是 index 的值G[1,0] = 3

如果这是错误的，请解释。

我遇到的问题是以这种方式有效地输入节点连接，从字典开始，其中键是节点，值是连接节点的数组。

{'node1' : [node2,weight1],[node3,weight2]}边缘在哪里node1->node2 = weight1

我可以遍历键的循环并创建一个新的数组[ [node1,node2,,weight1],[node1,node3,weight2] ]，但这也不会让我更接近 scipy 格式。有没有一种简单的方法可以从我可以制作的字典或迭代数组进行这种转换？

标签： pythonsearchscipygraph-theory

Answer 1

假设您已经知道图中的节点数 N 并且您的图是有向的，您可以这样做：

def create_csgraph_matrix(d, N):
    M = np.zeros((N,N))
    for i, node_weights in d.items():
        for j, weight in node_weights:
            M[i, j] = weight
    return M

d你的表格的字典在哪里。例子：

In [38]: d = {0: [[1, 10], [2, 20]], 2: [[1, 15]]}

In [39]: create_csgraph_matrix(d,3)
Out[39]: 
array([[ 0., 10., 20.],
       [ 0.,  0.,  0.],
       [ 0., 15.,  0.]])

请注意，此图中的节点是 0,1,2。