Как создать матрицу смежности, которая имитирует 2-мерную сетку

Для сетки по строкам матрица смежности выглядит так:

• В одном ряду соседние числа образуют две параллельные диагонали. Это занимает субматрицу Столбцы Столбцы, каждая из которых повторяется по диагонали большой матрицы.
• Соседние ряды образуют одну диагональ. Он занимает две диагонали со смещением сразу за пределами субматриц строки.

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 . 

Хороший способ сделать это - использовать продукт Кронекера, который позволяет быстро построить такую ​​матрицу, как тот, который описывает Маркус Джардерот.

Вот код для решетки с периодическими граничными условиями

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) делает обратное: помещает единичную матрицу по диагоналям следующего блока вверх и вниз. Это означает, что узел связан с объектами в своем столбце в непрерывной строке вверх и вниз.

Если вы хотите, чтобы сетка была непериодической и вместо этого имела границы без связей, вы можете использовать конструкцию Теплица вместо циркулянтной: la.toeplitz([0,1,0,0,0])

Я бы начал с создания вручную нескольких матриц смежности для нескольких примеров и посмотрел, появятся ли какие-нибудь (легко программируемые) шаблоны. Матрица смежности зависит от того, как вы маркируете узлы (в каком порядке), поэтому другой порядок может дать шаблон, который легче или сложнее закодировать в генерирующей функции.

Это интересная проблема, и хотя сейчас у меня нет точного ответа, я буду продолжать думать (и, возможно, это может помочь вам или кому-то другому прийти к решению).

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

Вот чистое решение NumPy, которое, надеюсь, более интуитивно понятно. Уловка состоит в том, чтобы думать об узлах в 2-мерной сетке, рассматривая их координаты x, y, а затем соединять узлы, которые находятся на + -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

Это создаст: