first version of greedy routing works.
diff --git a/sim.py b/sim.py new file mode 100644 --- /dev/null +++ b/sim.py @@ -0,0 +1,68 @@ +#!/usr/bin/env python3 + +"""very simple gnutella path folding simulator.""" + +from random import random, choice +from collections import defaultdict + +def randomnodes(num=8000): + """Generate num nodes with locations between 0 and 1.""" + nodes = set() + for n in range(num): + n = random() + while n in nodes: + n = random() + nodes.add(n) + return list(nodes) + +def generateflat(nodes, connectionspernode=10): + """generate a randomly connected network with the given connectionspernode.""" + net = defaultdict(list) + for node in nodes: + connections = [] + for n in range(connectionspernode - len(net[node])): + conn = choice(nodes) + while (conn == node or + node in net[conn] or + net[conn][connectionspernode-1:]): + conn = choice(nodes) + connections.append(conn) + net[conn].append(node) + for node, conns in net.items(): + net[node] == sorted(conns) + return net + +def closest(target, sortedlist): + """return the node which is closest to the target.""" + dist = 1 + for n in sortedlist: + d = abs(n - target) + if d < dist: + best = n + dist = d + else: + return best + return best + +def findroute(target, start, net): + """Find the best route to the target usinggreedy routing.""" + best = start + seen = set() + route = [] + while not best == target: + prev = best + best = closest(target, net[prev]) + # never repeat a route + if best in seen: + best = choice(net[prev]) + route.append(best) + seen.add(best) + return route + +if __name__ == "__main__": + nodes = randomnodes() + net = generateflat(nodes) + start = choice(nodes) + target = choice(nodes) + route = findroute(target, start, net) + print (route)