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