scipy.sparse.csgraph.

structural_rank#

scipy.sparse.csgraph.structural_rank(graph)#

Compute the structural rank of a graph (matrix) with a given sparsity pattern.

The structural rank of a matrix is the number of entries in the maximum transversal of the corresponding bipartite graph, and is an upper bound on the numerical rank of the matrix. A graph has full structural rank if it is possible to permute the elements to make the diagonal zero-free.

Added in version 0.19.0.

Parameters:
graphsparse matrix

Input sparse matrix.

Returns:
rankint

The structural rank of the sparse graph.

References

[1]

I. S. Duff, “Computing the Structural Index”, SIAM J. Alg. Disc. Meth., Vol. 7, 594 (1986).

Examples

>>> from scipy.sparse import csr_matrix
>>> from scipy.sparse.csgraph import structural_rank
>>> graph = [
... [0, 1, 2, 0],
... [1, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 1, 3, 0]
... ]
>>> graph = csr_matrix(graph)
>>> print(graph)
  (np.int32(0), np.int32(1))        1
  (np.int32(0), np.int32(2))        2
  (np.int32(1), np.int32(0))        1
  (np.int32(1), np.int32(3))        1
  (np.int32(2), np.int32(0))        2
  (np.int32(2), np.int32(3))        3
  (np.int32(3), np.int32(1))        1
  (np.int32(3), np.int32(2))        3
>>> structural_rank(graph)
4