matriz - Cómo generar un subgrafo completamente conectado desde la lista de nodos usando el módulo networkx de python

matriz de adyacencia python

Question

Necesito generar un subgrafo totalmente conectado con networkx , comenzando desde la lista de nodos que quiero conectar. Básicamente, quiero que todos los nodos de la lista que pase a la función estén todos conectados entre sí.

Me pregunto si hay alguna función incorporada para lograr esto (que no he encontrado)? ¿O debería pensar en algún algoritmo?

Muchas gracias.

Answer 1

Hay una función para crear gráficos totalmente conectados (es decir, completos), nameley complete_graph .

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

Toma un argumento entero (el número de nodos en el gráfico) y, por lo tanto, no puede controlar las etiquetas de los nodos. No he encontrado una función para hacerlo automáticamente, pero con itertools es bastante fácil:

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) crearán tuplas de 2 elementos con todas las combinaciones de pares de nodes que luego funcionarán como bordes en el gráfico.

Sin embargo, esta solución solo es válida para gráficos no dirigidos. Eche un vistazo a la solución de zubinmehta para un enfoque más general.

Answer 2

No conozco ningún método que haga esto, pero puede imitar fácilmente el método complete_graph () de networkx y cambiarlo ligeramente (casi como un componente):

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 3

Puede usar los comandos networkx para generar directamente una camarilla con nodos enteros, y luego hay un comando simple para volver a etiquetar los nodos con otros nombres de hashable.

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.