[FIXED] Generate graph from a list of connected components

Issue

Setup

Let's assume the following undirected graph:

import networkx as nx

G = nx.from_edgelist([(0, 3), (0, 1), (2, 5), (0, 3)])
G.add_nodes_from(range(7))

or even adding the (1, 3) edge (it doesn't matter here):

The connected components are:

list(nx.connected_components(G))
# [{0, 1, 3}, {2, 5}, {4}, {6}]

Question

Is it possible to generate the graph G from the list of connected components directly with networkx? Or using a simple method?

The only solution I found so far is to generate the successive edges or all combinations of nodes per group and feed it to nx.from_edgelist, then to add the single nodes with add_nodes_from:

from itertools import pairwise, chain

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G = nx.from_edgelist(chain.from_iterable(pairwise(e) for e in l))
G.add_nodes_from(set.union(*l))

or for all edges:

from itertools import combinations, chain

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G = nx.from_edgelist(chain.from_iterable(combinations(e, 2) for e in l))
G.add_nodes_from(set.union(*l))

Solution

An alternative to itertools.pairwise is networkx.path_graph.

An alternative to itertools.combinations is networkx.complete_graph.

These two networkx functions return a new graph, not a list of edges, so you can combine them with networkx.compose_all.

Note also union_all and disjoint_union_all as alternatives to compose_all.

import networkx as nx

l = [{0, 1, 3}, {2, 5}, {4}, {6}]

G = nx.compose_all(map(nx.path_graph, l))

H = nx.compose_all(map(nx.complete_graph, l))

print(G.nodes, G.edges)
# [0, 1, 3, 2, 5, 4, 6] [(0, 1), (1, 3), (2, 5)]

print(H.nodes, H.edges)
# [0, 1, 3, 2, 5, 4, 6] [(0, 1), (0, 3), (1, 3), (2, 5)]

I haven't actually run benchmarks, but I suspect creating several graphs and composing them might be slower than creating lists of edges and chaining them to create only one graph.

Answered By - Stef