如何使用 Networkx 创建每个节点至少有 1 条边的随机图

Question

我已经成功地创建了一个随机无向加权图，用于使用 Dijkstra 算法进行测试，但我怎样才能做到这一点，以便每个节点至少有一条边将它们连接到该图？

我正在使用 Networkx，我的图表生成器如下：

import networkx as nx
import random

random.seed()
nodes = random.randint(5,10)
seed = random.randint(1,10)
probability = random.random()
G = nx.gnp_random_graph(nodes,probability,seed, False)
for (u, v) in G.edges():
    G.edges[u,v]['weight'] = random.randint(0,10)

这很好地创建了图表，我设法绘制了它，所以我可以实际看到它，我的问题是边创建的概率。我不希望它太高以至于所有节点都具有最大边数，但是设置较低的值会导致节点的边数为 0。有没有办法确保每个节点至少有一条边？

Answer 1

好像没有NetworkX graph generator可以直接生成满足这种要求的图表。

但是，您可以 稍微调整 nx.gnp_random_graph 中使用的方法，这样就不会在所有可能的边组合中以随机概率设置边，我们为每个节点随机添加一条边，然后然后以 p.

的概率添加剩余的边

以下方法不仅生成每个节点至少有一条边的图，而且还会生成 connected graph。这在下面的进一步说明-

中有解释

def gnp_random_connected_graph(n, p):
    """
    Generates a random undirected graph, similarly to an Erdős-Rényi 
    graph, but enforcing that the resulting graph is conneted
    """
    edges = combinations(range(n), 2)
    G = nx.Graph()
    G.add_nodes_from(range(n))
    if p <= 0:
        return G
    if p >= 1:
        return nx.complete_graph(n, create_using=G)
    for _, node_edges in groupby(edges, key=lambda x: x[0]):
        node_edges = list(node_edges)
        random_edge = random.choice(node_edges)
        G.add_edge(*random_edge)
        for e in node_edges:
            if random.random() < p:
                G.add_edge(*e)
    return G

样本运行 -

如下例所示，即使分配一个很低的概率，结果图也是connected:

from itertools import combinations, groupby
import networkx as nx
import random

nodes = random.randint(5,10)
seed = random.randint(1,10)
probability = 0.1
G = gnp_random_connected_graph(nodes,probability)

plt.figure(figsize=(8,5))
nx.draw(G, node_color='lightblue', 
        with_labels=True, 
        node_size=500)

nodes = 40
seed = random.randint(1,10)
probability = 0.001
G = gnp_random_connected_graph(nodes,probability)

plt.figure(figsize=(10,6))

nx.draw(G, node_color='lightblue', 
        with_labels=True, 
        node_size=500)

补充说明 -

上述方法，不仅保证了每个节点至少有一条边，而且如前所述，生成的图是连通的。这是因为我们使用 itertools.combinations(range(n_nodes), 2) 的结果为每个节点设置至少一条边。举个例子可能会更清楚：

edges = combinations(range(5), 2)
for _, node_edges in groupby(edges, key=lambda x: x[0]):
    print(list(node_edges))

#[(0, 1), (0, 2), (0, 3), (0, 4)]
#[(1, 2), (1, 3), (1, 4)]
#[(2, 3), (2, 4)]
#[(3, 4)]

在这种情况下，我们在每种情况下至少设置一条边，从每次迭代的可用边中取 random.choice，这些边 尚未设置。这是使用 itertools.combinations 的结果设置边缘的结果。对于无向图，如果这些边之前已经以 p.

的概率添加，则在每次迭代时遍历所有现有边是没有意义的

这不是取permutations的情况（见源码取一个directed graph case）。在有向图的情况下，按照这种方法不能保证连通性，因为可能有两个节点由相反方向的两条边连接，并且与图的其余部分隔离。所以应该遵循另一种方法（也许扩展上述想法）。

如何使用 Networkx 创建每个节点至少有 1 条边的随机图

How to create random graph where each node has at least 1 edge using Networkx

python

graph-theory

networkx

weighted-graph