Source code online books for professionals by professionals

Listing 2-5.  An Adjacency Matrix, Implemented with Nested Lists
a, b, c, d, e, f, g, h = range(8)
 
#     a b c d e f g h
 
N = [[0,1,1,1,1,1,0,0], # a
     [0,0,1,0,1,0,0,0], # b
     [0,0,0,1,0,0,0,0], # c
     [0,0,0,0,1,0,0,0], # d
     [0,0,0,0,0,1,0,0], # e
     [0,0,1,0,0,0,1,1], # f
     [0,0,0,0,0,1,0,1], # g
     [0,0,0,0,0,1,1,0]] # h
 
The way we’d use this is slightly different from the adjacency lists/sets. Instead of checking whether b is in N[a], 
you would check whether the matrix cell N[a][b] is true. Also, you can no longer use len(N[a]) to find the number of 
neighbors, because all rows are of equal length. Instead, use sum:
 
>>> N[a][b]    # Neighborhood membership
1
>>> sum(N[f])  # Degree
3
 
Adjacency matrices have some useful properties that are worth knowing about. First, as long as we aren’t 
allowing self-loops (that is, we’re not working with pseudographs), the diagonal is all false. Also, we often implement 
undirected graphs by adding edges in both directions to our representation. This means that the adjacency matrix for 
an undirected graph will be symmetric.
Extending adjacency matrices to allow for edge weights is trivial: Instead of storing truth values, simply store the 
weights. For an edge (u, v), let N[u][v] be the edge weight w(u, v) instead of True. Often, for practical reasons, we let 
nonexistent edges get an infinite weight. This is to guarantee that they will not be included in, say, shortest paths, as 
long as we can find a path along existent edges. It isn’t necessarily obvious how to represent infinity, but we do have 
some options.
One possibility is to use an illegal weight value, such as None, or -1 if all weights are known to be non-negative. 
Perhaps more useful in many cases is using a really large value. For integral weights, you could use sys.maxint, even 
though it’s not guaranteed to be the greatest possible value (long ints can be greater). There is, however, one value that 
is designed to represent infinity among floats: inf. It’s not available directly under that name in Python, but you can 
get it with the expression float('inf').
16
Listing 2-6 shows what a weight matrix, implemented with nested lists, might look like. I’m using the same 
weights as I did in Listing 2-3, with inf = float('inf'). Note that the diagonal is still all zero, because even though 
we have no self-loops, weights are often interpreted as a form of distance, and the distance from a node to itself is 
customarily zero.
16
This expression is guaranteed to work from Python 2.6 onward. In earlier versions, special floating-point values were  
platform-dependent, although float('inf') or float('Inf') should work on most platforms.

---

Chapter 2 
■
 the BasiCs
29