Как разложить матрицу на сумму связных компонент?

Question

У меня есть матрица 0 и 1.:

 1 0 0 0 0 
     0 0 1 1 0 
    a = 0 0 1 1 0 
     1 0 0 0 0 
     1 1 0 0 0 

и я хочу использовать питон, чтобы разложить его на сумму связных компонент, где к «связному» Я имею в виду матрицы, где каждый «1» имеет, по крайней мере, другой «1» выше/ниже/слева/справа от него. В противном случае «1» должны быть изолированы:

 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
     0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 
    a = 0 0 1 1 0 = 0 0 0 0 0 + 0 0 1 1 0 + 0 0 0 0 0 
     1 0 0 0 0 0 0 0 0 0 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 1 0 0 0 

Это может быть интересно, что в этом вопросе (Largest rectangle of 1's in 2d binary matrix) Гай Adini предлагает использовать разложение BFS для разложения матрицы в компонент связности. Однако я не смог найти реализацию python, а также как использовать BFS для решения моей проблемы.

Answer 1

алгоритм, который работает следующая:

• Вы держите visited матрицу того же размера с истинно для элементов посещенных алгоритма (или, что то же самое, набор координат посещаемых элементов).

• Вы пройти через все элементы матрицы по одному:

  • Если элемент не посещался и 1, пометить его как посещенные, и вы рекурсивное всех своих соседей в том же путь. Рекурсивная функция должна возвращать набор связанных (матрица с этими, набор с их координатами и т. Д.).

Answer 2

Сюда приходят собственную реализацию. Я разрешаю вам изменять его, чтобы удалить дубликаты, если хотите.

import itertools 

class Matrix(): 
    def __init__(self, matrix): 
     self.matrix = matrix 

    def computeConnectedComponents(self): 
     rows_id = list(range(len(self.matrix))) 
     cols_id = list(range(len(self.matrix[0]))) 

     #here are the position of every 1 in the grid. (row number, column number) indexes start at 0 
     positions = [couple for couple in self.generate_pairs(rows_id, cols_id) if self.matrix[couple[0]][couple[1]]==1] 

     #here we store all the connected component finded 
     allConnectedComponents = [] 

     #while there is position not affected to any connected component 
     while positions != [] : 
      #the first element is taken as start of the connected component 
      to_explore = [positions.pop(0)] 
      currentConnectedComponent = set() 
      #while there is node connected to a node connected to the component 
      while list(to_explore) != []: 
       currentNode = to_explore.pop() 
       currentConnectedComponent.add(currentNode) 

       to_explore += [coord for coord in self.node_neighbourhood(currentNode) if (self.matrix[coord[0]][coord[1]]==1 and (coord not in to_explore) and (coord not in currentConnectedComponent))] 

       allConnectedComponents.append(currentConnectedComponent) 
       positions = [position for position in positions if position not in currentConnectedComponent] 

     return allConnectedComponents 

    #http://stackoverflow.com/questions/16135833/generate-combinations-of-elements-from-multiple-lists 
    def generate_pairs(self, *args): 
     for i, l in enumerate(args, 1): 
      for x, y in itertools.product(l, itertools.chain(*args[i:])): 
       yield (x, y) 

    def node_neighbourhood(self, coordinates): 
     row, column = coordinates[0], coordinates[1] 
     result = [] 
     if (row - 1) >= 0 : 
      result.append((row-1, column)) 
     if (row + 1) < len(self.matrix): 
      result.append((row+1, column)) 
     if (column - 1) >= 0: 
      result.append((row, column-1)) 
     if (column + 1) < len(self.matrix[0]): 
      result.append((row, column+1)) 
     return result 


if __name__ == "__main__": 
    data = [[1,0,0,0,0], 
      [0,0,1,1,0], 
      [0,0,1,1,0], 
      [1,0,0,0,0], 
      [1,1,0,0,0]] 

    matrix = Matrix(data) 
    for connectedComponent in matrix.computeConnectedComponents(): 
     print(connectedComponent)