Fully connect an unconnected graph in NetworkX

Question

I have a non fully-connected graph, and I need to transform it to a fully connected one by randomly assigning edges between the components of the graph. Is there a smart way of doing it in networkx?

For example, if I have this graph:

>>> import networkx as nx

>>> G = nx.fast_gnp_random_graph(10000,0.0001,seed=1)
>>> print("Connected?",nx.is_connected(G))
Connected? False

It has 5031 components.
How can I randomly assign the minimum amount of edges that are required to make this graph fully connected?

score 3 · Answer 1 · answered Jul 14 '20 at 13:25

Following the idea in this answer, we can iterate over the combinations of connected components and connect random pairs of nodes. The advantage of taking the combinations, is that we only need to iterate once over the components, and we ensure that on each iteration, previously seen components are ignored, since in combinations order does not matter, i.e. if we've seen the combination (1,2) we won't be seing (2,1), which could lead to two components being connected through two different nodes, and possibly isolated from the rest of the graph.

So using a reduced version of your example:

G = nx.fast_gnp_random_graph(100,0.02,seed=1)

plt.figure(figsize=(12,6))
nx.draw(G, node_size=100, node_color='lightgreen')

import random
from itertools import combinations, groupby

components = dict(enumerate(nx.connected_components(G)))
components_combs = combinations(components.keys(), r=2)

for _, node_edges in groupby(components_combs, key=lambda x: x[0]):
    node_edges = list(node_edges)
    random_comps = random.choice(node_edges)
    source = random.choice(list(components[random_comps[0]]))
    target = random.choice(list(components[random_comps[1]]))
    G.add_edge(source, target)

plt.figure(figsize=(12,6))
nx.draw(G, node_size=100, node_color='lightgreen')

score 1 · Answer 2 · answered Jul 14 '20 at 11:18

If you have 5031 components, you will have to assign exactly 5030 edges to connect your graph.

It is rather simple, you can do this greedily.
First, compute the set of components C (you can represent your component as a set of vertices).
Then do as follows (pseudocode):

C = connected_components_of(the_graph)  # set of sets of vertices
while len(C) < 2:
    c1 = C.pop()
    c2 = C.pop()
    v1 = choose_random_vertex_in(c1)
    v2 = choose_random_vertex_in(c2)
    add_edge(v1, v2)
    C.add(c1 | c2)

And the graph will be connex.

Fully connect an unconnected graph in NetworkX

2 Answers2

Linked