How can you make an adjacency matrix which would emulate a 2d grid

Question

Basically just want to know what a good way to do this is in python, I have done this before with a kind of bruteforce way also in python but it just doesnt to be the intuitive way. So if anyone could help out it would be good.

Answer 1

A good way to do this is using the Kronecker product, which allows you to quickly construct a matrix like the one which Markus Jarderot describes.

Here's the code for a lattice with periodic boundary conditions

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()

Here np.kron(I,offdi) places the matrix offdi, which encodes the connectivity within a row of the grid, in the main block diagonal. This is done by Kronecker multiplying by I. np.kron(offdi,I) does the opposite: placing an identity matrix in the next block diagonals up and down. This means a node is connected to things in its same column in the contiguous row up and down.

If you wanted the grid to be non-periodic, and instead just have boundaries without links, you can use a Toeplitz construction instead of a circulant one: la.toeplitz([0,1,0,0,0])

Answer 2

For the row-by-row grid, the adjacency-matrix looks like this:

• Within one row, the adjacent numbers form two parallel diagonals. This occupies a Columns × Columns sub-matrix each, repeated along the diagonal of the large matrix.
• The adjacent rows form one diagonal. This occupies two diagonals, offset just outside the row-sub-matrices.

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  _|

The sub-matrices have two diagonals, on each side of the main diagonal:

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

For a 3 × 4 grid, the matrix looks like:

. 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 .