你怎么能建立一个模拟二维网格的邻接矩阵

Question

基本上只是想知道这样做的好方法是在python中,我之前在python中使用了一种强力方式,但它只是不是直观的方式.所以,如果有人能帮忙,那就好了.

Answer 1

对于逐行网格,邻接矩阵如下所示:

• 在一行内,相邻的数字形成两个平行的对角线.这占据了Columns × Columns子矩阵,每个子矩阵沿着大矩阵的对角线重复.
• 相邻的行形成一个对角线.这占据了两个对角线,在行 - 子矩阵外偏移.

row 1 row 2 row 3
----- ----- -----  _
A A A 1 . . . . .   |
A A A . 1 . . . .   | row 1
A A A . . 1 . . .  _|
1 . . B B B 1 . .   |
. 1 . B B B . 1 .   | row 2
. . 1 B B B . . 1  _|
. . . 1 . . C C C   |
. . . . 1 . C C C   | row 3
. . . . . 1 C C C  _|

子矩阵在主对角线的每一侧都有两个对角线:

column
1 2 3 4 5 6
- - - - - -
. 1 . . . .  1 column
1 . 1 . . .  2
. 1 . 1 . .  3
. . 1 . 1 .  4 
. . . 1 . 1  5
. . . . 1 .  6

def make_matrix(rows, cols):
    n = rows*cols
    M = matrix(n,n)
    for r in xrange(rows):
        for c in xrange(cols):
            i = r*cols + c
            # Two inner diagonals
            if c > 0: M[i-1,i] = M[i,i-1] = 1
            # Two outer diagonals
            if r > 0: M[i-cols,i] = M[i,i-cols] = 1

对于3×4网格,矩阵看起来像:

. 1 . . 1 . . . . . . . 
1 . 1 . . 1 . . . . . . 
. 1 . 1 . . 1 . . . . . 
. . 1 . . . . 1 . . . . 
1 . . . . 1 . . 1 . . . 
. 1 . . 1 . 1 . . 1 . . 
. . 1 . . 1 . 1 . . 1 . 
. . . 1 . . 1 . . . . 1 
. . . . 1 . . . . 1 . . 
. . . . . 1 . . 1 . 1 . 
. . . . . . 1 . . 1 . 1 
. . . . . . . 1 . . 1 . 

Answer 2

一个很好的方法是使用Kronecker 乘积，它允许您快速构建一个类似于 Markus Jarderot 描述的矩阵。

这是具有周期性边界条件的晶格的代码

import scipy.linalg as la
import numpy as np
offdi = la.circulant([0,1,0,0,1])
I = np.eye(5)

import matplotlib.pyplot as plt
A = np.kron(offdi,I) + np.kron(I,offdi)
plt.matshow(A)
plt.show()

此处np.kron(I,offdi)将矩阵offdi用于对网格一行内的连通性进行编码，位于主块对角线上。这是通过 Kronecker 乘以 来完成的I。 np.kron(offdi,I)做相反的事情：在下一个块对角线上和向下放置一个单位矩阵。这意味着一个节点向上和向下连接到连续行中同一列中的事物。

如果您希望网格是非周期性的，而只是具有没有链接的边界，则可以使用 Toeplitz 构造而不是循环构造： la.toeplitz([0,1,0,0,0])

Answer 3

我将首先为一些示例手动生成一些邻接矩阵，然后查看是否出现任何（易于编程的）模式。邻接矩阵取决于您如何标记节点（以什么顺序），因此不同的顺序可能会产生在生成函数中更容易或更难编码的模式。

这是一个有趣的问题，虽然我现在没有给你确切的答案，但我会继续思考（也许这可能有助于引导你或其他人找到解决方案）。