scipy.sparse.csgraph.

reverse_cuthill_mckee

scipy.sparse.csgraph.reverse_cuthill_mckee(graph, symmetric_mode=False)

Returns the permutation array that orders a sparse CSR or CSC matrix in Reverse-Cuthill McKee ordering.

It is assumed by default, symmetric_mode=False, that the input matrix is not symmetric and works on the matrix A+A.T. If you are guaranteed that the matrix is symmetric in structure (values of matrix elements do not matter) then set symmetric_mode=True.

Parameters:

graphsparse array or matrix

Input sparse in CSC or CSR sparse array or matrix format.

symmetric_modebool, optional

Is input matrix guaranteed to be symmetric.

Returns:

permndarray

Array of permuted row and column indices.

Notes

Added in version 0.15.0.

References

E. Cuthill and J. McKee, “Reducing the Bandwidth of Sparse Symmetric Matrices”, ACM ‘69 Proceedings of the 1969 24th national conference, (1969).

Examples

Try it in your browser!

>>> from scipy.sparse import csr_array
>>> from scipy.sparse.csgraph import reverse_cuthill_mckee

>>> graph = [
... [0, 1, 2, 0],
... [0, 0, 0, 1],
... [2, 0, 0, 3],
... [0, 0, 0, 0]
... ]
>>> graph = csr_array(graph)
>>> print(graph)
<Compressed Sparse Row sparse array of dtype 'int64'
    with 5 stored elements and shape (4, 4)>
    Coords  Values
    (0, 1)  1
    (0, 2)  2
    (1, 3)  1
    (2, 0)  2
    (2, 3)  3

>>> reverse_cuthill_mckee(graph)
array([3, 2, 1, 0], dtype=int32)

Go BackOpen In Tab