Computational Modeling Fall 2008 For today, you should: 1) work on Chapter 4 2) read a review a swappy book, any unread chapter, last recommended. 3) brace yourself for a quiz on Chapter 4 and Barabasi/Albert Today: 1) no quiz -- next time 2) mini-lecture on depth-first search 3) questions on CDFs? 4) Chapter 4 work time 5) show me your "pimp my code" solutions For next time you should: 1) prepare for a quiz 2) aim to finish your chapter 4 by the end of Friday Depth-first search ------------------ Assume that we have a tree where each node has attributes named cargo, left and right. Here is a recursive function that adds up all the cargo (assuming that is it addable): def sum_tree(node): if node == None: return 0 return node.cargo + sum_tree(node.left) + sum_tree(node.right) Now modify this function to make a list of all the cargo in the tree. What is the run time of your implementation? Versions: 1) simple recursion with list addition 2) recursion with append 3) eliminate the recursion My solution to the "pimp my code" challenge: def get_resources_including_children(self): """ Returns a list of unique resources assigned to the instance and its children. """ # stack is a list of tree nodes we have not visited yet stack = [self] # resources is a dictionary that maps from resource codes to a resources resources = {} while stack: hierarchy_element = stack.pop() if hierarchy_element.is_leaf(): links = HierarchyLink.objects.filter(hierarchy_element=hierarchy_element) resource_codes = [h_link.resource_code for h_link in links] # I assume that if resource_codes is [], filter returns [] cur_resources = Resource.objects.filter(code__in=resource_codes) resources.update([(resource.code, resource) for resource in cur_resources]) else: stack.extend(hierarchy_element.children()) return resources.values()