mosp.routing

1 """Store and calculate routing data""" 2 3 import os 4 import time 5 import logging 6 import array 7 import struct 8 import bz2 9 10 __author__ = "F. Ludwig" 11 __maintainer__ = "B. Henne" 12 __contact__ = "henne@dcsec.uni-hannover.de" 13 __copyright__ = "(c) 2010-2011, DCSec, Leibniz Universitaet Hannover, Germany" 14 __license__ = "GPLv3" 15 16

17 -def init_array(n, value=0):

18 """Yields n times the value (default=0) to init an array.array. 19 @author: F. Ludwig""" 20 for i in xrange(int(n)): 21 yield value

22 23

24 -class RoutingNode(object):

25 """A routing node. 26 @author: F. Ludwig""" 27

28 - def __init__(self, id):

29 """Inits the RoutingNode.""" 30 self.id = id #: RoutingNode id 31 self.neighbors = {} #: dict of neighbor RoutingNodes of this RoutingNode, keys=RoutingNode, values=its distance 32 self.ways = {} #: dict of ways the RoutingNode is connect with 33 self.todo = set() #: todo list for routing table calculation 34 self.worldobject = None #: Stores a Location or other real world objects at this road network node/place, e.g used for act_at_node()

35

36 - def setup(self, nodes_num):

37 """Set up arrays route_next and route_dist with default values 38 39 - route_dist default = 0. 40 - route_next default = max_int = 255: a RoutingNode should never 41 have 255 neighbors! for performace (mem usage) reasons we store 42 id of the x-th sorted neighbor instead of the mosp wide node id. 43 44 @param nodes_num: number of way nodes""" 45 self.route_next = array.array('B', init_array(nodes_num, 255)) 46 self.route_dist = array.array('H', init_array(nodes_num))

47

48 - def setup2(self, nodes_num):

49 """Feed arrays route_next and route_dist with routing information to direct neighbors. 50 51 self is source, for all neighbors as destination: self.set_route(neighborX, via itself (neighborX), distance) 52 @param nodes_num: number of way nodes""" 53 self.n = sorted(self.neighbors.keys()) #: list of sorted neighbor keys = mapping of route_next ids (0..254) to mosp nodes (any id) 54 for node, n_dist in self.neighbors.items(): 55 self.set_route(node, node, n_dist) # set route to direct neighbor <node> via itself <node> to distance <n_dist>

56

57 - def update(self, nodes_num):

58 """Calculate some routing data for all RoutingNodes in self.todo. 59 60 For any node X in todo: set distance from any of my neighbor to X as the sum 61 of the distance from my neighbor to me plus the distance from me to X. 62 Finally: empty todo list. 63 @return: self.todo has not been empty? 64 @rtype: Boolean""" 65 if not self.todo: 66 return False 67 68 for to in self.todo: # for all RoutingNodes on my todo list 69 next, dist = self.get_route_dist(to) # get <next> hop and <dist> 70 for n, d in self.neighbors.items(): # for all my neighbors <n> with dist <d> 71 n.set_route(to, self, dist+d) # set route from neighbor <n> to <to> via myself to dist sum 72 self.todo = set() 73 return True

74

75 - def get_route(self, node):

76 """Returns the next RoutingNode on the route from this routingNode to <node> 77 78 @param node: destination node 79 @return: next RoutingNode on route 80 @rtype: RoutingNode""" 81 # route = self.routes.get(node) 82 node_id = node if isinstance(node, int) else node.id 83 next = self.route_next[node_id] 84 if next != 255: 85 return self.n[next] 86 else: 87 return None

88

89 - def get_route_dist(self, node):

90 """Returns the next RoutingNode and distance to it on the route from this routingNode to <node> 91 92 @param node: destination node 93 @return: 2-tupel list <next RoutingNode, distance> 94 @rtype: [RoutingNode, float]""" 95 node_id = node if isinstance(node, int) else node.id 96 dist = self.route_dist[node_id] 97 next = self.route_next[node_id] 98 if next != 255: 99 return self.n[next], dist 100 else: 101 return None, float('inf')

102

103 - def get_routes(self):

104 """Yields all distances from this RoutingNode to all nodes as 2-tuples <n, distance>.""" 105 for n, dist in enumerate(self.route_dist): 106 if dist > 0: 107 yield n, self.get_route(n)

108

109 - def set_route(self, to, next, dist):

110 """Sets value of route_next (<next>) and route_dist (<dist>) for route from this RoutingNode to <to> 111 112 Updates a routing table entry within table calculation, 113 also marks destination as dirty for recalculation.""" 114 cur_route = self.get_route_dist(to) # get current route 115 if cur_route[1] > dist: # if distance of new route is shorter 116 to_id = to if isinstance(to, int) else to.id # get destination (<to>) RoutingNode id 117 next_pos = self.n.index(next) # get position of <next> in mapping self.n 118 self.route_next[to_id] = next_pos # set new next 119 self.route_dist[to_id] = dist # set dist to next 120 self.todo.add(to) # mark RoutingNode <to> as dirty for recalculation

121

122 - def cleanup(self):

