Генерация случайных графиков

Question

Мне нужно генерировать случайные потоковые сети с одним источником / одним приемником различных измерений, чтобы я мог измерить производительность некоторых алгоритмов, таких как Ford-Fulkerson и Dinic.

Является ли алгоритм Крускала способом генерации таких графов?

Answer 1

Чтобы создать общую потоковую сеть, вам просто нужно создать матрицу смежности.

adj [u] [v] = емкость от узла u к узлу v

Итак, вам просто нужно случайным образом создать эту матрицу.

Например, если n - это количество вершин, которое вы хотите (вы также можете сделать это случайным):

for u in 0..n-1:
    for v in 0..u-1:
      if (rand() % 2 and u != sink and v != source or u == source):
         adj[u][v] = rand()
         adj[v][u] = 0
      else:
         adj[u][v] = 0
         adj[v][u] = rand()