Génération de graphiques aléatoires avec probabilités

Question

J'essaie de créer un graphe généré aléatoirement avec le paramètre qui prend 5 paramètres d'entrée, n1, n2, p1, p2 et p3 et génère le graphe aléatoire noté G (n1, n2, p1, p2 , p3) qui a n1 + n2 sommets partitionnés en deux ensembles V1, V2 tels que | V1 | = n1 et | V2 | = n2. P1, p2 et p3 sont des probabilités et donc comprises entre 0 et 1. Pour chaque paire des sommets u, v ∈ V1, ajouter une arête reliant u et v avec la probabilité p1. Pour chaque paire des sommets u, v ∈ V2, ajoutez un bord reliant u et v avec la probabilité p2. Pour chaque paire des sommets u ∈ V1 et v ∈ V2, ajoutez un bord reliant u et v avec la probabilité p3.

Actuellement je l'ai fait un graphe aléatoire

private static ArrayList<LinkedList<Integer>> RandomGraph(int n1, int n2, double p1, double p2, double p3) { 
int V = n1 + n2; 
int[] verticies = new int[V]; 
// Fills up the verticies array 
for (int i = 0; i < V; i++) { 
    verticies[i] = i; 
} 
// Shuffles the array 
Random rand = new Random(); 
for (int i = 0; i < V; i++) { 
    int pos = i + rand.nextInt(V - i); 
    int temp = verticies[i]; 
    verticies[i] = verticies[pos]; 
    verticies[pos] = temp; 
} 
// System.out.println(Arrays.toString(verticies)); 
// V1 
ArrayList<Edge> a = new ArrayList<>(); 
int i; 
int j; 
// for every pair so double for loop for each 
for (i = 0; i < n1; i++) { 
    for (j = i + 1; j <= rand.nextInt(n1 - i) + i; j++) { 
     if(rand.nextDouble()<p1) 
     { 
      a.add(new Edge(verticies[i], verticies[j], p1)); 
      a.add(new Edge(verticies[j], verticies[i], p1)); 
     } 
    } 
} 

// V2 
for (j = n1 + 1; j < V; j++) { 
    for (int k = j + 1; j <= rand.nextInt(V - k) + k; k++) { 
     if(rand.nextDouble<p2) 
     { 
      a.add(new Edge(verticies[j], verticies[k], p2)); 
      a.add(new Edge(verticies[k], verticies[j], p2)); 
     } 

    } 
} 
// V3 
for (j = 0; j < n1; j++) { 
    for (int k = n1 + 1; k < V; k++) { 
     if(rand.nextDouble()<p3) 
     { 
     a.add(new Edge(verticies[j], verticies[k], p3)); 
     a.add(new Edge(verticies[k], verticies[j], p3)); 
     } 
    } 
} 
ArrayList<LinkedList<Integer>> Alist = new ArrayList<>(); 
for (j = 0; j < V; j++) { 
    Alist.add(new LinkedList<Integer>()); 
} 
for (j = 0; j < a.size(); j++) { 

    Alist.get(a.get(j).start).add(a.get(j).end); 
} 

return Alist; 

}

mais je ne sais pas où les probabilités entrent en jeu. D'après ce que j'ai vu, ils sont utilisés pour calculer les coûts, mais je ne suis pas sûr de savoir comment l'implémenter dans la génération de graphiques. Edit: Nous nous sommes penchés sur le modèle Erdos-Renyi, mais cela ne nous aide pas vraiment en matière d'analyse des coûts? Ajout de la mise en œuvre de la GRE

Merci pour toute aide

Answer 1

Je pense que vous seriez sur la bonne voie en utilisant un modèle ER. Quelque chose comme:

List<List<Integer>> adjacencyList = new ArrayList<>(); 
for (ArrayList<Integer> list : adjacencyList) { 
    list = new ArrayList<>(); 
} 

Random random = new Random(); 
// Randomly add edges for V1. 
for (int u = 0; u < n1; u++) { 
    for (int v = u + 1; v < n1; v++) { 
    if (random.nextDouble() < p1) { 
     adjacencyList.get(u).add(v); 
     adjacencyList.get(v).add(u); 
    } 
    } 
} 

// Randomly add edges for V2. 
for (int u = n1; u < n1 + n2; u++) { 
    for (int v = u + 1; v < n1 + n2; v++) { 
    if (random.nextDouble() < p2) { 
     adjacencyList.get(u).add(v); 
     adjacencyList.get(v).add(u); 
    } 
    } 
} 

// Randomly add edges between V1 and V2. 
for (int u = 0; u < n1; u++) { 
    for (int v = n1; v < n1 + n2; v++) { 
    if (random.nextDouble() < p3) { 
     adjacencyList.get(u).add(v); 
     adjacencyList.get(v).add(u); 
    } 
    } 
} 

Si les graphiques sont petits, vous pouvez être mieux mettre en œuvre la liste de contiguïté comme une matrice de contiguïté:

boolean[][] adjacencyMatrix = new boolean[n1 + n2][n1 + n2]; 

Ensuite, si un bord existe entre deux sommets, définissez l'élément correspondant dans la matrice à true:

adjacencyMatrix[u][v] = true; 

Si vous devez ajouter des poids aux arêtes, remplacez les valeurs booléennes avec deux valeurs ou tout ce que vous utilisez pour représenter le poids.