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