Come generare un sottografo completamente connesso dalla lista dei nodi usando il modulo networkx di python

Question

Ho bisogno di generare un sottografo completamente connesso con networkx, a partire dall'elenco dei nodi che voglio collegare. Fondamentalmente, voglio che tutti i nodi nella lista che passo alla funzione siano tutti collegati tra loro.

Mi chiedo se non ci sia una funzione integrata per raggiungere questo obiettivo (che non ho trovato)? O dovrei pensare ad un algoritmo?

Grazie mille.

Answer 1

non so di qualsiasi metodo che fa questo, ma si può facilmente imitare il metodo complete_graph() di NetworkX e leggermente cambiarlo (quasi come un built-in):

import networkx 
import itertools 

def complete_graph_from_list(L, create_using=None): 
    G = networkx.empty_graph(len(L),create_using) 
    if len(L)>1: 
     if G.is_directed(): 
      edges = itertools.permutations(L,2) 
     else: 
      edges = itertools.combinations(L,2) 
     G.add_edges_from(edges) 
    return G 

S = complete_graph_from_list(["a", "b", "c", "d"]) 
print S.edges() 

Answer 2

v'è una funzione per creare grafici completamente connessi (cioè completi), nameley complete_graph.

import networkx as nx 
g = nx.complete_graph(10) 

Si prende un argomento intero (il numero di nodi nel grafico) e quindi non è possibile controllare le etichette dei nodi. Non ho trovato una funzione per farlo automaticamente, ma con itertools è abbastanza facile:

from itertools import combinations 

nodes = ['A', 'B', 'C', 'D', 'E'] 
edges = combinations(nodes, 2) 
g = nx.Graph() 
g.add_nodes_from(nodes) 
g.add_edges_from(edges) 

combinations(nodes, 2) creerà tuple 2-elemento con tutte le combinazioni di coppie di nodes che poi lavoreranno come i bordi nel grafico.

Questa soluzione è tuttavia valida solo per i grafici non orientati. Dai un'occhiata a zubinmehta's solution per un approccio più generale.

Answer 3

È possibile utilizzare i comandi networkx per generare direttamente una cricca con nodi interi, quindi esiste un semplice comando per ridenominare i nodi con qualsiasi altro nome hashing.

import networkx as nx 
L=["hello", "world", "how", "are", "you"] 
G=nx.complete_graph(len(L)) 
nx.relabel_nodes(G,dict(enumerate(L)), copy = False) #if copy = True then it returns a copy.