Генерация случайных графов с вероятностями
Я пытаюсь создать случайно сгенерированный граф с тем, который принимает 5 входных параметров, n1, n2, p1, p2 и p3 и генерирует случайный граф, обозначенный G(n1, n2, p1, p2, p3), который имеет n1+n2 вершин разбит на два множества V1, V2 так, что |V1| = n1 и | V2 | = n2.
p1, p2 и p3 - вероятности и, следовательно, в диапазоне от 0 до 1. Для каждой пары вершин u, v ∈ V1, добавьте ребро, соединяющее u и v с вероятностью p1. Для каждой пары 1 вершин u, v ∈ V2 добавим ребро, соединяющее u и v с вероятностью p2. Для каждой пары вершин u ∈ V1 и v ∈ V2 добавим ребро, соединяющее u и v с вероятностью p3.
В настоящее время у меня есть случайный график
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;
}
но я не уверен, где вероятности вступают в игру. Из того, что я видел, они получают, когда вычисляют стоимость, но я не уверен, как реализовать это в генерации графа.
Изменить: заглянул в модель Erdos-Renyi, но это действительно помогает, когда дело доходит до анализа затрат? Добавлена реализация ERM
Спасибо за любую помощь
1 ответ
Я думаю, что вы будете на правильном пути, используя модель ER. Что-то вроде:
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);
}
}
}
Если графики малы, вам может быть лучше реализовать список смежности в виде матрицы смежности:
boolean[][] adjacencyMatrix = new boolean[n1 + n2][n1 + n2];
Затем, если существует ребро между двумя вершинами, установите соответствующий элемент в матрице в true:
adjacencyMatrix[u][v] = true;
Если вам нужно добавить веса к краям, замените логические значения двойными значениями или любым другим значением, которое вы используете для представления веса.