The graph is unweighed, an element of the array of HashSets neighbours[] is a node neighbours[1] is node 1 (they start from 0 mind you) with its unique neighbouring nodes say 2 3 4 5. (so neighbours[5] will contain 1). And I have the following method I did with great deal of help as I dont get the algo much beyond theory. The number it returns should be the average distance between 2 nodes in the graph.
Imagine I have the following graph (node: in_links | out_links; neighbours[] does not contain the 0 loops at node 0, and no duplicates as I said.)
0: 0 0 0 | 0 0 0 1 1 1 2 3 5 6 7 7 8 8 9 9 11
1: 0 0 0 | 2 2 3 4 4 5 6 8
2: 0 1 1 | 3
3: 0 1 2 | 4 9
4: 1 1 3 | 5 12
5: 0 1 4 | 6 7 10
6: 0 1 5 | 10 11 12
7: 0 0 5 |
8: 0 0 1 | 10
9: 0 0 3 | 12
10: 5 6 8 | 11
11: 0 6 10 |
12: 4 6 9 |
And for this trivial graph the distance that's returned is 5.781686749230769E8 ?!?! the code:
public double getAvgDistance() {
double total = 0;
int[] dist = new int[n];
ArrayList<Integer> Q = new ArrayList<Integer>();
int tmp, index = 0, w = 0;
for (int u=0; u<n; u++) {
System.out.print("Avg Dist at "+u+"\r");
// Initialise Q and dist for this iteration
for (int v=u+1; v<n; v++) {
Q.add(v);
if (neighbours[u].contains(v)) {
dist[v] = 1;
} else {
dist[v] = Integer.MAX_VALUE;
}
}
while (!Q.isEmpty()) {
tmp = dist[0];
for (int e=1; e<Q.size(); e++) {
if (dist[e] < tmp) {
w = Q.get(e);
tmp = dist[w]; // smallest dist is for this element w so far
index = e;
}
}
Q.remove(index);
for (int z : neighbours[w]) {
if ( Q.contains(z)
&& (dist[w]+1 < dist[z]) ) {
dist[z] = dist[w]+1;
}
}
} // while end
for (int v = u+1; v < n; v++ ) {
total += dist[v];
}
} // for 0-n end
return total /= (double)(n*(n-1)/2);
}
I don't have much experience with casting or printing real numbers so I hope its something to do with those! All comments welcome