come calcolare i nodi "vicini" con networkx

Question

Quello che sto cercando potrebbe essere una funzione incorporata in networkx e avere un nome matematico - se sì, mi piacerebbe sapere di cosa si tratta! è molto difficile per Google, a quanto pare.

Dato un grafico G e un nodo di partenza i, vorrei trovare il sottografo di tutti i nodi "all'interno P spigoli" da i - cioè quelli che sono collegati ad i da un percorso inferiore P bordi.

mio progetto di implementazione per questo è:

import networkx as nx 

N = 30 
G = nx.Graph() 

# populate the graph... 
G.add_cycle(range(N)) 

# the starting node: 
i = 15 

# the 'distance' limit: 
P = 4 

neighborhood = [i] 
new_neighbors = [i] 
depth = 0 

while depth < P: 
    new_neighbors = list(set(sum([ 
     [k for k in G[j].keys() if k not in neighborhood] 
    for j in new_neighbors], []))) 

    neighborhood.extend(new_neighbors) 

    depth += 1 

Gneighbors = G.subgraph(neighborhood) 

Questo codice funziona, tra l'altro, in modo da non ho bisogno di aiuto con l'implementazione. Vorrei semplicemente sapere se questo ha un nome e se è fornito dalla libreria networkx.

È molto utile quando il codice si arresta in modo anomalo e si desidera visualizzare il motivo: è possibile eseguire il rendering solo della "località/regione" del grafico vicino al nodo del problema.

Answer 1

Usa single_source_shortest_path o single_source_shortest_path_length con un cut-off di p

qualcosa di simile:

nx.single_source_shortest_path_length(G ,source=i, cutoff=p) 

Answer 2

due anni di ritardo, ma ero alla ricerca di questa stessa cosa e ho trovato un built-in che penso otterrà il sottografo che desideri: ego_graph. La firma della funzione e la documentazione:

ego_graph(G, n, radius=1, center=True, undirected=False, distance=None) 

Restituisce sottografo dei vicini centrati al nodo n entro un determinato raggio indotte.