Source code online books for professionals by professionals

Listing 2-1.  A Straightforward Adjacency Set Representation
a, b, c, d, e, f, g, h = range(8)
N = [
    {b, c, d, e, f},    # a
    {c, e},             # b
    {d},                # c
    {e},                # d
    {f},                # e
    {c, g, h},          # f
    {f, h},             # g
    {f, g}              # h
] 
Note
 
■
  in python versions prior to 2.7 (or 3.0), you would write set literals as 
set([1, 2, 3])
 rather than 
{1, 2, 3}
. 
Note that an empty set is still written 
set()
 because 
{}
 is an empty dict.
The name N has been used here to correspond with the N function discussed earlier. In graph theory, N(v) 
represents the set of v’s neighbors. Similarly, in our code, N[v] is now a set of v’s neighbors. Assuming you have 
defined N as earlier in an interactive interpreter, you can now play around with the graph:
 
>>> b in N[a]  # Neighborhood membership
True
>>> len(N[f])  # Degree
3 
Tip
 
■
  if you have some code in a source file, such as the graph definition in Listing 2-1, and you want to explore it 
interactively as in the previous example, you can run 
python
 with the 
-i
 switch, like this:
python -i listing_2_1.py
this will run the source file and start an interactive interpreter that continues where the source file left of, with any global 
definitions available for your experimentation.
Another possible representation, which can have a bit less overhead in some cases, is to replace the adjacency 
sets with actual adjacency lists. For an example of this, see Listing 2-2. The same operations are now available, except 
that membership checking is now Q(n). This is a significant slowdown, but that is a problem only if you actually need 
it, of course. (If all your algorithm does is iterate over neighbors, using set objects would not only be pointless; the 
overhead would actually be detrimental to the constant factors of your implementation.)