在NetworkX中完全连接未连接的图形

2024-09-27 07:27:06 发布

您现在位置:Python中文网/ 问答频道 /正文

我有一个非完全连通的图,我需要通过在图的组件之间随机分配边将其转换为完全连通的图。在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个组件。
如何随机分配使此图完全连接所需的最小边数


Tags: 方法importnetworkxisas图表组件random
2条回答

按照this answer中的思想,我们可以迭代连接组件的^{}并连接随机的节点对。使用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')

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

如果有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)

图表将是connex

相关问题 更多 >

    热门问题