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
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)
x > 0
, or
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
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
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