scipy.sparse.csgraph.

структурный ранг#

scipy.sparse.csgraph.структурный ранг(граф)#

Вычислить структурный ранг графа (матрицы) с заданным шаблоном разреженности.

Структурный ранг матрицы - это количество элементов в максимальном поперечнике соответствующего двудольного графа и является верхней границей числового ранга матрицы. Граф имеет полный структурный ранг, если возможно переставить элементы так, чтобы диагональ была свободна от нулей.

Добавлено в версии 0.19.0.

Параметры:

графразреженный массив или матрица: Входной разреженный массив.

Возвращает:

rankint: Структурный ранг разреженного графа.

Ссылки

[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

Примеры

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

    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