从二维网格numpy阵列获取邻接矩阵的优化方法

Question

给定一个值数组：

x = array([[0, 1, 2],
           [3, 4, 5],
           [6, 7, 8]])

我想知道是否有一种最佳方法可以轻松获得其等效邻接矩阵：

M = array([[ inf,   1.,  inf,   3.,   4.,  inf,  inf,  inf,  inf],
           [  0.,  inf,   2.,   3.,   4.,   5.,  inf,  inf,  inf],
           [ inf,   1.,  inf,  inf,   4.,   5.,  inf,  inf,  inf],
           [  0.,   1.,  inf,  inf,   4.,  inf,   6.,   7.,  inf],
           [  0.,   1.,   2.,   3.,  inf,   5.,   6.,   7.,   8.],
           [ inf,   1.,   2.,  inf,   4.,  inf,  inf,   7.,   8.],
           [ inf,  inf,  inf,   3.,   4.,  inf,  inf,   7.,  inf],
           [ inf,  inf,  inf,   3.,   4.,   5.,   6.,  inf,   8.],
           [ inf,  inf,  inf,  inf,   4.,   5.,  inf,   7.,  inf]])

这个想法实际上是在networkx中构建一个对象，我希望获得单元网格的邻接矩阵，以便能够在networkx中加载该矩阵，但如果有更好的方法实现它，我愿意接受建议。 根据文档，我已经能够找到grid_2d_graph（）函数，该函数允许在给定原始矩阵的n行和m列的情况下对我想要的图进行尺寸标注，但是我希望权重从一个节点转移到另一个节点（如果可能），即目标节点占用的数组的值

编辑

尽管所提出的示例是一种特殊情况（方阵和有序值），但对于维数不一定相等且随机值的任何矩阵都会出现问题

Answer 1

使用networkx从数组构造隐含网络，我们 将每个di图形边的权重指定为 目标节点。然后，我们可以使用adj_matrix（）函数来生成 矩阵：

import networkx as nx
import numpy as np

x = np.arange(9).reshape(3, 3)
G = nx.DiGraph()
# Ensure nodes sort order
G.add_nodes_from(np.arange(9))
i1, j1 = x.shape
for i in range(i1):
    for j in range(j1):
        if i < i1-1:
            G.add_edge(x[i,j], x[i+1,j], weight=x[i+1,j])
            G.add_edge(x[i+1,j], x[i,j], weight=x[i,j])
            if j > 0:
                G.add_edge(x[i,j], x[i+1,j-1], weight=x[i+1,j-1])
                G.add_edge(x[i+1,j-1], x[i,j], weight=x[i,j])
        if j < j1-1:
            G.add_edge(x[i,j], x[i,j+1], weight=x[i,j+1])
            G.add_edge(x[i,j+1], x[i,j], weight=x[i,j])
            if i < i1-1:
                G.add_edge(x[i,j], x[i+1,j+1], weight=x[i+1,j+1])
                G.add_edge(x[i+1,j+1], x[i,j], weight=x[i,j])
            if i > 0:
                G.add_edge(x[i,j], x[i-1,j+1], weight=x[i-1,j+1])
                G.add_edge(x[i-1,j+1], x[i,j], weight=x[i,j])
am1 = nx.adj_matrix(G).todense().astype(float)
np.putmask(am1, am1==0, np.inf)
print(am1)

输出：

# [[inf  1. inf  3.  4. inf inf inf inf]
#  [inf inf  2.  3.  4.  5. inf inf inf]
#  [inf  1. inf inf  4.  5. inf inf inf]
#  [inf  1. inf inf  4. inf  6.  7. inf]
#  [inf  1.  2.  3. inf  5.  6.  7.  8.]
#  [inf  1.  2. inf  4. inf inf  7.  8.]
#  [inf inf inf  3.  4. inf inf  7. inf]
#  [inf inf inf  3.  4.  5.  6. inf  8.]
#  [inf inf inf inf  4.  5. inf  7. inf]]

Answer 2

我想这就是你想要的：

def create_adj_mat(x):
    y = np.ones([x.size,np.max(x)+1]) * np.inf #initialize
    for I,i in enumerate(np.ravel(x)): 
        #get adjacent values of y and x points
        d = x[max(0,I//x.shape[1]-1):min(x.shape[0],I//x.shape[1]+2),  
              max(0,I%x.shape[1]-1):min(x.shape[1],I%x.shape[1]+2)]
        y[I,np.ravel(d)] = np.ravel(d) 
    np.fill_diagonal(y,np.inf) #remove i,i points
    return y

它遍历输入矩阵的散列值，并查找相邻值（-1和+2偏移量，+2，因为python索引），并根据这些值设置数组y

当你通过矩阵时，你会得到：

x = np.array([[0, 1, 2], 
            [3, 4, 5], 
            [6, 7, 8]])
y = create_adj_mat(x)
print(y)

array([[inf,  1., inf,  3.,  4., inf, inf, inf, inf],
   [ 0., inf,  2.,  3.,  4.,  5., inf, inf, inf],
   [inf,  1., inf, inf,  4.,  5., inf, inf, inf],
   [ 0.,  1., inf, inf,  4., inf,  6.,  7., inf],
   [ 0.,  1.,  2.,  3., inf,  5.,  6.,  7.,  8.],
   [inf,  1.,  2., inf,  4., inf, inf,  7.,  8.],
   [inf, inf, inf,  3.,  4., inf, inf,  7., inf],
   [inf, inf, inf,  3.,  4.,  5.,  6., inf,  8.],
   [inf, inf, inf, inf,  4.,  5., inf,  7., inf]])

编辑

假设表示的是一个非有序的非方矩阵，我对代码做了一个小改动，如下所示：

def create_adj_mat(x):
    y = np.ones([np.max(x)+1,np.max(x)+1]) * np.inf #initialize
    for I,i in enumerate(np.ravel(x)): 
        #get adjacent values of y and x points
        d = x[max(0,I//x.shape[1]-1):min(x.shape[0],I//x.shape[1]+2),  
              max(0,I%x.shape[1]-1):min(x.shape[1],I%x.shape[1]+2)] 
        y[i,np.ravel(d)] = np.ravel(d) 
    np.fill_diagonal(y,np.inf) #remove i,i points
    return y

然后，当您通过这样一个数组时：

d = np.array([[10,3],[5,12],[2,1]])
create_adj_mat(d)
array([[inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf, inf,  2., inf, inf,  5., inf, inf, inf, inf, inf, inf, 12.],
   [inf,  1., inf, inf, inf,  5., inf, inf, inf, inf, inf, inf, 12.],
   [inf, inf, inf, inf, inf,  5., inf, inf, inf, inf, 10., inf, 12.],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf,  1.,  2.,  3., inf, inf, inf, inf, inf, inf, 10., inf, 12.],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf, inf, inf,  3., inf,  5., inf, inf, inf, inf, inf, inf, 12.],
   [inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf],
   [inf,  1.,  2.,  3., inf,  5., inf, inf, inf, inf, 10., inf, inf]])