debugging: it lostt connections and now I broke it...
diff --git a/sim.py b/sim.py
--- a/sim.py
+++ b/sim.py
@@ -3,9 +3,9 @@
"""very simple gnutella path folding simulator."""
from random import random, choice
-from collections import defaultdict
+import numpy as np
-def randomnodes(num=8000):
+def randomnodes(num=800):
"""Generate num nodes with locations between 0 and 1."""
nodes = set()
for n in range(num):
@@ -17,15 +17,22 @@ def randomnodes(num=8000):
def generateflat(nodes, connectionspernode=10):
"""generate a randomly connected network with the given connectionspernode."""
- net = defaultdict(list)
+ net = {}
for node in nodes:
+ if not node in net:
+ net[node] = []
for n in range(connectionspernode - len(net[node])):
+ # find connections to others we do not know yet
conn = choice(nodes)
- while (conn == node or
- node in net[conn] or
- net[conn][connectionspernode:]):
+ while (conn == node or
+ conn in net and (
+ conn in net[node] or
+ node in net[conn] or
+ net[conn][connectionspernode:])):
conn = choice(nodes)
net[node].append(conn)
+ if not conn in net:
+ net[conn] = []
net[conn].append(node)
for node, conns in net.items():
net[node] == sorted(conns)
@@ -33,7 +40,9 @@ def generateflat(nodes, connectionsperno
def closest(target, sortedlist):
"""return the node which is closest to the target."""
- dist = 1
+ if not sortedlist:
+ raise ValueError("Cannot find the closest node in an emtpy list.")
+ dist = 1.1
for n in sortedlist:
d = abs(n - target)
if d < dist:
@@ -58,23 +67,31 @@ def findroute(target, start, net):
seen.add(best)
return route
-def checkfold(target, prev, net, probability=0.07):
+def numberofconnections(net):
+ """Get the number of connections for each node."""
+ numconns = []
+ for n in net.values():
+ numconns.append(len(n))
+ return numconns
+
+def dofold(target, prev, net):
+ """Actually do the switch to the target location."""
+ # do not switch to exactly the target to avoid duplicate entries
+ # (implementation detail)
+ realtarget = target
+ while realtarget in net or realtarget == prev:
+ realtarget = (realtarget + (random()-0.5)*1.e-9) % 1
+ conns = net[prev]
+ net[realtarget] = conns
+ del net[prev]
+ for conn in conns:
+ net[conn] = sorted([c for c in net[conn] if not c == prev] + [realtarget])
+
+def checkfold(target, prev, net, probability=0.7):
"""switch to the target location with some probability"""
if random() > probability:
return
- # do not switch to exactly the target to avoid duplicate entries
- # (implementation detail)
- while target in net:
- target = (target + (random()-0.5)*1.e-9) % 1
- conns = net[prev]
- # never switch with a neighbour
- if target in conns:
- return
- net[target] = conns
- del net[prev]
- for conn in conns:
- net[conn].remove(prev)
- net[conn] = sorted(net[conn] + [target])
+ dofold(target, prev, net)
def fold(net, num=10):
"""do num path foldings."""
@@ -86,8 +103,10 @@ def fold(net, num=10):
target = choice(nodes)
route = findroute(target, start, net)
- for prev in route:
+ for prev in route[:-1]:
+ pnet = net[prev]
checkfold(target, prev, net)
+
def linklengths(net):
"""calculate the lengthsof all links"""
@@ -102,10 +121,6 @@ if __name__ == "__main__":
nodes = randomnodes()
net = generateflat(nodes)
print (np.mean(linklengths(net)))
- fold(net)
- print (np.mean(linklengths(net)))
- fold(net)
- print (np.mean(linklengths(net)))
- fold(net)
- print (np.mean(linklengths(net)))
-
+ for i in range(1000):
+ fold(net)
+ print (np.mean(linklengths(net)))