帶概率的隨機圖生成

我想創建一個隨機生成的圖，其中需要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。對於頂點u，v∈V2的每一對，添加以概率p2連接u和v的邊。對於頂點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;

}

，但我不知道在哪裏的概率開始發揮作用。從我看到他們進入計算成本時，但我不知道如何將其實現到圖生成中。

編輯：看着鄂爾多斯 - 仁義模型，但它在成本分析方面並沒有真正的幫助？加入ERM

實施感謝您的幫助

來源

2017-02-20 Georgrio

我想你會使用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;

如果需要權重加入到邊，雙值或任何你正在使用，以代表重替換布爾值。

來源

2017-05-30 13:55:15 amb85

帶概率的隨機圖生成

回答

相關問題