Algorithms For Dummies

  Understanding Graph Basics 

     171

In addition, the number of nodes affects its content. If n is number of nodes, you 

find a minimum of (n−1) ones and a maximum of n(n−1) ones. The fact that the 

number of ones is few or large makes the graph dense or sparse, and that’s rele-

vant because if the connection between nodes are few, such as in the case of web-

sites, more efficient solutions exist for storing graph data.

Using sparse representations

The SciPy package also performs various math, scientific, and engineering tasks. 

When using this package, you can rely on a sparse matrix to hold the data. A 

sparse matrix is one in which only the actual connections appear in the matrix; all 

other entries don’t exist. Using a sparse matrix saves resources because the mem-

ory requirements for a sparse matrix are small. Here is the code you use to create 

a SciPy sparse matrix from a NetworkX graph:

print(nx.to_scipy_sparse_matrix(AGraph))

  (0, 1)    1

  (0, 2)    1

  (0, 4)    1

  (0, 5)    1

  (1, 0)    1

  (1, 2)    1

  (2, 0)    1

  (2, 1)    1

  (2, 3)    1

  (3, 2)    1

  (3, 4)    1

  (4, 0)    1

  (4, 3)    1

  (5, 0)    1

As you can see, the entries show the various edge coordinates. Each active 

coordinate has a 1 associated with it. The coordinates are 0 based. This means that 

(0, 1)

 actually refers to a connection between nodes 1 and 2.