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.

possible duplicate of [Adjacency List and Adjacency Matrix in Python](http://stackoverflow.com/questions/13547133/adjacency-list-and-adjacency-matrix-in-python) — Ashwini Chaudhary, May 02 '13 at 02:29
I meant in a sense to make a matrix from a given 2d grid, I understand the implementations and have already implemented graphs. I am just looking for some ways to easily make an adjacency matrix from a 2d grid. — user2341439, May 02 '13 at 02:52
Do you mean: how do I generate the adjacency list of an M x N [grid graph](https://en.wikipedia.org/wiki/Lattice_graph)? — Wesley Baugh, May 02 '13 at 03:37

Markus Jarderot · Answer 1 · 2013-05-03T10:49:26.010

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 .

`matrix(r, c)` is a constructor that creates an `r x c` matrix. — Markus Jarderot, Aug 12 '13 at 14:41

guillefix · Answer 2 · 2017-08-30T12:15:41.117

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

Wesley Baugh · Answer 3 · 2013-05-02T18:54:06.187

I would start by manually generating a few adjacency matrices for a few examples, and see if any (easily programmable) patterns emerge. The adjacency matrix depends on how you label the nodes (in what order), so a different ordering might yield a pattern that is easier or harder to encode in a generating function.

a couple example lattice grid graphs with different structure depending on the node labeling

This is an interesting problem, and though I don't have the exact answer for you right now I will keep thinking (and perhaps this may help lead you or someone else to a solution).

score 1 · Answer 4 · answered Nov 06 '18 at 20:37

PySAL (Python Spatial Analysis Library) includes a function to create adjacency matrices -

import pysal

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

For a sparse representation:

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

For a full array representation:

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

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

score 0 · Answer 5 · answered Feb 21 '20 at 16:32

Here is a pure NumPy solution that is hopefully more intuitive. The trick is to think of the nodes in a 2d grid by considering their x, y coordinates and then connect nodes that +-1 x or y away from them. This solution does not wrap around the grid.

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

This will produce:

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

5 Answers5

Linked