def
keyword, which we used earlier to define methods for a class.
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