Source code online books for professionals by professionals

SpeCIaL-pUrpOSe arraYS WIth NUMpY
the Numpy library has a lot of functionality related to multidimensional arrays. We don’t really need much of that 
for graph representation, but the Numpy array type is quite useful, for example, for implementing adjacency or 
weight matrices.
Where an empty list-based weight or adjacency matrix for n nodes is created, for example, like this
 
>>> N = [[0]*10 for i in range(10)]
 
in Numpy, you can use the 
zeros
 function:
 
>>> import numpy as np
>>> N = np.zeros([10,10])
 
the individual elements can then be accessed using comma-separated indices, as in 
A[u,v]
. to access the 
neighbors of a given node, you use a single index, as in 
A[u]
.
if you have a relatively sparse graph, with only a small portion of the matrix filled in, you could save quite a bit of 
memory by using an even more specialized form of sparse matrix, available as part of the scipy distribution, in 
the 
scipy.sparse
 module.

---

Chapter 2 
■
 the BasiCs
30
the Numpy package is available from 
http://www.numpy.org
. You can get scipy from 
http://www.scipy.org
.
Note that you need to get a version of Numpy that will work with your python version. if the most recent release of 
Numpy has not yet “caught up” with the python version you want to use, you can compile and install directly from 
the source repository.
You can find more information about how to download, compile, and install Numpy, as well as detailed 
documentation on its use, on the web site.
Implementing Trees
Any general graph representation can certainly be used to represent trees because trees are simply a special kind 
of graph. However, trees play an important role on their own in algorithmics, and many special-purpose tree 
structures have been proposed. Most tree algorithms (even operations on search trees, discussed in Chapter 6) can be 
understood in terms of general graph ideas, but the specialized tree structures can make them easier to implement.
It is easiest to specialize the representation of rooted trees, where each edge is pointed downward, away from the 
root. Such trees often represent hierarchical partitionings of a data set, where the root represents all the objects (which 
are, perhaps, kept in the leaf nodes), while each internal node represents the objects found as leaves in the tree rooted 
at that node. You can even use this intuition directly, making each subtree a list containing its child subtrees. Consider 
the simple tree shown in Figure 
2-4
.
a
b
c
d
e
f
0
1
2
T