임의의 그래프 생성 가능성

Question

5 개의 입력 매개 변수 n1, n2, p1, p2 및 p3을 사용하는 무작위로 생성 된 그래프를 만들려고 시도하고 은 G (n1, n2, p1, p2 , p3)은 두 개의 세트 V1, V2로 분할 된 의 n1 + n2 개의 꼭지점을 가지며 | V1 | = n1 및 | V2 | = n2.

p1, p2 및 p3은 확률이며 따라서 0에서 1까지의 범위입니다. 각 쌍 개의 꼭지점 u, v ∈ V1에 대해 u와 v를 확률 p1로 연결하는 가장자리를 추가하십시오. 모든 쌍에 대해 verticle 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; 

}

을하지만 확률이 놀이에 와서 어디 확실하지 않다 있습니다. 내가 본 것에서 그들은 컴퓨팅 비용을 들여 오지만 그래프 생성에 그것을 어떻게 구현할 지 확신하지 못합니다.

편집 : Erdos-Renyi 모델을 살펴 보았지만 비용 분석에 도움이되지는 않습니까?

ERM

의 추가 구현 내가 당신이 ER 모델을 사용하여 올바른 궤도에있을 거라고 생각 도움

Answer 1

주셔서 감사합니다. 뭔가 같이 :

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; 

는 당신이 무게를 나타 내기 위해 사용하는 어떤 두 배 값이나와 부울 값을 대체합니다.