SciPy CSGraph – Compressed Sparse Graph in SciPy

SciPy consists of the CSGraph module. CSGraph stands for Compressed Sparse Graph. This module consists of operations to work with graphs. The modules use various algorithms to deal with graphs. The algorithms are usually based on sparse matrix representations.

The concept of sparse matrices is necessary when working with CSGraph. We can work with a variety of graphs. With this article, we can work on sparse matrices. We then represent these matrices as graphs. We can also work with both directed and undirected graphs.

Sparse Graphs

We can consider a graph to be a representation of links between the nodes. These can represent the relationships amongst the nodes. We connect the nodes to their nearest possible neighbors through a link.

We can represent this with the use of sparse matrices. Consider a matrix G. The matrix is N*N, G[i,j] represents the value of the connection between node ‘i’ and ‘j’. These values are most probably zero.

A zero means no connection. Hence, very few nodes have a connection. We represent the connection with assigning weights to the link.

We consider the following graph. It consists of three nodes. Node 0 and 1 are by link weight of 2, while 0 and 2 are given weight 1. We can create different representations of the graph. We can represent it as a sparse, dense, or masked graph.

       G

     (0)

    /   \

   1     2

  /       \

(2)       (1)

We now implement the three representations of the above graph:

import numpy as np
import scipy
from scipy.sparse import csr_matrix
 
#dense representation
G_dense = np.array([ [0, 2, 1],
                     [2, 0, 0],
                     [1, 0, 0] ])
print(G_dense,'\n')
                     
#masked representation
G_masked = np.ma.masked_values(G_dense, 0)
print(G_masked,'\n')
 
#sparse representation
G_sparse = csr_matrix(G_dense)
print (G_sparse.data)

Output

We now consider a graph having zero edge weights. It becomes slightly challenging in this case. We consider a graph where we connect nodes 0 and 2 with weight 0.

     G2

     (0)

    /   \

   0     2

  /       \

(2)       (1)

It causes difficulties in case of dense representation. It is difficult to represent non-edges if the value zero has significance. Hence, it is meaningful to use masked or sparse representation.

import numpy as np
import scipy
from scipy.sparse.csgraph import csgraph_from_dense
 
G2_data = np.array([[np.inf, 2,      0     ],
                    [2,      np.inf, np.inf],
                    [0,      np.inf, np.inf]])
print(G2_data,'\n')
 
#masked representation
G2_masked = np.ma.masked_invalid(G2_data)
print(G2_masked,'\n')
 
#sparse representation
G2_sparse = csgraph_from_dense(G2_data, null_value=np.inf)
print(G2_sparse.data)

Output

Directed vs. Undirected Graphs

The matrices can be either directed or undirected. We can specify using a Boolean value in the SciPy CSGraph module. By default, the graphs are directed.

In the case of directed graphs, traversal from node I to node j is possible but the reverse is not possible. It means we can traverse over G[i,j] but not across G[j,i]. We can set the Boolean function directed as True or False.

G_dense = np.array([[0, 1, 0],

                                           [2, 0, 3],

                                           [0, 4, 0]])

When we set directed as TRUE we get the following output,

—1–> —3–>
(0) (1) (2)
<–2— <–4—

When we set directed as FALSE we get an undirected graph,
(0)–1–(1)–2–(2)

Summary

The CSGraph module is a very important feature when dealing with graphs in SciPy. We can perform the functions on sparse matrices. We then concert those matrices into sparse graphs.

It provides functions to represent the graph in different forms. It also consists of features to help traverse the matrices either directly or indirectly.