Как сгенерировать полностью подключенный подграф из списка узлов с помощью модуля networkx python

Question

Мне нужно создать полностью подключенный подграф с networkx, начиная с списка узлов, которые я хочу подключить. В принципе, я хочу, чтобы все узлы в списке, которые я передал функции, были связаны друг с другом.

Интересно, существует ли какая-либо встроенная функция для достижения этого (чего я не нашел)? Или я должен думать о некотором алгоритме?

спасибо.

Answer 1

Я не знаю ни одного метода, который делает это, но вы можете легко имитировать метод complete_graph() из NetworkX и немного изменить его (почти как встроено в него):

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

Существует функция для создания полностью связанных (т.е. полных) графиков, nameley complete_graph.

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

Он принимает целочисленный аргумент (количество узлов на графике) и, следовательно, вы не можете управлять метками узла. Я не нашел функцию делать это автоматически, но с itertools это достаточно легко:

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) создаст 2-элементные кортежи со всеми комбинациями пары nodes, которые затем будут работать в качестве ребер в графе.

Это решение, однако, применимо только для неориентированных графов. Взгляните на zubinmehta's solution для более общего подхода.

Answer 3

Вы можете использовать команды networkx для непосредственного создания клики с целыми узлами, а затем есть простая команда, чтобы перемаркировать узлы с любыми другими хешируемыми именами.

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.