How to generate a fully connected subgraph from no

问题:

I need to generate a fully connected subgraph with networkx, starting from the list of nodes I want to connect. Basically, I want all the nodes in the list I pass to the function to be all connected with each other.

I wonder if there is any built-in function to achieve this (which I haven't found)? Or should I think of some algorithm?

Thank you very much.

回答1:

I don't know of any method which does this, but you can easily mimic the complete_graph() method of networkx and slightly change it(almost like a builtin):

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()

回答2:

There is a function for creating fully connected (i.e. complete) graphs, nameley complete_graph.

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

It takes an integer argument (the number of nodes in the graph) and thus you cannot control the node labels. I haven't found a function for doing that automatically, but with itertools it's easy enough:

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) will create 2-element tuples with all pair combinations of nodes which then will work as the edges in the graph.

This solution is however only valid for undirected graphs. Take a look at zubinmehta's solution for a more general approach.

回答3:

You can use the networkx commands to directly generate a clique with integer nodes, and then there is a simple command to relabel the nodes with any other hashable names.

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.