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

Question

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

pythonnetworkxgraph-theoryweighted-graph

4

我已经成功创建了一个随机的无向加权图，用于测试 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)

这个图形创建得很好，我成功地绘制了它，所以我现在能够看到它了，但我的问题在于边缘创建的概率。我不希望所有节点都有最大数量的边缘，但是设置一个低值可能会导致某些节点没有边缘。有没有办法确保每个节点至少有一条边缘？

- Koala-tastic21

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- yatu · Accepted Answer

看起来没有直接生成满足此要求的图形的NetworkX图形生成器。

但是，您可以稍微调整nx.gnp_random_graph中使用的方法，使其不是以随机概率设置所有可能的边组合之间的边，而是随机为每个节点添加一条边，然后使用概率p添加剩余的边。

以下方法不仅生成每个节点至少有一条边的图形，还会生成一个连通图。这在下面的进一步说明中有解释 -

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

示例运行 -

如下面的示例所示，即使分配非常低的概率，结果图形仍然是连通的：

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。

这不是采用排列（请参见有向图案例的源代码）。在有向图的情况下，无法保证遵循这种方法连接性，因为可能存在两个节点由两个方向相反的边连接，并与图的其余部分隔离。因此，应采用另一种方法（可能扩展上述思想）。