Определение наибольшего компонента связности в матрице

У меня есть матрица python numpy с 1 и 0, мне нужно определить самую большую «коллекцию» 1 в матрице: http://imgur.com/4JPZufS

Матрица может иметь до 960 000 элементов, поэтому я хотел бы избежать решения грубой силы.

Как разумнее всего решить эту проблему?


python algorithm matrix connected-components depth-first-search
person NicolaiF    schedule 23.04.2015    source источник
comment
Вы уже пытались это сделать? Как насчет того, чтобы поделиться тем, что у вас уже есть?   -  person Jake Griffin    schedule 23.04.2015
comment
У меня есть реализация, в которой я делю матрицу на подматрицы, затем беру сумму этих подматриц и нахожу наибольшую, я делаю это дважды, а затем перебираю решение, проверяя соседние поля и добавляя компонент в кластер   -  person NicolaiF    schedule 23.04.2015
comment
Если вам не нужна собственная реализация (например, если это домашнее задание), ознакомьтесь с модулем python NetworkX (networkx. github.io) и соответствующий вопрос здесь: stackoverflow.com/questions/24374627/   -  person Jake Griffin    schedule 23.04.2015
comment
Спасибо. Посмотрю!   -  person NicolaiF    schedule 23.04.2015

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете использовать структуру данных под названием disjoint-set (здесь — реализация Python). Эта структура данных была разработана для такого рода задач.

Вы перебираете строки, если текущий элемент равен 1, проверяете, равен ли какой-либо из уже пройденных соседей 1. Если это так, добавьте этот элемент в его набор. Если существует более 1 объединения этих наборов. Если нет соседей 1, создайте новый набор. В конце выведите самый большой набор.

Это будет работать следующим образом:

def MakeSet(x):
  x.parent = x
  x.rank   = 0
  x.size = 1

def Union(x, y):
  xRoot = Find(x)
  yRoot = Find(y)
  if xRoot.rank > yRoot.rank:
    yRoot.parent = xRoot
  elif xRoot.rank < yRoot.rank:
    xRoot.parent = yRoot
  elif xRoot != yRoot: # Unless x and y are already in same set, merge them
    yRoot.parent = xRoot
    xRoot.rank = xRoot.rank + 1
  x.size += y.size
  y.size = x.size

def Find(x):
  if x.parent == x:
    return x
  else:
    x.parent = Find(x.parent)
    return x.parent

""""""""""""""""""""""""""""""""""""""""""

class Node:
  def __init__ (self, label):
    self.label = label
  def __str__(self):
    return self.label

rows = [[1, 0, 0], [1, 1, 0], [1, 0, 0]]
setDict = {}
for i, row in enumerate(rows):
  for j, val in enumerate(row):
    if row[j] == 0:
      continue
    node = Node((i, j))
    MakeSet(node)
    if i > 0:
      if rows[i-1][j] == 1:
        disjointSet = setDict[(i-1, j)]
        Union(disjointSet, node)
    if j > 0:
      if row[j-1] == 1:
      disjointSet = setDict[(i, j-1)]
      Union(disjointSet, node)
    setDict[(i, j)] = node
print max([l.size for l in setDict.values()])

>> 4

Это полный рабочий пример с кодом для непересекающегося множества, взятого по ссылке выше.

person Benjy Kessler    schedule 23.04.2015
comment
На самом деле, если вы заранее знаете края, непересекающийся набор несколько излишен. вместо этого вы можете просто выполнить обход графа - person Niklas B.; 23.04.2015

arrow_upward
2
arrow_downward

Я думаю, что в предоставленном ответе счет будет отключен. Например. если строки изменены на rows = [[1, 0, 0], [1, 1, 1], [1, 0, 0]], все равно будет 4, хотя должно быть 5. Изменение Union на

def Union(x, y):
  xRoot = Find(x)
  yRoot = Find(y)
  if xRoot.rank > yRoot.rank:
    yRoot.parent = xRoot
    xRoot.size += yRoot.size
  elif xRoot.rank < yRoot.rank:
    xRoot.parent = yRoot
    yRoot.size += xRoot.size
  elif xRoot != yRoot:  # Unless x and y are already in same set, merge them
    yRoot.parent = xRoot
    xRoot.rank = xRoot.rank + 1
    xRoot.size += yRoot.size

вроде исправляется.

person Ken    schedule 11.07.2017