{
  "nbformat_minor": 0, 
  "nbformat": 4, 
  "cells": [
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "%matplotlib inline"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }, 
    {
      "source": [
        "\n# Rcm\n\n\nCuthill-McKee ordering of matrices\n\nThe reverse Cuthill-McKee algorithm gives a sparse matrix ordering that\nreduces the matrix bandwidth.\n\n"
      ], 
      "cell_type": "markdown", 
      "metadata": {}
    }, 
    {
      "execution_count": null, 
      "cell_type": "code", 
      "source": [
        "# Copyright (C) 2011-2017 by\n# Author:    Aric Hagberg <aric.hagberg@gmail.com>\n# BSD License\nimport networkx as nx\nfrom networkx.utils import reverse_cuthill_mckee_ordering\nimport numpy as np\n\n# build low-bandwidth numpy matrix\nG = nx.grid_2d_graph(3, 3)\nrcm = list(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(\"lower bandwidth:\",(y-x).max())\n#print(\"upper bandwidth:\",(x-y).max())\nprint(\"bandwidth: %d\" % ((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(\"lower bandwidth:\",(y-x).max())\n#print(\"upper bandwidth:\",(x-y).max())\nprint(\"bandwidth: %d\" % ((y - x).max() + (x - y).max() + 1))\nprint(B)"
      ], 
      "outputs": [], 
      "metadata": {
        "collapsed": false
      }
    }
  ], 
  "metadata": {
    "kernelspec": {
      "display_name": "Python 2", 
      "name": "python2", 
      "language": "python"
    }, 
    "language_info": {
      "mimetype": "text/x-python", 
      "nbconvert_exporter": "python", 
      "name": "python", 
      "file_extension": ".py", 
      "version": "2.7.12", 
      "pygments_lexer": "ipython2", 
      "codemirror_mode": {
        "version": 2, 
        "name": "ipython"
      }
    }
  }
}