Skip to main content
`Ctrl`+`K`
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:
    graph sparse array or matrix

      Input sparse array.

  Returns:
    rank int

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

  [2]

  http://www.cise.ufl.edu/research/sparse/matrices/legend.html

  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