Creating an adjacency list graph from a matrix in python

Question

So I'm trying to make a graph of letters (to represent a boggle board) from a matrix of letters. So say I have something like:

[ [ A, B, C, D], 
  [E, F, G, H], 
  [I, J, K, L], 
  [M, N, O, P] ].

I want each node to be a letter, but I'm having trouble figuring out how to get the neighbors for each node. For example, node A would have neighbors B, E, and F. While node K would have neighbors F, G, H, J, L, M, O, and P. Any help would be appreciated!

if you are talking about [graphs in python](http://www.python-course.eu/graphs_python.php) you should change your approach. — bhansa, Aug 05 '16 at 06:49
"Any help would be appreciated!" is [not a question](https://meta.stackoverflow.com/questions/284236). "I'm having trouble figuring out" can't be answered clearly, because we don't know what the trouble is. — Karl Knechtel, Sep 06 '22 at 05:35

score 2 · Answer 1 · edited May 23 '17 at 11:51

Assuming your matrix is an n x m matrix, and each element is a unique string like the following:


    # The matrix

matrix = [
    ['A', 'B', 'C', 'D'],
    ['E', 'F', 'G', 'H'],
    ['I', 'J', 'K', 'L'],
    ['M', 'N', 'O', 'P']
]

You can first locate the index of the element:


    node = 'K' # Input

    # Get the matrix dimension
    n = len(matrix)
    m = len(matrix[0])

    # Assume there is exactly one matching node
    for i in xrange(n):
        for j in xrange(m):
            if matrix[i][j] == node:
                x, y = i, j

And then return the neighbors as a list:

    # Get the (at most) 8 neighbors

    neighbors = [row[max(0,y-1):y+2] for row in matrix[max(0,x-1):x+2]]
    answer = set([v for r in neighbors for v in r])
    answer.remove(node)
    answer = list(answer)

If the node can have multiple occurrences, see How to find the index of a value in 2d array in Python? Also these links might be useful for you if you are new to Python:

score 2 · Accepted Answer · answered Aug 05 '16 at 08:24

You could loop through every node in your matrix and then add every neighboring node at right & below to the result:

matrix = [
    ['A', 'B', 'C', 'D'],
    ['E', 'F', 'G', 'H'],
    ['I', 'J', 'K', 'L'],
    ['M', 'N', 'O', 'P']
]

def add(adj_list, a, b):
    adj_list.setdefault(a, []).append(b)
    adj_list.setdefault(b, []).append(a)

adj_list = {}
for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        if j < len(matrix[i]) - 1:
            add(adj_list, matrix[i][j], matrix[i][j+1])
        if i < len(matrix[i]) - 1:
            for x in range(max(0, j - 1), min(len(matrix[i+1]), j+2)):
                add(adj_list, matrix[i][j], matrix[i+1][x])

import pprint
pprint.pprint(adj_list)

Output:

{'A': ['B', 'E', 'F'],
 'B': ['A', 'C', 'E', 'F', 'G'],
 'C': ['B', 'D', 'F', 'G', 'H'],
 'D': ['C', 'G', 'H'],
 'E': ['A', 'B', 'F', 'I', 'J'],
 'F': ['A', 'B', 'C', 'E', 'G', 'I', 'J', 'K'],
 'G': ['B', 'C', 'D', 'F', 'H', 'J', 'K', 'L'],
 'H': ['C', 'D', 'G', 'K', 'L'],
 'I': ['E', 'F', 'J', 'M', 'N'],
 'J': ['E', 'F', 'G', 'I', 'K', 'M', 'N', 'O'],
 'K': ['F', 'G', 'H', 'J', 'L', 'N', 'O', 'P'],
 'L': ['G', 'H', 'K', 'O', 'P'],
 'M': ['I', 'J', 'N'],
 'N': ['I', 'J', 'K', 'M', 'O'],
 'O': ['J', 'K', 'L', 'N', 'P'],
 'P': ['K', 'L', 'O']}

score 0 · Answer 3 · answered Aug 05 '16 at 06:51

You have to use dictionary to store the nodes connected to a node :

g = { "A" : ["D", "F"],
      "B" : ["C"],
      "C" : ["B", "C", "D", "E"],
      "D" : ["A", "C"],
      "E" : ["C"],
      "F" : ["D"]
    }

depending on the structure of your graph.

To get the neighbors of a node in the graph you can simply access the node's value

>>> g["A"]
>>> ["D","F"]

Creating an adjacency list graph from a matrix in python

3 Answers3

Linked