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()