Matrix search: Finding the blocks of neighboring fields in a matrix with Python

Task

In this article we will look at a solution in python to the following grid search task:

Find the biggest block of adjoining elements of the same kind and into how many blocks the matrix is divided. As adjoining blocks, we will consider field touching by the sides and not the corners.

Input data

For the ease of the explanation, we will be looking at a simple 3×4 matrix with elements of three different kinds, 0, 1 and 2 (see above). To test the code, we will simulate data to achieve different matrix sizes and a varied number of element types. It will also allow testing edge cases like, where all elements are the same or all elements are different.

To simulate some test data for later, we can use the numpy randint() method:

import numpy as np
matrix = [[0,0,1,1], [0,1,2,2], [0,1,1,2]]

matrix_test1 = np.random.randint(3, size = (5,5))
matrix_test2 = np.random.randint(5, size = (10,15))

The code

def find_blocks(matrix):
    visited = []
    block_list = []     
    for x in range(len(matrix)):
        for y in range(len(matrix[0])):
            if (x, y) not in visited:
                field_count, visited = explore_block(x, y, visited)
                block_list.append(field_count)                 
    return print('biggest block: {0}, number of blocks: {1}'
                 .format(max(block_list), len(block_list)))

def explore_block(x, y, visited):
    queue = {(x,y)}
    field_count = 1
    while queue:  
        x,y = queue.pop()
        visited.append((x,y))
        if x+1<len(matrix) and (x+1,y) not in visited and (x+1,y) not in queue:
            if matrix[x+1][y] == matrix[x][y]:
                field_count += 1
                queue.add((x+1,y))         
        if x-1>=0 and (x-1,y) not in visited and (x-1,y) not in queue:
            if matrix[x-1][y] == matrix[x][y]:
                field_count += 1
                queue.add((x-1,y))                    
        if y-1>=0 and (x,y-1) not in visited and (x,y-1) not in queue:
            if matrix[x][y-1] == matrix[x][y]:
                field_count += 1
                queue.add((x,y-1))                    
        if y+1<len(matrix[0]) and (x,y+1) not in visited and (x,y+1) not in queue:
            if matrix[x][y+1] == matrix[x][y]:
                field_count += 1
                queue.add((x,y+1))                                              
    return field_count, visited

How the code works

In summary, the algorithm loops through all fields of the matrix looking for unseen fields that will serve as a starting point for a local exploration of each block of color – the find_blocks() function. The local exploration is done by looking at the neighboring fields and if they are within the same kind, moving to them to explore further fields – the explore_block() function. The fields that have already been seen and counted are stored in the visited list.

find_blocks() function:

1. Finds a starting point of a new block
2. Runs a the explore_block() function for local exploration of the block
3. Appends the size of the explored block
4. Updates the list of visited points
5. Returns the result, once all fields of the matrix have been visited.

explore_block() function:

1. Takes the coordinates of the starting field for a new block and the list of visited points
2. Creates the queue set with the starting point
3. Sets the size of the current block (field_count) to 1
4. Starts a while loop that is executed for as long as the queue is not empty
   1. Takes an element of the queue and uses its coordinates as the current location for further exploration
   2. Adds the current field to the visited list
   3. Explores the neighboring fields and if they belong to the same block, they are added to the queue
   4. The fields are taken off the queue for further exploration one by one until the queue is empty
5. Returns the field_count of the explored block and the updated list of visited fields
   

Execute the function

find_blocks(matrix)

The returned result is biggest block: 4, number of blocks: 4.

Run the test matrices:

find_blocks(matrix_test1)
find_blocks(matrix_test2)

Visualization

The matrices for the article were visualized with the seaborn heatmap() method.

import seaborn as sns
import matplotlib.pyplot as plt
# use annot=False for a matrix without the number labels
sns.heatmap(matrix, annot=True, center = 0, linewidths=.5, cmap = "viridis",
            xticklabels=False, yticklabels=False, cbar=False, square=True)
plt.show()

About Author

Emilia Cheladze

Emilia Cheladze is a Data Scientist with a background in neuroscience, who is passionate about exploring business insights. Before she started working for DATANOMIQ she received M. Sc. from the Berlin School of Mind and Brain, Humboldt Universität zu Berlin and a B. Sc. in Cognitive Science from Nicolaus Copernicus University in Torun, Poland.

See author's posts