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!
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']}
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:
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"]
