[freenet-cvs] r10651 - trunk/apps/load-balancing-sims/phase6

[mrog...@freenetproject.org]

Author: mrogers
Date: 2006-10-08 20:45:38 +0000 (Sun, 08 Oct 2006)
New Revision: 10651

Modified:
   trunk/apps/load-balancing-sims/phase6/Sim.java
Log:
Kleinberg shortcuts chosen randomly with replacement

Modified: trunk/apps/load-balancing-sims/phase6/Sim.java
===================================================================
--- trunk/apps/load-balancing-sims/phase6/Sim.java      2006-10-08 20:21:05 UTC 
(rev 10650)
+++ trunk/apps/load-balancing-sims/phase6/Sim.java      2006-10-08 20:45:38 UTC 
(rev 10651)
@@ -41,24 +41,23 @@

        private void makeKleinbergNetwork()
        {
-               // Add DEGREE/2 outgoing edges to each node, with replacement
-               double outDegree = DEGREE * 0.5;
+               // Calculate the normalising constant
+               double norm = 0.0;
+               for (int i = 1; i < NODES; i++)
+                       norm += 1.0 / latticeDistance (0, i);
+               
+               // Add DEGREE shortcuts per node, randomly with replacement
                for (int i = 0; i < NODES; i++) {
-                       // Calculate the normalising constant
-                       double c = 0.0;
-                       for (int j = 0; j < NODES; j++) {
-                               if (i == j) continue;
-                               c += 1.0 / latticeDistance (i, j);
+                       for (int j = 0; j < i; j++) {
+                               double p = 1.0 / latticeDistance (i, j) / norm;
+                               for (int k = 0; k < DEGREE; k++) {
+                                       if (Math.random() < p) {
+                                               nodes[i].connectBothWays
+                                                       (nodes[j], LATENCY);
+                                               break;
+                                       }
+                               }
                        }
-                       // Add the outgoing edges
-                       for (int j = 0; j < NODES; j++) {
-                               if (i == j) continue;
-                               int dist = latticeDistance (i, j);
-                               double prob = outDegree / dist / c;
-                               if (Math.random() < prob)
-                                       nodes[i].connectBothWays
-                                               (nodes[j], LATENCY);
-                       }
                }
        }