Counting dots by finding clusters of 1's in binary matrices.

group_finder.py

def groupify(binary_matrix):
    """
    Finds all distinct groups of 1's in a 2x2 binary matrix

    :param binary_matrix: A 2x2 binary matrix
    :type binary_matrix: list
    :return: A matrix with all nodes, arranged in a disjoint set forest
    :rtype: list
    """

    n, m = len(binary_matrix), len(binary_matrix[0])
    set_matrix = [[None for _ in range(m)] for _ in range(n)]

    for i, row in enumerate(binary_matrix):
        for j, cell in enumerate(row):
            if cell == 1:
                set_matrix[i][j] = Node(j, i)

    for i in range(n):
        for j in range(m):
            if set_matrix[i][j]:
                for k in range(i + 1, i - 2, -1):
                    for l in range(j + 1, j - 2, -1):
                        if n > k >= 0 and m > l >= 0:
                            if set_matrix[k][l]:
                                set_matrix[i][j].union(set_matrix[k][l])
    return set_matrix


def get_set_forest(set_matrix):
    set_forest = set()

    for row in set_matrix:
        for cell in row:
            if cell:
                set_forest.add(cell.parent)
    return set_forest


if __name__ == '__main__':
    from random import choice

    def main(matrix):
        set_matrix = groupify(matrix)
        for row in set_matrix:
            for cell in row:
                print(cell if cell else '.', end='')
            print()

        print(get_set_forest(set_matrix))


    """ MATRICIES """
    M1 = [[0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
          [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1],
          [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1],
          [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
          [0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1],
          [1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0],
          [1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]]

    M2 = [[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
          [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0],
          [1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
          [0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0],
          [1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
          [0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0],
          [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]]

    M3 = [[0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
          [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
          [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
          [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
          [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
          [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
          [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
          [1, 0, 1, 0, 1, 0, 1, 0, 1, 0],
          [0, 1, 0, 1, 0, 1, 0, 1, 0, 1],
          [1, 0, 1, 0, 1, 0, 1, 0, 1, 0]]

    M4 = [[1, 1],
          [1, 1],
          [1, 1],
          [1, 1],
          [0, 0],
          [1, 1]]

    M5 = [[1, 0, 1],
          [1, 1, 0],
          [1, 0, 0]]

    M6 = [[1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1]]

    _l = [0,0,0,0,0,0,1]
    n, m = 100, 100
    M7 = [[choice(_l) for _ in range(m)] for _ in range(n)]
    """ END MATRICIES """

    main(M1)

set_tree_node.py

class Node:
    """ Class that represents a node in a tree """

    i = 0  # Class vaiable used to uniquely name each node

    def __init__(self, x, y):
        """ Constructs a node from the cell at coordinates (x, y) """
        self.coord = (x, y)
        self.parent = self
        self.rank = 0
        self.name = chr((Node.i % 26) + 65)  # Names start at ASCII 65 = 'A'
        Node.i += 1

    def find_set(self):
        """ Finds the parent of the node, thereby flattening the tree structure """
        if self.parent != self:
            self.parent = self.parent.find_set()
        return self.parent

    @staticmethod
    def link(own_parent, other_parent):
        """ Joins two trees by making one parent the parent of the other based on their rank """
        if own_parent.rank > other_parent.rank:
            other_parent.parent = own_parent
        else:
            own_parent.parent = other_parent
            if own_parent.rank == other_parent.rank:
                other_parent.rank += 1

    def union(self, other):
        """ Finds the parent of both nodes and joins their trees """
        if self.parent != other.parent:
            self.link(self.find_set(), other.find_set())

    def __bool__(self):
        """ Used in make_set_forest to make sure there is a node """
        return True

    def __str__(self):
        """ Returns the name of the parent node """
        return self.parent.name

    def __repr__(self):
        return '<Node: name=' + self.name + ' rank=' + str(self.rank) + '>'