Recupera i nodi connessi in un grafico NetworkX

Question

Domanda diretta: Vorrei recuperare tutti i nodi connessi a un determinato nodo all'interno di un grafico NetworkX per creare un sottografo. Nell'esempio mostrato di seguito, voglio solo estrarre tutti i nodi all'interno del cerchio, dato il nome di uno qualsiasi di loro.

Ho provato la seguente funzione ricorsiva, ma ha colpito limite di ricorsione di Python, anche se ci sono solo 91 nodi di questa rete.

Indipendentemente dal fatto che il codice riportato di seguito sia difettoso, qual è il modo migliore per fare ciò che sto cercando di ottenere? Farò funzionare questo codice su grafici di varie dimensioni e non saprò in anticipo quale sarà la profondità massima di ricorsione.

def fetch_connected_nodes(node, neighbors_list): 
    for neighbor in assembly.neighbors(node): 
     print(neighbor) 
     if len(assembly.neighbors(neighbor)) == 1: 
      neighbors_list.append(neighbor) 
      return neighbors_list 
     else: 
      neighbors_list.append(neighbor) 
      fetch_connected_nodes(neighbor, neighbors_list) 

neighbors = [] 
starting_node = 'NODE_1_length_6578_cov_450.665_ID_16281' 
connected_nodes = fetch_connected_nodes(starting_node, neighbors) 

Answer 1

Assumendo il grafico è non orientato, ci è un comando networkx incorporato per questo:

node_connected_component(G, n) 

La documentazione è here. Restituisce tutti i nodi nel componente connesso di G contenente n.

Non è ricorsivo, ma non penso che tu abbia effettivamente bisogno o anche solo di quello.

---

commenti sul tuo codice: hai un bug che spesso causare una ricorsione infinita. Se u e v sono vicini entrambi con grado almeno 2, quindi inizierà con u, inserirà v nell'elenco e durante l'elaborazione di v inserisce u nell'elenco e continua a ripetere. Deve cambiare per elaborare solo i vicini che non sono in neighbors_list. È costoso controllarlo, quindi usa un set. C'è anche un piccolo problema se il nodo di partenza ha il grado 1. Il test per il grado 1 non fa ciò che stai cercando.Se il nodo iniziale ha il grado 1, ma il suo vicino ha un grado più elevato, non troverà i vicini del vicino.

Ecco una modifica del codice:

def fetch_connected_nodes(G, node, seen = None): 
    if seen == None: 
     seen = set([node]) 
    for neighbor in G.neighbors(node): 
     print(neighbor) 
     if neighbor not in seen: 
      seen.add(neighbor) 
      fetch_connected_nodes(G, neighbor, seen) 
    return seen 

Si chiama questo come fetch_connected_nodes(assembly, starting_node).

Answer 2

È possibile utilizzare semplicemente una ricerca di ampiezza a partire dal nodo specificato o da qualsiasi nodo.

In NetworkX si può avere l'albero-grafico da nodo di partenza utilizzando la funzione di:

bfs_tree(G, source, reverse=False) 

Ecco un link al documento: Network bfs_tree.

Answer 3

Ecco un algoritmo ricorsivo per connettere tutti i nodi a un nodo di input.

def create_subgraph(G,sub_G,start_node): 
sub_G.add_node(start_node) 
for n in G.neighbors_iter(start_node): 
    if n not in sub_G.neighbors(start_node): 
     sub_G.add_path([start_node,n]) 
     create_subgraph(G,sub_G,n) 

Credo che la cosa chiave qui per evitare chiamate ricorsive infinite è la condizione di verificare che il nodo che è prossimo nel grafico originale non è già collegata nella sub_G che si sta creando. Altrimenti, andrai sempre avanti e indietro e i bordi tra i nodi che hanno già dei bordi.

ho provato la seguente:

G = nx.erdos_renyi_graph(20,0.08) 
nx.draw(G,with_labels = True) 
plt.show() 
sub_G = nx.Graph() 
create_subgraph(G,sub_G,17) 
nx.draw(sub_G,with_labels = True) 
plt.show() 

Troverete nell'immagine allegata, il grafico completo e l'sub_graph che contiene il nodo 17.