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.
New 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) (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