demo/PageRank.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PageRank\n",
    "\n",
    "This is a translation of the [PageRank function](https://github.com/GraphBLAS/LAGraph/blob/master/Source/Algorithm/LAGraph_pagerank3a.c) for the GAP Benchmark work done by Dr. Tim Davis at TAMU.\n",
    "\n",
    "\"PageRank works by counting the number and quality of links to a page to determine a rough estimate of how important the website is. The underlying assumption is that more important websites are likely to receive more links from other websites.\" - <https://en.wikipedia.org/wiki/PageRank>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(11, 11)\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"332pt\"\n",
       " viewBox=\"0.00 0.00 260.00 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-328 256,-328 256,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"124\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"124\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"124\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"124\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M124,-262.4274C124,-267.3208 124,-272.4096 124,-277.3099\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.5001,-262.1686 124,-252.1686 120.5001,-262.1687 127.5001,-262.1686\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"120.5001,-277.5867 124,-287.5867 127.5001,-277.5868 120.5001,-277.5867\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"51\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M64.0509,-174.8722C75.0546,-185.7251 90.9889,-201.4411 103.6642,-213.9428\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"101.4846,-216.709 111.0621,-221.2393 106.4001,-211.7252 101.4846,-216.709\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"51\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">0</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>3&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M51,-180.1686C51,-187.869 51,-197.0257 51,-205.5834\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"47.5001,-205.5867 51,-215.5867 54.5001,-205.5868 47.5001,-205.5867\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"116\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">4</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M115.2138,-108.3004C114.6167,-126.5058 114.1747,-155.2234 116,-180 116.6267,-188.5065 117.8015,-197.7061 119.0616,-206.0601\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.6282,-206.7545 120.6685,-216.0736 122.5398,-205.6454 115.6282,-206.7545\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M103.774,-103.5426C94.2412,-114.1021 80.8337,-128.9535 69.9184,-141.0442\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"67.2743,-138.75 63.1712,-148.5181 72.4702,-143.4407 67.2743,-138.75\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"143\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"143\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">5</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M125.9497,-116.5324C128.2407,-122.6419 130.6786,-129.143 132.973,-135.2612\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.1871,-115.1973 122.3986,-107.063 122.6328,-117.6552 129.1871,-115.1973\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.8589,-136.9251 136.6473,-145.0595 136.4132,-134.4672 129.8589,-136.9251\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M138.4006,-179.4292C136.2461,-187.5935 133.6286,-197.5127 131.2191,-206.6434\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.7903,-205.9197 128.6229,-216.4818 134.5586,-207.7058 127.7903,-205.9197\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;1 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M139.7259,-29.8701C157.9823,-46.2002 188.0815,-75.246 189,-90\"/>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M189,-90C191.5403,-130.8026 188.0325,-143.3102 170,-180 163.8039,-192.6069 153.9973,-204.6997 145.0276,-214.2339\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"142.3039,-212.0118 137.7875,-221.5958 147.2948,-216.9201 142.3039,-212.0118\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>6&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M123.4766,-36.1686C122.3906,-43.9875 121.0961,-53.3077 119.892,-61.9779\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.397,-61.7001 118.488,-72.0866 123.3305,-62.6632 116.397,-61.7001\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"180\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"180\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">7</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M183.6569,-35.6786C186.3128,-50.208 189.3803,-71.3599 189,-90\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;4 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>7&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M167.9621,-31.5426C158.6653,-42.0015 145.6258,-56.671 134.9351,-68.698\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"132.0117,-66.7187 127.9839,-76.5181 137.2435,-71.3692 132.0117,-66.7187\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">8</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;1 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>8&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M220.451,-30.3367C207.378,-43.6344 189.487,-66.1252 189,-90\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;4 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>8&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M218.9544,-28.2322C215.0848,-30.808 210.9096,-33.5392 207,-36 184.7885,-49.9806 159.0275,-65.1744 140.596,-75.8734\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.8379,-72.847 131.9341,-80.8837 142.3428,-78.9063 138.8379,-72.847\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">9</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;4 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>9&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M32.8841,-28.9353C48.8778,-40.6857 74.4983,-59.509 93.0699,-73.1534\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"91.1658,-76.0975 101.2969,-79.1978 95.3104,-70.4564 91.1658,-76.0975\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"72\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">10</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;4 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>10&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M81.5473,-33.6229C87.2555,-42.9636 94.6314,-55.0332 101.0931,-65.6068\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.2702,-67.6998 106.4713,-74.4076 104.2432,-64.0496 98.2702,-67.6998\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f3f8014a0a0>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from operator import methodcaller\n",
    "from pygraphblas import *\n",
    "from pygraphblas.gviz import *\n",
    "\n",
    "I = [1,2,3,4,5,3,4,4,5,6,6,7,7,8,8,9,10]\n",
    "J = [2,1,1,1,1,0,3,5,4,1,4,1,4,1,4,4,4]\n",
    "V = 1.0\n",
    "M = Matrix.from_lists(I, J, V, 11, 11, typ=FP32)\n",
    "\n",
    "print(M.shape)\n",
    "draw(M, show_weight=False, rankdir='BT')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\n",
       "<!-- Generated by graphviz version 2.40.1 (20161225.0304)\n",
       " -->\n",
       "<!-- Title: %3 Pages: 1 -->\n",
       "<svg width=\"260pt\" height=\"332pt\"\n",
       " viewBox=\"0.00 0.00 260.00 332.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 328)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-328 256,-328 256,4 -4,4\"/>\n",
       "<!-- 1 -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>1</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"124\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"124\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">32.4</text>\n",
       "</g>\n",
       "<!-- 2 -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>2</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"124\" cy=\"-306\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"124\" y=\"-302.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">28.9</text>\n",
       "</g>\n",
       "<!-- 1&#45;&gt;2 -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>1&#45;&gt;2</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M124,-262.4274C124,-267.3208 124,-272.4096 124,-277.3099\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.5001,-262.1686 124,-252.1686 120.5001,-262.1687 127.5001,-262.1686\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"120.5001,-277.5867 124,-287.5867 127.5001,-277.5868 120.5001,-277.5867\"/>\n",
       "</g>\n",
       "<!-- 3 -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>3</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"51\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3.29</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;1 -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>3&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M64.0509,-174.8722C75.0546,-185.7251 90.9889,-201.4411 103.6642,-213.9428\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"101.4846,-216.709 111.0621,-221.2393 106.4001,-211.7252 101.4846,-216.709\"/>\n",
       "</g>\n",
       "<!-- 0 -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>0</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"51\" cy=\"-234\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"51\" y=\"-230.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2.76</text>\n",
       "</g>\n",
       "<!-- 3&#45;&gt;0 -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>3&#45;&gt;0</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M51,-180.1686C51,-187.869 51,-197.0257 51,-205.5834\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"47.5001,-205.5867 51,-215.5867 54.5001,-205.5868 47.5001,-205.5867\"/>\n",
       "</g>\n",
       "<!-- 4 -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>4</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"116\" cy=\"-90\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"116\" y=\"-86.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">6.82</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;1 -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>4&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M115.2138,-108.3004C114.6167,-126.5058 114.1747,-155.2234 116,-180 116.6267,-188.5065 117.8015,-197.7061 119.0616,-206.0601\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"115.6282,-206.7545 120.6685,-216.0736 122.5398,-205.6454 115.6282,-206.7545\"/>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;3 -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>4&#45;&gt;3</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M103.774,-103.5426C94.2412,-114.1021 80.8337,-128.9535 69.9184,-141.0442\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"67.2743,-138.75 63.1712,-148.5181 72.4702,-143.4407 67.2743,-138.75\"/>\n",
       "</g>\n",
       "<!-- 5 -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>5</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"143\" cy=\"-162\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"143\" y=\"-158.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">3.29</text>\n",
       "</g>\n",
       "<!-- 4&#45;&gt;5 -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>4&#45;&gt;5</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M125.9497,-116.5324C128.2407,-122.6419 130.6786,-129.143 132.973,-135.2612\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.1871,-115.1973 122.3986,-107.063 122.6328,-117.6552 129.1871,-115.1973\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"129.8589,-136.9251 136.6473,-145.0595 136.4132,-134.4672 129.8589,-136.9251\"/>\n",
       "</g>\n",
       "<!-- 5&#45;&gt;1 -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>5&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M138.4006,-179.4292C136.2461,-187.5935 133.6286,-197.5127 131.2191,-206.6434\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"127.7903,-205.9197 128.6229,-216.4818 134.5586,-207.7058 127.7903,-205.9197\"/>\n",
       "</g>\n",
       "<!-- 6 -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>6</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"126\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"126\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1.36</text>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;1 -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>6&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M139.7259,-29.8701C157.9823,-46.2002 188.0815,-75.246 189,-90\"/>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M189,-90C191.5403,-130.8026 188.0325,-143.3102 170,-180 163.8039,-192.6069 153.9973,-204.6997 145.0276,-214.2339\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"142.3039,-212.0118 137.7875,-221.5958 147.2948,-216.9201 142.3039,-212.0118\"/>\n",
       "</g>\n",
       "<!-- 6&#45;&gt;4 -->\n",
       "<g id=\"edge11\" class=\"edge\">\n",
       "<title>6&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M123.4766,-36.1686C122.3906,-43.9875 121.0961,-53.3077 119.892,-61.9779\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.397,-61.7001 118.488,-72.0866 123.3305,-62.6632 116.397,-61.7001\"/>\n",
       "</g>\n",
       "<!-- 7 -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>7</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"180\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"180\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1.36</text>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;1 -->\n",
       "<g id=\"edge12\" class=\"edge\">\n",
       "<title>7&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M183.6569,-35.6786C186.3128,-50.208 189.3803,-71.3599 189,-90\"/>\n",
       "</g>\n",
       "<!-- 7&#45;&gt;4 -->\n",
       "<g id=\"edge13\" class=\"edge\">\n",
       "<title>7&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M167.9621,-31.5426C158.6653,-42.0015 145.6258,-56.671 134.9351,-68.698\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"132.0117,-66.7187 127.9839,-76.5181 137.2435,-71.3692 132.0117,-66.7187\"/>\n",
       "</g>\n",
       "<!-- 8 -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>8</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1.36</text>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;1 -->\n",
       "<g id=\"edge14\" class=\"edge\">\n",
       "<title>8&#45;&gt;1</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M220.451,-30.3367C207.378,-43.6344 189.487,-66.1252 189,-90\"/>\n",
       "</g>\n",
       "<!-- 8&#45;&gt;4 -->\n",
       "<g id=\"edge15\" class=\"edge\">\n",
       "<title>8&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M218.9544,-28.2322C215.0848,-30.808 210.9096,-33.5392 207,-36 184.7885,-49.9806 159.0275,-65.1744 140.596,-75.8734\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"138.8379,-72.847 131.9341,-80.8837 142.3428,-78.9063 138.8379,-72.847\"/>\n",
       "</g>\n",
       "<!-- 9 -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>9</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1.36</text>\n",
       "</g>\n",
       "<!-- 9&#45;&gt;4 -->\n",
       "<g id=\"edge16\" class=\"edge\">\n",
       "<title>9&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M32.8841,-28.9353C48.8778,-40.6857 74.4983,-59.509 93.0699,-73.1534\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"91.1658,-76.0975 101.2969,-79.1978 95.3104,-70.4564 91.1658,-76.0975\"/>\n",
       "</g>\n",
       "<!-- 10 -->\n",
       "<g id=\"node11\" class=\"node\">\n",
       "<title>10</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"72\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"72\" y=\"-14.3\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1.36</text>\n",
       "</g>\n",
       "<!-- 10&#45;&gt;4 -->\n",
       "<g id=\"edge17\" class=\"edge\">\n",
       "<title>10&#45;&gt;4</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M81.5473,-33.6229C87.2555,-42.9636 94.6314,-55.0332 101.0931,-65.6068\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"98.2702,-67.6998 106.4713,-74.4076 104.2432,-64.0496 98.2702,-67.6998\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x7f3f8014acd0>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from pygraphblas import *\n",
    "from pygraphblas.gviz import draw\n",
    "\n",
    "\n",
    "def pagerank(A, d, damping, itermax):\n",
    "    n = A.nrows\n",
    "    r = Vector.sparse(FP32, n)\n",
    "    t = Vector.sparse(FP32, n)\n",
    "    d.assign_scalar(damping, accum=FP32.div)\n",
    "    r[:] = 1.0 / n\n",
    "    teleport = (1 - damping) / n\n",
    "    tol = 1e-4\n",
    "    rdiff = 1.0\n",
    "    for iters in range(itermax):\n",
    "        # swap t and r\n",
    "        temp = t ; t = r ; r = temp\n",
    "        w = t / d\n",
    "        r[:] = teleport\n",
    "        A.plus_second(w,\n",
    "              out=r,\n",
    "              accum=FP32.plus,\n",
    "              desc=descriptor.T0)\n",
    "        t -= r\n",
    "        t.abs(out=t)\n",
    "        rdiff = t.reduce_float()\n",
    "        if rdiff <= tol:\n",
    "            break\n",
    "    return r, iters\n",
    "\n",
    "# GAP passes the out degree\n",
    "d = M.reduce_vector(FP32.plus_monoid)\n",
    "pr, iters = pagerank(M, d, 0.85, 100)\n",
    "\n",
    "draw(M, label_vector=pr*100, show_weight=False, label_width=4, rankdir='BT')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wikipedia Reference\n",
    "\n",
    "![](https://upload.wikimedia.org/wikipedia/en/8/8b/PageRanks-Example.jpg)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "ename": "OSError",
     "evalue": "[Errno 14] Bad address",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mOSError\u001b[0m                                   Traceback (most recent call last)",
      "\u001b[0;32m/tmp/ipykernel_21934/661247538.py\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0;32mfrom\u001b[0m \u001b[0mpathlib\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mPath\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mc\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mPath\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'~/.ssgetpy'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0mwikipedia\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mdict\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mMatrix\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mssget\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Gleich/wikipedia-20070206'\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbinary_cache_dir\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0mc\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0mW\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mwikipedia\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m'wikipedia-20070206.mtx'\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/dev/pygraphblas/pygraphblas/matrix.py\u001b[0m in \u001b[0;36mssget\u001b[0;34m(cls, name_or_id, binary_cache_dir)\u001b[0m\n\u001b[1;32m    558\u001b[0m                 \u001b[0mM\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mcls\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mfrom_mm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmm_path\u001b[0m \u001b[0;34m/\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    559\u001b[0m                 \u001b[0;32mif\u001b[0m \u001b[0mbinary_cache_dir\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 560\u001b[0;31m                     \u001b[0mM\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mto_binfile\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mMbin\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    561\u001b[0m             \u001b[0mM\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mwait\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    562\u001b[0m             \u001b[0;32myield\u001b[0m \u001b[0mm\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mname\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mM\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/dev/pygraphblas/pygraphblas/matrix.py\u001b[0m in \u001b[0;36mbinwrite\u001b[0;34m(self, filename, comments, opener)\u001b[0m\n\u001b[1;32m    869\u001b[0m         \u001b[0;32mfrom\u001b[0m \u001b[0msuitesparse_graphblas\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mio\u001b[0m \u001b[0;32mimport\u001b[0m \u001b[0mbinary\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    870\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 871\u001b[0;31m         \u001b[0mbinary\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mbinwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_matrix\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mfilename\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mcomments\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mopener\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    872\u001b[0m         \u001b[0;32mreturn\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    873\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m~/dev/pygraphblas/venv/lib/python3.8/site-packages/suitesparse_graphblas/io/binary.py\u001b[0m in \u001b[0;36mbinwrite\u001b[0;34m(A, filename, comments, opener)\u001b[0m\n\u001b[1;32m    298\u001b[0m             \u001b[0mfwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbuff\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mAb\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mAb_size\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    299\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 300\u001b[0;31m         \u001b[0mfwrite\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mbuff\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mAx\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mAx_size\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;36m0\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    301\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    302\u001b[0m     \u001b[0;32mif\u001b[0m \u001b[0mby_col\u001b[0m \u001b[0;32mand\u001b[0m \u001b[0mis_hyper\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;31mOSError\u001b[0m: [Errno 14] Bad address"
     ]
    }
   ],
   "source": [
    "from pathlib import Path\n",
    "c = Path('~/.ssgetpy')\n",
    "wikipedia = dict(Matrix.ssget('Gleich/wikipedia-20070206', binary_cache_dir=c))\n",
    "W = wikipedia['wikipedia-20070206.mtx']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "W = W.cast(FP32)\n",
    "d = W.reduce_vector(FP32.plus_monoid)\n",
    "pr, iters = pagerank(W, d, 0.85, 100)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pr.reduce_float(FP32.max_monoid)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}