part_2.introducing_networkx.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Part 2: Introducing NetworkX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Throughout this tutorial we will use the NetworkX python package, so now is a good time to import it."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We'll be working with version 1.11 of the package, which is the latest stable version."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'1.11'"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.__version__"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.1: Building a graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One way to work with a graph using NetworkX is to construct one from scratch. Let's initialize an empty graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g = nx.Graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now grow it by adding edges manually."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "g.add_edge('a', 'b', weight=0.1)\n",
    "g.add_edge('b', 'c', weight=1.5)\n",
    "g.add_edge('a', 'c', weight=1.0)\n",
    "g.add_edge('c', 'd', weight=2.2) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nodes corresponding to the endpoints of the edges you add are automatically added to the graph. Any python object can be a node in the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can also add nodes instead of edges:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "g.add_node('e')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.2: Plotting graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Like many python packages, NetworkX uses the popular matplotlib package to plot graphs. To have these graphs displayed natively inside our Jupyter notebook, we need to use the following IPython magic command:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can now display our simple graph using NetworkX's `draw()` function:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFBCAYAAACrYazjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3X1U1HX+9/HXeBegSIj31mqleBekBnaZmuXmHeiwaFdm\n63qTZpEp0y4nf/jbPZ2u3Y2tpXWwNnbLtsmtfnmuWgUFLe9SV01G3cK0ZM3M1lJQCFEHFZjrD2wu\nb0DQZvgMw/NxjufI8GV4czz69PO9tbjdbrcAAIARzUwPAABAU0aIAQAwiBADAGAQIQYAwCBCDACA\nQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAhBgDAIEIMAIBBhBgAAIMIMQAABhFiAAAM\nIsQAABhEiAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgxAAAGEWIAAAwixAAAGESIAQAwiBADAGAQ\nIQYAwCBCDACAQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAhBgDAIEIMAIBBhBgAAIMI\nMQAABhFiAAAMIsQAABhEiAEAMIgQAwBgUAvTAwAIbIWFhVrqcKggP1+nSkvVJixMkdHRmj5zpjp0\n6GB6PMA4i9vtdpseAkDgcTqdykhLU87q1ZooKba8XKGSyiTlBQdrudut+HHjlJyaqtjYWMPTAuYQ\nYgBe92pmpp5JSdECl0vT3W6F17BNiSSHxaIXgoP1bHq65iQlNfSYgF8gxAC86tXMTD2fkqIPzpxR\nz3psf0DSmJAQLSDGaKIIMQCvcTqdst57r7bUM8I/OCBpeEiIVm7apJiYGF+NB/glzpoG4DUZaWla\n4HJdU4Qlqaekp10uZaSl+WIswK+xIgbgFYWFherdvbsOlpdfcUz4eUmvSSqU9BNJv5P0s8u2KZZ0\nW1CQCg4f5mxqNCmsiAF4xVKHQ4lSjSdm9ZS0VdJJSc9Imirp2GXbtJOUaLFoqcPhyzEBv0OIAXhF\nQX6+BpeX1/i5SZI6Xfj9/5bUS1JeDdvFulwq2LPHNwMCfooQA/CKU6WlCq3lc0slDVT1ajlc0l5J\nx2vYLlRSWUmJbwYE/BR31gLgFW3CwlRWw+uHJc2RtFHSkAuvDZRU08kpZZJCw2vauQ0ELlbEALwi\nMjpaeUFBV7x+WtX/0LSXVCXpDUmf1fIeeUFBioyK8tmMgD8ixAC8YtqMGVqu6jtmXayvpF9J+l+S\nOqt6t/SwGr6+WNKy8nIdPHRIhw8f9umsgD8hxAC8omPHjoofN05vWixXfO63kk6o+vKldFXvpn7k\nsm3etFg0dswYBQUFaeDAgXrwwQe1bds2cYUlAh3XEQPwGm/dWausrExvvPGGFi9erHbt2slms+mB\nBx5Qq1atfDU6YAwhBuBV3rzXdGVlpXJycmS327V//37NnTtXc+bMUfv27X0yO2ACu6YBeNWcpCTN\n++1vFSPpTxbLFceMf1B84fPDr/LAh+bNm8tqtWrDhg3Kzc3VgQMH1KtXL82ZM0d79+715Y8BNBhW\nxAC8bt68eTpy5IhaWyxalZurRItFsS6X53nEzgvPIx4fF6fk1NRretDDsWPH9Ne//lWZmZmKioqS\nzWbT2LFj1awZ6wo0ToQYgFft3r1bcXFx2rt3ryIiIlRUVKSlDocK9uxRWUmJQsPDFRkVpWkzZvyo\ne0qfPXtWy5Yt06JFi+RyuZScnKxp06apdevWXvxpAN8jxAC8pqqqSkOGDNFjjz2mRx65/Lxo33C7\n3dq8ebPsdru2bNmiWbNmae7cufrJT37SIN8f+LHYlwPAa5YsWaIWLVpoxowZDfY9LRaLRowYoeXL\nlysvL0/nzp3TgAEDNHnyZG3fvr3B5gCuFytiAF5RVFSk/v37a926dYqOjjY6y8mTJz2XP3Xo0EE2\nm02TJk1Sy5Ytjc4F1IQQA/CKWbNmqW3btlq0aJHpUTwqKyu1atUq2e12/fvf/9aTTz6pRx99VBER\nEaZHAzwIMYAfbevWrZo8ebL27duntm3bmh6nRp988onsdruysrI0efJkJScnq2/fvqbHAjhGDODH\nqaio0BNPPKEXX3zRbyMsSQMGDJDD4dDnn3+uzp0767777tPYsWO1Zs0aVVVVmR4PTRgrYgA/it1u\nV05Ojj788ENZarjPtL8qLy/Xu+++K7vdrrNnzyo5OVm/+MUvuPwJDY4QA7huR44c0R133KGtW7eq\nd+/epse5Lm63W5s2bZLdbtc///lPzZ49W08++aRuuukm06OhiWDXNIDr9qtf/UqPP/54o42wVH35\n07333qsVK1Zox44dKi8vV3R0tKZMmaIdO3aYHg9NACtiANdl3bp1evTRR7V3716FhISYHserSktL\nPZc/derUSTabTRMnTuTyJ/gEIQZwzc6ePavo6Gi9+OKLGj9+vOlxfKayslLZ2dmy2+06ePCg5/Kn\ndu3amR4NAYRd0wCuWXp6uvr06RPQEZaqn/6UmJioTZs2KSsrS/v27dNtt92mpKQkffHFF6bHQ4Bg\nRQzgmnz11VeKjY3Vzp071aNHD9PjNLijR48qMzNTf/nLXzRo0CA99dRTGjVqVKM6Yxz+hRADuCYT\nJkzQ3XffrdTUVNOjGFVeXq533nlHdrtdlZWVSk5O1tSpUwPueDl8jxADqLfs7Gw9/fTTys/PV6tW\nrUyP4xfcbrc2btwou92u7du369FHH9XcuXPVrVs306OhkeAYMYB6OX36tObPn68///nPRPgiFotF\nI0eOVHZ2trZt26ZTp04pKipKDz/8sPLy8kyPh0aAFTGAelm4cKEOHTqkd955x/Qofu/777/X3/72\nNy1evFjdunWTzWZTYmKiWrRoYXo0+CFCDKBOX3zxhYYPH678/Hx16dLF9DiNRkVFhefyp0OHDmne\nvHmaPXu2wsPDTY8GP8KuaQBX5Xa7NXfuXP36178mwteoRYsWmjhxojZv3qzly5crPz9ft956q+bO\nnav9+/ebHg9+ghADuKp3331XJ06c0Ny5c02P0qjdeeed+vvf/669e/eqXbt2Gj58uOLj47V27Vqx\nY7JpY9c0gFqVlpaqX79+eu+99zRkyBDT4wQUl8vlufzJ7XZ7Ln8KDg42PRoaGCEGUCubzabTp0/r\ntddeMz1KwHK73dqwYYPsdrt27NihOXPm6IknnlDXrl1Nj4YGQogB1OiTTz7RmDFjtHfvXrVv3970\nOE1CQUGBXnrpJb399tuKi4uTzWZTTEyM6bHgYxwjBnCFqqoqJSUl6fe//z0RbkCRkZF66aWXdPDg\nQQ0cOFCTJk3SsGHD9N5776miosL0ePARVsQArrBkyRK9/vrr2rp1q5o14//rplRUVGjFihWy2+36\n5ptvPJc/3XjjjaZHgxcRYgCXOH78uPr3768PPvhAAwYMMD0OLnA6ncrIyFBubq5+/vOfa/78+erV\nq5fpseAF/FcXwCVSU1P10EMPEWE/Exsbq7feekufffaZwsLCNHToUE2YMEHr16/n8qdGjhUxAI/t\n27frgQce0L59+xQWFmZ6HFyFy+XS22+/LbvdLovFIpvNpocffpjLnxohQgxAUvXxyJiYGC1YsEBT\npkwxPQ7qye12a926dbLb7dq5c6fn8ifugtZ4sGsagCTplVdeUUREhB566CHTo+AaWCwWjRo1Sjk5\nOdq8ebOKi4vVv39/TZs2Tbt27TI9HuqBFTEAfffdd4qOjtaWLVvUp08f0+PgRyopKdGSJUv00ksv\nqUePHrLZbEpISFDz5s1Nj4YaEGIAevjhh9WjRw8999xzpkeBF1VUVGj58uWy2+369ttvNW/ePM2a\nNYvj/36GEANN3Pr16zVr1izt27dPISEhpseBj+Tl5SkjI0OrV6/W1KlTNX/+fPXs2dP0WBDHiIEm\n7dy5c5o7d64WL15MhAPc4MGD9fbbbys/P19t2rTRkCFDZLVatXHjRi5/MowVMdCEpaWladu2bVq5\ncqXpUdDAzpw5o7feekt2u10tW7aUzWbTlClTFBQUZHq0JocQA03UoUOHFBMTI6fTqVtuucX0ODDE\n7XZr7dq1stvt2r17tx577DElJSWpc+fOpkdrMtg1DTRRNptNTz31FBFu4iwWi0aPHq3c3Fx99NFH\nKioqUt++fTV9+nT961//Mj1ek0CIgSZo5cqV+vzzz5WSkmJ6FPiRPn366JVXXtGXX36pfv36yWq1\nasSIEVq+fLkqKytNjxew2DUNNDFnzpxR//799dprr+n+++83PQ782Pnz5/WPf/xDdrtdx44d0/z5\n8/XII4+obdu2pkcLKKyIgSbmueee01133UWEUaeWLVtq8uTJ2r59u9555x3t2LHDc4OQL7/80vR4\nAYMVMdCE7N+/X8OGDdOnn36qrl27mh4HjdA333yjV155RUuWLNHQoUNls9k0YsQIWSyWa36vwsJC\nLXU4VJCfr1OlpWoTFqbI6GhNnzlTHTp08MH0/okQA02E2+3W6NGjFR8fL5vNZnocNHKnT5/2XP50\nww03eC5/uuGGG+r8WqfTqYy0NOWsXq2JkmLLyxUqqUxSXnCwlrvdih83TsmpqYqNjfX1j2IcIQaa\niGXLlum5557Trl271KJFC9PjIEBUVVXpww8/lN1u1yeffKKkpCQ9/vjj6tSpU43bv5qZqWdSUrTA\n5dJ0t1vhNWxTIslhseiF4GA9m56uOUlJPv0ZTCPEQBNw8uRJ9evXT8uWLdPQoUNNj4MAtW/fPi1e\nvFjLli3Tz372MyUnJ2vAgAGez7+amannU1L0wZkz6inpFkmvSxpZy/sdkDQmJEQLAjzGhBhoAn75\ny1+qtLRUr7/+uulR0AScOHFCr732ml5++WX16tVLNptNnTp1UuJPf6otFyIs1R1iqTrGw0NCtHLT\nJsXExPh8dhMIMRDgPv30U40ePVp79+5V+/btTY+DJuT8+fN6//33tWjRIn312WdKdbn01EXJqU+I\nJWmRxaLdiYn6+/vv+3JcYwgxEMCqqqo0fPhwTZ8+XXPmzDE9DpqowsJCRd58s746d+6SY8K3SHpM\n0t8lHZX0M0mZklpd9vXFkm4LClLB4cMBeTY11xEDAczhcKiiokKzZ882PQqasKUOhyY2a1bjiVnv\nSFor6UtJ+yX9roZt2klKtFi01OHw3ZAGEWIgQJ04cUILFy5UZmammjXjrzrMKcjP1+Dy8ho/N09S\nV0k3SvpvSf9Ty3vEulwq2LPHNwMaxjUMQIBauHChHnzwQQ0aNMj0KAhw58+f13fffacjR47U+OsL\np1Mjavnamy76fXdJ39ayXaikspISr87tLwgxEIB27NjhebADcL3cbrdKS0trDewPv4qLi9WxY0d1\n69btkl9RUVHq1q2bXrXbVVbLM6+/uej3X6t6dVyTMkmh4TXt3G78CDEQYCorK5WUlKQ//vGPCgsL\nMz0O/NT58+d19OjROiPbvHnzKwJ7++23a8yYMZ6PO3XqpObNm9f6vXbv3Km8tWv1eA27p/8sKV5S\nsKTnJD1Uy3s4g4PVPyrKCz+5/+GsaSDAvPzyy3r//fe1YcOG67r/Lxo3t9utkydP1hnYEydOqEOH\nDldE9vJfoaGhP3qmwsJC9e7eXQfLyy85YetWVZ81vVTSd6o+a/oVSUGXfX2gnzVNiIEAcvToUUVF\nRWnz5s3q27ev6XHgZRUVFfVaxVosljoD26lTpwa91enUiRMVs2KFbNeRHK4jBtBoTJ06VTfddJP+\n8Ic/mB4F16g+q9jjx4+rffv2dUbWH58X7HQ6Zb333kvurFUf3FkLQKPx0Ucfafr06dq3b59at25t\nehxcUFFRoWPHjtUZWbfbXWdgO3fu3Kgf2HH5vabr0lTuNd14/0QBeJw7d05PPPGEMjIyiHADKisr\nqzOwRUVFioiIuCKqI0eOvGIVG+jH9H+I6fCUFD3tcmlGLU9fKlb105f+yNOXADQWzz//vLZs2aKV\nK1cG/D/mDaGysrJeq9jKysp6rWJbtmxp+kfyKzt37lRGWppW5eYq0WJRrMvleR6x88LziMfHxSk5\nNTVgd0dfjBADjdzhw4c1aNAg5eXl6dZbbzU9jt87depUnYEtLCxUu3bt6oxsWFgY//H5EYqKirTU\n4VDBnj0qKylRaHi4IqOiNG3GjIA8O7o2hBhoBAoLC6v/wcrP16nSUrUJC1NkdLSmz5ypxx57TAMH\nDtRvfvMb02MaVVlZqcLCwjoje/78+ToD26VLF1axaDCEGPBjTqdTGWlpylm9WhMlxZaXe3bh5QUH\n6/2KCt3QqpX+sWaNhg0bZnha36lpFfvtt99e8vGxY8cUHh5eZ2RvvPFGVrHwK4QY8FOvZmbqmZQU\nLXC5NL2Wk1pKJL3RiE9qqe8q9ty5c/VaxbZqdfkD9AD/R4gBPxQIl3mcPn26zsAeO3ZMN954Y52R\nDQ8PZxWLgEWIAT/j7zc+qKqqqtcqtry8vF6r2BtuuMFnswKNASEG/IzJWwGeOXOmzsAePXpUYWFh\ndUa2Xbt2rGKBeiDEgB+p7eb4kvQfScmStkhyS5oiafFl29R2c/yqqioVFRXVGVmXy6WuXbteNbBd\nu3ZlFQt4EXfWAvzIUodDidIVEa6SNF7S/ZLeltRM0s4avr6dpPEVFZqUmKhOXbpcsooNDQ29IqpD\nhgy55OOIiAhWsUADI8SAHynIz9fgGp7Zmqfqx8S9oOoIS9LdtbzH3RUVOuRyadKkSZesYoOCLn+4\nHAB/QIgBP3KqtFQ1Pf31G0nd9f8jfDWhkm7u2lUPPVTbI9YB+JP6/L0G0EBuaN1aZTW8frOkw6re\nRV2XMkmh4TVddQzAHxFiwLD//Oc/yszM1NixY/U/y5drS7Mr/1oOltRF0n9JOiPprKRttbyfMzhY\nkVFRPpsXgHdx1jTQwNxut/Lz85WVlaXs7Gx99dVXiouLk9Vq1aBBgxRz++21njU9T9VnTTeT9LAk\n+2Xb1HbWNAD/RYiBBnDu3Dlt3rxZ2dnZys7OVrNmzZSQkKCEhAQNHTr0kgcMmLyOGEDDI8SAj3z/\n/fdavXq1srOztWbNGvXu3VtWq1UJCQnq169frZcJ+fudtQB4FyEGvOjrr79Wdna2srKylJeXp3vu\nuUcJCQkaP368unTpUu/3CYR7TQOoH0IM/Ahut1u7du3y7HI+cuSIxo8fL6vVqtGjR6t169bX/d4/\nPH3paZdLM2p5+lKxJEcjfvoSAEIMXLOzZ89q48aNysrK0sqVKxUSEuI53jtkyBA1b97ca99r586d\nykhL06rcXCVaLIp1uTzPI3YGB2u5263xcXFKTk1ldzTQSBFioB6Ki4uVk5Oj7OxsrV27Vrfffrus\nVqusVqv69Onj8+9fVFSkpQ6HCvbsUVlJiULDwxUZFaVpM2ZwdjTQyBFioBZffvml53jv7t27NXLk\nSCUkJCg+Pl4dO3Y0PR6AAEGIgQuqqqqUl5fnOd57/PhxTZgwQVarVffff7+Cg4NNjwggABFiNGku\nl0vr16/3HO+NiIjwXGI0ePBgNavhLlcA4E2EGE1OUVGRVq1apezsbG3YsEEDBw70HO/t2fNartwF\ngB+PEKNJ2L9/v+d47549ezRq1CglJCQoLi5OERERpscD0IQRYgSkyspKffzxx577OZeVlXlWvffd\ndx/P5gXgNwgxAsbp06e1du1aZWVlKScnR126dFFCQoLnYQoc7wXgjwgxGrWjR49q5cqVys7O1qZN\nmzR48GDPyrdHjx6mxwOAOhFiNCput1v79u3zHO/dv3+/xowZo4SEBI0dO1bh4TXdCBIA/Bchht+r\nqKjQ1q1bPcd7z50759nlPGLECLVq1cr0iABw3Qgx/FJZWZk++OADZWVlKTc3Vz169PDE94477qj1\nEYIA0NgQYviNI0eOeO5qtXXrVt19992yWq2aMGGCbr75ZtPjAYBPEGIY43a7lZ+f7znee/DgQcXF\nxSkhIUFjxoxR27ZtTY8IAD5HiNGgzp8/r82bN3uO9zZr1syzy3nYsGFq2bKl6REBoEG1MD0AAt/3\n33+vNWvWKCsrS2vWrFFkZKQSEhK0atUq9e/fn+O9AJo0VsTwia+//tpzvHfHjh265557PMd7u3Tp\nYno8APAbhBhe4Xa7tXv3bs/x3iNHjig+Pl4JCQkaNWqU2rRpY3pEAPBLhBjX7ezZs9q4caNn5RsS\nEuI53nv33XerefPmpkcEAL/HMWJck+LiYuXm5iorK0tr165V//79ZbVatW7dOvXu3ZvjvQBwjVgR\no04HDx70nOW8a9cujRw5UlarVePHj1fHjh1NjwcAjRohxhWqqqrkdDo9x3uLioo0YcIEJSQk6Kc/\n/alCQkJMjwgAAYMQNwKFhYVa6nCoID9fp0pL1SYsTJHR0Zo+c6Y6dOjgle/hcrm0fv16ZWdna+XK\nlQoPD/cc773rrrt4hCAA+Agh9mNOp1MZaWnKWb1aEyXFlpcrVFKZpLzgYC13uxU/bpySU1MVGxt7\nze9fVFSknJwcZWVlacOGDRowYIDnEYK9evXy9o8DAKgBIfZTr2Zm6pmUFC1wuTTd7dbFD/ebKelm\nSU9JclgseiE4WM+mp2tOUlKd71tQUOA53pufn69Ro0bJarUqPj5eERERPvppAAC14axpP/RqZqae\nT0nRljNn1PMq24VLesrt1oQzZzQmJUWSrohxZWWlPv74Y8/x3pMnT8pqtWrhwoW67777FBQU5Lsf\nBABQJ1bEfsbpdMp6771XjfAPK+L/c9FrByQNDwnRyk2b1LdvX61du1bZ2dlatWqVunTp4tnlfOed\nd3K8FwD8CCH2M1MnTlTMihWyXfTH8i9Js1Ud23GSLJJ66dIQS9KfLBb9uVMnFZ0+rdjYWCUkJGjC\nhAm65ZZbGmp8AMA1IsR+pLCwUL27d9fB8nLPMeHzqo7uLyXNlbRC0hRJ/6UrQ1wsqUfLltq1dy8n\nWwFAI8E+Sj+y1OFQonTJiVkfS6qQNF9Sc0mTJNV2fnQ7SQ+0aKHsFSt8OicAwHsIsR8pyM/X4PLy\nS177VlK3y7brfpX3iHW5VLBnj7dHAwD4CCH2I6dKSxV62WtdJB257LXDV3mPUEllJSVenQsA4DuE\n2I+0CQtT2WWvDVH1NWYvqXoX9T8k5V3lPcokhYaHX2ULAIA/IcR+JDI6WnmXXdfbUtXxfUNShKT/\nq+rjxLVxBgcrMirKZzMCALyLs6b9SE1nTV+LYkm3BQWp4PBhr92DGgDgW6yI/UjHjh0VP26c3rzO\nZ/q+abFofFwcEQaARoQVsZ+pz521anLxnbViYmJ8NR4AwMtYEfuZ2NhYPZuerjEhITpQz685IGlM\nSIieTU8nwgDQyBBiPzQnKUkL0tM1PCREiywW1XYxUrGqb2s5PCREC+r59CUAgH9h17Qf27lzpzLS\n0rQqN1eJFotiXS7P84idF55HPD4uTsmpqayEAaCRIsSNQFFRkZY6HCrYs0dlJSUKDQ9XZFSUps2Y\nwYlZANDIEWIAAAziGDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAhBgDAIEIMAIBBhBgAAIMIMQAA\nBhFiAAAMIsQAABhEiAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgxAAAGEWIAAAwixAAAGESIAQAw\niBADAGAQIQYAwCBCDACAQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAhBgDAIEIMAIBB\nhBgAAIMIMQAABhFiAAAMIsQAABhEiAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgxAAAGEWIAAAwi\nxAAAGESIAQAwiBADAGAQIQYAwCBCDACAQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAh\nBgDAIEIMAIBBhBgAAIMIMQAABhFiAAAMIsQAABhEiAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgx\nAAAGEWIAAAwixAAAGESIAQAwqIXpAQAAga2wsFBLHQ4V5OfrVGmp2oSFKTI6WtNnzlSHDh1Mj2ec\nxe12u00PAQAIPE6nUxlpacpZvVoTJcWWlytUUpmkvOBgLXe7FT9unJJTUxUbG2t4WnMIMQDA617N\nzNQzKSla4HJputut8Bq2KZHksFj0QnCwnk1P15ykpIYe0y8QYgCAV72amannU1L0wZkz6lmP7Q9I\nGhMSogVNNMaEGADgNU6nU9Z779WWekb4BwckDQ8J0cpNmxQTE+Or8fwSZ00DALwmIy1NC1yua4qw\nJPWU9LTLpYy0NF+M5ddYEQMAvKKwsFC9u3fXwfLyK44JfydpnqTNkkIl2S58fLFiSbcFBang8OEm\ndTY1K2IAgFcsdTiUKF0RYbekCZIGqjrI6yVlSFp72XbtJCVaLFrqcPh4Uv9CiAEAXlGQn6/B5eVX\nvO6UdFzSf0tqLqmHpNmS3q3hPWJdLhXs2ePDKf0PN/QAAHjFqdJShdbw+teSjqh6xStVr5CrJN1T\nw7ahkspKSnwzoJ8ixAAAr2gTFqayGl6/WdKtkvbX4z3KJIWG13TVceBi1zQAwCsio6OVFxR0xeuD\nVb3SfUFSuaRKSXsl7azhPZzBwYqMivLlmH6Hs6YBAF5xtbOmj0r6paSNks5J6i3pd5JGXrQNZ00D\nAPAjdOzYUfHjxulNi+WKz3WW9I6qz5o+IWmbLo2wJL1psWh8XFyTirDEihgA4EXcWevasSIGAHhN\nbGysnk1P15iQEB2o59f8cK/pZ9PTm1yEJUIMAPCyOUlJWpCeruEhIVpksai2i5GKJf3JYtHwJvzA\nB4ld0wAAH9m5c6cy0tK0KjdXiRaLYl0uz/OInReeRzw+Lk7JqalNciX8A0IMAPCpoqIiLXU4VLBn\nj8pKShQaHq7IqChNmzGjyZ2YVRNCDACAQRwjBgDAIEIMAIBBhBgAAIMIMQAABhFiAAAMIsQAABhE\niAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgxAAAGEWIAAAwixAAAGESIAQAwiBADAGAQIQYAwCBC\nDACAQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAhBgDAIEIMAIBBhBgAAIMIMQAABhFi\nAAAMIsTt98VZAAAAdUlEQVQAABhEiAEAMIgQAwBgECEGAMAgQgwAgEGEGAAAgwgxAAAGEWIAAAwi\nxAAAGESIAQAwiBADAGAQIQYAwCBCDACAQYQYAACDCDEAAAYRYgAADCLEAAAYRIgBADCIEAMAYBAh\nBgDAIEIMAIBBhBgAAIP+Hx551FQocDpbAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10a84f9b0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "nx.draw(g, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we also want to display the edge weights in our weighted graph, we'll have to work a bit harder."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeIAAAFBCAYAAACrYazjAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xtc1VW+//H3BktgJNSS7OY9bFLwaKCpoFZmB9QSsjK1\nUcv85SkVjUZNG6uZogxzdJpBPTUSqdmYo3l3ND0qWoKXxMucyCtlFihIEHsjbPbvD3QfUfDK3msD\nr+c/6ff7dfvZPcq3n7XWdy2Lw+FwCAAAGOFlugAAAGozghgAAIMIYgAADCKIAQAwiCAGAMAgghgA\nAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAG\nAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKI\nAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMI\nYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMAgghgAAIMIYgAADCKIAQAwiCAGAMCg\nOqYLqK2ysrKUnJSkjPR0FeTlqV5AgIJCQjRk2DA1atTIdHkAADexOBwOh+kiapO0tDTNiI/XytWr\nFSMpzGaTv6R8Sam+vlricKh3ZKTGTJyosLAww9UCAFyNIHajOYmJmhIXp/FWq4Y4HGpQwTO5kpIs\nFk319dUbCQkaMXKku8sEALgRQewmcxIT9W5cnNYWFqrVFTx/UNIjfn4aTxgDQI1GELtBWlqaHu3R\nQ1uuMITPOSgpws9PyzdtUmhoqKvKAwAYxKppN5gRH6/xVutVhbAktZL0e6tVM+LjXVEWAMAD0BG7\nWFZWllo3barDNttFc8InJI2StFmSv6TYsz8/X46klj4+ysjMZDU1ANRAdMQulpyUpGjpohB2SOor\nqb3KAvlLSTMkrbvguYaSoi0WJSclubhSAIAJBLGLZaSnq6PNdtH1NEknJU2S5C2pmaThkhZW8Blh\nVqsy9u51YZUAAFPY0MPFCvLy5F/B9WOSjqus45XKOuRSSd0qeNZfUn5urmsKBAAYRRC7WL2AAOVX\ncP0uSS0kfXsFn5Evyb9BRW8dAwCqO4amXSwoJESpPj4XXe+osk53qiSbJLuk/ZJ2VPAZab6+CgoO\ndmWZAABDWDXtYpdaNf2TpHGSNko6I6m1pD9JevC8Z1g1DQA1Gx2xiwUGBqp3ZKQ+tlguutdY0gKV\nrZo+JWmbyoewJH1ssahPVBQhDAA1FB2xG7CzFgCgMnTEbhAWFqY3EhL0iJ+fDl7hrzm31/QbCQmE\nMADUYASxm4wYOVLjExIU4een6RaLKnsZKUfS+xaLIjjwAQBqBYam3WzHjh2aER+vFatWKdpiUZjV\n6jyPOO3secR9oqI0ZuJEOmEAqAUIYkOys7OVnJSkjL17lZ+bK/8GDRQUHKzfDR3KwiwAqEUIYgAA\nDGKOGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogBADCIIAYAwCCCGAAAgwhiAAAMIogB\nADCojukCAACXl5WVVXZQTHq6CvLyVC8gQEEhIRoybBgHxVRzHPoAAB4sLS1NM+LjtXL1asVICrPZ\nnEenpp49OrV3ZKTGTJyosLAww9XiWhDEAOCh5iQmakpcnMZbrRricKhBBc/kSkqyWDTV11dvJCRo\nxMiR7i4T14kgBgAPNCcxUe/GxWltYaFaVXB/mKS7JL159ucHJT3i56fxhHG1QxADgIdJS0vToz16\naEslISxdHMRSWRhH+Plp+aZNCg0NdXmdqBqsmgYADzMjPl7jrdZKQ7gyrST93mrVjPh4V5QFF6Ej\nBgAPkpWVpdZNm+qwzVZuTni3pOEq63ojJVkk3a3yHbEk5Uhq6eOjjMxMVlNXE3TEAOBBkpOSFC2V\nC+FiSdGShqgsaJ+QtLiSX99QUrTFouSkJFeWiSpEEAOAB8lIT1dHm63cta8llUgaLclb0uOSLvWi\nUpjVqoy9e11WI6oWQQwAHqQgL0/+F1z7UdIdF1xreonP8JeUn5tbpXXBdQhiAPAg9QIClH/Btdsk\nHb/gWuYlPiNfkn+Dit46hiciiAHAgwSFhCjVx6fctc4q24/4Lyobov6npNRLfEaar6+CgoNdViOq\nFqumAcCDVLZqepfKVk0fkhR19hqrpmsGDn0AAA8SGBio3pGR+njpUsWe1yd1UFkYX87HFov6REUR\nwtUIHTEAeJgr2VmrIuysVT0xRwwAHiYsLEwvjh+vCJWF65U4t9f0GwkJhHA1QxADgIcpKirS0mXL\n1OPJJxXh56fpFosqexkpR9L7FosiOPCh2mJoGgA8zLhx43T48GEtWbJEO3fu1Iz4eK1YtUrRFovC\nrFbnecRpZ88j7hMVpTETJ9IJV1MEMQB4kBUrVujFF1/U7t271bBhQ+f17OxsJSclKWPvXuXn5sq/\nQQMFBQfrd0OHsjCrmiOIAcBD/PDDDwoNDdXixYvVtWtX0+XATZgjBgAPYLfbNWjQII0aNYoQrmUI\nYgDwAH/6059Up04dTZgwwXQpcDM29AAAwzZt2qRZs2Zp165d8vb2Nl0O3IyOGAAMOnnypAYPHqy5\nc+fqtttuM10ODGCxFgAY4nA41LdvX917772aOnWq6XJgCB0xABjy5z//WSdPntRbb71luhQYREcM\nAAbs2LFDUVFR2r59u5o3b266HBhERwwAbvbLL79owIAB+utf/0oIg44YANzJ4XBo4MCBCggI0KxZ\ns0yXAw/A60sA4EZz587Vvn37lJqaaroUeAg6YgBwkwMHDqh79+7atGmT7r33XtPlwEMwRwwAbmC1\nWvXUU0/pnXfeIYRRDh0xALjByJEjdfr0aS1YsEAWi8V0OfAgzBEDgIstWrRI69at065duwhhXISO\nGABc6MiRI+rUqZNWrVql0NBQ0+XAAzFHDAAuUlxcrKeffloTJkwghFEpOmIAcJHx48dr//79Wr58\nOUPSqBRzxADgAmvXrtX8+fO1e/duQhiXREcMAFXsxIkTuu+++7RgwQL16NHDdDnwcMwRA0AVcjgc\nWrRokUaMGEEI44rQEQNAFbNarapbt668vOh1cHkEMQAABvHXNQC4TqWlpaZLQDVGRwwAV+mtt97S\n6dOnZbFYNHXqVNPloJqjIwaAq/D6669ry5Yt6tWrl3bt2qUXXnhBdrudrhjXjPeIAeAK7dmzR0uW\nLFFKSor8/f119913a+LEiZIkLy8vORwOWSwW5z+BK0FHDABXyGKxaMKECfL395fdbtedd96pU6dO\nadu2bZLKzhs+9xxwpQhiALhCISEh6tmzp6SyDrhOnTq6++67tX//fmVnZ6tPnz7avXu34SpR3bBY\nCwCuQGlpaYXvBW/cuFHr16/XsWPH1K5dO73yyisGqkN1RhADwCXY7XZ5e3tXej8jI0P33HOPYmJi\n9Pnnn7uxMtQUDE0DQCWKi4v15ptvavDgwVq0aJF++eWXi55p2rSpRowYoQ8//NBAhagJ6IgBoBKD\nBg1Sw4YN1bp1a61du1a9e/fWCy+84LxfXFysvLw81a9fX3Xq8BIKrg3/5QBABZYuXapDhw5p/vz5\nkqT27dvrj3/8o4YOHSofHx9J0qJFi9SgQQNFRkaaLBXVHEPTAFCBe++9V6+//rokqaioSO3bt9fP\nP/+sf//735Kkb775Rk2aNCGEcd3oiAGgAkFBQbrzzjslSXXr1pUktWvXTjabTd9++62GDx+u9evX\nmywRNQRBDACV8PPzk/R/ry517NhRixcv1jfffKOxY8eqfv36hitETcDQNABcxrn3h5s3b673339f\n9913nwYNGmS4KtQUrJoGgEqUlJSouLhYvr6+kspWScfHx+sPf/iD4cpQk9ARA0AFSktL9fjjj2v/\n/v3OazfccIMmT55ssCrURAQxAFRg2rRpOnnypNq1a1fuekXbXALXg6FpALjA9u3b9eijjyo1NVVN\nmzY1XQ5qOP5qBwDnOX36tJ5++mnNmjWLEIZb0BEDwFkOh0NPPfWUAgMD9cEHH5guB7UE7xEDwFn/\n/d//rYyMDCUnJ5suBbUIHTEASNq3b58eeOABpaSkqHXr1qbLQS3CHDGAWq+wsFBPPfWUEhISCGG4\nHR0xgFrv+eefl81mU3JysiwWi+lyUMswRwygVlu4cKE2bdqknTt3EsIwgo4YQK116NAhde7cWWvW\nrFGHDh1Ml4NaijliALXSmTNnNGDAAE2ePJkQhlF0xABqpbi4OH333XdaunQpQ9IwijliALXOypUr\ntWjRIu3atYsQhnF0xABqlePHj+u+++7T559/rvDwcNPlAMwRA6g97Ha7Bg8erJdeeokQhscgiAHU\nGm+99Za8vLw0ceJE06UATswRA6gVNm/erMTERO3cuVPe3t6mywGc6IgB1HgnT57UoEGD9Pe//123\n33676XKAclisBaBGczgcevTRR3XPPffovffeM10OcBGGpgHUaDNnzlRWVpYWL15suhSgQnTEAGqs\nnTt3KjIyUl9//bVatGhhuhygQnTEAKqlrKwsJSclKSM9XQV5eaoXEKCgkBANGTZMjRo10i+//KIB\nAwbogw8+IITh0eiIAVQraWlpmhEfr5WrVytGUpjNJn9J+ZJSfX21xOFQ78hInSwsVNOmTTV79mzD\nFQOXRhADqDbmJCZqSlycxlutGuJwqEEFz+RKmmux6I+S/jh9ul4aM8bNVQJXhyAGUC3MSUzUu3Fx\nWltYqFZX8PxBSY/4+Wl8QoJGjBzp6vKAa0YQA/B4aWlperRHD225whA+56CkCD8/Ld+0SaGhoa4q\nD7gubOgBwOPNiI/XeKv1qkJYklpJ+r3Vqhnx8a4oC6gSdMQAPFpWVpZaN22qwzZbhXPCP0gaI2mL\nJIekpyXNPO9+jqSWPj7KyMxUo0aNXF8wcJXoiAF4tOSkJEVLFYZwqaQ+kppLypR0XNKAC55pKCna\nYlFyUpIrywSuGe8RA/BoGenp6mizVXgvVdIJSVP1f11FlwqeC7Na9c3eva4pELhOdMQAPFpBXp78\nK7n3vaSmuvwfZP6S8nNzq7QuoKoQxAA8Wr2AAOVXcu8ulQ1Jl17mM/Il+TeoaHAbMI8gBuDRgkJC\nlOrjU+G9jpJukzRBUqGkIknbKnguzddXQcHBLqsRuB6smgbg0a5k1fQola2a9pI0UNKfz7ufI6lZ\nnTrak5Gh5s2bu75g4CrREQPwaIGBgeodGamPLZYK798paYmkk5KyVD6EJSnJYlHjW29VWFiYJkyY\noB9//NG1BQNXiSAG4PHGTJyod319dfAqf91BSe/5+mrB0qVKS0tTYWGh2rZtq2HDhmnfvn2uKBW4\nagQxAI8XFhamp559VhHSFYfxub2m30hIUGhoqJo3b66ZM2fq4MGDuvvuu/Xwww8rMjJSGzZsEDN0\nMIkgBuDxUlJSNH/hQj3z8suK8PPTdItFlb2MlCPpfYtFEZUc+NCwYUO9+uqrOnLkiPr3768XX3xR\noaGh+vTTT1VcXOzy7wJciMVaADza7t279cgjj2jevHnq1auXduzYoRnx8VqxapWiLRaFWa3O84jT\nzp5H3CcqSmMmTryigx5KS0u1atUqJSQk6MiRI4qNjdXw4cPl71/Z28tA1SKIAXisb7/9Vj169NAH\nH3ygxx9/vNy97OxsJSclKWPvXuXn5sq/QQMFBQfrd0OHXvOe0qmpqZo2bZq+/PJLDR8+XKNHj9bt\nt99eFV8FqBRBDMAjZWZmKiIiQq+//rqGDRvm1t/7yJEjmj59uubNm6fHHntML7/8stq2bevWGlB7\nMEcMwOP8/PPP6tmzp8aNG+f2EJZU4cKuqKgoFnbBJeiIAXiU3Nxc9ejRQzExMZoyZYrpciRJNptN\n8+fPV0JCgvz8/BQXF6cnnnhCdepwbg6uH0EMwGMUFBSoV69e6tSpk95//31ZKtnEw5TzF3YdPXpU\nsbGxeu6551jYhetCEAPwCEVFRerTp4+aNGmiDz/80ONC+ELnL+x6/vnnNWrUKBZ24ZowRwzAuJKS\nEj399NOqX7++5syZ4/EhLEkdO3bUZ599ptTUVP3666/OHbv2799/xZ9BHwSJIAZgWGlpqYYPH67C\nwkLNmzdP3t7epku6Ki1atNDMmTP13XffqVWrVurZs+cVL+zatWuXHnroIc2ePdtN1cITEcQAjHE4\nHIqNjdXBgwe1ePFi1a1b13RJ1+zmm2/WpEmTdOTIEcXExDh37Priiy8qDeQbb7xRTz75pMaMGaMD\nBw64uWJ4CuaIARgzZcoULVu2TBs3blT9+vVNl1OlSktLtXLlSpWUlKh379668cYbK3xuwYIFmjdv\nnlatWnXRPYfDUS2G6XF9CGIARrz//vuaPXu2tmzZosDAQNPlGGG1WvWf//mfio2NVXR0tOx2+0VD\n8ydOnNBtt91mqEK4A0PTANzuo48+0syZM7V+/fpaG8KStHr1apWUlCg6OlqS5O3t7RzG/uGHH/Tm\nm2/qySefVOfOnbVjxw6TpcKFCGIAbrVo0SK99tpr+te//qW77rrLdDlGzZ07V4MGDZIk2e1251B0\nXl6e3n33XWVlZWnFihUaOHBghUPXqBkIYgBus2bNGr300ktavXq1goKCTJdjRF5enqZOnaolS5Yo\nJydH//Vf/yVJslgszm543rx5stvtGjt2rAICAhQREaGlS5eaLBsuRBADcIuUlBQ988wzWrJkidq1\na2e6HGMsFouOHj2qIUOG6PDhwyosLJQkeXl5ycvLS3a7XV9++aV69erlHDH49NNPFRERIamsc0bN\nQhADcLldu3YpJiZGCxYsUJcuXUyXY9RNN92kv/3tb/rxxx81dOhQzZo1SytXrtThw4clSXv27FGj\nRo3UunVr3XjjjcrLy9PevXvVr18/Sap271nj8tixHIBL/e///q969+6tWbNm6eGHHzZdjseoV6+e\n4uPjJZX9RWXr1q1q1qyZbrvtNv3www+6+eabJUmzZs3SrbfeqpCQEJPlwoUIYgAuc/ToUfXq1Uvv\nvPOOYmJiTJfjsTp06KAOHTpIkurWravS0lJ99tln6tChg+bMmaMFCxY4g1ni/eKahveIAbjETz/9\npIiICI0aNUqjR482XU61smfPHo0fP17NmjVTr169FBMT4wzfkpISbdiwQTk5Oerfvz9HMdYABDGA\nKpebm6vu3bvriSee0GuvvWa6nGqrpKTEGbTngtjhcOh//ud/9Prrr+vYsWMaO3asnn32WY5irMYI\nYgBVqqCgQA8//LC6dOmihIQEhlBdaPv27Zo2bZo2bNig559/XqNHj2YXrmqIVdMAqozNZlO/fv3U\npk0bQtgNOnXqpH/84x/avn27CgoK1KZNGz377LNXdRQjzCOIAVSJc2cKN2zYULNnzyaE3ahly5b6\ny1/+ou+++04tWrTQQw89pN69e2vjxo2ceVwNMDQN4LqVlpZq2LBhysrK0hdffFHpSUNwD5vNpk8+\n+UTTpk1TvXr1FBcXx8IuD0YQA7guDodDY8aM0e7du7V27Vr5+fmZLglnnTuK8b333lNmZqbGjh2r\n5557TvXq1TNdGs7D0DSA6zJlyhSlpKRoxYoVhLCH8fLyUt++fbV582Z99tlnSklJUbNmzfTqq6/q\nxIkTpsvDWQQxgGv20Ucf6R//+IfWrFmjgIAA0+XgEjp16qRFixZp+/btys/Pdy7sOnDggOnSaj2G\npgFck9LSUv3yyy+y2Wxq3Lix6XJwlU6dOqXExER98MEHuu+++/TKK6+oe/fuLLIzgCAGcM3YarH6\nq6qFXVlZWUpOSlJGeroK8vJULyBAQSEhGjJsmBo1auSi6msGghjAJe3fv19t2rQxXQZc7FoXdqWl\npWlGfLxWrl6tGElhNpv8JeVLSvX11RKHQ70jIzVm4kSFhYW546tUO8wRA6jU4MGDtXHjxnLX+Lt7\nzXQtC7vmJCbq0R49FLp0qQ7bbPrIZtMLkgZJekHS361WHbbZdN/SpXq0Rw/NSUx051eqNghiABUa\nNGiQ6tWrp5deeqnc9XP7HaPmqmhh13PPPVduYdecxES9GxenLYWFinU41KCSz2ogaazDoS2FhXo3\nLo4wrgBD0wAu8q9//UvR0dFav369OnfurFmzZqmgoEBHjx7V9OnTdcMNN8hut3NIfS1x/sKu0NBQ\n9enTR2+8/LK2FBaq1VV8zkFJEX5+Wr5pk0JDQ11VbrVDEAO4SE5Ojv75z39qw4YNOnPmjE6ePKnY\n2FjNnj1bRUVF2rBhg+kSYcC5hV2Tx43T7wsK9PI1fMZ0i0W7oqP1yeLFVV5fdcXQNICLNGzYUP37\n99eDDz6ozMxMLVy4UP369dPq1avl7e2tr7/+2nSJMMDHx0ePPfaYzpSU6NkK7r8rqZWkmyS1lbS0\ngmeGOBxasWqVsrOzXVlqtUIQA3DO+Z4/QFa/fn0NHDhQX3zxhfM94dLSUp05c0alpaVG6oR5yUlJ\nipYqnBNuJWmrpF8kTZE0WNLPFzzTUFK0xaLkpCRXllmtEMQA9NNPP0m6eCGWn5+f83zb0tJSPfbY\nY+rQoYO6dOlipE6Yl5Gero42W4X3Hpd069kfPyHpbkmpFTwXZrUqY+9e1xRYDRHEQC33ySefKCQk\nRB9++KGksjC+sOMtKirS3Llz1apVK02fPt1EmfAQBXl58q/kXrKk9irrlhtI2i/pZAXP+UvKz811\nTYHVEGdiAbXY0aNHNW3aNMXFxemjjz5SQUGBYmNj5eXlpZKSEufuSlarVYMGDZKPj4/hiuFudrtd\n6enp2rJli1JSUvTl+vXqVsFzmZJGSNooqfPZa+0lVbQaOF+Sf4PKXniqfQhioBZr1qyZZsyYoe7d\nu6t79+4aM2aM8vPz9dprrzlDeOXKlTp9+rQGDRpkuFq4Q2FhoVJTU5WSkqItW7bo66+/1h133KHw\n8HD17dtXrVq00PYZM/TCBcPTv6psiPUWSaWSPpa0r5LfI83XV22Cg136PaoTXl8C4LRv3z6NHDlS\n4eHhio+P1/r161VUVKTevXubLg0ucurUKW3dutXZ8aanpys4OFgREREKDw9X165ddcsttzifz8rK\nUuumTXXYZrtowdZrkv4myVvS7yTtlPSMVG6FdY6klj4+ysjMZA/qswhiAOUcOnRIY8eO1b59+xQY\nGKjNmzfrxhtvNF0WqoDD4dDRo0eVkpLi7HiPHz+u+++/3xm8HTt2vOy50oNjYhS6dKliryE+eI/4\nYgQxgItMnjxZCxcu1LZt2xQYGGi6HFwju92uffv2ObvdlJQU2e12Z+hGREQoODj4qk9aSktL06M9\nerCzVhUhiIFabOfOnfrtb39brgP6+eefNXDgQH344Ydq3ry5wepwtaxWq9LS0pzd7ldffaXGjRs7\ngzc8PFwtWrSokqMrz+01vfYKw/igpEf8/DQ+IUEjRo687t+/JiGIgVrqs88+07hx4/TNN99cNFdn\ntVrl6+trqDJcqZycHG3dutXZ7e7Zs0dt2rRxhm54eLhL52HnJCZqSlycfm+1amglBz/kSEqyWPSe\nr6/eIIQrRBADtdCqVas0bNgwrV+/XsGsXq02jh075ux2U1JSlJmZqU6dOjk73k6dOuk3v/mNW2va\nsWOHZsTHa8WqVYq2WBRmtTrPI047ex5xn6gojZk4keHoShDEQC2zefNm9e/fX8uWLdP9999vuhxU\norS0VPv37y83v1tUVFRufrddu3ZXPb/rKtnZ2UpOSlLG3r3Kz82Vf4MGCgoO1u+GDmV19GUQxEAt\nsnPnTkVGRurTTz/VQw89ZLocnMdms2nHjh3Ojnfbtm1q1KhRufndVq1aVcn8LjwLQQzUEgcOHNCD\nDz6oWbNmqV+/fqbLqfVOnz5dbn539+7d+u1vf+vsdrt27apbb7318h+Eao8gBmqBI0eOqFu3bnr7\n7bf1zDPPmC6nVvr+++/Lze8eOXJEnTp1cna7999/v+rVq2e6TBhAEAM13IkTJxQREaHY2Fi99NJL\npsupFUpLS3XgwIFyG2dYrVZn6EZEROg//uM/dMMNN5guFR6AIAZqsJycHHXv3l0DBgzQpEmTTJdT\nYxUVFWnnzp3Obnfr1q1q2LBhufndoKAg5ndRIYIYqKHy8/PVs2dPdevWTVOnTq31IeBwOLR582al\np6frgQceUNu2beVwOK7p30teXp62bdvm7Hh37typ1q1bl5vfPXeOM3A5nrHuHUCVstls6tevn0JC\nQgjhszZs2KDRo0fLbrerTp06atu27RX/ezl+/Hi514gOHTqksLAwhYeHa9KkSercubP8/Ss7pRe4\nNDpioIYpLi5W//795evrq/nz58vb29t0SW5x5swZzZ8/X7t27VLPnj312GOPlbufnZ0tu92uf/7z\nn8rLy1NsbGyFu4c5HA79+9//LrewKj8/39nthoeHq3379hyEgSpDRwzUIKWlpRo2bJhKSkqUnJxc\na0JYkpYtW6bPP/9cvXv31ttvvy1fX189/PDDzq73lltukcVi0U033aTDhw/rxIkTatGixUWfc+zY\nMfXt21fh4eHq1q2bJk2apNatWzOqAJchiIEawuFwaNSoUfr++++1evXqWtexzZw5U6+88or69u0r\nX19frVmzRrfccos6dOig8wf+WrZsqbS0NGVmZqpFixYXzRM3bdpUhw4dMvEVUEt5mS4AQNWYPHmy\ntm/fruXLl1/2PNmaxm63q0OHDsrKypIkdevWTXXr1tXu3bslqVzY3nXXXfLy8tLRo0cl6aJOl84X\n7kZHDNQAU6dO1ZIlS7R582bddNNNpstxO4fDodtvv10nTpyQJN16661q3LixM2zPd+edd6ply5ay\n2Wyy2Wzy9vbmfV4YRUcMVHNz5sxRYmKi1q1bp1tuucV0OUbUqVNHd911lzN469WrJ29vb+dKZi+v\n//ujbvv27Zo7d64mT54sf39/bdy40UTJgBNBDFRjCxcu1BtvvKF169bpjjvuMF2Oy+Xn52vdunX6\nwx/+oJQ9a2PgAAAHBElEQVSUlHL3wsPDdejQIe3atUuS9NVXX6lRo0Y6deqUFi5c6Jz33bhxo7p3\n765ly5bp119/Va9evdz+PYDzMTQNVFMrV67UmDFjtH79erVq1cp0OS7x008/ldsm8ttvv1WHDh0U\nHh6u+vXrXzT3e27zkqKiIp0+fVrh4eEqLi5W48aNFRgYKEmaMGGCya8EXIT3iIFqaNOmTXriiSe0\nfPlyderUyXQ5VcLhcOi7774r9/7uqVOn1LVrV+c2kaGhoapbt26ln1FcXKyUlBRlZGSoT58+tWKU\nANUfQQxUMzt27FBUVJQWLlyoBx980HQ516ykpES7d+92drwpKSny8fEpt3HGvffeW25+F6iJCGKg\nGjl3pvDs2bMv2jnK0xUUFGj79u3Objc1NVXNmjVzdrvh4eFq0qSJ6TIBtyOIgWri3JnC8fHxGjx4\nsOlyLuvnn392Hny/ZcsWHThwQO3bt3d2u126dFGDBg1MlwkYRxAD1cCPP/6oiIgIjRs3Ti+++KLp\nci7icDh06NChcgcjZGVlqUuXLs6h5tDQUPn4+JguFfA4BDHg4U6dOqXu3btr4MCBevXVV02XI6ls\nfnfPnj3lFlbVqVNHERERzo63TZs2tWqva+BaEcSAB8vPz9dDDz2kBx54QO+8846x7Rd//fVXpaam\nOkP366+/VpMmTZxzuxEREWrSpAnbQwLXgCAGPJTValVUVJSCgoI0a9Yst4ZcdnZ2ufndffv2qV27\nduXmd2+++Wa31QPUZAQx4IGKi4v1+OOP6ze/+Y3mzZvn0iFeh8OhI0eOlJvfPXHihDp37uzsdsPC\nwio8uxfA9SOIATfKyspSclKSMtLTVZCXp3oBAQoKCdGQYcPUqFEjSWVnCj/zzDPKy8vTkiVLqvxA\nArvdrvT09HLzuxaLxdnthoeHKzg4mPldwE0IYsAN0tLSNCM+XitXr1aMpDCbTf6S8iWl+vpqicOh\n3pGRGj1hgpKSkrR//36tWbOmSrrQwsJCpaamOrvdr776SnfccUe5jTOaNWvG/C5gCEEMuNicxERN\niYvTeKtVQxwOVfTmbK6kJItFb3l7y//227Vn795rPs7w1KlT2rp1q7PbTU9PV3BwsDN0u3btWmtP\naQI8EUEMuNCcxES9GxentYWFOncsQ3NJH0mqaHPKg5J6+fpqwrRpGjFy5GU/3+Fw6OjRo+UORjh+\n/Ljuv/9+Z8fbsWNH+fn5Vd2XAlClCGLARdLS0vRojx7acl4IS5cOYqksjCP8/LR80yaFhoaWu2e3\n27Vv375yC6vsdnu5+d2QkBDVqcPBakB1QRADLjI4JkahS5cq9oL/xS4XxJI03WLRruhozZk3T2lp\nac5u96uvvlLjxo3Lze+2aNGC+V2gGiOIARfIyspS66ZNddhmu2hOuLmk/yfpE0k/SeonKVHSjec9\nkyPpLotF8vVV27Ztnd1u165dnefqAqgZGL8CXCA5KUnRUoULsyRpgaR1kvwk9ZH0J0lvnne/oaT+\nN9yge159VRMnTXJprQDM4qBPwAUy0tPV0War9P4oSbdLqi9pkqRPK3jm/jNndPTbb11TIACPQRAD\nLlCQlyf/S9y/87wfN5X0YwXP+EvKz82t0roAeB6CGHCBegEByr/E/e/P+/ExlXXHF8qX5M95vUCN\nRxADLhAUEqLUS5y9+1dJx1W2KOttSQMqeCbN11dBwcGuKRCAx2DVNOACl1o13UJlq6aTJZ1Q2arp\nv0k6P7ZzJLX08VFGZqZzD2oANRMdMeACgYGB6h0ZqY8reL/3sKTxkvarLHD/rvIhLEkfWyzqExVF\nCAO1AB0x4CKV7ax1OZfaWQtAzUNHDLhIWFiY3khI0CN+fjp4hb/moKRH/Pz0RkICIQzUEgQx4EIj\nRo7U+IQERfj5abrFospeRsqR9L7Fogg/P41PSLiiAx8A1AwMTQNusGPHDs2Ij9eKVasUbbEozGp1\nnkecdvY84j5RURozcSKdMFDLEMSAG2VnZys5KUkZe/cqPzdX/g0aKCg4WL8bOpSFWUAtRRADAGAQ\nc8QAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACA\nQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMA\nYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQA\nABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQQQx\nAAAGEcQAABhEEAMAYBBBDACAQQQxAAAGEcQAABhEEAMAYBBBDACAQf8fnKU2C9xqAJcAAAAASUVO\nRK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x10bcaec50>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pos = nx.spring_layout(g) #this will create a common layout for nodes; a dict mapping each node to a position\n",
    "nx.draw(g, pos, with_labels=True) #we can now draw the same graph using these specific positions for nodes\n",
    "nx.draw_networkx_edge_labels(g,pos,edge_labels=nx.get_edge_attributes(g,'weight')); #and add edge labels using the same positions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 2.3: Basic algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NetworkX includes implementations of many common graph and network-related algorithms. One of them is the renowned Dijkstra’s algorithm for finding the shortest path between two nodes in a graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', 'c', 'd']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.shortest_path(g, source='b', target='d')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If no path exists, a NetworkXNoPath error will be thrown."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No path between node b and e.\n"
     ]
    }
   ],
   "source": [
    "from networkx import NetworkXNoPath\n",
    "try:\n",
    "    print(nx.shortest_path(g, source='b', target='e'))\n",
    "except NetworkXNoPath:\n",
    "    print('No path between node b and e.')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can also have the algorithm consider edge weights by telling it which edge attribute to treat as weight:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['b', 'a', 'c', 'd']"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.shortest_path(g, 'b', 'd', weight='weight')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If you do not specify the target, you'll get a dict keyed by all possible targets - all other nodes in the graph - each mapping to the shortest path from the given source node to that target (if such a path exists):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': ['b', 'a'], 'b': ['b'], 'c': ['b', 'c'], 'd': ['b', 'c', 'd']}"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.shortest_path(g, 'b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The same goes for leaving out the source. Note that these two operations have different results - besides the order of nodes in the paths - only in directed graphs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': ['a', 'b'], 'b': ['b'], 'c': ['c', 'b'], 'd': ['d', 'c', 'b']}"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.shortest_path(g, target='b')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Leaving out both the source in the target will yield all pair-wise shortest paths in the graph:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'a': {'a': ['a'], 'b': ['a', 'b'], 'c': ['a', 'c'], 'd': ['a', 'c', 'd']},\n",
       " 'b': {'a': ['b', 'a'], 'b': ['b'], 'c': ['b', 'c'], 'd': ['b', 'c', 'd']},\n",
       " 'c': {'a': ['c', 'a'], 'b': ['c', 'b'], 'c': ['c'], 'd': ['c', 'd']},\n",
       " 'd': {'a': ['d', 'c', 'a'],\n",
       "  'b': ['d', 'c', 'b'],\n",
       "  'c': ['d', 'c'],\n",
       "  'd': ['d']},\n",
       " 'e': {'e': ['e']}}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.shortest_path(g)"
   ]
  }
 ],
 "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.5.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}