Module « scipy.sparse.csgraph »

Fonction structural_rank - module scipy.sparse.csgraph

Signature de la fonction structural_rank

Description

structural_rank.__doc__

    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.

    .. versionadded:: 0.19.0

    Parameters
    ----------
    graph : sparse matrix
        Input sparse matrix.

    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_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