Fully connect an unconnected graph in NetworkX

user_2051572 0
Viewed 766

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?

networkx graph-theory python
2 Answers

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

enter image description here

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

enter image description here

user_96986840

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.

user_74426730
Related