1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"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.9.16"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
|
