scipy.sparse.csgraph.

structural_rank#

scipy.sparse.csgraph.structural_rank(graph)#

Berechnet den strukturellen Rang eines Graphen (Matrix) mit einem gegebenen Sparsity-Muster.

Der strukturelle Rang einer Matrix ist die Anzahl der Einträge in einer maximalen Transversale des entsprechenden bipartiten Graphen und stellt eine Obergrenze für den numerischen Rang der Matrix dar. Ein Graph hat den vollen strukturellen Rang, wenn es möglich ist, die Elemente so zu permutieren, dass die Diagonale keine Nullen enthält.

Hinzugefügt in Version 0.19.0.

Parameter:

graphspärliches Array oder spärliche Matrix: Eingehender Sparse-Array.

Rückgabe:

rankint: Der strukturelle Rang des Sparse-Graphen.

Referenzen

[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

Beispiele

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