123 """Clears RoutingNode's route_dist and neighbors""" 124 self.route_dist = None 125 self.neighbors = None

126

127 - def on_visit(self, visitor):

128 """What has to be done when a Person visits this node in simulation? 129 130 Must be overwritten in simulation implementation to make it come alive. 131 @param visitor: visiting Person""" 132 pass

133

134 - def __repr__(self):

135 """String respresentation of RoutingNode.""" 136 return '<RoutingNode id="%i">' % self.id

137

138 - def __cmp__(self, o):

139 """Compares two RoutingNodes by their id.""" 140 return cmp(self.id, o.id)

141 142

143 -def calc(nodes, path=None, dist=True, check=True, setup=True):

144 """Calculate routing tables 145 146 @param path: sets the base path. It is used to save a cached version of 147 the routing tables 148 149 @param dist: if set to false the distance between every node to every 150 other node is not held in memory 151 152 @param check: even if the routing tables are loaded from cache files its 153 checked if they are complete - by doing at least one 154 routing iteration. If check is false this is skipped 155 @author: F. Ludwig 156 """ 157 cache = None 158 if path: 159 cache_path = path + '.routes' 160 cache_path_bz2 = cache_path + '.bz2' 161 if os.path.exists(cache_path_bz2): 162 cache = bz2.BZ2File(cache_path_bz2) 163 elif os.path.exists(cache_path): 164 cache = open(cache_path) 165 166 nodes_num = float(len(nodes)) 167 if cache: 168 pass # replaces next logging statement 169 #logging.debug('using %s for routing cache' % cache) 170 cache_nodes_num = struct.unpack('!I', cache.read(4))[0] 171 if cache_nodes_num == len(nodes): 172 setup = False 173 for node in nodes: 174 node.route_next = array.array('B') 175 node.route_next.fromstring(cache.read(len(nodes))) 176 if dist or check: 177 node.route_dist = array.array('H') 178 node.route_dist.fromstring(cache.read(len(nodes)*2)) 179 180 if setup: 181 pass # replaces next logging statement 182 #logging.debug('started calculating routing for %i nodes' % nodes_num) 183 t = time.time() 184 for n in nodes: 185 n.setup(nodes_num) 186 pass # replaces next logging statement 187 #logging.debug(' node setup step 1 done (%is)' % (time.time() - t)) 188 189 t = time.time() 190 for n in nodes: 191 n.setup2(nodes_num) 192 pass # replaces next logging statement 193 #logging.debug(' node setup step 2 done (%is)' % (time.time() - t)) 194 195 run = True 196 changed = False 197 while check and run: 198 t = time.time() 199 run = False 200 for n in nodes: 201 if n.update(nodes_num): 202 run = True 203 changed = True 204 # f = sum(n.finished/nodes_num for n in nodes) 205 pass # replaces next logging statement 206 #logging.debug(' node iteration done (%is)' 207 #% (time.time() - t)) 208 # save routing cache 209 if path and changed: 210 cache = bz2.BZ2File(cache_path_bz2, 'w') 211 cache.write(struct.pack('!I', len(nodes))) 212 for i, n in enumerate(nodes): 213 assert i == n.id 214 cache.write(n.route_next.tostring()) 215 cache.write(n.route_dist.tostring()) 216 cache.close() 217 218 if not dist: 219 for node in nodes: 220 node.cleanup()

221 222

223 -def slow_calc(nodes, path=None, dist=True, check=True, setup=True):

224 """Calculate routing tables in a slower, but memory-saving way. 225 226 This method should be used, when big maps are used. 227 228 @param path: sets the base path. It is used to save a cached version of 229 the routing tables 230 231 @param dist: if set to false the distance between every node to every 232 other node is not held in memory 233 234 @param check: even if the routing tables are loaded from cache files its 235 checked if they are complete - by doing at least one 236 routing iteration. If check is false this is skipped 237 @author: P. Tute 238 """ 239 import networkx as nx 240 graph = nx.Graph() 241 cache = None 242 if path: 243 cache_path = path + '.routes' 244 cache_path_bz2 = cache_path + '.bz2' 245 if os.path.exists(cache_path_bz2): 246 cache = bz2.BZ2File(cache_path_bz2) 247 elif os.path.exists(cache_path): 248 cache = open(cache_path) 249 250 nodes_num = float(len(nodes)) 251 if cache: 252 pass # replaces next logging statement 253 #logging.debug('using %s for routing cache' % cache) 254 cache_nodes_num = struct.unpack('!I', cache.read(4))[0] 255 # TODO fix reading of cached routes for networkx!!! 256 if cache_nodes_num == len(nodes): 257 setup = False 258 for node in nodes: 259 node.route_next = array.array('B') 260 node.route_next.fromstring(cache.read(len(nodes))) 261 if dist or check: 262 node.route_dist = array.array('H') 263 node.route_dist.fromstring(cache.read(len(nodes)*2)) 264 265 if setup: 266 # fill graph with nodes and edges 267 graph.add_nodes_from(nodes) 268 for node in nodes: 269 for neigh in node.neighbors: 270 graph.add_edge(node, neigh, {'dist': node.neighbors[neigh]})

271

Source Code for Module mosp.routing