Effizient finden Sie den N-Ring jedes Knotens in einem Diagramm in Python

Question

Ich habe eine Reihe von M-Kante-Definitionen, die Mx2 ist und Knotenindizes enthält. Für jeden Knoten würde ich gerne Kanten innerhalb des n-Rings (in meinem Fall 3-Ring) des Knotens finden. Ich habe N = 250K Knoten von einem mittelgroßen Computergitter für ein kommerzielles Modell, also suche ich nach etwas entsprechend Effizientem und Spärlichem.

Answer 1

import numpy as np 
import networkx as nx 
G = nx.dorogovtsev_goltsev_mendes_graph(4) 
edges_list = G.edges() 
edges_list = np.array(edges_list) 
one_ring = [] 
for n in G.nodes(): 
    first = edges_list[edges_list[:, 0] == n, 1] 
    second = edges_list[edges_list[:, 1] == n, 0] 
    one_ring.append(np.hstack([first, second])) 
N = 3 
n_ring = [] 
def find_n_ring(root, node, i): 
    if i >= N: 
     return node 
    for node2 in one_ring[node]: 
     n_ring_node = find_n_ring(root, node2, i + 1) 
     if n_ring_node is not None and n_ring_node not in n_ring[root]: 
      n_ring[root].append(n_ring_node) 
for root in G.nodes(): 
    n_ring.append([]) 
    find_n_ring(root, root, 0) 
print(n_ring)