Génération de graphiques aléatoires

Question

J'ai besoin de générer des réseaux de flux aléatoires mono-source/mono-puits de différentes dimensions afin que je puisse mesurer la performance de certains algorithmes tels que Ford-Fulkerson et Dinic. L'algorithme de Kruskal est-il un moyen de générer de tels graphes?

Answer 1

Pour créer un réseau de flux générique, il vous suffit de créer une matrice d'adjanctions.

adj [u] [v] = capacité du nœud u vers le nœud v

Alors, il vous suffit de créer au hasard cette matrice.

Par exemple, si n est le nombre de sommets que vous voulez (vous pouvez faire ce hasard aussi):

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()