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 array or matrix
- Input sparse array. 
 
- 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_array >>> 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_array(graph) >>> print(graph) <Compressed Sparse Row sparse array of dtype 'int64' with 8 stored elements and shape (4, 4)> Coords Values (0, 1) 1 (0, 2) 2 (1, 0) 1 (1, 3) 1 (2, 0) 2 (2, 3) 3 (3, 1) 1 (3, 2) 3 - >>> structural_rank(graph) 4