more optimization strategies.
diff --git a/sim.py b/sim.py
--- a/sim.py
+++ b/sim.py
@@ -19,7 +19,7 @@ def distances(target, nodelist):
lengths.append(dist(n,target))
return lengths
-def randomnodes(num=2000):
+def randomnodes(num=500):
"""Generate num nodes with locations between 0 and 1."""
nodes = set()
for n in range(num):
@@ -42,7 +42,7 @@ def generateflat(nodes, connectionsperno
conn in net and (
conn in net[node] or
node in net[conn] or
- net[conn][connectionspernode:])):
+ net[conn][connectionspernode+2:])):
conn = choice(nodes)
net[node].append(conn)
if not conn in net:
@@ -120,12 +120,14 @@ def closest(target, sortedlist):
return best
return best
-def findroute(target, start, net):
+def findroute(target, start, net, maxhtl=9999):
"""Find the best route to the target usinggreedy routing."""
best = start
seen = set()
route = []
- while not best == target:
+ for i in range(maxhtl):
+ if best == target:
+ return route
prev = best
best = closest(target, net[prev])
# never repeat a route deterministically
@@ -137,7 +139,7 @@ def findroute(target, start, net):
best = choice(possible)
route.append(best)
seen.add(best)
- return route
+ return []
def numberofconnections(net):
"""Get the number of connections for each node."""
@@ -193,12 +195,23 @@ def jumptotarget(target, prev, net):
realtarget = target
while realtarget in net or realtarget == prev:
realtarget = (realtarget + (random()-0.5)*1.e-9) % 1
- connections = net[prev]
+ connections = net[prev][:]
net[realtarget] = connections
del net[prev]
for conn in connections:
net[conn] = sorted([c for c in net[conn] if not c == prev] + [realtarget])
+def switchwithtarget(target, prev, net):
+ """switch the location with the target."""
+ prevconnections = net[prev][:]
+ targetconnections = net[target][:]
+ net[target] = prevconnections
+ net[prev] = targetconnections
+ for conn in prevconnections:
+ net[conn] = sorted([c for c in net[conn] if not c == prev] + [target])
+ for conn in targetconnections:
+ net[conn] = sorted([c for c in net[conn] if not c == target] + [prev])
+
def connecttotarget(target, prev, net):
"""Connect prev to the target."""
net[prev].append(target)
@@ -209,12 +222,43 @@ def disconnectfromtarget(target, prev, n
net[prev].remove(target)
net[target].remove(prev)
+def hasbetterlinks(target, prev, net):
+ """Check if the target position has better links than the
+ previous."""
+ conns = net[prev][:]
+ old = distances(prev, conns)
+ new = distances(target, conns)
+ newdev = deviationfromsmallworld(new)
+ olddev = deviationfromsmallworld(old)
+ if sum(newdev) < sum(olddev):
+ return True
+
def checkjump(target, prev, net):
"""Check if we should jump to the target.
:param targetdeviation: deviation of the link distribution at the
target from a small world distribution."""
- conns = net[prev]
+ if hasbetterlinks(target, prev, net):
+ jumptotarget(target, prev, net)
+ return True
+
+def checkswitch(target, prev, net):
+ """Check if we should jump to the target.
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ if hasbetterlinks(target, prev, net):
+ if hasbetterlinks(prev, target, net):
+ switchwithtarget(target, prev, net)
+ return True
+
+def checkjumphalf(target, prev, net):
+ """Check if we should jump halfway to the target.
+
+ :param targetdeviation: deviation of the link distribution at the
+ target from a small world distribution."""
+ conns = net[prev][:]
+ target = (prev+target)/2
old = distances(prev, conns)
new = distances(target, conns)
newdev = deviationfromsmallworld(new)
@@ -253,6 +297,34 @@ def checkconnect(target, prev, net):
if enoughconnections:
disconnectfromtarget(tokillconn, prev, net)
return True
+
+def checkreplacebest(target, prev, net):
+ """Check if we should connect to the target.
+
+ Check: Does it improve our local links if we replace the worst
+ connection with it."""
+ oldconns = net[prev][:]
+ olddist = distances(prev, oldconns)
+ deviation = deviationfromsmallworld(olddist, numbins=5)
+ bindefupper = smallworldbindef(numbins=5)
+ bestidx = deviation.index(min(deviation))
+ bestupper = bindefupper[bestidx]
+ if bestidx:
+ bestlower = bindefupper[bestidx-1]
+ else:
+ bestlower = 0
+ gooddist = [i for i in olddist if bestlower <= i < bestupper]
+ if not gooddist:
+ return # no really good connections
+ tokill = choice(gooddist)
+ connecttotarget(target, prev, net)
+ # if tokill has at least half as many connections as prev,
+ # disconnect it.
+ tokillconn = oldconns[olddist.index(tokill)]
+ enoughconnections = net[tokillconn][int(len(net[prev])/2):]
+ if enoughconnections:
+ disconnectfromtarget(tokillconn, prev, net)
+ return True
def checksimpleconnect(target, prev, net):
"""Just connect to the target and disconnect a random node, if it
@@ -265,18 +337,39 @@ def checksimpleconnect(target, prev, net
disconnectfromtarget(tokillconn, prev, net)
return True
-def checkfold(target, prev, net, probability=0.07, strategy="connectsimple"):
+def checkreplacelongest(target, prev, net):
+ """Just connect to the target and disconnect a random node, if it
+ has enough connections."""
+ conns = net[prev][:]
+ connecttotarget(target, prev, net)
+ dist = distances(prev, conns)
+ idx = dist.index(max(dist))
+ tokillconn = conns[idx]
+ enoughconnections = net[tokillconn][int(len(net[prev])/2):]
+ if enoughconnections:
+ disconnectfromtarget(tokillconn, prev, net)
+ return True
+
+def checkfold(target, prev, net, probability=0.2, strategy="connect"):
"""switch to the target location with some probability"""
if random() > probability:
return
if strategy == "jump":
return checkjump(target, prev, net)
- elif strategy == "connect":
+ if strategy == "switch":
+ return checkswitch(target, prev, net)
+ if strategy == "jumphalf":
+ return checkjumphalf(target, prev, net)
+ if strategy == "connect":
return checkconnect(target, prev, net)
- elif strategy == "connectsimple":
+ if strategy == "replacebest":
+ return checkreplacebest(target, prev, net)
+ if strategy == "replacelongest":
+ return checkreplacelongest(target, prev, net)
+ if strategy == "connectsimple":
return checksimpleconnect(target, prev, net)
-def fold(net, num=100):
+def fold(net, num=100, maxhtl=20):
"""do num path foldings.
:return: the lengths of all used routes."""
@@ -288,12 +381,17 @@ def fold(net, num=100):
while target == start:
target = choice(nodes)
route = findroute(target, start, net)
+ if not route:
+ continue
routelen = len(route)
routelengths.append(routelen)
+ if routelen > maxhtl:
+ continue
# fold all on the route except for the start and the endpoint
for prev in route[:-1]:
pnet = net[prev]
- if checkfold(target, prev, net):
+ didfold = checkfold(target, prev, net)
+ if didfold:
target = prev
return routelengths
@@ -317,13 +415,18 @@ if __name__ == "__main__":
lensnapshots[(run,0)] = linklengths(net), [0]
print (np.mean(lensnapshots[(0,0)][0]))
print("===", "run", run, "===")
+ routelengths = fold(net, 20)
+ linklens = linklengths(net)
+ print (np.mean(linklens), np.mean(routelengths), "±", np.std(routelengths), "succ", len([r for r in routelengths if r < 20])/len(routelengths), min(routelengths), max(routelengths), sum(deviationfromsmallworld(linklens, numbins=10)))
for i in range(40):
- lengths = fold(net, foldperstep)
- lensnapshots[(run, i+1)] = linklengths(net), lengths
- print (np.mean(lensnapshots[(run, i+1)][0]), np.mean(lensnapshots[(run, i+1)][1]))
+ routelengths = fold(net, foldperstep)
+ linklens = linklengths(net)
+ lensnapshots[(run, i+1)] = linklens, routelengths
+ print (np.mean(linklens), np.mean(routelengths), "±", np.std(routelengths), "succ", len([r for r in routelengths if r < 20])/len(routelengths),
+ min(routelengths), max(routelengths), sum(deviationfromsmallworld(linklens, numbins=10)))
# now plot the data
- import matplotlib as pl
+ import pylab as pl
for key, val in sorted(lensnapshots.items()):
run, i = key
linklen, routelen = val