6
votes

python trouver des composants connectés dans un graphique / tuple 3D avec trois éléments?

J'ai un tableau numpy binaire 3D, pour lequel je voudrais trouver des composants connectés, i.d. éléments voisins avec la valeur 1.

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)

Alternativement, je peux obtenir les coordonnées de chaque élément avec la valeur un et obtenir un ensemble de listes avec trois éléments pour lesquels je pourrais obtenir des clusters voisins

XXX

Comment puis-je faire cela, ou implémenter une fonction 2D connected_components pour un paramètre 3D?

python graph connected-components

1 commentaires

Êtes-vous autorisé à vous déplacer uniquement le long de l'axe pour trouver des composants connectés ou sommes-nous autorisés à en faire plus

3 Réponses :

0
votes

Supposons:

Vous parlez de 6 voisins possibles d'un nœud (i, j, k) dans un graphe 3D, et par "voisin" vous entendez la distance entre le voisin et le nœud vaut 1; et
"Un composant connecté valide" signifie que nodeA et nodeB sont voisins et que les deux valeurs sont 1.

Ensuite, nous pouvons avoir une telle fonction pour obtenir les voisins possibles:

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

0 commentaires

1
votes

DFS pour rechercher les composants connectés

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()

Algo principal:

Ensemble visité de chaque point = 0 (indiquant qu'il ne fait partie d'aucun composant encore)
pour tous les points dont la valeur == 1
1. Si le point n'est pas visité, démarrez un DFS à partir de celui-ci

DFP: : il s'agit de l'algorithme DFS traditionnel utilisant Queue. La seule différence pour le cas 3D est donnée (x, y, z) nous calculons tout le voisin valide de celui-ci en utilisant itertools.product . Dans le cas 3D, chaque point aura 27 voisins y compris lui-même (3 positions et 3 valeurs possibles - idem, incrémenter, décrémenter, donc 27 voies).

La matrice v stocke les composants connectés numérotés à partir de 1.

Testcase:

when data =

XXX

Visualisation:

les deux côtés opposés sont les deux composants connectés différents

L'algorithme renvoie 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]]]

0 commentaires

2
votes

Comme suggéré dans la question, nous générons d'abord les données et trouvons les coordonnées.

Ensuite, nous pouvons utiliser kd tree cKDTree pour trouver des voisins à une distance de 1 avec query_pairs et utilisez-les comme arêtes du graphe, ce qui réduit essentiellement le problème à une recherche de composants connectés par graphe standard.

Ensuite, nous créons le graphe networkx à partir de ces arêtes avec from_edgelist et exécutez connected_components pour trouver les composants connectés.

Et la dernière étape est la visualisation.

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

Output:

Remarques:

J'ai réduit la probabilité de distribution binomiale lors de la génération des nœuds de 0,4 à 0,1 pour rendre la visualisation plus «lisible»

Je ne montre pas les composants connectés qui ne contiennent qu'un seul nœud. Cela peut être fait en décommentant la ligne sous le # pour inclure les composants connectés à un seul nœud commentaire

DataFrame df contient les coordonnées x , y et z et l'index du composant connecté c pour chaque nœud:

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

Sortie :

     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
...

Sur la base du DataFrame df , nous pouvons également vérifier des choses amusantes, comme la taille des plus gros composants connectés trouvés (avec le numéro du composant connecté):

print(df)

Sortie :

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 commentaires