Полностью подключить несвязанный граф в NetworkX

Question

У меня неполносвязный граф, и мне нужно преобразовать его в полносвязный, случайным образом назначив ребра между компонентами графа. Есть ли разумный способ сделать это в networkx?

Например, если у меня есть этот график:

>>> import networkx as nx

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

Он имеет 5031 компонент. Как я могу случайным образом назначить минимальное количество ребер, необходимое для того, чтобы этот граф был полностью связан?

Answer 1

Следуя идее этого ответа , мы можем перебирать combinations связанных компонентов и соединять случайные пары узлов. Преимущество использования combinations состоит в том, что нам нужно выполнить итерацию по компонентам только один раз, и мы гарантируем, что на каждой итерации ранее просмотренные компоненты игнорируются, поскольку порядок combinations не имеет значения, т.е. видели комбинацию (1,2), мы не увидим (2,1), что может привести к тому, что два компонента будут соединены через два разных узла и, возможно, изолированы от остальной части графа.

Итак, используя сокращенную версию вашего примера:

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

введите описание изображения здесь

Answer 2

Если у вас 5031 компонент, вам придется назначить ровно 5030 ребер для соединения вашего графа.

Это довольно просто, вы можете сделать это с жадностью. Сначала вычислите набор компонентов C (вы можете представить свой компонент как набор вершин). Затем выполните следующие действия (псевдокод):

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)

И график будет связан.