11

基本上只是想知道在python中有什么好方法，我之前在python中也用一种蛮力方式做到了这一点，但这并不是直观的方式。所以如果有人能帮忙就好了。

4

5 回答 5

12

对于逐行网格，邻接矩阵如下所示：

  • 在一排内，相邻的数字形成两条平行的对角线。这占用了一个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 .
于 2013-05-02T16:01:42.290 回答
6

做到这一点的一个好方法是使用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这是通过克罗内克乘以 来完成的I。 np.kron(offdi,I)做相反的事情：在下一个块的对角线上和下放置一个单位矩阵。这意味着一个节点在上下连续行的同一列中连接到事物。

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

于 2017-08-30T11:00:07.157 回答
3

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

根据节点标签具有不同结构的几个示例格子网格图

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

于 2013-05-02T04:06:15.890 回答
1

PySAL（Python 空间分析库）包含一个创建邻接矩阵的函数 -

import pysal

w = pysal.lat2W(2, 2) # make a 2x2 lattice with rook connectivity
# <pysal.weights.weights.W at 0x257aa470128>

对于稀疏表示：

w.neighbors
# {0: [2, 1], 2: [0, 3], 1: [0, 3], 3: [1, 2]}

对于完整的数组表示：

w.full()[0]
# array([[0., 1., 1., 0.],
#        [1., 0., 0., 1.],
#        [1., 0., 0., 1.],
#        [0., 1., 1., 0.]])

见https://pysal.readthedocs.io/en/latest/users/tutorials/weights.html#spatial-weights

于 2018-11-06T20:37:40.023 回答
0

这是一个纯粹的 NumPy 解决方案，希望更直观。诀窍是通过考虑它们的 x、y 坐标来考虑 2d 网格中的节点，然后连接距离它们 +-1 x 或 y 的节点。此解决方案不会环绕网格。

def grid_adj(N: int) -> np.ndarray:
  """Creates a 2D grid adjacency matrix."""
  sqN = np.sqrt(N).astype(int)  # There will sqN many nodes on x and y
  adj = np.zeros((sqN, sqN, sqN, sqN), dtype=bool)
  # Take adj to encode (x,y) coordinate to (x,y) coordinate edges
  # Let's now connect the nodes
  for i in range(sqN):
    for j in range(sqN):
      # Connect x=i, y=j, to x-1 and x+1, y-1 and y+1
      adj[i, j, max((i-1), 0):(i+2), max((j-1), 0):(j+2)] = True
      # max is used to avoid negative slicing, and +2 is used because
      # slicing does not include last element.
  adj = adj.reshape(N, N)  # Back to node-to-node shape
  # Remove self-connections (optional)
  adj ^= np.eye(N, dtype=bool)
  return adj

# Visualise
plt.matshow(grid_adj(25))
plt.show()
# Print number of edges
np.flatnonzero(adj).size

这将产生： adj_matrix_image

于 2020-02-21T16:32:14.363 回答