如何使用Networkx创建每个节点至少具有1条边的随机图 [英] How to create random graph where each node has at least 1 edge using Networkx

问题描述

我已经设法创建了一个随机的无向加权图，以使用Dijkstra的算法进行测试，但是如何做到这一点，以便每个节点至少具有一个将它们连接到图的边?

I've managed to create a random undirected weighted graph for testing with Dijkstra's algorithm, but how can I make it so each node has at least one edge that connects them to the graph?

我正在使用Networkx，并且图形生成器如下:

I'm using Networkx and my graph generator is as follows:

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.有没有办法确保每个节点至少有一个边缘?

This creates the graph well, and I managed to plot it, so I can actually see it, my problem is with the probability for edge creation. I don't want it so high that all nodes have the max amount of edges, but putting a low value can result in a node with 0 edges. Is there a way to make sure that each node has at least one edge?

推荐答案

似乎没有

There doesn't seem to be a NetworkX graph generator to directly generate a graph that fulfills such requirement.

但是，您可以调整一点

However, you could tweak a little bit the approach used in nx.gnp_random_graph, so that instead of setting an edge among all possible edge combinations with a random probability, we add one edge for each node randomly, and then add the remaining edges with a probability p.

以下方法不仅会生成每个节点至少具有一条边的图形，还会导致

The following approach not only generates a graph where each node has at least one edge, but also results in a connected graph. This is explained bellow in Further notes -

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

---

示例运行-

如下面的示例所示，即使分配的概率很小，结果图也是已连接:

As shown in the following example, even assigning a very low probability, the resulting graph is 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)的结果为每个节点设置了至少一条边.用一个例子可能会更清楚:

The above approach, not only ensures that each node has at least one edge, but also as mentioned that the resulting graph is connected. This is because we are setting at least one edge for each node using the result from itertools.combinations(range(n_nodes), 2). This might be clearer with an example:

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添加了这些边缘，那么在每次迭代时都对所有现有边缘进行迭代就没有意义了.

In this case, we are setting at least one edge in each case taking a random.choice from the available edges on each iteration, which are edges that have not yet been set. This is a consequence of using the result of itertools.combinations to set an edge. For undirected graphs it wouldn't make sense to iterate over all existing edges at each iteration, if those edges have previously already been added with a probability p.

这不是采用permutations的情况(请参见有向图的情况).在有向图的情况下，不能采用这种方法保证连接性，因为可能会有两个节点通过相反方向的两个边连接，并与图的其余部分隔离.因此，应该遵循另一种方法(也许扩展了上述想法).

This is not the case of taking the permutations (see source code for a directed graph case). In the case of a directed graph, connectivity cannot be guaranteed following this approach, since there could two nodes connected by two edges of opposite direction, and be isolated from the rest of the graph. So another approach (perhaps extending the above idea) should be followed.

这篇关于如何使用Networkx创建每个节点至少具有1条边的随机图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！