scipy.sparse.csgraph.csgraph_to_dense

scipy.sparse.csgraph.csgraph_to_dense(csgraph, null_value=0)

Convert a sparse graph representation to a dense representation

New in version 0.11.0.

Parameters:

csgraph : csr_matrix, csc_matrix, or lil_matrix

Sparse representation of a graph.

null_value : float, optional

The value used to indicate null edges in the dense representation. Default is 0.

Returns:

graph : ndarray

The dense representation of the sparse graph.

Notes

For normal sparse graph representations, calling csgraph_to_dense with null_value=0 produces an equivalent result to using dense format conversions in the main sparse package. When the sparse representations have repeated values, however, the results will differ. The tools in scipy.sparse will add repeating values to obtain a final value. This function will select the minimum among repeating values to obtain a final value. For example, here we’ll create a two-node directed sparse graph with multiple edges from node 0 to node 1, of weights 2 and 3. This illustrates the difference in behavior:

>>> from scipy.sparse import csr_matrix, csgraph
>>> data = np.array([2, 3])
>>> indices = np.array([1, 1])
>>> indptr = np.array([0, 2, 2])
>>> M = csr_matrix((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0, 5],
       [0, 0]])
>>> csgraph.csgraph_to_dense(M)
array([[0., 2.],
       [0., 0.]])

The reason for this difference is to allow a compressed sparse graph to represent multiple edges between any two nodes. As most sparse graph algorithms are concerned with the single lowest-cost edge between any two nodes, the default scipy.sparse behavior of summming multiple weights does not make sense in this context.

The other reason for using this routine is to allow for graphs with zero-weight edges. Let’s look at the example of a two-node directed graph, connected by an edge of weight zero:

>>> from scipy.sparse import csr_matrix, csgraph
>>> data = np.array([0.0])
>>> indices = np.array([1])
>>> indptr = np.array([0, 1, 1])
>>> M = csr_matrix((data, indices, indptr), shape=(2, 2))
>>> M.toarray()
array([[0, 0],
       [0, 0]])
>>> csgraph.csgraph_to_dense(M, np.inf)
array([[ inf,   0.],
       [ inf,  inf]])

In the first case, the zero-weight edge gets lost in the dense representation. In the second case, we can choose a different null value and see the true form of the graph.

Examples

>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import csgraph_to_dense

>>> graph = csr_matrix( [
... [0, 1 , 2, 0],
... [0, 0, 0, 1],
... [0, 0, 0, 3],
... [0, 0, 0, 0]
... ])
>>> graph
<4x4 sparse matrix of type '<class 'numpy.int64'>'
    with 4 stored elements in Compressed Sparse Row format>

>>> csgraph_to_dense(graph)
array([[ 0.,  1.,  2.,  0.],
       [ 0.,  0.,  0.,  1.],
       [ 0.,  0.,  0.,  3.],
       [ 0.,  0.,  0.,  0.]])