CODEWITHSUNDEEP
pythonnetworkxgraph-theory
Ohm
Ohm

Reputation: 2442

Fully connect an unconnected graph in NetworkX

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?

Upvotes: 3

Views: 1579

Answers (2)

yatu
yatu

Reputation: 88226

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

Upvotes: 3

m.raynal
m.raynal

Reputation: 3113

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.

Upvotes: 1

Related Questions