NanoPy #2

Numbers in parentheses refer to chapter and/or section numbers in "Learning Python" (2nd edition) by Lutz and Ascher (L&A).

Contents

functions / if tests / while loops / for loops

functions (12)

Functions are units of code which take a set of input parameters and return a value. (They are known as subroutines in many languages.) In Python, functions are typically defined using the def keyword, which we used earlier to define methods for a class.

You will need to define various functions for operating on an instance of an UndirectedGraph, such as one to compute the average path length separating all pairs of nodes in the graph. That function definition would have a form like this: 


def FindAveragePathLength(graph):
   # "graph" is the internal name in this function for the graph object; 
   # traverse graph nodes to compute path lengths, assigning the result to
   #    a variable named, for example, average_path_length
   return average_path_length
The return statement identifies what is returned from the function. In this case, we are returning a single number (the average path length). Python functions can return multiple values, as a tuple. Any Python object can be return by a function (including other functions). In this case, when we call the function (passing in a graph instance as input), we can assign the return value to a variable, e.g.: 

avg_path_length = FindAveragePathLength(g)

if tests (9)

if is a Python keyword that allows branching based on whether or not some condition holds (i.e., whether the condition is true). By a condition being true, we mean either (see L&A, section 9.3) The simplest form is a standalone if test: 

if x > 0:
    # do something with x
More complicated forms involve else or elif clauses: 

if x > 0:
    # do something with x
else:
    # do something different with x



if x > 0:
    # do something with x
elif x < 0:
    # do something different with x
else:
    # do something different still; x must = 0
In an algorithm to find shortest path lengths in a graph, one needs to test whether the distance to a given node has already been calculated, e.g., by determining whether that node is a key in a dictionary associating nodes to path lengths: 

if node not in pathlengths:    # uses efficient "in" test for dictionaries, and "not" to negate the test
    # add node to the pathlength dictionary

while loops (10.1)

Python (as do most programming languages) provides syntax for various control flow structures, to providing looping, branching, etc. In order to implement graph traversal algorithms, for example, a few different types of looping structures are useful.

while is a Python keyword that allows for looping over a code block as long as some condition is true: 


while someCondition:
   # execute code in block
For the breadth-first search of our graph objects, you will need to test whether the currentShell of nodes to be visited has any elements in it: 

while len(currentShell) > 0:    # len(alist) returns the number of elements in alist
   # execute code to visit nodes

for loops (10.3)

Python's for keyword allows one to iterate over the elements of a sequence: 

for element in sequence:
   # operate on each element of the sequence
A "sequence" here refers to any object which supports iteration in a specified order. The most straightforward kind of sequence is the list (although more subtle sorts of "iterator objects" can also be iterated over): 

for element in alist:
   # operate on alist[0], alist[1], ..., in order
For graph traversal algorithms, one often wants to iterate over the list of neighbors attached to a given node: 

for node2 in graph.GetNeighbors(node1):
   # operate on neighbor node2