{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Reverse Cuthill--McKee\n\nCuthill-McKee ordering of matrices\n\nThe reverse Cuthill--McKee algorithm gives a sparse matrix ordering that\nreduces the matrix bandwidth.\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import numpy as np\nimport matplotlib.pyplot as plt\nimport seaborn as sns\nimport networkx as nx\n\n\n# build low-bandwidth matrix\nG = nx.grid_2d_graph(3, 3)\nrcm = list(nx.utils.reverse_cuthill_mckee_ordering(G))\nprint(\"ordering\", rcm)\n\nprint(\"unordered Laplacian matrix\")\nA = nx.laplacian_matrix(G)\nx, y = np.nonzero(A)\n# print(f\"lower bandwidth: {(y - x).max()}\")\n# print(f\"upper bandwidth: {(x - y).max()}\")\nprint(f\"bandwidth: {(y - x).max() + (x - y).max() + 1}\")\nprint(A)\n\nB = nx.laplacian_matrix(G, nodelist=rcm)\nprint(\"low-bandwidth Laplacian matrix\")\nx, y = np.nonzero(B)\n# print(f\"lower bandwidth: {(y - x).max()}\")\n# print(f\"upper bandwidth: {(x - y).max()}\")\nprint(f\"bandwidth: {(y - x).max() + (x - y).max() + 1}\")\nprint(B)\n\nsns.heatmap(B.todense(), cbar=False, square=True, linewidths=0.5, annot=True)\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.12.7"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
Generated by dwww version 1.16 on Wed Apr 8 15:14:52 CEST 2026.