Python найти связанные компоненты в трехмерном графике / кортеже с тремя элементами?

Question

У меня есть двоичный трехмерный массив, для которого я хотел бы найти подключенные компоненты, т.е. соседние элементы со значением 1.

data = np.random.binomial(1, 0.4, 1000)
data = data.reshape((10,10,10))

В качестве альтернативы я могу получить координаты для каждого элемента со значением один и получить набор списков с тремя элементами, для которых я могу получить соседние кластеры

coordinates = np.argwhere(data > 0)

connected_elements = []
for node in coordinates:
  neighbors = #Get possible neighbors of node
  if neighbors not in connected_elements:
    connected_elements.append(node)
  else:
    connected_elements.index(neighbor).extend(node)

Как я могу это сделать или реализовать функцию 2D connected_components для настройки 3D?

Answer 1

DFS для поиска подключенных компонентов

import queue
import itertools
n = 10

def DFS(data, v, x,y,z, component):
    q = queue.Queue()
    q.put((x,y,z))
    while not q.empty():
        x,y,z = q.get()
        v[x,y,z] = component

        l = [[x], [y], [z]]

        for i in range(3):
            if l[i][0] > 0:
                l[i].append(l[i][0]-1)
            if l[i][0] < v.shape[1]-1:
                l[i].append(l[i][0]+1)

        c = list(itertools.product(l[0], l[1], l[2]))
        for x,y,z in c:
            if v[x,y,z] == 0 and data[x,y,z] == 1:
                q.put((x,y,z))

data = np.random.binomial(1, 0.2, n*n*n)
data = data.reshape((n,n,n))

coordinates = np.argwhere(data > 0)
v = np.zeros_like(data)

component = 1
for x,y,z in coordinates:
    if v[x,y,z] != 0:
        continue
    DFS(data, v, x,y,z, component)
    component += 1

Основной алгоритм:

1. Установить посещение каждой точки = 0 (это означает, что она не является частью какого-либо подключенного компонента пока нет)
2. для всех точек, значение которых == 1
   3. Если точка не посещена, запустите DFS, начиная с формы

DFP: : Это традиционный алгоритм DFS, использующий очередь. Единственное различие для трехмерного случая дано (x,y,z), мы рассчитываем всех действительных соседей, используя itertools.product В трехмерном случае каждая точка будет иметь 27 соседей, включая себя (3 позиции и 3 возможных значения - то же самое, приращение, уменьшение, то есть 27 путей).

В матрице v хранятся подключенные компоненты, пронумерованные начиная с 1.

TestCase:

когда данные =

 [[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[1 1 1]
  [1 1 1]
  [1 1 1]]]

Визуализация:

две противоположные стороны - это два разных соединенных компонента

Алгоритм возвращает v

[[[1 1 1]
  [1 1 1]
  [1 1 1]]

 [[0 0 0]
  [0 0 0]
  [0 0 0]]

 [[2 2 2]
  [2 2 2]
  [2 2 2]]]

что правильно.

Визуализация:

Как видно из визуализации v зеленый цвет обозначает один подключенный компонент, а синий цвет обозначает другой подключенный компонент.

Код визуализации

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def plot(data):
    fig = plt.figure(figsize=(10,10))
    ax = fig.gca(projection='3d')

    for i in range(data.shape[0]):
        for j in range(data.shape[1]):
            ax.scatter([i]*data.shape[0], [j]*data.shape[1], 
            [i for i in range(data.shape[2])], 
                   c=['r' if i == 0 else 'b' for i in data[i,j]], s=50)

plot(data)
plt.show()
plt.close('all')
plot(v)
plt.show()

Answer 2

Как предложено в вопросе, мы сначала генерируем данные и находим координаты.

Тогда мы можем использовать дерево kd cKDTree, чтобы найти соседей на расстоянии 1 с query_pairs и использовать их в качестве ребер графа, что существенно уменьшает проблему к стандартному графу подключен компонент поиска.

Затем мы создаем граф networkx из этих ребер с помощью from_edgelist и запускаем connected_components, чтобы найти связанные компоненты.

И последний шаг - это визуализация.

import pandas as pd
import numpy as np
import networkx as nx
import matplotlib.pyplot as plt
from scipy.spatial.ckdtree import cKDTree
from mpl_toolkits.mplot3d import Axes3D

# create data
data = np.random.binomial(1, 0.1, 1000)
data = data.reshape((10,10,10))

# find coordinates
cs = np.argwhere(data > 0)

# build k-d tree
kdt = cKDTree(cs)
edges = kdt.query_pairs(1)

# create graph
G = nx.from_edgelist(edges)

# find connected components
ccs = nx.connected_components(G)
node_component = {v:k for k,vs in enumerate(ccs) for v in vs}

# visualize
df = pd.DataFrame(cs, columns=['x','y','z'])
df['c'] = pd.Series(node_component)

# to include single-node connected components
# df.loc[df['c'].isna(), 'c'] = df.loc[df['c'].isna(), 'c'].isna().cumsum() + df['c'].max()

fig = plt.figure(figsize=(10,10))
ax = fig.add_subplot(111, projection='3d')
cmhot = plt.get_cmap("hot")
ax.scatter(df['x'], df['y'], df['z'], c=df['c'], s=50, cmap=cmhot)

Выход:

Примечания:

• Я уменьшил вероятность биномиального распределения при генерации узлов с 0,4 до 0,1, чтобы сделать визуализацию более «читабельной»
• Я не показываю подключенные компоненты, которые содержат только один узел. Это можно сделать, раскомментировав строку под комментарием # to include single-node connected components
• DataFrame df содержит координаты x, y и z и индекс подключенного компонента c для каждого узла:

print(df)

Выход:

     x  y  z     c
0    0  0  3  20.0
1    0  1  8  21.0
2    0  2  1   6.0
3    0  2  3  22.0
4    0  3  0  23.0
...

• На основе DataFrame df мы также можем проверить некоторые забавные вещи, такие как размеры самых больших найденных подключенных компонентов (вместе с номером подключенного компонента):

df['c'].value_counts().nlargest(5)

Выход:

4.0    5
1.0    4
7.0    3
8.0    3
5.0    2
Name: c, dtype: int64

Answer 3

Предположим:

1. Вы говорите о 6 возможных соседях узла (i, j, k) на трехмерном графике, и под "соседством" вы подразумеваете расстояние между соседом и узлом 1; и

2. «Допустимый подключенный компонент» означает, что узел A и узел B являются соседями, и оба значения равны 1.

Тогда у нас может быть такая функция, чтобы получить возможных соседей:

def get_neighbors(data, i, j, k):
    neighbors = []
    candidates = [(i-1, j, k), (i, j-1, k), (i, j, k-1), (i, j, k+1), (i, j+1, k), (i+1, j, k)]
    for candidate in candidates:
        try:
            if data[candidate] == 1:
                neighbors.append(candidate)
        except IndexError:
            pass
    return neighbors