`scipy.sparse.csgraph._reordering:structural_rank`

Signature

def structural_rank(graph)

Summary

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

Extended Summary

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.

Parameters

graph : sparse array or matrix: Input sparse array.

Returns

rank : int: The structural rank of the sparse graph.

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)

✗

np.int64(4)