Skip to main content
`Ctrl`+`K`

Note

Go to the end to download the full example code.

# Reverse Cuthill–McKee

Cuthill-McKee ordering of matrices

The reverse Cuthill–McKee algorithm gives a sparse matrix ordering that reduces the matrix bandwidth.

    ordering [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)]
    unordered Laplacian matrix
    bandwidth: 7
    <Compressed Sparse Row sparse array of dtype 'int64'
            with 33 stored elements and shape (9, 9)>
      Coords        Values
      (0, 0)        2
      (0, 1)        -1
      (0, 3)        -1
      (1, 0)        -1
      (1, 1)        3
      (1, 2)        -1
      (1, 4)        -1
      (2, 1)        -1
      (2, 2)        2
      (2, 5)        -1
      (3, 0)        -1
      (3, 3)        3
      (3, 4)        -1
      (3, 6)        -1
      (4, 1)        -1
      (4, 3)        -1
      (4, 4)        4
      (4, 5)        -1
      (4, 7)        -1
      (5, 2)        -1
      (5, 4)        -1
      (5, 5)        3
      (5, 8)        -1
      (6, 3)        -1
      (6, 6)        2
      (6, 7)        -1
      (7, 4)        -1
      (7, 6)        -1
      (7, 7)        3
      (7, 8)        -1
      (8, 5)        -1
      (8, 7)        -1
      (8, 8)        2
    low-bandwidth Laplacian matrix
    bandwidth: 7
    <Compressed Sparse Row sparse array of dtype 'int64'
            with 33 stored elements and shape (9, 9)>
      Coords        Values
      (0, 0)        2
      (0, 1)        -1
      (0, 2)        -1
      (1, 0)        -1
      (1, 1)        3
      (1, 3)        -1
      (1, 4)        -1
      (2, 0)        -1
      (2, 2)        3
      (2, 4)        -1
      (2, 5)        -1
      (3, 1)        -1
      (3, 3)        2
      (3, 6)        -1
      (4, 1)        -1
      (4, 2)        -1
      (4, 4)        4
      (4, 6)        -1
      (4, 7)        -1
      (5, 2)        -1
      (5, 5)        2
      (5, 7)        -1
      (6, 3)        -1
      (6, 4)        -1
      (6, 6)        3
      (6, 8)        -1
      (7, 4)        -1
      (7, 5)        -1
      (7, 7)        3
      (7, 8)        -1
      (8, 6)        -1
      (8, 7)        -1
      (8, 8)        2

    import numpy as np
    import matplotlib.pyplot as plt
    import seaborn as sns
    import networkx as nx

    # build low-bandwidth matrix
    G = nx.grid_2d_graph(3, 3)
    rcm = list(nx.utils.reverse_cuthill_mckee_ordering(G))
    print("ordering", rcm)

    print("unordered Laplacian matrix")
    A = nx.laplacian_matrix(G)
    x, y = np.nonzero(A)
    # print(f"lower bandwidth: {(y - x).max()}")
    # print(f"upper bandwidth: {(x - y).max()}")
    print(f"bandwidth: {(y - x).max() + (x - y).max() + 1}")
    print(A)

    B = nx.laplacian_matrix(G, nodelist=rcm)
    print("low-bandwidth Laplacian matrix")
    x, y = np.nonzero(B)
    # print(f"lower bandwidth: {(y - x).max()}")
    # print(f"upper bandwidth: {(x - y).max()}")
    print(f"bandwidth: {(y - x).max() + (x - y).max() + 1}")
    print(B)

    sns.heatmap(B.todense(), cbar=False, square=True, linewidths=0.5, annot=True)
    plt.show()

Total running time of the script: (0 minutes 0.136 seconds)

Gallery generated by Sphinx-Gallery