Как создать полностью связанный направленный случайный граф в сети x 2.1?

Question

Мне нужно сгенерировать случайный полностью связный ориентированный граф в сети x 2.1, чтобы оценить производительность алгоритма асимметричной задачи коммивояжера.например, сгенерировать граф с 100 узлами, они полностью связаны, веса ребер назначаются случайным образом.график направлен (вес ребра от узла i до узла j не обязательно равен весу ребра от узла j до узла i)

Интересно, существует ли функция networkx для генерации такого вида ориентированного графа илипример кода для ссылки.

Я проверил часть "направленных генераторов" в документации по networkx 2.1 (https://networkx.github.io/documentation/networkx-2.1/reference/generators.html?highlight=generator#module-networkx.generators.directed),, но эти генераторы, по-видимому, не соответствуют моему требованию.

Answer 1

Возможно несколько вариантов, как это сделать. Здесь я просто делаю список всех взвешенных ребер со случайным весом, используя itertools. Затем я использую add_weighted_edges_from для создания ориентированного графа. Так что это не слишком долго, я использую только 3 узла.

import networkx as nx
import itertools
import random

G = nx.DiGraph()
weighted_edge_list = [(u,v,random.random()) for u,v in itertools.permutations(range(3),2)]
G.add_weighted_edges_from(weighted_edge_list) 

G.edges(data=True)
> OutEdgeDataView([(0, 1, {'weight': 0.025851202944826346}), (0, 2, {'weight': 0.8067025754602839}), (1, 0, {'weight': 0.7729736390607577}), (1, 2, {'weight': 0.8724493159416196}), (2, 0, {'weight': 0.9049870220916731}), (2, 1, {'weight': 0.9636865700934618})])

Answer 2

У Networkx нет именно такого рода генераторов, потому что это очень специфическая задача. Таким образом, вы должны построить этот график вручную. Вы можете создать полный ориентированный граф:

import networkx as nx
import random

N = 7
G = nx.complete_graph(N, nx.DiGraph())

и затем назначить случайные веса каждому ребру графа:

for (start, end) in G.edges:
    G.edges[start, end]['weight'] = random.random()

, поэтому вы получите именно тот график, который вам нужен:

G.edges.data('weight')

OutEdgeDataView([(0, 1, 0.7188354727617898), (1, 0, 0.9755945178178834),  ...