examples/callgraph-decorator-examples.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Callgraph Decorator Examples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from functools import lru_cache\n",
    "import callgraph.decorator as callgraph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Instrument the function, and call it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@callgraph()\n",
    "@lru_cache()\n",
    "def nchoosek(n, k):\n",
    "    if k == 0:\n",
    "        return 1\n",
    "    if n == k:\n",
    "        return 1\n",
    "    return nchoosek(n - 1, k - 1) + nchoosek(n - 1, k)\n",
    "\n",
    "nchoosek(3, 2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The call graph is an instance of a [GraphViz](http://graphviz.readthedocs.io/en/stable/) [`Digraph`](http://graphviz.readthedocs.io/en/stable/api.html#digraph). Jupyter knows how to display this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "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=\"470pt\" height=\"194pt\"\n",
       " viewBox=\"0.00 0.00 470.20 193.52\" 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 189.5238)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-189.5238 466.2038,-189.5238 466.2038,4 -4,4\"/>\n",
       "<!-- nchoosek(1, 0){} -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>nchoosek(1, 0){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"87.1019\" cy=\"-18.9206\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"87.1019\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 0) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>nchoosek(2, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"183.1019\" cy=\"-92.7619\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"183.1019\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 1) ↦ 2</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M159.3715,-74.509C147.1406,-65.1012 132.0567,-53.499 118.8387,-43.332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"120.9523,-40.5421 110.8919,-37.2195 116.6845,-46.0906 120.9523,-40.5421\"/>\n",
       "</g>\n",
       "<!-- nchoosek(1, 1){} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>nchoosek(1, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"279.1019\" cy=\"-18.9206\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"279.1019\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 1) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M206.8322,-74.509C219.0631,-65.1012 234.1471,-53.499 247.3651,-43.332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"249.5193,-46.0906 255.3118,-37.2195 245.2515,-40.5421 249.5193,-46.0906\"/>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){} -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>nchoosek(3, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"279.1019\" cy=\"-166.6032\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"279.1019\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(3, 2) ↦ 3</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M255.3715,-148.3503C243.1406,-138.9425 228.0567,-127.3402 214.8387,-117.1732\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.9523,-114.3834 206.8919,-111.0607 212.6845,-119.9319 216.9523,-114.3834\"/>\n",
       "</g>\n",
       "<!-- nchoosek(2, 2){} -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>nchoosek(2, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"375.1019\" cy=\"-92.7619\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"375.1019\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 2) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M302.8322,-148.3503C315.0631,-138.9425 330.1471,-127.3402 343.3651,-117.1732\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"345.5193,-119.9319 351.3118,-111.0607 341.2515,-114.3834 345.5193,-119.9319\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x10c0e8320>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nchoosek.__callgraph__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Outside of Jupyter, you can call `nchoosek.__callgraph__.view()`.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The calls from multiple statements are collected into graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "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=\"566pt\" height=\"267pt\"\n",
       " viewBox=\"0.00 0.00 566.20 267.37\" 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 263.365)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-263.365 562.2038,-263.365 562.2038,4 -4,4\"/>\n",
       "<!-- nchoosek(1, 0){} -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>nchoosek(1, 0){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"87.1019\" cy=\"-18.9206\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"87.1019\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 0) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>nchoosek(2, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"183.1019\" cy=\"-92.7619\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"183.1019\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 1) ↦ 2</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M159.3715,-74.509C147.1406,-65.1012 132.0567,-53.499 118.8387,-43.332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"120.9523,-40.5421 110.8919,-37.2195 116.6845,-46.0906 120.9523,-40.5421\"/>\n",
       "</g>\n",
       "<!-- nchoosek(1, 1){} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>nchoosek(1, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"279.1019\" cy=\"-18.9206\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"279.1019\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 1) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M206.8322,-74.509C219.0631,-65.1012 234.1471,-53.499 247.3651,-43.332\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"249.5193,-46.0906 255.3118,-37.2195 245.2515,-40.5421 249.5193,-46.0906\"/>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){} -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>nchoosek(3, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"279.1019\" cy=\"-166.6032\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"279.1019\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(3, 2) ↦ 3</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M255.3715,-148.3503C243.1406,-138.9425 228.0567,-127.3402 214.8387,-117.1732\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"216.9523,-114.3834 206.8919,-111.0607 212.6845,-119.9319 216.9523,-114.3834\"/>\n",
       "</g>\n",
       "<!-- nchoosek(2, 2){} -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>nchoosek(2, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"375.1019\" cy=\"-92.7619\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"375.1019\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 2) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M302.8322,-148.3503C315.0631,-138.9425 330.1471,-127.3402 343.3651,-117.1732\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"345.5193,-119.9319 351.3118,-111.0607 341.2515,-114.3834 345.5193,-119.9319\"/>\n",
       "</g>\n",
       "<!-- nchoosek(4, 3){} -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>nchoosek(4, 3){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"375.1019\" cy=\"-240.4444\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"375.1019\" y=\"-238.6233\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(4, 3) ↦ 4</text>\n",
       "</g>\n",
       "<!-- nchoosek(4, 3){}&#45;&gt;nchoosek(3, 2){} -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>nchoosek(4, 3){}&#45;&gt;nchoosek(3, 2){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M351.3715,-222.1915C339.1406,-212.7837 324.0567,-201.1815 310.8387,-191.0145\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"312.9523,-188.2246 302.8919,-184.902 308.6845,-193.7731 312.9523,-188.2246\"/>\n",
       "</g>\n",
       "<!-- nchoosek(3, 3){} -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>nchoosek(3, 3){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"471.1019\" cy=\"-166.6032\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"471.1019\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(3, 3) ↦ 1</text>\n",
       "</g>\n",
       "<!-- nchoosek(4, 3){}&#45;&gt;nchoosek(3, 3){} -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>nchoosek(4, 3){}&#45;&gt;nchoosek(3, 3){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M398.8322,-222.1915C411.0631,-212.7837 426.1471,-201.1815 439.3651,-191.0145\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"441.5193,-193.7731 447.3118,-184.902 437.2515,-188.2246 441.5193,-193.7731\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x10c0e8320>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nchoosek(4, 3)\n",
    "nchoosek.__callgraph__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "However, this simple use of the decorator creates a new call collector for each function.\n",
    "\n",
    "To graph mutually recursive functions (indirect recursion), create an explicit call graph collector. \\[The Jupyter magic does this automatically.\\]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "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=\"536pt\" height=\"194pt\"\n",
       " viewBox=\"0.00 0.00 536.49 193.52\" 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 189.5238)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-189.5238 532.4873,-189.5238 532.4873,4 -4,4\"/>\n",
       "<!-- fib(1,){} -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>fib(1,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"50.2688\" cy=\"-18.9206\" rx=\"50.0387\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"50.2688\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib(1) ↦ 1</text>\n",
       "</g>\n",
       "<!-- fib(3,){} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>fib(3,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"89.2688\" cy=\"-166.6032\" rx=\"50.0387\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"89.2688\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib(3) ↦ 2</text>\n",
       "</g>\n",
       "<!-- fib(3,){}&#45;&gt;fib(1,){} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>fib(3,){}&#45;&gt;fib(1,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M81.6292,-147.7658C77.5702,-137.2681 72.7209,-123.888 69.2688,-111.6825 63.3223,-90.6577 58.4289,-66.4596 55.098,-48.0509\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"58.5006,-47.1914 53.3212,-37.9488 51.6065,-48.404 58.5006,-47.1914\"/>\n",
       "</g>\n",
       "<!-- fib(2,){} -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>fib(2,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"128.2688\" cy=\"-92.7619\" rx=\"50.0387\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"128.2688\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib(2) ↦ 1</text>\n",
       "</g>\n",
       "<!-- fib(3,){}&#45;&gt;fib(2,){} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>fib(3,){}&#45;&gt;fib(2,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M99.1101,-147.9699C103.5442,-139.5746 108.8697,-129.4915 113.7492,-120.2527\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"116.8552,-121.8663 118.4306,-111.3892 110.6655,-118.5971 116.8552,-121.8663\"/>\n",
       "</g>\n",
       "<!-- fib(0,){} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>fib(0,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"169.2688\" cy=\"-18.9206\" rx=\"50.0387\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"169.2688\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib(0) ↦ 0</text>\n",
       "</g>\n",
       "<!-- fib(2,){}&#45;&gt;fib(1,){} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>fib(2,){}&#45;&gt;fib(1,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M109.3872,-74.887C99.5189,-65.5448 87.284,-53.9623 76.5094,-43.7621\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"78.6448,-40.9641 68.9765,-36.6309 73.8324,-46.0475 78.6448,-40.9641\"/>\n",
       "</g>\n",
       "<!-- fib(2,){}&#45;&gt;fib(0,){} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>fib(2,){}&#45;&gt;fib(0,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M138.6148,-74.1286C143.2763,-65.7333 148.8749,-55.6502 154.0046,-46.4115\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"157.1316,-47.9897 158.9261,-37.5479 151.0117,-44.5916 157.1316,-47.9897\"/>\n",
       "</g>\n",
       "<!-- fib1(1,){} -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>fib1(1,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"271.2688\" cy=\"-92.7619\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"271.2688\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib1(1) ↦ 1</text>\n",
       "</g>\n",
       "<!-- fib1(3,){} -->\n",
       "<g id=\"node6\" class=\"node\">\n",
       "<title>fib1(3,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"271.2688\" cy=\"-166.6032\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"271.2688\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib1(3) ↦ 2</text>\n",
       "</g>\n",
       "<!-- fib1(3,){}&#45;&gt;fib1(1,){} -->\n",
       "<g id=\"edge5\" class=\"edge\">\n",
       "<title>fib1(3,){}&#45;&gt;fib1(1,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M271.2688,-147.5872C271.2688,-139.7493 271.2688,-130.4909 271.2688,-121.8357\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"274.7689,-121.7134 271.2688,-111.7134 267.7689,-121.7134 274.7689,-121.7134\"/>\n",
       "</g>\n",
       "<!-- fib2(2,){} -->\n",
       "<g id=\"node8\" class=\"node\">\n",
       "<title>fib2(2,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"399.2688\" cy=\"-92.7619\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"399.2688\" y=\"-90.9408\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib2(2) ↦ 1</text>\n",
       "</g>\n",
       "<!-- fib1(3,){}&#45;&gt;fib2(2,){} -->\n",
       "<g id=\"edge8\" class=\"edge\">\n",
       "<title>fib1(3,){}&#45;&gt;fib2(2,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M299.6761,-150.2154C318.0707,-139.6038 342.2171,-125.6742 362.127,-114.1884\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"364.0278,-117.1326 370.9409,-109.1039 360.5299,-111.0692 364.0278,-117.1326\"/>\n",
       "</g>\n",
       "<!-- fib1(0,){} -->\n",
       "<g id=\"node7\" class=\"node\">\n",
       "<title>fib1(0,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"345.2688\" cy=\"-18.9206\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"345.2688\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib1(0) ↦ 0</text>\n",
       "</g>\n",
       "<!-- fib2(2,){}&#45;&gt;fib1(0,){} -->\n",
       "<g id=\"edge6\" class=\"edge\">\n",
       "<title>fib2(2,){}&#45;&gt;fib1(0,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M385.6423,-74.1286C379.3271,-65.493 371.7059,-55.0716 364.7942,-45.6202\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"367.432,-43.298 358.7039,-37.2921 361.7817,-47.4301 367.432,-43.298\"/>\n",
       "</g>\n",
       "<!-- fib2(1,){} -->\n",
       "<g id=\"node9\" class=\"node\">\n",
       "<title>fib2(1,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"473.2688\" cy=\"-18.9206\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"473.2688\" y=\"-17.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib2(1) ↦ 1</text>\n",
       "</g>\n",
       "<!-- fib2(2,){}&#45;&gt;fib2(1,){} -->\n",
       "<g id=\"edge7\" class=\"edge\">\n",
       "<title>fib2(2,){}&#45;&gt;fib2(1,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M417.5609,-74.509C426.7014,-65.3882 437.9089,-54.2047 447.8688,-44.2662\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"450.5806,-46.5046 455.1871,-36.9636 445.6362,-41.5495 450.5806,-46.5046\"/>\n",
       "</g>\n",
       "<!-- fib2(3,){} -->\n",
       "<g id=\"node10\" class=\"node\">\n",
       "<title>fib2(3,){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"399.2688\" cy=\"-166.6032\" rx=\"55.438\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"399.2688\" y=\"-164.7821\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">fib2(3) ↦ 2</text>\n",
       "</g>\n",
       "<!-- fib2(3,){}&#45;&gt;fib1(1,){} -->\n",
       "<g id=\"edge9\" class=\"edge\">\n",
       "<title>fib2(3,){}&#45;&gt;fib1(1,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M370.8615,-150.2154C352.4669,-139.6038 328.3205,-125.6742 308.4106,-114.1884\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"310.0077,-111.0692 299.5967,-109.1039 306.5098,-117.1326 310.0077,-111.0692\"/>\n",
       "</g>\n",
       "<!-- fib2(3,){}&#45;&gt;fib2(2,){} -->\n",
       "<g id=\"edge10\" class=\"edge\">\n",
       "<title>fib2(3,){}&#45;&gt;fib2(2,){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M399.2688,-147.5872C399.2688,-139.7493 399.2688,-130.4909 399.2688,-121.8357\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"402.7689,-121.7134 399.2688,-111.7134 395.7689,-121.7134 402.7689,-121.7134\"/>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x10c105588>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from callgraph import CallGraphRecorder\n",
    "\n",
    "recorder = CallGraphRecorder()\n",
    "\n",
    "@callgraph(recorder=recorder)\n",
    "@lru_cache()\n",
    "def fib(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib(n - 2) + fib(n - 1)\n",
    "\n",
    "@callgraph(recorder=recorder)\n",
    "@lru_cache()\n",
    "def fib1(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib1(n - 2) + fib2(n - 1)\n",
    "\n",
    "@callgraph(recorder=recorder)\n",
    "@lru_cache()\n",
    "def fib2(n):\n",
    "    if n <= 1:\n",
    "        return n\n",
    "    else:\n",
    "        return fib1(n - 2) + fib2(n - 1)\n",
    "\n",
    "fib(3)\n",
    "fib1(3)  \n",
    "fib2(3)\n",
    "\n",
    "recorder.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use `label_returns` to reverse the arrows and label them with the return values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "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=\"347pt\" height=\"218pt\"\n",
       " viewBox=\"0.00 0.00 347.32 217.84\" 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 213.8413)\">\n",
       "<title>%3</title>\n",
       "<polygon fill=\"#ffffff\" stroke=\"transparent\" points=\"-4,4 -4,-213.8413 343.3248,-213.8413 343.3248,4 -4,4\"/>\n",
       "<!-- nchoosek(1, 0){} -->\n",
       "<g id=\"node1\" class=\"node\">\n",
       "<title>nchoosek(1, 0){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"62.6624\" cy=\"-18\" rx=\"62.8252\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"62.6624\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 0)</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){} -->\n",
       "<g id=\"node2\" class=\"node\">\n",
       "<title>nchoosek(2, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"133.6624\" cy=\"-104\" rx=\"62.8252\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"133.6624\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 1)</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){} -->\n",
       "<g id=\"edge1\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 0){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M112.2722,-78.0907C100.9919,-64.4273 87.4415,-48.0141 77.3548,-35.7964\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"109.8856,-80.6975 118.9512,-86.1807 115.2837,-76.2409 109.8856,-80.6975\"/>\n",
       "<text text-anchor=\"middle\" x=\"106.1624\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- nchoosek(1, 1){} -->\n",
       "<g id=\"node3\" class=\"node\">\n",
       "<title>nchoosek(1, 1){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"205.6624\" cy=\"-18\" rx=\"62.8252\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"205.6624\" y=\"-13.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(1, 1)</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){} -->\n",
       "<g id=\"edge2\" class=\"edge\">\n",
       "<title>nchoosek(2, 1){}&#45;&gt;nchoosek(1, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M155.0759,-78.4228C166.6616,-64.5842 180.6732,-47.8482 191.0094,-35.5022\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"152.3166,-76.2664 148.5808,-86.1807 157.6839,-80.7599 152.3166,-76.2664\"/>\n",
       "<text text-anchor=\"middle\" x=\"178.1624\" y=\"-56.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){} -->\n",
       "<g id=\"node4\" class=\"node\">\n",
       "<title>nchoosek(3, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" stroke-width=\"3\" cx=\"232.6624\" cy=\"-190.9206\" rx=\"87.2039\" ry=\"18.8416\"/>\n",
       "<text text-anchor=\"middle\" x=\"232.6624\" y=\"-189.0995\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(3, 2) ↦ 3</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){} -->\n",
       "<g id=\"edge3\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 1){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M204.0119,-165.7659C187.7343,-151.4743 167.776,-133.9512 153.2808,-121.2247\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"201.8432,-168.5194 211.667,-172.487 206.4616,-163.2591 201.8432,-168.5194\"/>\n",
       "<text text-anchor=\"middle\" x=\"193.1624\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">2</text>\n",
       "</g>\n",
       "<!-- nchoosek(2, 2){} -->\n",
       "<g id=\"node5\" class=\"node\">\n",
       "<title>nchoosek(2, 2){}</title>\n",
       "<ellipse fill=\"none\" stroke=\"#000000\" cx=\"276.6624\" cy=\"-104\" rx=\"62.8252\" ry=\"18\"/>\n",
       "<text text-anchor=\"middle\" x=\"276.6624\" y=\"-99.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">nchoosek(2, 2)</text>\n",
       "</g>\n",
       "<!-- nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){} -->\n",
       "<g id=\"edge4\" class=\"edge\">\n",
       "<title>nchoosek(3, 2){}&#45;&gt;nchoosek(2, 2){}</title>\n",
       "<path fill=\"none\" stroke=\"#000000\" d=\"M246.9111,-162.7728C253.7025,-149.3565 261.624,-133.708 267.5848,-121.9326\"/>\n",
       "<polygon fill=\"#000000\" stroke=\"#000000\" points=\"243.6035,-161.5574 242.2097,-172.0601 249.8489,-164.7189 243.6035,-161.5574\"/>\n",
       "<text text-anchor=\"middle\" x=\"260.1624\" y=\"-142.8\" font-family=\"Times,serif\" font-size=\"14.00\" fill=\"#000000\">1</text>\n",
       "</g>\n",
       "</g>\n",
       "</svg>\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x10c115438>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@callgraph(label_returns=True)\n",
    "@lru_cache()\n",
    "def nchoosek(n, k):\n",
    "    if k == 0:\n",
    "        return 1\n",
    "    if n == k:\n",
    "        return 1\n",
    "    return nchoosek(n - 1, k - 1) + nchoosek(n - 1, k)\n",
    "\n",
    "nchoosek(3, 2)\n",
    "nchoosek.__callgraph__"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "kernelspec": {
   "display_name": "Python [conda env:callgraph]",
   "language": "python",
   "name": "conda-env-callgraph-py"
  },
  "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.6.4"
  },
  "toc": {
   "nav_menu": {
    "height": "30px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}