Создание графа Эрдоша-Рени с использованием объектов классов в Python

Question

Я строю граф Эрдоша-Рени из набора узлов, которые являются объектами классов разных типов.Класс взят из [blob example] (https://pythonprogramming.net/many-blob-objects-intermediate-python-tutorial/)

. Я начинаю с пустого графа, создаю узлы, которые являются объектами красного цвета и блобов, но чтобы получить граф Эрдоша-Рени, я хочу, чтобы эти узлыбыть связанным с вероятностью р. Использование синтаксиса Networkx для такого графа создает его с нуля.

Я нашел несколько подобных постов здесь [полный график] ( Networkx: создание полного графа для данного набораузлы ), но они не помогли мне с этим случайным графом.

import pygame
import random
import networkx
from matplotlib import pyplot as plt

STARTING_BLUE_BLOBS = 10
STARTING_RED_BLOBS = 3

WIDTH = 800
HEIGHT = 600
WHITE = (255, 255, 255)
BLUE = (0, 0, 255)
RED = (255, 0, 0
class Blob:
    def __init__(self, color):
        self.x = random.randrange(0, WIDTH)
        self.y = random.randrange(0, HEIGHT)
        self.size = random.randrange(4,8)
        self.color = color
def main():
       blue_blobs = dict(enumerate([Blob(BLUE) for i in 
range(STARTING_BLUE_BLOBS)]))
    red_blobs = dict(enumerate([Blob(RED) for i in range(STARTING_RED_BLOBS)]))
    Gb = nx.Graph()

    for i in range(10):
        Gb.add_node(blue_blobs[i])
    for i in range(3):
        Gb.add_node(red_blobs[i])
    Gb = nx.erdos_renyi_graph(13,0.5) 
    nx.draw(Gb, with_labels=True)
    plt.draw()
    plt.show()
if __name__ == '__main__':
    main()

Как мне сохранить свои узлы и использовать такой случайный граф? Большое спасибо,

Answer 1

Со страницы Википедии Модель Эрдеша – Реньи :

В модели G (n, p) граф строится путем случайного соединения узлов.Каждое ребро включено в граф с вероятностью p, независимой от любого другого ребра.

Чтобы создать граф ER на основе заранее определенного набора узлов, вам просто нужно сделать следующее:

1. Создать пустую ненаправленную networkx.Graph.
2. Добавить узлы на график.
3. Перебрать все возможные ребра (т.е. все пары узлов) и добавить ребро вграфик с вероятностью p.

Вот некоторый псевдокод python-ish, чтобы дать вам представление:

import random
import networkx as nx
from itertools import combinations

# probability for an edge to exist
p = 0.5

# ASSUMPTION: This array contains all desired nodes
nodes = [...]

g = nx.Graph()
g.add_nodes_from(nodes)

for u, v in combinations(g, 2):
    if random.random() < p:
        g.add_edge(u, v)

Это должно дать вам совершенно правильный граф ER с использованием заранее определенного набораузлов.Обратите внимание, что этот метод не будет особенно эффективен для генерации массивных графов.