Source code online books for professionals by professionals

Listing 2-6.  A Weight Matrix with Infinite Weight for Missing Edges
a, b, c, d, e, f, g, h = range(8)
inf = float('inf')
 
#       a    b    c    d    e    f    g    h
 
W = [[  0,   2,   1,   3,   9,   4, inf, inf], # a
     [inf,   0,   4, inf,   3, inf, inf, inf], # b
     [inf, inf,   0,   8, inf, inf, inf, inf], # c
     [inf, inf, inf,   0,   7, inf, inf, inf], # d
     [inf, inf, inf, inf,   0,   5, inf, inf], # e
     [inf, inf,   2, inf, inf,   0,   2,   2], # f
     [inf, inf, inf, inf, inf,   1,   0,   6], # g
     [inf, inf, inf, inf, inf,   9,   8,   0]] # h
 
Weight matrices make it easy to access edge weights, of course, but membership checking and finding the degree 
of a node, for example, or even iterating over neighbors must be done a bit differently now. You need to take the 
infinity value into account. Here’s an example:
 
>>> W[a][b] < inf   # Neighborhood membership
True
>>> W[c][e] < inf   # Neighborhood membership
False
>>> sum(1 for w in W[a] if w < inf) - 1  # Degree
5
 
Note that 1 is subtracted from the degree sum because we don’t want to count the diagonal. The degree 
calculation here is Q(n), whereas both membership and degree could easily be found in constant time with the proper 
structure. Again, you should always keep in mind how you are going to use your graph and represent it accordingly.