Computational Modeling Fall 2005 For today, you should have: 1) done HomeworkThree: wiki cleanup + news item 2) done HomeworkFour: next installment 3) got a Python book Today's outline: 1) data structures in Python 2) graph algorithms 3) discussion of modeling -- What makes a good model? 4) trade books For next time you should: 1) do HomeworkFive Data structures in Python ------------------------- six sequence types, but we'll concentrate on lists in and not in do membership checking in linear time s[i] is constant time s[i:j] makes shallow copies in linear time (draw the slicing diagram here) len(s) is constant time min and max are linear time + performs concatenation, the operands must be the same sequence type Draw an object diagram for the following program: class A(object): pass a = [A()] b = [A()] c = a + b a[0].x = 5 b[0].x = 7 print c[0].x print c[1].x c[1].x = 9 print b[0].x Lists are mutable ----------------- del is a funny operator in Python list methods: append: probably constant time on average extend: performance? count: linear index: linear pop: return and remove the last item, or the ith remove: removes but does not return an item reverse and sort return None!!! Tuples can be annoying ---------------------- A comma separated list is a tuple t = 1, 2, 3 It's often put in parentheses, but strictly speaking, the comma is the operator that creates the tuple, not the parentheses (so this is different from the [] operator) t = (1) # NOT A TUPLE t = 1, # tuple t = (1,) # tuple t = () # tuple t = tuple() # tuple x, y, z = 1, 2, 3 # tuple assignment! return v, w # return value is a tuple Edge(v, w) # two parameters Edge((v, w)) # one parameter, which is a tuple Dictionaries are mapping types ------------------------------ a[k] look up key k a[k] = v create a key, value pair forget about has_key, use in keys, values, items create lists (order is arbitrary) iterkeys, itervalues, iteritems probably faster update is often useful Idioms: for key in d: d[key] = blah... for key, value in d.iteritems(): print key, value If you are not sure whether a key already exists, get and setdefault can be useful. Instead of: if key in d: return d[y] else: return None You could write: try: return d[y] except KeyError: return None To save time, or return d.get(key) # default is None return d.get(key, []) # default is a new empty list Dictionaries are useful for implementing sets and checking uniqueness: def uniqueEdges(es): t = [(e, True) for e in es] d = dict(t) return d.keys() Actually, because Python is polymorphic, uniqueEdges works on any list. Almost. Graph algorithms ---------------- Graphs are made up of vertices (aka nodes) and edges. Directed graphs contain directed edges. In a connected graph, you can start from any vertex and reach any other vertex by following one or more edges. 1) think of an algorithm for checking whether a graph is connected 2) identify the operations we want to be able to perform on Vertices, Edges and Graphs 3) think of data structures to represent Vertices, Edges and Graphs, so that the operations we want to perform and neat and efficient 4) implement the data structure and algorithm in Python