CODEWITHSUNDEEP
algorithmadjacency-matrix
UndyingJellyfish
UndyingJellyfish

Reputation: 310

Creating adjacency matrix from 2D array

I have an array like the following:

a b c d 
e f g h
j k l m
n o p q

My idea is to create an adjacency matrix from this for only horizontal and vertical movement, where the costs are the ASCII value in the destination.

The solution would find the following kind of adjacency matrix (simplified 'a'=1):

  a b c d e f g h <- start
a 0 1 0 0 1 0 0 0 
b 2 0 2 0 0 2 0 0
c 0 3 0 3 0 0 3 0 
d 0 0 4 0 0 0 0 4
e 5 0 0 0 0 5 0 0
f 0 6 0 0 6 0 6 0
g 0 0 7 0 0 7 0 7
h 0 0 0 8 0 0 8 0
^ destination

I removed the last two rows of the original matrix for brevity. I've come as far as to realize that a row has only one specific cost, and has a maximum of 4 adjacencies. My question is how do I find these adjacencies? If possible, I want to only iterate through the original matrix to save myself from using the exponentially larger adjacency matrix.

Upvotes: 3

Views: 2882

Answers (1)

UndyingJellyfish
UndyingJellyfish

Reputation: 310

As with all good problems I needed some pen and paper. The solution seems to be the following code, where 'M' is the original matrix and 'adj' is the generated adjacency matrix with dimensions x and y:

makeAdjacencyMatrix(M,adj)
  for row = 0 .. y do
    for col = 0 .. x do
      val = M[row,col]
      loc = row * x + col
      above = loc - x
      below = loc + x
            
      if loc + 1 < x * y then
        adj[loc, loc + 1] = val
      if loc - 1 >= 0 then
        adj[loc, loc - 1] = val
      if above >= 0 then
        adj[loc, above] = val;
      if below < x * y then
        adj[loc, below] = val

  return adj

I will mark question as answered when possible.

Upvotes: 1

Related Questions