{
"cells": [
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# CS579: Lecture 05 \n",
"** Community Detection **\n",
"\n",
"*[Dr. Aron Culotta](http://cs.iit.edu/~culotta)* \n",
"*[Illinois Institute of Technology](http://iit.edu)*\n",
"\n",
"(Many figures come from [Mining of Massive Datasets](http://www.mmds.org/), Jure Leskovec, Anand Rajaraman, Jeff Ullman)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"\n",
"\n",
"- **Why do we want to identify communities?**\n",
"- **What are the \"communities\" in this graph?**\n",
"- **Why did you choose these communities?**\n",
"\n",
"<br><br><br><br><br>"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**A bad solution: Agglomerative clustering**\n",
"\n",
"- Let distance function $d(A,B)$ be the shortest path between nodes $A$ and $B$\n",
"- Let $C_i$ and $C_j$ be two clusters of nodes. Then, let the distance between two clusters be the minimum distance of any two nodes: $d(C_i, C_j) = \\min_{X \\in C_i, Y \\in C_j} \\hspace{.1cm} d(X, Y)$\n",
"- Greedy agglomerative clustering iterative merges the closest two clusters \n",
"\n",
"<img width=200 src=\"https://upload.wikimedia.org/wikipedia/commons/a/ad/Hierarchical_clustering_simple_diagram.svg\">"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**What would agglomerative clustering do on this network? **\n",
"\n",
"\n",
"\n",
"$d(A,B) = d(A,C) = d(B, C) = d(B,D) = d(D,E) = d(D,F) = d(D,G) = d(E,F) = d(G,F) = 1$\n",
"\n",
"$d(A,D) = d(C,D) ... = 2$\n",
"\n",
"<br><br><br>\n",
"First merge: sample randomly from all nodes with distance == 1.\n",
"\n",
"\n",
"<br><br><br>\n",
"So, $\\frac{1}{9}$ chance we merge $B$ and $D$ in first merge.\n",
"\n",
"Not desireable...any other ideas?\n",
"\n",
"What makes the edge between $B$ and $D$ special?\n",
"\n",
"<br><br><br><br>"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"**Betweenness:** The betweenness of an edge $(A, B)$ is the number of shortest paths between any nodes $X$ and $Y$ that include edge $(A, B)$.\n",
"\n",
"High betweenness $\\rightarrow$ $A$ and $B$ belong in different communities."
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"What is **betweenness** of $(B,D)$?\n",
"\n",
"<br><br><br>\n",
"\n",
"> $(B,D)$ is on all shortest paths connecting any of $\\{A,B,C\\}$ to any of $\\{D,E,F,G\\}$.\n",
"\n",
"> Thus, total number of shortest paths = number passing through $(B,D)$ = $3 * 4 = \\mathbf{12}.$. So, $bt(B,D) = 12$\n",
"\n",
"\n",
"<br><br><br><br>\n",
"What is **betweenness** of $(D,F)$?\n",
"\n",
"<br><br><br><br>\n",
"\n",
"> $(D,F)$ is on shortest paths from $\\{A,B,C,D\\}$ to $\\{F\\}$.\n",
"\n",
"> Thus, betweenness is $4 * 1 = \\mathbf{4}.$\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"<br>\n",
"Consider this graph:\n",
"\n",
"\n",
"\n",
"What is **betweenness** of $(D,G)$?\n",
"\n",
"<br><br><br>\n",
"\n",
"> $(D,G)$ is on the shortest path from $D$ to $G$. \n",
"> $(D,G)$ is also on one of the two shortest paths from $D$ to $F$ and $E$ to $G$. \n",
"\n",
"> Since there can be several shortest paths between two nodes, an edge (a, b) is credited with the fraction of those shortest paths that include the edge (a, b).\n",
"\n",
"> Thus, betweenness is $\\frac{1}{2} + \\frac{1}{2} + 1 = \\mathbf{2}.$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Formally:\n",
"\n",
"$$\n",
"bt(e) =\\sum_{s,t \\in V} \\frac{\\sigma(s, t|e)}{\\sigma(s, t)}\n",
"$$\n",
"where\n",
"\n",
"- $V$ is the set of nodes\n",
"- $\\sigma(s, t)$ is the number of shortest paths between nodes $s$ and $t$\n",
"- $\\sigma(s, t|e)$ is the number of those paths passing through some edge $e$ \n",
"\n",
"If $s = t$, $\\sigma(s, t) = 1$\n",
"\n",
"So, if there are two shortest paths between $s$ and $t$, but only one goes through $e$, betweenness only increases by 0.5.\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XlYlOXCP/DvMCwDIqKIS6CZoqCmJKaAC+KSJpqmgZrCdFzA8+Kx13ozO0dPb3WOV53j1usvMIdzjjKIivsWuaWYpIjmmmyhopAbosg6AzPz/P4wSQJZdGaeWb6f6+ryYubhma9ZfL2f57nvWyIIggAiIiIrYSN2ACIiImNi8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVVh8RERkVWxFTsAEZEpulemxrYfC5B1uwQlKg1cZLbw6eCCsP6ecHN2EDsePQcJ9+MjIvrNhfxixKTk4lhOIQBArdHVvCeztYEAINjbHdHDvODbyVWklPQ8WHxERL/akJaHpclZUGm0aOgno0QCyGylWBzig/CALkbLR/rBS51ERHhcepmorNY1eqwgAJXVWixNzgQAlp+Z4cMtRGT1LuQXY2lyVr2ldzvxI+SvmgpBU13nvcpqHZYmZ+FiQbExYpKesPiIyOrFpORCpdHWeV1TfAfqggxAIkFF7ql6v1el0SI2JdfQEUmPWHxEZNXulalxLKew3nt6ZT8dgcML3mjRZyTKL31X7/cLAnA0uxBFZWoDJyV9YfERkVXb9mPBU98r/+kIWvQORovew1F57Sy05Q/qPU4CYNvZp5+HTAuLj4isWtbtklpTFh5T5V+GpuQunHyGwKGDF2xdO6L88rF6z6HS6JB1q9TQUUlPWHxEZNVKVJp6Xy//6Ts4vtQPUqdWAIAWvYah7Kf6L3c+Ok/dh1/INHE6AxFZNRdZ3R+Dumo1yrNSAZ0O+f8v/NGLmmro1OWounMV9u271nMeO0NHJT1h8RGRVfPp4AIH29u1LndW/pwGicQGHed8BYn0t0Ir3PUFyn46gja/Kz47G6BHe2ejZabnw0udRGTVQvt71nmt7NJ3aNFnFGxbtYPUuXXNPy37j0d5RgoEXe2pD9XV1fj7rHFYtGgRLl++bKzo9Iy4ZBkRWb2ohDM4lHmnwWXKnkYiAcb0ao/5/RyhVCqxYcMGdOjQAXK5HG+//TbatWun/8D0XFh8RGT1LuQXY1pcGiqr605ib4yjnRRJUQHo6/lowWqtVosjR45AqVRi7969CAoKglwux/jx4yGTyfQdnZ4Bi4+ICM1bq/MxRzsbLA7p+dS1OktLS7Fjxw4olUqcP38eYWFhkMvlCAwMhEQi0VNyai4WHxHRrzak5eGzvZdRpdEBNk9/BOJZdme4ceMGEhMTER8fD41GA7lcjvDwcHTtWvcJUTIsFh8R0ROGTYqAY/83cU3tBAkeTU5/7PF+fMO93REd7FVzebM5BEHAmTNnoFQqsXnzZvTs2RNyuRxhYWFo1aqV/n4j9FQsPiKiX124cAFjx47FtWvXUFb9aBmyrFulKFFVw0VmB5+OLRHqp78d2KuqqpCcnAylUonvvvsOY8eOhVwux+jRo2Fry9lmhsLiIyL6lVwuR69evfDRRx8Z/bOLioqQlJQEpVKJvLw8TJ8+HXK5HK+88orRs1g6Fh8REYD8/Hz4+vri6tWrcHVt/iVMfcrOzkZCQgISEhLg6uoKuVyO6dOno2PHjqLmshQsPiIiAB988AG0Wi1WrVoldpQaOp0O33//PZRKJXbu3ImAgADI5XJMnDgRTk5OYsczWyw+IrJ6Dx8+RNeuXXH27Fm8+OKLYsepV0VFBXbt2gWlUolTp05h8uTJkMvlGDp0KGwaeAKV6mLxEZHVW7ZsGc6fP4/ExESxozTJzZs3a6ZGlJWVISIiAhEREejRo4fY0cwCi4+IrFpVVRW6du2KvXv3ol+/fmLHaRZBEHD+/HkolUps3LgR3bp1g1wux5QpU9CmTRux45ksFh8RWTWlUgmlUonDhw+LHeW5VFdX4+DBg1Aqldi/fz9ee+01yOVyvP7667C3txc7nklh8RGR1RIEAb6+vvjnP/+J119/Xew4elNcXIytW7dCqVQiOzsb06ZNg1wuR//+/blUGrgtERFZsYMHDwIAxowZI3IS/XJ1dUVkZCSOHz+OkydPws3NDVOnTkXv3r3xxRdfID8/X+yIouKIj4is1qhRoyCXyyGXy8WOYnCCIODEiRNQKpXYunUr/Pz8IJfLMXnyZDg7W9cmuiw+IrJKZ8+exYQJE3D16lWruwemUqmwd+9eKJVKHD9+HBMmTIBcLsfw4cMhlUrFjmdwLD4iskozZszAK6+8goULF4odRVR37tzBpk2boFQqUVhYiPDwcERERKBXr15iRzMYFh8RWZ3r16/Dz88PV69e5Y4IT7h06RISEhKwYcMGeHh4QC6XY9q0aXB3d9fL+e+VqbHtxwJk3S5BiUoDF5ktfDq4IKy//hb+bgoWHxFZnffeew9SqRTLly8XO4pJ0mq1+O6776BUKrFv3z4MGzasZhd5B4fmF9SF/GLEpOTiWE4hAEBdz1ZPwd7uiB7mBd9Ohl8nlcVHRFblwYMH6NatGy5cuIBOnTqJHcfklZaWYvv27VAqlbhw4QKmTJkCuVyOgICAJk2NeLSzfRZUGi0aaptn2dz3WbH4iMiqfPHFF8jIyIBSqRQ7itm5fv06NmzYAKVSCZ1OB7lcjoiICHTp0qXe4x+VXiYqq3X1vl8fRzsbLA7padDyY/ERkdVQq9V46aWX8O2338LX11fsOGZLEASkp6dDqVQiKSkJvXv3hlwuR2hoaM090wv5xZgWl4bKam2t7y2/nIKS07tQXVQAG3tH2LXvilaBUyDr1LvmGEc7KZKiAp5ph/umYPERkdVYt24dNm/ejAMHDogdxWKo1eqaXeSPHDmCcePGQS6XY/tdNxzOulvr8mZJ+k48TNsGtzHzIHvJDxKpLSqv/gh1/mW0HjGr5jiJBBjTqz2+Dn/VIJlZfERkFXQ6Hfr06YMvv/wSr732mthxLNK9e/eQlJSE9Zu24W7gu5DY/jY/UqcqR0HMO3AbtwAtfIY0ei4HWxucWDTCIE97cskyIrIK+/fvh729PUaNGiV2FIvVtm1bzJs3D7OX/qvO05/qm1kQNFVw6hHYpHNJAGw7W2CAlCw+IrISy5YtwwcffMBFmo0g63YJqrS1LyZqK0tg4+QCiU3TVoZRaXTIulVqiHgsPiKyfGfOnMGVK1cwZcoUsaNYhRKVps5rUkcX6CpKIOi09XzH085Trc9YNVh8RGTxli9fjgULFsDOzk7sKFbBRWZb5zWHF3wgsbVDRc7JZpzHMH9eLD4ismjXrl3DoUOHEBkZKXYUq9HWtgpSofbIzkbWAq5DZuD+wa9RkXMSumoVBK0GlVfO4MHR/9Q5h8zWBj4dWxokX91aJiKyIF9++SXmzJmDli0N80OUHlGr1di1axfWrl2Ly1duoMXbq+oc4+I/GTbOrfHwRBLu7V0Oib0jHDp4wSVwap1jBQChfp4GycrpDERkse7fvw8vLy9cunQJHh4eYsexSDk5OYiLi0N8fDx8fX0RFRWFiRMn4k9JF3Eo806Dy5Q9jaHn8fFSJxFZrDVr1mDChAksPT1Tq9XYtGkThg8fjqCgIEilUpw4cQKHDh1CWFgY7O3tMS/YCzLbZ9vbT2YrRXSwl55T/4YjPiKySCqVCi+99BIOHTqEl19+Wew4FiErKwtxcXFQKpXo168foqKiMGHChKdu5Guqa3XyHh8RWaQNGzagX79+LL3npFKpsH37digUCuTk5GDmzJlIS0tDt27dGv3ex+XF3RmIiAxMp9OhV69eiI2NxYgRI8SOY5YyMzMRFxeHhIQE+Pn5Ye7cuXjjjTeeaUrIxYJixKbk4mh2ISR4NDn9scf78Q33dkd0sJfBFqZ+Ekd8RGRxvvnmG7Ro0QLDhw8XO4pZqaysrBnd/fzzz5g1axbS09Px0ksvPdd5+3q64uvwV1FUpsa2swXIulWKElU1XGR28OnYEqF+3IGdiOi5BAUFITo6GtOmTRM7ilnIyMiAQqHAhg0bMGDAAERFRWH8+PEWO+GfIz4isiinTp3CjRs3EBoaKnYUk1ZZWYlt27Zh7dq1uHbtGmbNmoUzZ848dVNZS8LiIyKLsnz5crz33nuwteWPt/r89NNPiIuLQ2JiIgYOHIiFCxdi3LhxVvXvi5c6ichiXLlyBf7+/sjLy4Ozs7PYcUxGRUUFtm7dCoVCgby8PMyePRuzZ8/Giy++KHY0UVhPxRORxVu1ahWioqJYer+6dOkSFAoFNm7ciMDAQCxatAghISFWNbqrj3X/7onIYty7dw+JiYnIyMgQO4qoysvLsWXLFigUCuTn52POnDk4d+4cOnfuLHY0k8HiIyKLEBsbi8mTJ6Njx45iRxHFhQsXEBcXh02bNmHQoEH4y1/+grFjx1r96K4+/DdCRGavsrISMTExSElJETuKUZWXlyMpKQkKhQK//PIL5syZg/Pnz6NTp05iRzNpLD4iMntKpRIDBw5Ez549xY5iFOfPn4dCocDmzZsxdOhQ/PWvf8Xrr78OqfTZFoW2Niw+IjJrOp0OK1asQFxcnNhRDKqsrAxJSUlYu3Ytbt++jTlz5uDixYvw9DTMnnWWjMVHRGZtz549cHV1RVBQkNhRDOLcuXNQKBRISkpCUFAQPvnkE4wZM4aju+fA4iMis7Zs2TIsXLgQEolE7Ch6U1pais2bN0OhUODu3buIjIzkZrp6xOIjIrN14sQJ3Lp1C5MmTRI7il78+OOPUCgU2Lp1K4KDg/G3v/0Nr732Gkd3esbiIyKztXz5crz//vtm/ch+aWkpNm7cCIVCgfv37yMyMhKXL1+22mkZxsAly4jILOXk5GDw4MHIy8tDixYtxI7TLIIg1BrdjRgxAlFRUXjttddgY2MjdjyLZ75/TSIiq7Zq1Sr88Y9/NKvSKykpqRndFRcXIzIyEhkZGRzdGRlHfERkdu7evQtvb29kZWWhffv2YsdpkCAIOH36NBQKBbZv345Ro0YhKioKI0eO5OhOJBzxEZHZiY2NRVhYmEmX3sOHD2tGdyUlJYiMjDSLorYGHPERkVmpqKjASy+9hO+//x7e3t5ix6lFEASkp6dDoVBgx44deO211xAVFYURI0ZwdGdCOOIjIrOyfv16BAYGmlTpFRcXIzExEQqFAuXl5YiKiuLozoRxxEdEZkOr1cLb2xvr16/HkCFDRM0iCALS0tKgUCiwa9cujBkzBlFRUQgODubozsRxxEdEZmPXrl1wd3fH4MGDRcvw4MEDbNiwAQqFAmq1GlFRUfjnP/8Jd3d30TJR87D4iMgsCIKAZcuW4cMPPzT68mSCIODkyZM1o7uxY8di9erVCA4Otqil0qwFi4+IzMIPP/yAoqIiTJw40Wif+eDBAyQkJEChUKC6uhpRUVFYtmwZR3dmjsVHRGZh2bJleP/99w2+bqUgCPjhhx+gUCiwZ88ejBs3DjExMQgKCuLozkLw4RYiMnnZ2dkYOnQo8vLy4OTkZJDPuH//fs3oTqvVIioqCnK5HG3btjXI55F4OOIjIpO3YsUKREdH6730BEFAamoqFAoF9u7di/Hjx2PNmjUYOnQoR3cWjCM+IjJpd+7cgY+PD3JycvR2b62oqAhKpRIKhQISiQRRUVGIiIiAm5ubXs5Ppo0jPiIyaV999RWmTZv23KUnCAK+//57KBQKfPPNN5gwYQLi4uIwePBgju6sDEd8RCS6e2VqbPuxAFm3S1Ci0sBFZgufDi4Y17MN/Hr3wIkTJ9C9e/dnO/e9e4iPj0dcXBykUmnN6K5NmzZ6/l2QuWDxEZFoLuQXIyYlF8dyCgEAao2u5j2ZrQ2qNRq0LL2B+EUz4NvJtcnnFQQBx44dg0KhQHJyMiZOnIioqCgMGjSIozti8RGRODak5WFpchZUGi0a+ikkASCzk2JxiA/CA7o0eM7CwkLEx8dDoVDA3t4ec+fORXh4OFq3bq3X7GTeeI+PiIzuUellorJa1+ixAoDKai2WJmcCQJ3y0+l0SElJgUKhwP79+zFp0iTEx8cjICCAozuqF0d8RGRUF/KLMS0uDZXV2prXCmJnQVdRDEhsILGRwsGzJ9qMmQdbl9oPtDjaSZEUFYC+nq64e/cu1q9fj7i4ODg6OiIqKgrh4eFwdW36JVGyThzxEZFRxaTkQqXR1nndPfRjOHZ5BYKmCkUHYnH/0Fq0e2tJrWNUGi0+2XISdqfW4+DBg5g0aRISEhLg7+/P0R01GYuPiIzmXpkax3IKG76nZ2uPFj6Dcf9wXJ33BAE4e1uNPw0ZDoVCgVatWhkwLVkqbhpFREaz7ceCRo/RVatQnnkcDi/Uv9GszMEBLX1fY+nRM+OIj4iMJut2Sa0pC08q3P53wEYKoVoFqVMrtJvyWb3HqTQ6ZN0qNWRMsnAsPiIymhKV5qnvub+15NE9Pp0WlT+fwp2NH+GFOWsgda47FaFEVW3ImGTheKmTiIzGRdb437UlNlI4eQ8CJDZQFVx+ynns9B2NrAiLj4iMxqeDCxxsG/6xIwgCKnLSoFOVwc6tU533ZbY28OnY0lARyQrwUicRGU1of0+sOpxT73uF2z4DJDaARAJbF3e4jX8P9u4v1jlOABDq52ngpGTJWHxEZDRtnR0wrIc7DmXeqTWlwTP6P036fokEGO7tDjdnBwMlJGvAS51EZFT/NawrbIS6E9ibQmYrRXSwl54TkbVh8RGR0ZSUlOCT+TPR8ueDkDVyr+/3HO1ssDjEB309uSQZPR8WHxEZxc8//4yAgAB06NAB6RtXYsm4nnC0k6KxlcYkkkdrdC4O6dno7gxETcFFqonI4A4cOICIiAh89tln+OMf/1jz+sWCYsSm5OJodiEkeDQ5/TGZrQ0EPLqnFx3sxZEe6Q2Lj4gMRhAErFixAitWrEBSUhKCgoLqPa6oTI1tZwuQdasUJapquMjs4NOxJUL9PPkgC+kdi4+IDKKyshKRkZHIyMjArl270LlzZ7EjEQHgPT4iMoD8/HwMHToUWq0WqampLD0yKSw+ItKr1NRU+Pv7Y8qUKdi4cSOcnJzEjkRUCyewE5HeKBQKLFmyBPHx8Rg7dqzYcYjqxeIjoudWVVWF//7v/0ZKSgpSU1PRo0cPsSMRPRWLj4iey927dxEaGopWrVohLS2NG8SSyeM9PiJ6ZmfPnsWAAQMQFBSE3bt3s/TILHDER0TPZNOmTXj33XcRGxuLsLAwseMQNRmLj4iaRavV4i9/+Qu2bNmCw4cPw9fXV+xIRM3C4iOiJisuLsbbb78NtVqN06dPo23btmJHImo23uMjoibJzMyEv78/unfvjgMHDrD0yGyx+IioUXv37sWwYcPw0UcfYfXq1bCzsxM7EtEz46VOInoqQRDw+eefIyYmBnv27EFAQIDYkYieG4uPiOpVXl6OmTNn4vr160hPT4eHh4fYkYj0gpc6iaiOa9euYdCgQXBycsKxY8dYemRRWHxEVMvRo0cRGBiIWbNmYd26dZDJZGJHItIrXuokIgCP7ud99dVX+Pvf/46NGzdi5MiRYkciMggWHxFBrVYjOjoa6enpOHnyJLp27Sp2JCKD4aVOIit369YtBAcH4+HDhyw9sgosPiIrlp6ejgEDBiAkJARbtmyBs7Oz2JGIDI6XOomsVHx8PD744AP861//wsSJE8WOQ2Q0LD4iK6PRaLBw4ULs27cPKSkp6N27t9iRiIyKxUdkRYqKijB16lRIpVKkp6ejdevWYkciMjre4yOyEpcuXcLAgQPh5+eH5ORklh5ZLY74iKzAjh07MHfuXHz55ZeYMWOG2HGIRMXiI7JgOp0On3zyCdavX4/9+/ejf//+YkciEh2Lj8hClZSUICIiAkVFRTh9+jTat28vdiQik8B7fEQWKDc3F4GBgejQoQOOHDnC0iN6AouPyMIcOHAAgwcPxvz587F27VrY29uLHYnIpPBSJ5GFEAQBK1aswIoVK7B161YEBQWJHYnIJLH4iCxAZWUlIiMjkZGRgVOnTqFz585iRyIyWbzUSWTm8vPzMXToUGi1WqSmprL0iBrB4iMyY6mpqfD398eUKVOwceNGODk5iR2JyOTxUieRmVIoFFiyZAni4+MxduxYseMQmQ0WH5GZqaqqwoIFC3D06FGkpqaiR48eYkciMissPiIzcvfuXYSFhcHFxQVpaWlo1aqV2JGIzA7v8RGZibNnz2LAgAEYOnQodu/ezdIjekYc8RGZgc2bN2P+/PmIjY1FWFiY2HGIzBqLj8iEabVaLF68GElJSTh8+DB8fX3FjkRk9lh8RCaquLgY06dPh0qlwunTp9G2bVuxIxFZBN7jIzJBmZmZ8Pf3h5eXFw4cOMDSI9IjFh+Ridm3bx+CgoKwaNEirF69GnZ2dmJHIrIovNRJZCIEQcDnn3+OmJgY7NmzB4GBgWJHIrJILD4iE1BeXo6ZM2fi+vXrSE9Ph4eHh9iRiCwWL3USiezatWsYNGgQnJyccOzYMZYekYGx+IhEdPToUQQGBmLWrFlYt24dZDKZ2JGILB4vdRKJQBAEfPXVV1i6dCkSExMxcuRIsSMRWQ0WH5GRqdVqREdHIz09HSdOnEDXrl3FjkRkVXipk8iIbt26heDgYDx8+BAnT55k6RGJgMVHZCTp6ekYOHAgQkJCsGXLFjg7O4sdicgq8VInkRHEx8fjgw8+wL/+9S9MnDhR7DhEVo3FR2RAGo0GCxcuxL59+5CSkoLevXuLHYnI6rH4iAykqKgIU6dOhVQqRXp6Olq3bi12JCIC7/ERGcSlS5cwcOBA+Pn5ITk5maVHZEI44iPSsx07dmDu3Ln48ssvMWPGDLHjENHvsPiI9ESn0+HTTz/FunXrsH//fvTv31/sSERUDxYfkR6UlpYiIiIC9+7dw+nTp9G+fXuxIxHRU/AeH9Fzys3NRUBAANq3b48jR46w9IhMHIuP6DkcOHAAgwcPxvz587F27VrY29uLHYmIGsFLnUTPQBAErFy5EsuXL8fWrVsRFBQkdiQiaiIWH1EzVVZWIioqCpcvX8apU6fQuXNnsSMRUTPwUidRM+Tn52Po0KHQaDRITU1l6RGZIRYfUROlpqbC398fU6ZMwcaNG+Hk5CR2JCJ6BrzUSdQEcXFxWLx4MeLj4zF27Fix4xDRc2DxETWgqqoKCxYswNGjR5GamooePXqIHYmInhOLj+gp7t69i7CwMLi4uCAtLQ2tWrUSOxIR6QHv8RHV49y5cxgwYACGDh2K3bt3s/SILAhHfES/s3nzZsyfPx+xsbEICwsTOw4R6RmLj+hXWq0WixcvRlJSEg4fPgxfX1+xIxGRAbD4iAAUFxdj+vTpUKlUOH36NNq2bSt2JCIyEN7jI6uXlZUFf39/eHl54cCBAyw9IgvH4iOrtm/fPgQFBWHRokVYvXo17OzsxI5ERAbGS51klQRBwOeff46YmBjs3r0bgYGBYkciIiNh8ZHVKS8vx8yZM3H9+nWkp6fDw8ND7EhEZES81ElWJS8vD4MHD4aTkxOOHTvG0iOyQhzxkdm6V6bGth8LkHW7BCUqDVxktvDp4IKw/p5wc3aoc3xKSgqmTZuGP//5z3j33XchkUhESE1EYpMIgiCIHYKoOS7kFyMmJRfHcgoBAGqNruY9ma0NBADB3u6IHuYF306uEAQBX331FZYuXYrExESMHDlSpOREZApYfGRWNqTlYWlyFlQaLRr6L1ciAWS2Unw42gup6z5Heno6du/eja5duxovLBGZJBYfmY1HpZeJympd4wc/pq1C53tnkLz6z3B2djZcOCIyG7zHR2bhQn4xliZn1ZReQews6CqKARspILGBfdtOaPHyCDi/8jokkiee2ZLao9BzCK4Wa9CXvUdEYPGRmYhJyYVKo631mnvox3Ds8gp0qnKo8n/C/cMKqG/moO24BbWOU2l0iE3JxdfhrxozMhGZKE5nIJN3r0yNYzmFT72nZyNrAafu/nCf+CHKL32HqsK8Wu8LAnA0uxBFZWrDhyUik8fiI5O37ceCJh3n8II3pC5toc7PqPOeBMC2s007DxFZNhYfmbys2yW1piw0ROrcBjpVaZ3XVRodsm7VfZ2IrA/v8ZHJKi8vR35+Pq7m32ry92hLi2Aja1nveyWqan1FIyIzxuIjUZSXl6OgoAD5+flP/VWtVsPT0xP2wyKBtr0aPaf6Vg60pUVw8Kz/WBcZd14gIhYfGUBFRUWDhVZQUACVSgVPT094enqiU6dO8PT0RL9+/fDGG2/UfN2mTRtIJBJ8fewKVh3OeerlTp26Aqr8n/DgsAItegfDvl2XOsfIbG3g07H+kSARWRdOYKdmqaioaHSkVllZWavUHhfZk78+LrWmuFemxuB/HKlVfLXn8Ulg59YJzr2Hw7nfWEhspHXO4WBrgxOLRtS7hicRWRcWH9WoqKjAL7/8gvz8/KcWW3l5eZ0S+/2vbm5uel8AOirhDA5l3MGz/McqkQBjerXnPD4iAsBLnVajsrISBQUFDY7WysrK6lx+7Nu3L0JCQmq+btu2rdF3NRAEAa6/nIJO0xES2+aP2GS2UkQHexkgGRGZI474LEBlZWXNSO1pxVZWVgYPD48GR2pilFpjKisrERUVhcuXL+MPf/831qTdbtZanY52Nlgc0hPhAV0MF5KIzApHfCZOpVI1OlIrLS2Fh4dHrSLr3bs3xowZU/O1u7u7yZVaYwoKCjBp0iR4eXkhNTUVTk5OaNOmebszLA7xYekRUS2ijPiau4GopVKpVI2O1EpKSpo0UrOxsay1CH744QeEhYVhwYIFWLhwYa3SvlhQjNiUXBzNLoQEjyanPyZoqmBv74CRPdshOtgLfT1dRUhPRKbMqMXX3A1EzZlarW50pPbw4cM6I7Xf/+ru7m5xpdaYuLg4LF68GOvXr0dISMhTjysqU2Pb2QJk3SpFiaoaLjI75P54DN52D7B86SfGC0xEZsVoxdfcDURN+RII+Z4QAAATjklEQVSVWq1udKT28OFDvPDCCw2O1Kyx1BpSXV2NBQsW4MiRI9i9ezd69OjR7HOcPXsWoaGhuHLlitld2iUi4zDKPb7fbyBaMwfriX3TnPuMRJvR/wVBACqrtVianAkARi+/x6XW0EituLgYL7zwQq0i8/b2xsiRI2u+bteuHUutGe7evYuwsDC0bNkSaWlpaNWq1TOdp1+/frC3t8epU6cQEBCg55REZAkMXny/30D0scd7qT1NZbUOS5Oz0NfTVW/3adRqNW7evNngSK24uBgdO3asNTLr0aMHRo4cWfM1S02/zp07h0mTJmHGjBn47LPPIJXWnYDeVBKJBNOnT8fGjRtZfERUL4MXX30biDaVSqNt8gaiVVVVjY7UHjx4gI4dO9YaqXXv3h3Dhw+v+bp9+/YsNSNKSkrCn/70J8TGxiIsLEwv53z77bcxZMgQrFy5Era2fHCZiGoz6E+FxjYQbczjDURvPyiD6uG9Bkdq9+/frzNS8/LywvDhw2uN1J5nNEH6o9VqsWTJEmzevBmHDx+Gr6+v3s7dvXt3vPjiizhy5AhGjx6tt/MSkWUwaPE1tIFo4fa/P1pn8Veth89Ey1der3OcSlWJnuNmwuWX9FojtW7dumHYsGG1RmosNfPw8OFDTJ8+HRUVFUhPT4e7u7veP2PGjBlITExk8RFRHQZ9qnNB0jnsOn+zzusFsbPgFvJug/f4nvTmKy/gy6n99B2PRJCVlYWJEydizJgxWLFiBezsDLNV0K1bt9CrVy/cvHkTjo6OBvkMIjJPBr2ZVaLS6OU8pXo6D4nrm2++QVBQED788EOsXr3aYKUHAB07dsSrr76Kffv2GewziMg8GbT4XGT6uZLKDUTNmyAI+PzzzxEVFYXdu3dj9uzZRvncx093EhE9yaD3+Hw6uMDB9na9G4gWbvus1jw+WZdX0O6tJXWO4wai5q28vByzZ8/G1atXkZ6eDg8PD6N99uTJk7FgwQI8ePAArVu3NtrnEpFpM+g9vvo2EG0ubiBqvvLy8vDmm2/C19cXa9euhUwmM3qG0NBQjB071mijTCIyfQa91NnW2QHDerjjmVeO0unwqocjS88MHTt2DIGBgfjDH/6A9evXi1J6wKPLnYmJiaJ8NhGZJoPP1J4X7AWZ7bNNM7CVAof/byFiYmLAbQPNgyAIiImJwZQpU5CQkIAFCxaIumZmSEgIzp8/j19++UW0DERkWgxefL6dXLE4xAeOds37KEc7G3wyoQ+O705EQkICxowZg4KCp88LJPGp1WpERUVhzZo1OHHiBEaNGiV2JMhkMrz55ptISkoSOwoRmQijrM0VHtAFi0N6wtFO2uhlT4kEcLST1uya3aNHD6SmpmLYsGHw8/PDxo0bOfozQbdv38aIESNQVFSEkydPolu3bmJHqsGnO4noSUbdj6+hDUQf78c33Nv9qRuInj17FhEREejduzfWrFkDNzc3Y0WnBpw+fRqTJ09GZGQklixZYnJrnWq1WnTq1AlHjx6Ft7e32HGISGSi7MBe3waiPh1bItSv8R3YVSoVFi9ejM2bNyMuLq7BjUrJ8BISEvD+++8jLi4Ob775pthxnuq9996Di4sLPv30U7GjEJHIRCk+fUhJScHMmTMxevRorFixAs7OzmJHsioajQaLFi3C7t27sXv3bvTu3VvsSA06ffo0pk+fjpycHG5QS2TlTOuaVDMEBwfjwoUL0Gg08PX1xQ8//CB2JKtx//59hISE4NKlS0hPTzf50gOAV199tLXVmTNnRE5CRGIz2+IDABcXF/z73//GypUrERoaio8++ghqtVrsWBbt8uXLGDhwIPr06YPk5GS0adNG7EhN8uQGtURk3cz2Uufv3b17F3PnzsWVK1eQkJCg1/3d6JFdu3YhMjISK1euREREhNhxmi07OxvBwcEoKCjgFlZEVsysR3xPateuHXbs2IH/+Z//wahRo/DFF19Aq322nd+pNp1Oh08//RTz589HcnKyWZYeAHh7e8PDwwMpKSliRyEiEVnMiO9J169fx8yZM1FVVYX4+HiTmlNmbkpLS/HOO+/gzp072L59Ozp06CB2pOeycuVK/PTTT/jPf/4jdhQiEonFjPie9OKLL+Lw4cMIDQ1FQEAAFAoFJ70/gytXriAwMBBubm44cuSI2ZceAEydOhU7d+6ESqUSOwoRicQiiw8AbGxssGDBAhw7dgwKhQLjxo3DrVu3xI5lNg4fPoxBgwYhOjoaCoUCDg6WsVC4h4cH+vXrh+TkZLGjEJFILLb4HuvVqxdOnjyJgQMH4pVXXsGWLVvEjmTSBEHAqlWrEBERgaSkJERHR1vcvDc+3Ulk3SzyHt/TnD59GhEREfDz80NMTAw3J/0dlUqFuXPn4uLFi9i1axdefPFFsSMZxIMHD9ClSxfcuHEDrVq1EjsOERmZxY/4njRgwACcPXsW7u7u6Nu3Lw4ePCh2JJPxyy+/ICgoCCqVCqmpqRZbegDQunVrjBgxAjt37hQ7ChGJwKqKDwCcnJzwf//3f1i3bh3mzJmDefPmoby8XOxYonp8KXjSpEnYvHkzWrRoIXYkg+MGtUTWy+qK77FRo0bh4sWLKC0tRb9+/ZCWliZ2JFH8+9//xsSJE6FQKPDnP//Z4u7nPc348eNx5swZPvBEZIWkn3zyySdihxCLTCbDpEmT8MILL0Aul6O4uBhDhgyxilU9qqursWDBAiiVShw6dAiBgYFiRzIqOzs7ZGZm4v79+wgICBA7DhEZkdWO+J701ltv4fz587hw4QICAgJw+fJlsSMZVGFhIUaPHo2rV6/i1KlTVrtH3YwZM/h0J5EVYvH9qkOHDtizZw/mzZuH4OBgrFixwiKXPDt//jwGDhyIwMBA7NmzB66udTf8tRYjRozA9evXkZubK3YUIjIiq5rO0FRXr17FH/7wB0gkEsTHx6NLly5iR9KLLVu2YN68efjqq68wdepUseOYhHfffRdt27bFxx9/LHYUIjISjvjq0bVrVxw9ehRvvPEGBgwYgP/85z9mveSZTqfD4sWL8eGHH+LgwYMsvSc8nsxuzn++RNQ8HPE14qeffkJ4eDg6d+6MuLg4tG/fXuxIzfLw4UOEh4ejpKQE27Ztg7u7u9iRTIogCOjWrRu2bdsGPz8/seMQkRFwxNeIl19+Genp6ejTpw98fX3NatJzdnY2/P39axbtZunVxQ1qiawPR3zNcPLkScjlcgwaNAirV6826eWuvv32W7zzzjtYunQpIiMjxY5j0jIzMzFq1CjcuHHDKqayEFk7jviaITAwEOfPn0eLFi3Qt29ffPfdd2JHqkMQBPzjH//AnDlzsHPnTpZeE/Ts2RPt2rXD8ePHxY5CREbAEd8zOnDgAGbPno3Q0FB8/vnncHR0FDsSKioqMHv2bOTm5mLnzp3w9PQUO5LZWLZsGXJychAXFyd2FCIyMI74ntGYMWNw8eJF3LlzB35+fjh9+rSoeW7cuIEhQ4bA1tYW33//PUuvmaZNm4YdO3ZArVaLHYWIDIzF9xzatGmDTZs24X//938xfvx4fPrpp6iurjZ6ju+//x7+/v4IDw+HUqk0idGnuenUqRNefvll7N+/X+woRGRgLD49mDZtGs6dO4e0tDQMGjQIWVlZRvlcQRCwZs0ahIWFQalU4v3337eaRaYNgUuYEVkH3uPTI0EQsHbtWixZsgR//etfMX/+fNjYGObvFlVVVZg/fz5SU1Oxe/dueHl5GeRzrElRURG6du2KgoICtGzZUuw4RGQgLD4DyM3NhVwuh6OjI9atW4fOnTs3ePy9MjW2/ViArNslKFFp4CKzhU8HF4T194Sbs0Od4+/cuYO33noL7u7uUCqV/CGtRxMmTEBYWBgiIiLEjkJEBsLiMxCNRoNly5Zh1apVWLFiBcLDw+tchryQX4yYlFwcyykEAKg1upr3ZLY2EAAEe7sjepgXfDs9Wkz6zJkzmDx5MmbNmoWPP/7YYCNKa7V582asX7+e9/qILBiLz8DOnz+PiIgI9OjRA19//XXN6ikb0vKwNDkLKo0WDf0JSCSAzFaKxSE+QG4q3nvvPaxduxaTJ0820u/AupSXl8PDwwPZ2dlmtzwdETUNi88I1Go1Pv74YyQkJODrr79GSbu+WJqcicpqXePf/CupoIXux23Ys3Ih+vTpY8C0FBERAX9/f/zpT38SOwoRGQCLz4iOHz8O+Xt/hWTUe9BJbGu9VxA7C7qKYkDy26XLF6LWwralW83XMlsbbJkbiL6e1ruHnjF8++23+Nvf/oYTJ06IHYWIDIDFZ2Sz16Xhu+zCWgUHPCo+t5B34djllad+r0QCjOnVHl+Hv2romFaturoaHh4eSEtLQ9euXcWOQ0R6xicjjOhemRqpVx/UKb2mEgTgaHYhisq4uogh2dnZISwsDJs2bRI7ChEZAIvPiLb9WPDc55AA2Hb2+c9DDZs+fToSExO5QS2RBbJt/BDSl6zbJbWmLPxe4fa/AzaPtsWRde6Ddm8tqXOMSqND1q1Sg2WkRwYNGoTKykpcvHgRvr6+YschIj1i8RlRiUrT4Pvuby1p8B7fb+cx/nqg1kYikeDtt9/Gxo0bWXxEFoaXOo3IRaafv2fkZl7C+vXrcerUKZSUlOjlnFTX9OnTsWnTJuh0TZ92QkSmjyM+I/Lp4AIH29sNXu5sjK1EQHt7DQ4f/h6rV69GdnY2WrdujZ49e6JXr161fn08WZ6ezcsvvwxXV1f88MMPGDp0qNhxiEhPWHxGFNrfE6sO5zzXOaRSKdYsfAduzlEAAJ1Ohxs3biAjIwOZmZk4c+YMlEolMjMzIZVKa0rwyUL09PTkLg5N9PghFxYfkeXgPD4ji0o4g0OZdxpcpuxpmjOPTxAE3Llzp6YQH/+amZmJ8vJy+Pj41CrDnj17omvXrpBKpc/wu7Jc169fR//+/XHz5k3Y29uLHYeI9IDFZ2QX8osxLS4NldXaZn+vo50USVEBz71yy4MHD2pK8MlCvH37Nrp3715nlNi9e3c4ONTdJcJaDB06FIsWLcL48ePFjkJEesDiE8GjBaqbt1ano50NFof0RHhAF4PlKi8vR3Z2dq0yzMjIQF5eHjp37lznHqKPjw+cnZ0NlsdUrFmzBsePH+cmtUQWgsUnkmfZncGQpdeQqqoq5Obm1inEnJwcuLu717mH2LNnT7i5uTV+YjNx7949eHl5oaCgwCqKnsjSsfhEdLGgGLEpuTiaXQgJHk1Of+zxfnzDvd0RHexlkgtTa7Va5OXl1XvZVCaT1SnDXr16oWPHjmb5YM24ceMwY8YMTJ8+XewoRPScWHwmoKhMjW1nC5B1qxQlqmq4yOzg07ElQv3q34Hd1AmCgJs3b9YpxIyMDFRVVdUU4ZPF2KVLF5PeVDcxMRHKpJ2Y9D//QNbtEpSoNHCR2cKngwvC+pvnnxORtWLxkVEVFRXVGR1mZGTg3r178Pb2rjNK9PLyEv1pygv5xVj9XRYOX74FBwcHVGl/+1/m8cg82Nsd0cO84NvJ9EbmRFQbi49MQllZGbKysuoUYn5+Prp06VJngr63tzecnJwMnsuc7sUSUdOw+MikqdVq5OTk1Lls+vPPP6NDhw71TtB3ddXPqKu+p2/LM46h5PRuVN+7DomdDLat2sO5z0g49wuBRCIxytO3RPR8WHxkljQaDa5du1bnsmlmZiZatmxZ75Om7du3b/KDNfXNtyw5tQMPT+1Am9F/hONLfpDYO6L6zlU8TN+BtiELILG1A6C/+ZZEZBgsPrIogiCgoKCg3vuIOp2u3kLs3LlznQdrfr/Cjk5VjoIYOdzGvY8WPoMbzNCcFXaIyPi4VidZFIlEgk6dOqFTp04YPXp0rfcKCwtrFeK3336LzMxMFBcXw9vb+7e1TL164mi2Q617euqbWRA01XDqEdBoBkEAjmYXoqhMzac9iUwQi4+shru7O9zd3REUFFTr9YcPHyIrK6tmdLgn+UdUu/cHbH97mlRbUQIbJxdIbH5by/R2wgeoupcPaKvRbspnkHV+ueY9CYBtZwswN6ibwX9fRNQ8LD6yeq1atYK/vz/8/f0BAAuSzmHX+Zu1jpE6toSuogSCTltTfh0ilgMACmLeAYTay8+pNDpk3So1Qnoiai7TnTFMJJISlabOaw4ePpDY2qEiJ60Z56nWZywi0hOO+Ih+x0VW938LG5kzWg1+G/cPrgEg/PpUpwzVd/MgVKmech47AyclomfB4iP6HZ8OLnCwvQ21pvbly1YBoZC2dEPJqe0o2rcKEjsH2Lp2gOvwmXDw7FnrWJmtDXw6tjRmbCJqIk5nIPqde2VqDP7HkTrF1xwOtjY4sWgEn+okMkG8x0f0O22dHTCshzuedRMJieTRrhosPSLTxOIjqse8YC/IbKWNH1gPma0U0cFeek5ERPrC4iOqh28nVywO8YGjXfP+F3m0VqcPlysjMmF8uIXoKR4vNM3dGYgsCx9uIWrExYJixKbk4mh2ISR4NDn9scf78Q33dkd0sBdHekRmgMVH1ERFZWpsO1uArFulKFFVw0VmB5+OLRHqxx3YicwJi4+IiKwKH24hIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKrwuIjIiKr8v8BzH1QwpZRsoEAAAAASUVORK5CYII=\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"import networkx as nx\n",
"%matplotlib inline\n",
"def create_example_graph():\n",
" graph = nx.Graph()\n",
" graph.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'),\n",
" ('B', 'D'), ('D', 'E'), ('D', 'F'),\n",
" ('D', 'G'), ('E', 'F'), ('G', 'F')])\n",
" return graph\n",
"\n",
"graph = create_example_graph()\n",
"nx.draw(graph, with_labels=True)"
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{('A', 'B'): 5.0,\n",
" ('A', 'C'): 1.0,\n",
" ('B', 'C'): 5.0,\n",
" ('B', 'D'): 12.0,\n",
" ('D', 'E'): 4.5,\n",
" ('D', 'F'): 4.0,\n",
" ('D', 'G'): 4.5,\n",
" ('E', 'F'): 1.5,\n",
" ('F', 'G'): 1.5}"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# We'll use networkx's built-in betweenness computation in this example.\n",
"nx.edge_betweenness_centrality(graph, normalized=False)\n",
"# nx.edge_betweenness_centrality(graph, normalized=True)\n",
"# normalized between 0-1"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"** How to compute shortest path in undirected graph? **\n",
"\n",
"<br><br><br>\n",
"<img src=\"https://upload.wikimedia.org/wikipedia/commons/4/46/Animated_BFS.gif\">\n",
"\n",
"[source](https://en.wikipedia.org/wiki/File:Animated_BFS.gif)\n",
"\n",
"** Breadth first search: ** Given a sourse node $s$, compute the shortest paths to each of its neighbors. Proceed"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"deque([1])\n",
"deque([1, 2])\n",
"deque([1, 2, 3])\n",
"popleft returns: 1\n",
"deque([2, 3])\n",
"pop returns: 3\n",
"deque([2])\n"
]
}
],
"source": [
"from collections import deque\n",
"# double ended queue\n",
"# stored as a doubly linked list\n",
"\n",
"q = deque()\n",
"q.append(1)\n",
"print(q)\n",
"q.append(2)\n",
"print(q)\n",
"q.append(3)\n",
"print(q)\n",
"print('popleft returns: %d' % q.popleft())\n",
"print(q)\n",
"print('pop returns: %d' % q.pop())\n",
"print(q)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"1\n"
]
},
{
"data": {
"text/plain": [
"[2, 3]"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# compare with:\n",
"a = [1,2,3]\n",
"print(a.pop(0))\n",
"#print(a.pop())\n",
"a"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**What is running time to remove first element of a dynamic array with $n$ elements (a list in Python)?**\n",
"\n",
"<br><br><br>\n",
"\n",
"$O(n)$: Need to shift all elements to the left.\n",
"\n",
"<br><br><br>\n",
"\n",
"**What is the running time to remove first element of a doubly linked list $n$ elements (a deque in Python)?**\n",
"\n",
"<br><br><br>\n",
"\n",
"$O(1)$\n",
"\n",
"See more:\n",
"https://wiki.python.org/moin/TimeComplexity\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[1, 2, 3]\n",
"1\n",
"2\n"
]
}
],
"source": [
"# Sample implementation of doubly linked list.\n",
"\n",
"class Node:\n",
" def __init__(self, val):\n",
" self.val = val\n",
" self.prev = None # previous node\n",
" self.next = None # next node\n",
" self.head = self\n",
" \n",
" def display(self):\n",
" node = self.head\n",
" vals = []\n",
" while node:\n",
" vals.append(node.val)\n",
" node = node.next\n",
" print(vals)\n",
" \n",
" def popleft(self):\n",
" \"\"\"\n",
" Remove leftmost element of list.\n",
" \"\"\"\n",
" v = self.head.val\n",
" self.next.prev = None\n",
" self.head = self.next\n",
" return v\n",
" \n",
"n1 = Node(1)\n",
"n2 = Node(2)\n",
"n3 = Node(3)\n",
"n1.next = n2\n",
"n2.prev = n1\n",
"n2.next = n3\n",
"n3.prev = n2\n",
"\n",
"mylist = n1\n",
"mylist.display() \n",
"print(mylist.popleft())\n",
"print(mylist.popleft())"
]
},
{
"cell_type": "code",
"execution_count": 17,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['B', 'C']"
]
},
"execution_count": 17,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# to get the neighbors of a node:\n",
"list(graph.neighbors('A'))\n",
"# vs\n",
"#graph.neighbors('A')"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDMuMC4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvOIA7rQAAIABJREFUeJzt3XtczffjB/DXOZ3qlBRrISqFyP2WRhpiueSemGs42dw2xPbz3fjuyne2ucwtRhcRE7kMqzZEzOXr1hgrFVHNLSlJnXQ65/eHad9WKJ1zPufyej4eHo+vzulzXvnaeXm/z+f9fotUKpUKRERERkIsdAAiIiJtYvEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRYfEREZFRkQgdwNDdLyhG9PksJN/JR75cAWupBG4NrDGyswNsrcyFjkdEZHREPIFdMy5m5mHt0TQkpGQDAIoVyrLHpBIxVAB6tbDDjJ7N0N6xjkApiYiMD4tPAyJP38DimGTIFaV40Z+uSARIJSZY4OuG8V2dtZaPiMiYcapTzZ6WXhKKSpQvfa5KBRSVlGJxTBIAsPyIiLSAIz41upiZh9EbT6OopLTc17OCZVAW5gGiv+8lsmrbB6/1nV72ewtTE0S92xXtHDjtSUSkSRzxqdHao2mQK0orfczO/xNYOHd47vfKFaUIPpqG9ePdNRWPiIjA5Qxqc7+gGAkp2S/8TO9FVCrgyNVs5BQUqzcYERGVw+JTk+jzWTW+hghA9IWaX4eIiJ6PU51qknwnv9yShX/K3rUIEJuU/b6u92TU7tC/3HPkCiWSbz/SWEYiImLxqU2+XPHCx+1GLHzhZ3x/X6dEXZGIiKgSnOpUE2upev4NYS01Vct1iIiociw+NXFrYA1zSc3+OKUSMdzsa6spERERVYZTnWri39kBKw6lPPfx7Ogvyq3jkzp3QL0RC8s9RwXAv5ODpiISERFYfGrzupU5eja3w8GkuxWWNDjMCHvp94tEgHcLO25cTUSkYZzqVKOZvZpBKjF5+RMrIZWYYEavZmpORERE/8TiU6P2jnWwwNcN0mp+1mdhKsYCXzduV0ZEpAUsPjV7u3MjWF6NhQlKIRK9+LkiPN2jc4FvS25QTUSkJSw+Nfvoo49QLz8F0dO90K9VfZhLxBVGgFKJGCZQom5hBqLe7crSIyLSIp7OoEY7d+7E//3f/+HcuXOwtbUFAOQUFCP6QhaSbz9CvrwE1lJTuNnXRl9XG3Ru3Ry//fYbnJycBE5ORGQ8WHxqkpSUhB49euDnn39Gp06dqvQ9c+fOhVgsxtKlSzWcjoiInmHxqUF+fj48PDwwf/58TJ48ucrfd/PmTXTq1AnXr1+HjY2NBhMSEdEz/IyvhlQqFWQyGXr27Fmt0gOAxo0bo2/fvggJCdFQOiIi+ieO+Gpo6dKl2LFjB44fPw5z8+ovPj937hz8/Pxw7do1mJpyn04iIk3jiK8Gjhw5gqVLlyI6OvqVSg8A3N3d4eLigujoaDWnIyKiyrD4XlFWVhbGjh2LyMjIGt+V+cEHH2Dp0qXg4JuISPNYfK+guLgY/v7+mD17Nt56660aX2/gwIF4/PgxEhIS1JCOiIhehJ/xvYKZM2fi1q1b2L17N0Qv256lijZs2IB9+/bhwIEDarkeERFVjsVXTZs3b8aiRYtw9uxZtS5BKCoqgrOzM44ePYqWLVuq7bpERFQei68afvvtN/j4+ODIkSNo06aN2q//2Wef4datW9iwYYPar01ERE+x+KooNzcX7u7uWLRoEcaMGaOR17h37x5atGiB5ORk1K9fXyOvQURk7HhzSxUolUpMmDABgwcP1ljpAUC9evUwatQoBAcHa+w1iIiMHUd8VfDFF1/g4MGDiI+P1/gi8+TkZPTo0QM3btyApaWlRl+LiMgYccT3ErGxsfj++++xY8cOreys4ubmhq5du2Lz5s0afy0iImPEEd8LpKeno2vXrti1axe8vLy09roJCQl45513kJycDLGY/zYhIlInvqs+R1FREUaMGIGPP/5Yq6UHAD169IC1tTX279+v1dclIjIGHPFV4tmJC3K5HNu2bVPbIvXq2L59O4KDg3Hs2DGtvzYRkSHjiK8SGzduxNmzZ7Fx40ZBSg8A/P39cfPmTZw5c0aQ1yciMlQc8f3DmTNnMGjQIPz6669o3ry5oFlWrFiB06dPIyoqStAcRESGhMX3P7Kzs+Hu7o5Vq1Zh6NChQsdBfn4+XFxccP78eTg7Owsdh4jIIHCq8y8KhQJjxozBuHHjdKL0AMDa2hoymQwrV64UOgoRkcHgiO8vH330Ec6dO4e4uDiYmJgIHadMZmYm2rdvj+vXr6NOnTpCxyEi0nsc8QHYs2cPtm3bhm3btulU6QGAo6MjfH19uXE1EZGaGP2ILyUlBV5eXjhw4AA8PDyEjlOpxMREDB48GNevX4eZmZnQcYiI9JpRj/gKCgrg5+eHRYsW6WzpAUDHjh3RokUL3t1JRKQGRjviU6lUGDNmDCwtLREaGirYer2qiomJwccff4zExESdz0pEpMuMdsS3atUqpKamYu3atXpRJP3790dJSQkOHz4sdBQiIr1mlCO+48ePY+TIkTh9+rRerY8LDQ1FdHQ0YmNjhY5CRKS3jK74bt++DXd3d4SGhqJ///5Cx6kWuVwOZ2dnHDp0CG3atBE6DhGRXjKqqc6SkhKMHDkS06ZN07vSAwCpVIr33nsPy5cvFzoKEZHeMqoR35w5c5CWloZ9+/bp7Tl3OTk5aNasGf744w/Y29sLHYeISO/o57v/K/jhhx9w4MABbNmyRW9LDwBsbW0xZswYrFmzRugoRER6yShGfJcvX4a3tzcOHTqE9u3bCx2nxlJTU+Hp6YkbN26gVq1aQschItIr+jv0qaKHDx/Cz88PK1asMIjSAwBXV1d4eXlh06ZNQkchItI7Bj3iUyqV8PPzg4ODg8FNDf7666+YOHEiUlJSdG5/USIiXWbQI76vv/4ad+/eNci7ILt37w47Ozv8+OOPQkchItIrBlt8Bw8exOrVq7Fz506D3NhZJBJh3rx5WLZsmdBRiIj0ikEWX0ZGBiZMmIBt27bBwcFB6DgaM3z4cNy+fRunTp0SOgoRkd4wuOKTy+UYMWIEPvjgA/Tq1UvoOBolkUgwZ84cjvqIiKrB4G5umTp1Kh48eIAdO3boxebTNVVQUABnZ2f897//RdOmTYWOQ0Sk8wxqxBcWFoZjx44hLCzMKEoPAKysrPDOO+/gu+++EzoKEZFeMJgR34ULF9C/f38kJCSgZcuWQsfRqlu3bqF169a4du0aXnvtNaHjEBHpNIMY8eXk5GDEiBEIDg42utIDgIYNG2LIkCFYv3690FGIiHSe3o/4SktLMXDgQLRt2xbffvut0HEEc+nSJfTv3x/p6ekwNzcXOg4Rkc7S+xHf559/juLiYnz11VdCRxFUu3bt0KZNG/zwww9CRyEi0ml6PeI7cOAApk+fjnPnzqF+/fpCxxHcL7/8gnnz5uHSpUtGc3MPEVF16e2ILy0tDTKZDDt27GDp/cXHxwcikQi//PKL0FGIiHSWXhZfYWEhRowYgc8++wzdunUTOo7OEIlEmDt3Lhe0ExG9gN5NdapUKgQEBEAkEiEiIoJTev9QXFwMFxcXxMbGGswxTERE6qR3I75169bh0qVLWL9+PUuvEubm5nj//fcN8kQKIiJ10KsR36lTpzBs2DCcPHmS23O9wIMHD9C0aVNcvnwZjRo1EjoOEZFO0Zniu19QjOjzWUi+k498uQLWUgncGlhjZGcH2FqZ4+7du3B3d8e6deswaNAgoePqvFmzZsHS0hJLliwROgoRkU4RvPguZuZh7dE0JKRkAwCKFcqyx6QSMVQAeri+jstRy9DXvQU+//xzgZLql+vXr8PDwwPp6emoXbu20HGIiHSGoMUXefoGFsckQ64oxQtTqFQQKRX4fFh7BHi6aC2fvvP398ebb76J2bNnCx2FiEhnCFZ8T0svCUUlypc/+S8WpmIs8G2J8V2dNRfMgJw+fRpjxoxBamoqJBKJ0HGIiHSCIMV3MTMPozeeRlFJabmvZwXLoCzMA0R/32za8N3vIaltW/Z7C1MTRL3bFe0c6mgtrz7r3r075syZg5EjRwodhYhIJwgyDFh7NA1yRWmlj9n5fwIL5w7P/V65ohTBR9Owfry7puIZlA8++ABLliyBv78/l38QEUGAdXz3C4qRkJL94s/0XkClAo5czUZOQbF6gxmoIUOGICcnBydOnBA6ChGRTtB68UWfz6rxNUQAoi/U/DrGwMTEBEFBQVi6dKnQUYiIdILWpzqT7+SXW7LwT9m7FgFiEwCA1Kkt6o1YWOE5coUSybcfaSyjoZk0aRI+++wzpKamwtXVVeg4RESC0nrx5csVL3zcbsTCF37G9/d1StQVyeDVqlULU6dOxYoVKxAcHCx0HCIiQWl9qtNaqp6utZaaquU6xuK9997DDz/8gPv37wsdhYhIUFovPrcG1jCX1OxlpRIx3Oy5G0l1NGjQAH5+fli3bp3QUYiIBKX14vPv7FDjaxTJ5fjjp3AkJyerIZHxmDt3LtauXQu5XC50FCIiwWi9+F63MkfP5naobEmZw4ywl36+JxIBXk3qQooSeHt7w9PTEyEhIcjPz9dQYsPRunVrdOrUCZGRkUJHISISjCDn8c3s1QxSickrfa9UYoL5gzvg66+/RmZmJj7++GPExMTAyckJkyZNwrFjx6AjB07opHnz5mH58uVQKqu+VRwRkSERpPjaO9bBAl83WJhW7+Wf7tXpVrZdmUQiwaBBg7B7926kpKSgXbt2mDFjBlxdXbF48WJkZXGt3z/17t0bZmZmiI2NFToKEZEg9OJ0BpHo6Uhvga/bSzeoVqlUOHfuHMLCwhAVFQUPDw/IZDIMHToU5ubm6v0B9FRkZCTCwsIQHx8vdBQiIq0T/Dy+S1l5CD6ahiNXs6FUKvG/hzU8O4/Pu4UdZvRqVu2NqQsLC7Fnzx6Eh4fjt99+w9ixYzF58mR07NhRvT+EnikpKYGLiwv27duHTp06CR2HiEirBC++Z3IKivH5lp9x7OI1dO7mBWupKdzsa8O/09MT2GsqPT0dERERCA8Px2uvvQaZTIaxY8fC1tb25d9sgL755htcvHgRW7duFToKEZFW6UzxAUBERATi4+MRERGhsddQKpU4cuQIwsLC8NNPP6Fv376QyWTw8fGBicmr3XCjj/Ly8tCkSRNcvHgRjo6OQschItIaQW5ueZ68vDzUqaPZc/bEYjH69OmDrVu3Ij09Hd7e3vjkk0/QuHFjLFy4EGlpaRp9fV1Rp04dTJw4EatWrRI6ChGRVulU8eXm5mq8+P5X3bp1MX36dJw5cwaxsbEoLCyEp6cnevbsiYiICDx+/FhrWYQwe/ZshIWFcQ0kERkVnSo+bYz4nqdt27ZYvnw5srKyMGfOHERHR8PBwQFTpkzByZMnDXJtoLOzM3x8fBASEiJ0FCIirdG54qtbt66gGczMzDB8+HDs378fV65cgaurK2QyGVq2bImvv/4at2/fFjSfus2bNw/fffcdSkp42gURGQedKj5tT3W+TMOGDTF//nwkJSUhLCwMqampaNWqFQYPHow9e/bgyZMnQkessS5dusDFxQXR0dFCRyEi0gqdKj4hpzpfRCQSle0JmpmZCX9/f3z33XdwdHTE3LlzcfnyZaEj1si8efOwdOlSg5zOJSL6J50rPqGnOl/GysoKEydOREJCAn799VdYWFigf//+8PDwwLp165CXlyd0xGobNGgQCgoKkJCQIHQUIiKN06ni07Wpzpd5tifozZs38cUXX+DIkSNwdnbGuHHjcPjwYb3ZCFosFmPu3LlYtmyZ0FGIiDROpxawW1tbIzMzEzY2NkJHeWX379/Htm3bEBYWhry8PEyaNAmTJk2Cs7Oz0NFeqKioCM7OzkhISICbm5vQcYiINEZnik+hUEAqleLJkycQi3VqIPrKEhMTERYWhh9++AEdOnTA5MmT4efnBwsLC6GjVerTTz/F7du3sWHDBqGjEBFpjM4UX05ODlxdXfHgwQOho6idXC7Hvn37EBYWhjNnzuDtt9+GTCaDu7s7RJWdyCuQe/fuoUWLFrh69Srq1asndBwiIo3QmaGVrt7RqQ5SqRSjRo1CXFwcLl68CAcHB4wePbps0fy9e/eEjggAqFevHkaOHIm1a9cKHYWISGN0qvh0/Y5OdXB0dMSCBQuQmpqKtWvX4uLFi2jevDn8/Pywf/9+KBQKQfPNnTsX69atQ1FRkaA5iIg0RWeKT9/u6KwpsVhctidoRkYGfH198dVXX8HR0RHz589HcnKyILnc3NzwxhtvYPPmzYK8PhGRpulM8RnyVOfLWFtbl+0JGh8fD5VKBW9v77JF89reRHrevHlYvny53izHICKqDp0qPmOY6nyZli1b4ptvvkFGRgY++ugj/PTTT3BycipbNK+Ne5F69uyJ2rVr48CBAxp/LSIibdOZ4jO2qc6XMTU1LdsTNCUlBe3bt8eMGTPKFs1nZWVp7LVFIhHmzZvHBe1EZJB0pviMearzZerVq1e2J+i2bduQmZmJdu3aoX///tixYweKi4vV/pr+/v5IT0/H2bNn1X5tIiIh6Uzx5ebmcqrzJUQiETw8PLB+/XpkZWVhwoQJ+P7779GoUSO8//77SExMVNtrmZqaYs6cORz1EZHB0Zni44iveiwtLcv2BD179ixsbW0xbNgwdOzYEatXr0ZOTk6NX2PKlCk4ePAgbty4UfPAREQ6Qmd2bvH19cXMmTMxcOBAoaPoLaVSifj4eISFhSEmJgZ9+/aFTCaDj48PTExMXumaH374IRQKBRZ8uQTR57OQfCcf+XIFrKUSuDWwxsjODrC1MlfzT0JEpDk6U3zdunXDsmXL4OnpKXQUg5Cbm4vt27cjLCwMt2/fxsSJEzF58mQ0a9asWtf55dxVTF66HbWadYFIJEKx4u8lDlKJGCoAvVrYYUbPZmjvyBE7Eek+TnUaqLp162L69Ok4e/YsYmNjUVRUBE9Pz7JF848fP37pNSJP38Dsfekwde6EJ6WqcqUHAHKFEsUKJX754y5GbzyNyNM3NPTTEBGpj86M+Ozt7XH+/Hk0bNhQ6CgG68mTJzhw4ADCwsJw4sQJjBgxAjKZDN26dauwWXbk6RtYHJOEopKqL2K3MBVjgW9LjO/qrObkRETqozPFJ5VKkZubq7NH9hiaW7duYcuWLQgLC4NIJMLkyZMREBAAe3t7XMzMw+iNp1FUUgoAyAqWQVmYB4hNAJEYZq87olab3rDq0B8iUflJAwtTE0S92xXtHDh6JyLdpBPFJ5fLYWNjA7lcrlPH9BgDlUqFkydPIjw8HLt27YKXlxdUXu/gykMTPPubkRUsg63vLFg4d4BS/hjyzMt4cGgDpE5t8frAOeWuJxIB/VrVx/rx7gL8NEREL6cTn/E9+3yPpad9IpEI3bt3R0hICDIzM9FvqD8uP1Dhef8cEktrwdL1DdgN/T88/v0wnmTfKPe4SgUcuZqNnAL1L6onIlIHnSg+Ll7XDVZWVpC4esHczOylzzVv2AIm1q+jOPOPCo+JAERf0NyWakRENaETxcc7OnVH8p38CndvPo+J1WtQyh9V+LpcoUTy7YpfJyLSBSw+KidfXvWDcEsf5UAsrf2c65SoKxIRkVrpRPFxqlN3WEslVXpe8e0UlD7KgblDq+dcx1SdsYiI1KZq73IaxhGf7nBrUBumIqDkOTe3KIsLIc+8jNxDG1CrdS+Y1XOu8BwzExHc7CsfCRIRCY3FRwCAoqIiREZGYlXwRpT4fAyYlB+xZUd/8dc6PhFMbR1h3WUYrDoOqPRaxcXFCP9kGkwDxmDUqFGwsrLSxo9ARFQlOlF8ubm5sLOzEzqGUbpz5w7Wrl2LDRs2oEuXLli99CtE3bLBwaS7ZUsaHGaEVfl6IhHQt50DBveYhZCQEMybNw8jRozAlClT8MYbb3DJChEJTic+4+OIT/t+++03TJw4ES1btkROTg6OHTuGAwcOoE+fPpjZqxmkklc7zUEqMcF73q4YPHgwfvzxR/zxxx9wdXVFQEAA2rRpg+XLlyM7O1vNPw0RUdWx+IyIUqnE/v374e3tjUGDBqFly5a4du0agoOD0aJFi7LntXesgwW+brAwrd5fj6d7dbqV267M3t4e8+fPx9WrV7F+/XpcunQJrq6u8Pf3R1xcHEpLS9X28xERVYVObFn21ltvYf78+fDx8RE6ikEqKChAREQEVq5cCRsbGwQFBWHkyJEwNX3xnZdPN6pOhlxR+tydXICn05tSiQkW+LpVaYPqhw8fYvv27QgNDcWdO3cwadIkTJ48GS4uLtX8yYiIqo8jPgOWmZmJ+fPnw9nZueyA2jNnzmDs2LEvLT0AGN/VGVHvdkW/VvVhLhFDKin/10UqEcNcIka/VvUR9W7XKp/KYGNjg6lTp+LMmTM4cOAAHj58CA8PD7z11lvYvn075HL5q/y4RERVohMjvmbNmiE2Nhaurq5CRzEIZ86cwYoVK/Dzzz8jICAAs2bNQpMmTWp0zZyCYkRfyELy7UfIl5fAWmoKN/va8O+knhPY5XI5fvzxR4SGhuLChQsYO3YsAgMD0b59+xpfm4jof+lE8dna2uLq1at4/fXXhY6itxQKBfbu3YsVK1bgzz//xKxZsxAYGAgbGxuho1XbjRs3EB4ejvDwcNSvXx+BgYEYM2aMXv4sRKR7BC8+lUoFU1NTFBUVVWn6jcp7+PAhQkNDsWrVKjRq1AhBQUEYNmwYJBKdWKlSI6WlpTh06BBCQ0Nx8OBBDB48GIGBgejRoweXRRDRKxO8+B49egR7e3sUFBQIGUPvXL9+HatWrcLmzZvRr18/BAUFwcPDQ+hYGpOdnY3IyEiEhobiyZMnkMlkmDhxIuzt7YWORkR6RvCbW7hPZ9WpVCocP34cfn5+8PDwgLm5OS5evIgffvjBoEsPAOzs7BAUFITff/8dW7ZswfXr19GqVSsMGTIE+/btg0JR9c21ici4CT7iu3TpEsaNG4fff/9dyBg6raSkBDt27MB3332HvLw8zJkzBxMnTjT6rcAKCgqwc+dOhIaG4vr16wgICIBMJkPz5s2FjkZEOkzwER+XMjzfgwcPsGTJEri4uCA0NBSffPIJrl69ipkzZxp96QFPD86dPHkyfv31V8THx6O0tBQ9evRAjx49EBERgcePHwsdkYh0kODFx6nOiq5evYoZM2agadOmSEpKwoEDBxAfH4/BgwdDLBb8/zKd5Obmhm+//RaZmZkICgrCzp074ejoiGnTpuHs2bPQgZuXiUhHCP4uyhHfUyqVCocPH8agQYPw5ptvwtbWFn/88QciIiLQoUMHoePpDVNTUwwfPhwHDhzA77//DkdHR4wePRrt27fHypUrkZOTI3REIhIYi09gxcXFCA8PR4cOHTBr1iwMHToUN2/exJdffsk7FmuoUaNGWLBgAVJTU7Fy5UqcPXsWTZs2xejRo3Hw4EEolUqhIxKRAARf7GWsU5337t3DunXrsG7dOnTo0AHffPMN+vbty/VpGiAWi+Ht7Q1vb2/k5uZi27ZtmD9/Ph48eACZTIZJkybByclJ6JhEpCUc8WnZ5cuXERgYiBYtWuDPP/9EfHw84uLi0K9fP5aeFtStWxczZ87EhQsXsGfPHty7dw8dO3ZE//79sXPnThQXFwsdkYg0jMWnBUqlErGxsfDx8UHfvn3h4uKClJQUbNiwAa1atRI6ntHq2LEj1qxZg6ysLEyYMAHr1q2Do6Mj5s6diytXrggdj4g0RPDiM+SpzsLCQnz//fdo3bo1Pv74Y0yYMAHp6elYuHAhT5zXIRYWFhg3bhzi4+Nx6tQpWFhYoG/fvujatSs2btyIR48eCR2RiNRI8OIzxBHfrVu3sGDBAjg7OyMmJgbr1q3DhQsXEBAQAHPzmp9kQJrTtGlTLF68GDdv3sS///1vxMbGwsnJCTKZDCdOnOCyCCIDwOJTowsXLmDChAlo3bo1Hj58iBMnTuDHH39Er169+PmdnpFIJBg4cCB2796N5ORktGzZEoGBgWjVqhW+/fZb3L17V+iIRPSKBC8+fZ/qLC0txd69e9GzZ08MHToUbdu2xfXr17FmzRqeL2gg6tevjw8//BBJSUkICQlBUlIS3Nzc4Ofnh59++on7hBLpGcH36rS2tkZmZqbenbX26NEjhIeHY9WqVbC1tUVQUBBGjBjBo5WMRH5+PqKiohAaGoqsrCxMnDgRMpkMTZs2FToaEb2EoMWnUCgglUrx5MkTvdmK6+bNm1i9ejXCw8PRu3dvBAUFoVu3bpzKNGJXrlxBaGgoIiMj0aZNGwQGBsLPzw8WFhZCRyOiSgjaNg8fPoS1tbVelN6pU6cwatQodOrUCSqVCufPn8fOnTvh6enJ0jNyrVu3xvLly5GZmYnp06djy5YtcHBwwHvvvYfExESh4xHRPwjaOLp+Y4tCocCOHTvQrVs3jBs3Dt27d0d6ejqWLVsGZ2dnoeORjjE3N8fIkSMRFxeHxMRE1KtXD8OHD0enTp2wdu1a5ObmCh2RiCDwVOf58+fxzjvv4MKFC0JFqFReXh5CQkKwevVqNG7cGEFBQRgyZAhMTEyEjkZ6RqlU4vDhwwgNDUVcXBwGDhyIKVOmoGfPnnox00FkiAT9L0/X7ui8du0aZs2ahSZNmiAxMRG7du3CsWPHMHz4cJYevRKxWAwfHx9s374d165dwxtvvIHZs2fD1dUVixcvxp9//il0RCKjY/RTnSqVCgkJCRg2bBi6du2KWrVq4ffff8fWrVvh7u4uaDYyLLa2tpg1axYuXryI7du3IzMzE23btsWgQYOwZ88elJSUCB2RyCgIPuITqviePHmCLVu2oHPnznj33XfRr18/3LhxA1999RUaNWokSCYyDiKRCF26dMH69euRlZWFUaNGYcWKFXB0dMSHH36I5ORkoSMSGTTBR3zanuq8f/8+Fi9eDBcomglAAAAXbklEQVQXF0RERODLL79EUlISpk+fjlq1amk1C5GlpSUCAgJw7NgxHDt2DCYmJvD29oaXlxfCw8NRUFAgdEQigyN48WlrxJeUlISpU6fC1dUV165dQ2xsLA4dOoSBAwfyJgPSCc2bN8eSJUuQkZGBDz/8EHv27IGjoyPeeecdnD59mvuEEqmJQU91qlQqHDx4EL6+vvD29oa9vT2Sk5MRFhaGdu3aaex1iWrC1NQUQ4cOxb59+3DlyhU0bdoUEyZMQNu2bbFixQrcv39f6IhEek3wEZ8mpjrlcjlCQ0PRrl07zJ07F/7+/rhx4wY+++wz1K9fX+2vR6QpDRs2xL/+9S+kpKRg7dq1SExMRLNmzTBy5Ej8/PPPKC0tFToikd4RvPjUOeK7e/cuPv30UzRu3Bi7d+/GihUrcOnSJchkMkilUrW9DpG2iUQi9OzZE5s3b8bNmzfRp08fLFiwAC4uLvj0009x48YNoSMS6Q2tF9/9gmKsT7iGOVGJuNbIB9vSTbE+4RpyCopf+ZqXLl3C5MmT4ebmhrt37yIhIQE//fQT3nrrLW4nRgbHxsYG06ZNw7lz57B//37k5ubC3d0dPj4+iIqKQnHxq/+3RGQMtLZzy8XMPKw9moaElGwAQLFCWfaYVCKGCkCvFnaY0bMZ2ju+fBSoVCoRExODFStWIDk5GTNnzsTUqVNha2urqR+BSGfJ5XLs2bMHoaGhuHjxIsaOHYvAwEB+lk1UCa0UX+TpG1gckwy5ohQvejWRCJBKTLDA1w3juzpX+pzHjx8jIiICK1euhJWVFYKCgjBq1CiYmZlpJjyRnklPT0d4eDjCw8PRoEEDTJkyBaNHj9a7o7+INEXjxfe09JJQVKJ8+ZP/YmEqxgLfluXKLysrC2vWrEFoaCi8vLwQFBSEN998k1OZRM9RWlqKX375BaGhoTh06BCGDh2KwMBA/ndDRk+jxXcxMw+jN55GUUn5O88e/5GA/LM/ouT+TYhMpZDY1IdV2z6w6uhb9h+khakJot7tiuLbqVixYgXi4uIwYcIEzJo1i4d9ElVTdnY2tmzZgpCQEJSWlkImk2HixIlo0KCB0NGItE6jxffulnM4mHS33PRm/n934+F/d+O1vtNg4dIJIjMLlNy9jodnduN13zkQSZ6eYC6CCtL7KSj8ZSVmzZqFwMBAwff1JNJ3KpUKp0+fRmhoKHbt2oUePXogMDAQvr6+kEgkQscj0gqNFd/9gmJ0/zq+3E0sSvljZK0NgO3Auajl1v2l15CIVDgxvzfq21hqIiKRUSsoKMCOHTsQGhqK9PR0TJw4ETKZDK6urkJHI9IojS1niD6fVeFrxbeSoVKUwLJ51ypdQ2Jigr0Xb6s7GhEBsLKygkwmw4kTJ3D48GGUlJTAy8urbL1gYWGh0BGJNEJjxZd8J7/caA8ASgvzIba0hkj899l2d7Z8gIwVbyNjqR/kGZfLPV+uUCL59iNNRSSiv7Rs2RJLly5FZmYmZs+eje3bt8PBwQHTp0/HuXPnuE8oGRSNFV++XFHhayYWtaEszIdK+ffNLg0mLIVTUBTEFrUBVcU7P/PlPKOMSFvMzMzg5+eHmJgYXLp0CY0aNcKoUaPQoUMHrF69Gg8ePBA6IlGNaaz4rKUVPyg3b+QGkcQUhSmnq3EdU3XGIqIqcnBwwMKFC5GWlobly5fj1KlTaNKkCcaMGYNDhw5Bqaz6EiUiXaKx4nNrYA1zSfnLi6VWsOk+Bg9+WYfHyb9CWVwIlUqJJ3evQ/VEXuEaUokYbva1NRWRiKpALBajT58+2LZtG65fv47u3bvjgw8+QNOmTfHll18iMzNT6IhE1aLVuzqfKbhyBI/O7UNJdgZEpuaQ1GkAq/Z9YdW2D0Qmf4/wzCVinJzfG7ZW5pqISESvSKVS4cKFCwgNDUVUVBQ8PDwQGBiIIUOG1HgXpfsFxYg+n4XkO/nIlytgLZXArYE1RnZ24HsBqYXW1/FVlUgE9GtVH+vHu6s/GBGpTWFhIXbv3o3Q0FBcuXIF48ePR2BgIFq3bl2t66h7P1+i5xFk55aqeLZzSzsH/gUn0hdpaWkICwvDpk2b0LhxYwQGBuLtt99G7dov/shCnfv5Er2M3uzVSUT6Q6FQIC4uDiEhIUhISICfnx8CAwPRrVu3CvuE8j3CeOjKNLbenc5ARPrlzp072Lx5M0JDQyEWixEYGIiAgADUq1ev0lmhrGAZlIV5gEgMkdgE5g4t8Vq/mZBY25W7LmeF9IeuTWNr7Ty+S1l5CD6ahiNXsyHC08Xpzzz7wb1b2GFGr2b8i0xkgFQqFU6cOIGQkBDs3bsXffr0gaKbDJceoNw/iLOCZbD1nQUL5w5QKZ4g5+dgKOUFqDdiYbnr8T4A/aCLAx+t7UrbzqEO1o93R05BMaIvZCH59iPky0tgLTWFm31t+HfiHVtEhkwkEsHLywteXl7Iz89H6NYdWJleApg8f62uSGKGWm7d8eDQxgqPqVTAkavZyCko5nuHjqrONLZKBRSVlGJxTBIAaLT8tL4du62VOab24LFCRMbM2toaFq28YX4rpdIlT88oS+R4nHQc5g1bVPq4CED0hSy+p+igi5l5WByTXGnp3dn6L5TcS4fD+5FlJ/I8U1SixOKYZLRzqKOx2T+eQ0JEgqhsP99nsnctAsQmUJXIYWJpg3qjvqj0eXKFEkm38zUZk17R2qNpkCsq3tGvyLuL4qw/IDa3RGHaf1HLzavCc+SKUgQfTdPYNDaLj4gEUdl+vs/YjVj49DM+ZSmKUv+Lu9v+hYZT1sHEqm6F527buQdrxnWBmZlZ2S9zc/Nyv//nrxc9ronHnv365x2thup+QTESUrIr/Uyv4HI8zBu2gFnD5nj8++FKi0/T09gsPiISRGX7+f6TSGwCyxaeyIlbA3nWlUrfJMeNHI5vt3+CJ0+e4MmTJyguLi7735X9etHj//tYYWEh8vLyqvy9VXnc1NRU7YWq7qKWSCQ1LujKjqV75vHleFh7DINZwxa4s3keSh/nwqRWxX/QaHIam8VHRIJ4up/vnRd+xqdSqVCU+l8o5QUwtXWs8PjT/XytIZFIIJFIYGmpu4dWq1QqlJSUqKWU//fXo0eP1FLKzx4vLS196cj1ZYX6h00XFJs5VPgzkGdegSL/HizdvGBiaQNJHXs8vpIAa49hFZ+rwWPpWHxEJAj/zg5YcSil0seyo78ARGJAJILE2g62g4JgZte4wvNUAPw7VXyD1UUikaisHHSZUqmsUNDVLdX0LGug4rkDeHz5MCxcOsLE0gYAUKtVTxRcPlxp8QGaO5aOxUdEgnjdyhw9m9tV2M/XYUZYlb5fJHq69pdLGdRLLBbD3Nwc5uav/uf6e1Qirv12q9zXlCXFeJz8K6BUInP1+KdfVJRAWfwYT+5eh1n9JhWuo6lj6Vh8RCSYmb2a4Xjq/Vfaz9dMLMKMXs00kIpqqrJp7KLU0xCJxLCfsqbcKTzZe5eg4HI8XvtH8WnyWDqNncdHRPQy7R3rYIGvGyxMq/dWZCpSouB4BB7dvKKhZFQT/p0rTj8X/H4Ytdq+BYlNPZhY1S37VbvzIDz+4yhUyvL/+NHkNLbWtiwjInqeV9nWyu7hVUyYMAHr1q3DiBEjtBeWqkSXj6XjVCcRCW58V2e0c6hTzf18nfHzzz9j8ODByMjIQFBQkFDxqRI1mcaWSkw0Oo3NER8R6ZTq7uebkZGBAQMGwMfHB8uWLYOJiYkAqakyunrkFIuPiPRebm4u/Pz88NprryEyMhIWFhZCR6K/lE1jl5TiRWWjzdMZWHxEZBCKi4shk8mQnp6Offv24fXXXxc6Ev3lUlYeZq3/CRmK2jAzNRX8WDoWHxEZDKVSiYULFyI6OhqxsbFo2pSnNugCpVIJV1dXbNj8A9JKbQU/lo43txCRwRCLxfjPf/4DJycneHl5Ye/evXjjjTeEjmX0jh8/DktLS/T27II+OrBRN9fxEZHBmTZtGjZu3IhBgwbhxx9/FDqO0QsLC4NMJtOZ0yk41UlEBuvcuXMYMmQIFixYgJkzZwodxyjl5+fDyckJqampsLOzEzoOAE51EpEBc3d3x4kTJzBgwADcvHkTS5YsgVjMiS5t2rFjB3r37q0zpQdwqpOIDJyLiwtOnDiBU6dOYezYsZDLKzk2gDQmLCwMkydPFjpGOSw+IjJ4tra2OHjwIJRKJfr27YsHDx4IHckoJCcnIz09HQMGDBA6SjksPiIyClKpFNu3b4eHhwe6d++OGzduCB3J4IWHhyMgIAASiW59qsabW4jI6KxevRpLlizBvn370LlzZ6HjGCSFQgEnJyfEx8fDzc1N6DjlcMRHREbn/fffx5o1a9C/f3/ExMQIHccgxcXFwdnZWedKD2DxEZGRGj58OPbv34/AwEBs2LBB6DgGJzw8XOduanmGU51EZNTS0tIwYMAAjBo1CosWLdKZRdb6LDs7G66ursjIyIC1tbXQcSrgiI+IjFqzZs1w8uRJxMfHY8KECXjy5InQkfTe1q1bMWTIEJ0sPYDFR0QEOzs7HD58GI8fP0b//v2Rl5cndCS9pVKpyrYo01UsPiIiAJaWloiOjkabNm3g5eWFzMxMoSPppfPnz6OgoAA9evQQOspzsfiIiP5iYmKClStXQiaTwdPTE7/99pvQkfTOs5tadHlrON7cQkRUiZ07d2LmzJmIjIxE3759hY6jF+RyORo1aoTExEQ4OTkJHee5dLeSiYgENHLkSOzevRsBAQEIDw8XOo5e2Lt3Lzp37qzTpQfwdAYioufy8vJCQkJC2ekOn376KZc7vICu39TyDKc6iYhe4u7duxg0aBDatm2L77//HqampkJH0jkZGRno2LEj/vzzT0ilUqHjvBCnOomIXqJ+/fo4evQosrOzMXDgQOTn5wsdSedERERg9OjROl96AIuPiKhKatWqhT179qBp06bo0aMH/vzzT6Ej6QylUolNmzbp7BZl/8TiIyKqIolEguDgYIwePRqenp64fPmy0JF0wrFjx1CrVi29OemCN7cQEVWDSCTCv/71Lzg5OaF3797Yvn07evfuLXQsQT1bu6cvN/7w5hYiold09OhRvP3221i2bBnGjx8vdBxB5Ofnw8nJCampqbCzsxM6TpVwxEdE9Ip69eqF+Ph4DBw4EBkZGfjoo4/0ZtSjLlFRUejdu7felB7Az/iIiGqkdevWOHnyJHbu3Ilp06ZBoVAIHUmrwsPD9WLt3v/iVCcRkRo8evQII0eOhImJCaKiomBlZSV0JI1LSkpCnz59kJGRAYlEfyYQOeIjIlKD2rVrY//+/bC3t0fPnj1x584doSNp3KZNmzBhwgS9Kj2AIz4iIrVSqVRYtGgRwsLCEBMTg5YtWwodSSMUCgUcHR1x5MgRuLm5CR2nWvSrpomIdJxIJMK///1vODk5oVevXti5c6dOn033quLi4uDi4qJ3pQdwqpOISCMmTpyIyMhI+Pv7IyoqSug4aqcvG1JXhlOdREQadOnSJQwaNAizZs3CvHnzDGK5Q3Z2NlxdXZGRkQFra2uh41QbR3xERBrUrl07nDx5Eps3b8b777+P0tJSoSPVWGRkJIYOHaqXpQew+IiINM7BwQHHjx9HcnIyRowYgcLCQqEjvTKVSoWwsDC92ZC6Miw+IiItsLGxQUxMDGxsbODt7Y179+4JHemVnD9/HoWFhXp9ww6Lj4hIS8zMzLBp0yb069cPnp6eSElJETpStYWFhWHSpEkQi/W3PnhzCxGRAEJCQrBw4ULs3r0bnp6eQsepkqKiIjg4OCAxMRFOTk5Cx3ll+lvZRER6bMqUKQgPD8ewYcOwe/duoeNUyd69e+Hu7q7XpQdwATsRkWAGDBiAuLg4DB48GJmZmZg9e7bQkV5IHzekrgynOomIBHbz5k0MGDAA/fr1w7Jly3Ty87OMjAx06tQJWVlZkEqlQsepEd370yUiMjKNGzfGiRMnkJiYiFGjRqGoqEjoSBVERETg7bff1vvSA1h8REQ6oW7duvj5559hamqKt956C/fv3xc6UhmlUmkw05wAi4+ISGeYm5tj69atePPNN9G9e3dcv35d6EgAgGPHjsHKygqdOnUSOopa8OYWIiIdIhaLsWTJEjRu3BheXl7Yu3cvPDw8BM30bENqQ9hnFODNLUREOmv//v0IDAxESEgIhgwZIkiGhw8fonHjxkhNTYWdnZ0gGdSNU51ERDpq8ODB+OmnnzBt2jQEBwcLkmHHjh3o06ePwZQewOIjItJpXbp0wa+//oqVK1di/vz5UCqVWn19fT5373k41UlEpAdycnIwZMgQODk5YdOmTTA3N9f4ayYlJaFPnz7IyMiARGI4t4RwxEdEpAdsbW1x6NAhKBQK9O3bF7m5uRp/zfDwcAQEBBhU6QEsPiIivWFhYYGoqCh07twZ3bt3x82bNzX2WiUlJdiyZYten7v3PCw+IiI9IhaLsXz5ckydOhWenp64cOGCRl4nLi4OTZo0QYsWLTRyfSGx+IiI9NDs2bOxevVq9OvXD7GxsWq/fnh4uEGO9gDe3EJEpNdOnTqF4cOH48svv8Q777yjlmveu3cPzZs3R0ZGBqytrdVyTV1iWJ9YEhEZmW7duuH48eMYMGAAMjIy8MUXX9R4h5XIyEgMHTrUIEsP4IiPiMgg3Lt3D0OGDEHz5s0REhICMzOzV7qOSqVC27ZtsXbtWvTs2VPNKXUDP+MjIjIA9erVQ3x8PPLz8+Hr64uHDx++0nXOnTsHuVyOHj16qDmh7mDxEREZCEtLS+zatQtubm7w8vJCZmZmta8RHh6OSZMmGcyG1JXhVCcRkYFRqVRYvnw5vvvuOxw4cADt27ev8Jz7BcWIPp+F5Dv5yJcrYC2VoKmtBT6f2B+Jp4/D0dFRgOTaweIjIjJQO3bswHvvvYetW7fCx8cHAHAxMw9rj6YhISUbAFCs+HvvT4lIhdLSUvRt2wgzejZDe8c6guTWNBYfEZEBO378OPz9/fH1119D4tYLi2OSIVeU4kXv/CIRIJWYYIGvG8Z3ddZaVm1h8RERGbikpCQMeP8/MOkyEqUwqfL3WZiKscC3pcGVH9fxEREZuCdW9pB2Gwu5ouKRRo+vHEX+2b0oycmC2MwCpvWbwKbbKEgdW6OoRInFMclo51AH7RwMZ9qTxUdEZODWHk1DcWnF0ss/swcPT0fDtt9MSF06QWQiQdH18yhK/S+kjq0BAHJFKYKPpmH9eHdtx9YYFh8RkQG7X1CMhJTsCp/pKeWPkXd8K2wHzoFlC8+yr1u6vgFL1zfKfq9SAUeuZiOnoBi2Vpo/A1AbuI6PiMiARZ/PqvTrxbeSoVI8gWXzbi+9hghA9IXKr6OPWHxERAYs+U5+uSULz5QW5UNsaQ2R+OU3u8gVSiTffqSJeIJg8RERGbB8uaLSr5tYWENZmA+VsrSK1ylRZyxBsfiIiAyYtbTyWznMG7pBJDFFYcqpKl7HVJ2xBMXiIyIyYG4NrGEuqfhWL5bWQh2vcXjwy3oUppyCskQOVakCRdfOIfdIWLnnSiViuNnX1lZkjeMCdiIiA3a/oBjdv46v9HM+ACi4cgSPzv6IkpxMiMwsYN6gGay7vQ2pQ8uy55hLxDg5v7fB3NXJ5QxERAbsdStz9Gxuh4NJdyvdpsyqtTesWns/9/tFIsC7hZ3BlB7AqU4iIoM3s1czSCVV36rsf0klJpjRq5maEwmLxUdEZODaO9bBAl83WJhW7y3/6V6dbga1XRnAqU4iIqPwbKNpns7Am1uIiIzKpaw8BB9Nw5Gr2RAB5TaulkrEUOHpZ3ozejUzuJHeMyw+IiIjlFNQjOgLWUi+/Qj58hJYS03hZl8b/p0cDOpGlsqw+IiIyKjw5hYiIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIqLD4iIjIq/w9GAD70G2jX1wAAAABJRU5ErkJggg==\n",
"text/plain": [
"<Figure size 432x288 with 1 Axes>"
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"nx.draw(graph, with_labels=True)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"['D', 'B', 'E', 'F', 'G', 'A', 'C']"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"def bfs(graph, start):\n",
" \"\"\"\n",
" Return the order in which nodes are visited in a breadth-first \n",
" traversal, starting with the given node.\n",
" \"\"\"\n",
" q = deque()\n",
" q.append(start)\n",
" seen = set() # nodes we have already visited.\n",
" res = []\n",
" while len(q) > 0: # while more to visit\n",
" n = q.popleft()\n",
" if n not in seen:\n",
" res.append(n)\n",
" seen.add(n)\n",
" for nn in graph.neighbors(n):\n",
" if nn not in seen:\n",
" q.append(nn)\n",
" return res\n",
"\n",
"bfs(graph, 'D')"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To get all shortest paths from a node, perform BFS, while keeping track of the depth of the search."
]
},
{
"cell_type": "code",
"execution_count": 18,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n",
"shortest paths for A\n",
"{'A': ['A'], 'B': ['A', 'B'], 'C': ['A', 'C'], 'D': ['A', 'B', 'D'], 'E': ['A', 'B', 'D', 'E'], 'F': ['A', 'B', 'D', 'F'], 'G': ['A', 'B', 'D', 'G']}\n",
"\n",
"shortest paths for B\n",
"{'B': ['B'], 'A': ['B', 'A'], 'C': ['B', 'C'], 'D': ['B', 'D'], 'E': ['B', 'D', 'E'], 'F': ['B', 'D', 'F'], 'G': ['B', 'D', 'G']}\n",
"\n",
"shortest paths for C\n",
"{'C': ['C'], 'A': ['C', 'A'], 'B': ['C', 'B'], 'D': ['C', 'B', 'D'], 'E': ['C', 'B', 'D', 'E'], 'F': ['C', 'B', 'D', 'F'], 'G': ['C', 'B', 'D', 'G']}\n",
"\n",
"shortest paths for D\n",
"{'D': ['D'], 'B': ['D', 'B'], 'E': ['D', 'E'], 'F': ['D', 'F'], 'G': ['D', 'G'], 'A': ['D', 'B', 'A'], 'C': ['D', 'B', 'C']}\n",
"\n",
"shortest paths for E\n",
"{'E': ['E'], 'D': ['E', 'D'], 'F': ['E', 'F'], 'B': ['E', 'D', 'B'], 'G': ['E', 'D', 'G'], 'A': ['E', 'D', 'B', 'A'], 'C': ['E', 'D', 'B', 'C']}\n",
"\n",
"shortest paths for F\n",
"{'F': ['F'], 'D': ['F', 'D'], 'E': ['F', 'E'], 'G': ['F', 'G'], 'B': ['F', 'D', 'B'], 'A': ['F', 'D', 'B', 'A'], 'C': ['F', 'D', 'B', 'C']}\n",
"\n",
"shortest paths for G\n",
"{'G': ['G'], 'D': ['G', 'D'], 'F': ['G', 'F'], 'B': ['G', 'D', 'B'], 'E': ['G', 'D', 'E'], 'A': ['G', 'D', 'B', 'A'], 'C': ['G', 'D', 'B', 'C']}\n"
]
}
],
"source": [
"for s in graph.nodes():\n",
" paths = nx.single_source_shortest_path(graph, s)\n",
" print('\\nshortest paths for %s' % s)\n",
" print(paths)"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"# Girvan-Newman Algorithm\n",
"\n",
"**Input:** Graph $G$; desired number of clusters $k$\n",
"\n",
"**Output:** A hierarchical clustering of nodes, based on edge betweenness\n",
"\n",
"- **While** number of clusters $< k$:\n",
" - Compute the betweenness of all edges in $G$\n",
" - Remove edge with highest betweenness\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
""
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"- All pairs-shortest-paths, but need to store the paths.\n",
"- How can we reduce redundant computation?"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"\n",
"\n",
"1.) Do breadth-first search starting at node $E$.\n",
" - Each level is length of shortest path from $E$ to that node\n",
" - Edges within the same level cannot be part of a shortest path from $E$ to some target.\n",
" \n",
"2.) Label each node by the number of shortest paths that reach it from the root.\n",
" - Start by labeling the root ($E$). Then, each child node is the sum of its parents.\n",
" - E.g., $G = D + F$\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"\n",
"\n",
"3.) Compute fraction of shortest paths through each edge (bottom up).\n",
" - leaf nodes get credit 1\n",
" - non-leaf nodes get credit of 1 + credits for edges to nodes at level below\n",
" - edges to level above gets credit proportional to fraction of shortest paths that go through it.\n",
"\n",
"E.g. Level 3:\n",
" - $A$ and $C$ are given credit 1 (they are leaf nodes)\n",
" \n",
"Level 2:\n",
" - $B$ gets credit $3$ ($A + C + 1$)\n",
" - All shortest paths from $\\{E\\}$ to $\\{A, B, C\\}$ go through B.\n",
" - $G$ gets credit 1 (leaf)\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"\n",
"\n",
"Level 1 Edges:\n",
" - $D,B$ edge gets all credit from node $B$ (3)\n",
" - $G$ has two parents, so edges $(D,G)$, $(F,G)$ share the credit from $G$\n",
" - From step 1, $D$ and $F$ each have credit 1, so shared equally. $(\\frac{1}{1+1} = .5)$\n",
" - What if $D=5$, $F=3$? $\\frac{5}{8}$, $\\frac{3}{8}$\n",
" \n",
"\n",
"Level 1 Nodes:\n",
" - $D = 1 + 3 + .5 = 4.5$\n",
" - $F = 1 + .5 = 1.5$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"\n",
"\n",
"- What if $D=5$, $F=3$? \n"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"## Computing betweenness of all edges\n",
"\n",
"\n",
"\n",
"- What if $D=5$, $F=3$? \n",
"$(D,G) = \\frac{5}{8}$, $(F,G) = \\frac{3}{8}$"
]
},
{
"cell_type": "markdown",
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"source": [
"Final steps:\n",
"\n",
"- Repeat for each node as source\n",
"- Divide total by 2 (since each shortest path found twice, once in each direction)\n",
"\n",
""
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**More detailed example for edge (D,E):**\n",
"\n",
"For each root node, we report the value computed for edge (D,E) for Girvan Newman:\n",
"\n",
"| root node | value for (D,E)|\n",
"|-----------|----------------|\n",
"| A | 1 |\n",
"| B | 1 |\n",
"| C | 1 |\n",
"| D | 1 |\n",
"| E | 4.5 |\n",
"| F | 0 |\n",
"| G | .5 |\n",
"| **total** | 9 |\n",
"\n",
"We then divide by 2 to get the final betweenness of (D,E), 4.5.\n",
"\n",
"\n",
"The reason the value is $1$ when the root node is one of ${A,B,C}$ is that $E$ will be a leaf node for each of these. (Shortest paths to $F$ or $G$ from $A,B,C$ will never traverse edge $(D,E)$). The value is 0.5 for $G$ as source, becasue half credit is given as there are two shortest paths of length 2 from $G$ to $E$, but only one traverses $(D,E)$. No other shortest path from root $G$ traverses $(D,E)$. \n"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"{('A', 'B'): 5.0,\n",
" ('A', 'C'): 1.0,\n",
" ('B', 'C'): 5.0,\n",
" ('B', 'D'): 12.0,\n",
" ('D', 'E'): 4.5,\n",
" ('D', 'F'): 4.0,\n",
" ('D', 'G'): 4.5,\n",
" ('E', 'F'): 1.5,\n",
" ('F', 'G'): 1.5}"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"nx.edge_betweenness_centrality(graph, normalized=False)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [],
"source": [
"def girvan_newman(G, depth=0):\n",
" \"\"\" Recursive implementation of the girvan_newman algorithm.\n",
" See http://www-rohan.sdsu.edu/~gawron/python_for_ss/course_core/book_draft/Social_Networks/Networkx.html\n",
" \n",
" Args:\n",
" G.....a networkx graph\n",
"\n",
" Returns:\n",
" A list of all discovered communities,\n",
" a list of lists of nodes. \"\"\"\n",
"\n",
" if G.order() == 1:\n",
" return [G.nodes()]\n",
" \n",
" def find_best_edge(G0):\n",
" eb = nx.edge_betweenness_centrality(G0)\n",
" # eb is dict of (edge, score) pairs, where higher is better\n",
" # Return the edge with the highest score.\n",
" return sorted(eb.items(), key=lambda x: x[1], reverse=True)[0][0]\n",
"\n",
" # Each component is a separate community. We cluster each of these.\n",
" components = [c for c in nx.connected_component_subgraphs(G)]\n",
" indent = ' ' * depth # for printing\n",
" while len(components) == 1:\n",
" edge_to_remove = find_best_edge(G)\n",
" print(indent + 'removing ' + str(edge_to_remove))\n",
" G.remove_edge(*edge_to_remove)\n",
" components = [c for c in nx.connected_component_subgraphs(G)]\n",
"\n",
" result = [c.nodes() for c in components]\n",
" print(indent + 'components=' + str(result))\n",
" for c in components:\n",
" result.extend(girvan_newman(c, depth + 1))\n",
"\n",
" return result"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"removing ('B', 'D')\n",
"components=[NodeView(('A', 'C', 'B')), NodeView(('D', 'E', 'F', 'G'))]\n",
" removing ('A', 'B')\n",
" removing ('A', 'C')\n",
" components=[NodeView(('A',)), NodeView(('C', 'B'))]\n",
" removing ('C', 'B')\n",
" components=[NodeView(('C',)), NodeView(('B',))]\n",
" removing ('D', 'E')\n",
" removing ('E', 'F')\n",
" components=[NodeView(('D', 'F', 'G')), NodeView(('E',))]\n",
" removing ('D', 'F')\n",
" removing ('D', 'G')\n",
" components=[NodeView(('D',)), NodeView(('F', 'G'))]\n",
" removing ('F', 'G')\n",
" components=[NodeView(('F',)), NodeView(('G',))]\n"
]
}
],
"source": [
"result = girvan_newman(create_example_graph())"
]
},
{
"cell_type": "code",
"execution_count": 14,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[NodeView(('A', 'C', 'B')),\n",
" NodeView(('D', 'E', 'F', 'G')),\n",
" NodeView(('A',)),\n",
" NodeView(('C', 'B')),\n",
" NodeView(('A',)),\n",
" NodeView(('C',)),\n",
" NodeView(('B',)),\n",
" NodeView(('C',)),\n",
" NodeView(('B',)),\n",
" NodeView(('D', 'F', 'G')),\n",
" NodeView(('E',)),\n",
" NodeView(('D',)),\n",
" NodeView(('F', 'G')),\n",
" NodeView(('D',)),\n",
" NodeView(('F',)),\n",
" NodeView(('G',)),\n",
" NodeView(('F',)),\n",
" NodeView(('G',)),\n",
" NodeView(('E',))]"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"result"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"<link href=\"https://fonts.googleapis.com/css?family=Droid+Sans+Mono\" rel=\"stylesheet\" type='text/css'>\n",
"\n",
"<link href=\"https://fonts.googleapis.com/css?family=Exo+2\" rel=\"stylesheet\" type='text/css'>\n",
"\n",
"<link href=\"https://fonts.googleapis.com/css?family=Lora\" rel=\"stylesheet\" type='text/css'>\n",
"\n",
"<link href=\"https://fonts.googleapis.com/css?family=Fira+Mono\" rel=\"stylesheet\" type='text/css'>\n",
"\n",
"<style>\n",
"\n",
"div#site {\n",
" height: 100% !important;\n",
"}\n",
"\n",
"strong {\n",
" font-weight: 900 !important;\n",
"}\n",
"\n",
".container { width:90% !important; }\n",
"\n",
"\n",
"div#notebook {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 20pt;\n",
" line-height: 170%;\n",
" color: #303030;\n",
"}\n",
"body,\n",
"div.body {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 20pt;\n",
" color: #303030;\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
"}\n",
"body.notebook_app {\n",
" padding: 0;\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
" padding-right: 0px !important;\n",
" overflow-y: hidden;\n",
"}\n",
"a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" color: #303030;\n",
"}\n",
"a:hover,\n",
"a:focus {\n",
" color: #2f2f2f;\n",
"}\n",
".list_header,\n",
"div#notebook_list_header.row.list_header {\n",
" font-size: 20pt;\n",
" color: #2f2f2f;\n",
" background-color: #ffffff;\n",
"}\n",
"div#cluster_list_header.row.list_header,\n",
"div#running .row.list_header {\n",
" font-size: 20pt;\n",
" color: #303030;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-bottom: 2px solid rgba(180,180,180,.30);\n",
"}\n",
"div#cluster_list > div.list_item.row,\n",
"div#cluster_list > div.list_item.row:hover {\n",
" background: #fafafa;\n",
" background-color: #fafafa;\n",
"}\n",
"div#clusters.tab-pane.active {\n",
" font-size: 12.0pt;\n",
" padding: 4px 0 4px 0;\n",
"}\n",
"#running .panel-group .panel .panel-heading {\n",
" font-size: 14pt;\n",
" color: #303030;\n",
" padding: 8px 8px;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
"}\n",
"#running .panel-group .panel .panel-heading a {\n",
" font-size: 14pt;\n",
" color: #303030;\n",
"}\n",
"#running .panel-group .panel .panel-heading a:focus,\n",
"#running .panel-group .panel .panel-heading a:hover {\n",
" font-size: 14pt;\n",
" color: #303030;\n",
"}\n",
"#running .panel-group .panel .panel-body .list_container .list_item {\n",
" background: #fafafa;\n",
" background-color: #fafafa;\n",
" padding: 2px;\n",
" border-bottom: 2px solid rgba(180,180,180,.30);\n",
"}\n",
"#running .panel-group .panel .panel-body .list_container .list_item:hover {\n",
" background: #fafafa;\n",
" background-color: #fafafa;\n",
"}\n",
"#running .panel-group .panel .panel-body {\n",
" padding: 2px;\n",
"}\n",
"div.running_list_info.toolbar_info {\n",
" font-size: 12.0pt;\n",
" padding: 4px 0 4px 0;\n",
" height: inherit;\n",
" line-height: inherit;\n",
" text-shadow: none;\n",
"}\n",
".list_placeholder {\n",
" font-weight: normal;\n",
"}\n",
"#tree-selector {\n",
" padding: 0px;\n",
"}\n",
"#project_name > ul > li > a > i.fa.fa-home {\n",
" color: #ff7823;\n",
" font-size: 17pt;\n",
" display: inline-block;\n",
" position: static;\n",
" padding: 0px 0px;\n",
" font-weight: normal;\n",
" text-align: center;\n",
" vertical-align: text-top;\n",
"}\n",
"#project_name {\n",
" display: inline-flex;\n",
" padding-left: 7px;\n",
" margin-left: -2px;\n",
" margin-bottom: -20px;\n",
" text-align: -webkit-auto;\n",
" vertical-align: text-top;\n",
"}\n",
"div#notebook_toolbar div.dynamic-instructions {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
"}\n",
".toolbar_info {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" color: #303030;\n",
" text-shadow: none;\n",
" border: none;\n",
" height: inherit;\n",
" line-height: inherit;\n",
"}\n",
".list_container {\n",
" font-size: 12.0pt;\n",
" color: #303030;\n",
" border: none;\n",
" text-shadow: none !important;\n",
"}\n",
".list_container > div {\n",
" border-bottom: 1px solid rgba(180,180,180,.14);\n",
" font-size: 12.0pt;\n",
"}\n",
".list_header > div,\n",
".list_item > div {\n",
" padding-left: 0px;\n",
"}\n",
".list_header > div input,\n",
".list_item > div input {\n",
" top: 0px;\n",
"}\n",
".list_header > div .item_link,\n",
".list_item > div .item_link {\n",
" margin-left: -1px;\n",
" vertical-align: middle;\n",
" line-height: 22px;\n",
" font-size: 12.0pt;\n",
"}\n",
".item_icon {\n",
" font-size: 12.0pt;\n",
" vertical-align: middle;\n",
"}\n",
".list_item input:not([type=\"checkbox\"]) {\n",
" padding-right: 0px;\n",
" height: auto;\n",
" width: 20%;\n",
" margin: 6px 0 0;\n",
" margin-top: 1px;\n",
"}\n",
"#button-select-all {\n",
" height: auto;\n",
" font-size: 12.0pt;\n",
" padding: 5px;\n",
" min-width: 65px;\n",
" z-index: 0;\n",
"}\n",
"button#tree-selector-btn {\n",
" height: auto;\n",
" font-size: 12.0pt;\n",
" padding: 5px;\n",
"}\n",
"input#select-all.pull-left.tree-selector {\n",
" margin-left: 7px;\n",
" margin-right: 2px;\n",
" margin-top: 5px;\n",
"}\n",
"input[type=\"radio\"],\n",
"input[type=\"checkbox\"] {\n",
" margin: 6px 0 0;\n",
" margin-top: 1px;\n",
" line-height: normal;\n",
"}\n",
".list_container a {\n",
" font-size: 17px;\n",
" color: #303030;\n",
" border: none;\n",
" text-shadow: none !important;\n",
" font-weight: normal;\n",
" font-style: normal;\n",
"}\n",
"div.list_container a:hover {\n",
" color: #2f2f2f;\n",
"}\n",
"div.list_item:hover {\n",
" background-color: #fafafa;\n",
"}\n",
".breadcrumb > li {\n",
" font-size: 12.0pt;\n",
" color: #303030;\n",
" border: none;\n",
" text-shadow: none !important;\n",
"}\n",
"ul#tabs a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" font-weight: normal;\n",
" font-style: normal;\n",
" border-color: transparent;\n",
" text-shadow: none !important;\n",
"}\n",
".nav-tabs {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" font-weight: normal;\n",
" font-style: normal;\n",
" background: #ffffff;\n",
" text-shadow: none !important;\n",
" border-color: transparent;\n",
" border-bottom-color: rgba(180,180,180,.30);\n",
"}\n",
".nav-tabs > li > a:hover {\n",
" color: #2f2f2f;\n",
" background-color: rgba(180,180,180,.14);\n",
"}\n",
".nav-tabs > li > a:active,\n",
".nav-tabs > li > a:focus,\n",
".nav-tabs > li.active > a,\n",
".nav-tabs > li.active > a:focus,\n",
".nav-tabs > li.active > a:hover,\n",
".nav-tabs > li.active > a,\n",
".nav-tabs > li.active > a:hover,\n",
".nav-tabs > li.active > a:focus {\n",
" color: #1c1c1c;\n",
" background-color: #eeeeee;\n",
" border: 1px solid transparent;\n",
" border-bottom-color: transparent;\n",
" cursor: default;\n",
"}\n",
".nav > li > a:hover,\n",
".nav > li > a:focus {\n",
" text-decoration: none;\n",
" background-color: rgba(180,180,180,.14);\n",
"}\n",
".nav > li.disabled > a,\n",
".nav > li.disabled > a:hover {\n",
" color: #aaaaaa;\n",
"}\n",
"div#notebook {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 20pt;\n",
" padding-top: 4px;\n",
"}\n",
".notebook_app {\n",
" background-color: #ffffff;\n",
"}\n",
"#notebook-container {\n",
" padding: 13px;\n",
" background-color: #ffffff;\n",
" min-height: 0px;\n",
" box-shadow: none;\n",
" width: 980px;\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
"}\n",
"div#ipython-main-app.container {\n",
" width: 980px;\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
"}\n",
".container {\n",
" width: 980px;\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
"}\n",
".notebook_app #header {\n",
" box-shadow: none !important;\n",
" background-color: #ffffff;\n",
" border-bottom: 2px solid rgba(180,180,180,.14);\n",
"}\n",
"#header {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 22pt;\n",
" box-shadow: none;\n",
" background-color: #ffffff;\n",
"}\n",
"#header .header-bar {\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
"}\n",
"body > #header .header-bar {\n",
" width: 100%;\n",
" background: #ffffff;\n",
"}\n",
"#menubar {\n",
" background-color: #ffffff;\n",
"}\n",
"#menubar .navbar,\n",
".navbar-default {\n",
" background-color: #ffffff;\n",
" margin-bottom: 0px;\n",
" margin-top: 5px;\n",
"}\n",
".navbar {\n",
" border: none;\n",
"}\n",
"div.navbar-text,\n",
".navbar-text {\n",
" margin-top: 6px !important;\n",
" margin-bottom: 0px;\n",
"}\n",
".navbar-default {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" background-color: #ffffff;\n",
" border-color: rgba(180,180,180,.14);\n",
" line-height: 1.5em;\n",
" padding-bottom: 0px;\n",
"}\n",
".navbar-default .navbar-nav > li > a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" color: #303030;\n",
" display: block;\n",
" line-height: 1.5em;\n",
" padding-top: 9px;\n",
" padding-bottom: 6px;\n",
"}\n",
".navbar-default .navbar-nav > li > a:hover,\n",
".navbar-default .navbar-nav > li > a:focus {\n",
" color: #2f2f2f;\n",
" background-color: rgba(180,180,180,.14);\n",
" border-color: rgba(180,180,180,.14);\n",
" line-height: 1.5em;\n",
"}\n",
".navbar-default .navbar-nav > .open > a,\n",
".navbar-default .navbar-nav > .open > a:hover,\n",
".navbar-default .navbar-nav > .open > a:focus {\n",
" color: #1c1c1c;\n",
" background-color: rgba(180,180,180,.14);\n",
" border-color: rgba(180,180,180,.14);\n",
" line-height: 1.5em;\n",
"}\n",
".edit_mode .modal_indicator:before {\n",
" font-size: 15pt;\n",
" color: #2c85f7;\n",
" content: \"\\f040\";\n",
" padding-top: 5px;\n",
" padding-bottom: 0px;\n",
" vertical-align: bottom;\n",
"}\n",
".command_mode .modal_indicator:before {\n",
" font-size: 17pt;\n",
" color: #2c85f7;\n",
" content: \"\\f1f9\";\n",
" padding-top: 5px;\n",
" padding-bottom: 0px;\n",
" vertical-align: bottom;\n",
"}\n",
".item_icon {\n",
" color: #126dce;\n",
"}\n",
".item_buttons .kernel-name {\n",
" font-size: 13pt;\n",
" color: #126dce;\n",
" line-height: 22px;\n",
"}\n",
".running_notebook_icon:before {\n",
" color: #009e07 !important;\n",
"}\n",
".item_buttons .running-indicator {\n",
" padding-top: 2px;\n",
" color: #009e07;\n",
"}\n",
"#modal_indicator {\n",
" float: right !important;\n",
" color: #126dce;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
"}\n",
"#kernel_indicator {\n",
" float: right !important;\n",
" color: #ff7823;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" font-size: 16pt;\n",
" border-left: 2px solid #ff7823;\n",
" padding-bottom: 2px;\n",
"}\n",
"#kernel_indicator .kernel_indicator_name {\n",
" color: #ff7823;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" font-size: 16pt;\n",
" padding-left: 5px;\n",
" padding-right: 5px;\n",
" margin-top: 10px;\n",
" vertical-align: text-bottom;\n",
" padding-bottom: 0px;\n",
"}\n",
"#kernel_indicator .kernel_indicator_name {\n",
" color: #ff7823;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" font-size: 15.5pt;\n",
" padding-left: 5px;\n",
" padding-right: 5px;\n",
" margin-top: 10px;\n",
" vertical-align: text-bottom;\n",
" padding-bottom: 0px;\n",
"}\n",
"div.notification_widget.info,\n",
".notification_widget.info,\n",
".notification_widget:active:hover,\n",
".notification_widget.active:hover,\n",
".open > .dropdown-toggle.notification_widget:hover,\n",
".notification_widget:active:focus,\n",
".notification_widget.active:focus,\n",
".open > .dropdown-toggle.notification_widget:focus,\n",
".notification_widget:active.focus,\n",
".notification_widget.active.focus,\n",
".open > .dropdown-toggle.notification_widget.focus,\n",
"div#notification_notebook.notification_widget.btn.btn-xs.navbar-btn,\n",
"div#notification_notebook.notification_widget.btn.btn-xs.navbar-btn:hover,\n",
"div#notification_notebook.notification_widget.btn.btn-xs.navbar-btn:focus {\n",
" color: #126dce;\n",
" background-color: #ffffff;\n",
" border-color: #ffffff;\n",
"}\n",
"#notification_area,\n",
"div.notification_area {\n",
" float: right !important;\n",
" position: static;\n",
"}\n",
"#kernel_logo_widget,\n",
"#kernel_logo_widget .current_kernel_logo {\n",
" display: none;\n",
"}\n",
"div#ipython_notebook {\n",
" display: none;\n",
"}\n",
"i.fa.fa-icon {\n",
" -webkit-font-smoothing: antialiased;\n",
" -moz-osx-font-smoothing: grayscale;\n",
" text-rendering: auto;\n",
"}\n",
".fa {\n",
" display: inline-block;\n",
" font: normal normal normal 12pt/1 \"FontAwesome\", \"Exo_2\", sans-serif;\n",
" text-rendering: auto;\n",
" -webkit-font-smoothing: antialiased;\n",
" -moz-osx-font-smoothing: grayscale;\n",
"}\n",
".dropdown-menu {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" box-shadow: none;\n",
" padding: 0px;\n",
" text-align: left;\n",
" border: 2px solid rgba(180,180,180,.30);\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
" line-height: 1.3;\n",
" margin: 0px;\n",
"}\n",
".dropdown-menu:hover {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" border: 2px solid rgba(180,180,180,.30);\n",
" background-color: #ffffff;\n",
" box-shadow: none;\n",
" line-height: 1.3;\n",
"}\n",
".dropdown-header {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" display: block;\n",
" color: #ff7823;\n",
" text-decoration: underline;\n",
" white-space: nowrap;\n",
" padding: 8px 0px 0px 6px;\n",
" line-height: 1.3;\n",
"}\n",
".dropdown-menu > li > a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" line-height: 1.3;\n",
" display: block;\n",
" padding: 10px 25px 10px 14px;\n",
" color: #303030;\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
"}\n",
".dropdown-menu > li > a:hover {\n",
" color: #2f2f2f;\n",
" background-color: rgba(180,180,180,.14);\n",
" background: rgba(180,180,180,.14);\n",
" border-color: rgba(180,180,180,.14);\n",
"}\n",
".dropdown-menu .divider {\n",
" height: 2px;\n",
" margin: 0px 0px;\n",
" overflow: hidden;\n",
" background-color: rgba(180,180,180,.30);\n",
"}\n",
".dropdown-submenu > .dropdown-menu {\n",
" top: 0;\n",
" left: 100%;\n",
" margin-top: -2px;\n",
" margin-left: 0px;\n",
" padding-top: 0px;\n",
"}\n",
".dropdown-menu > .disabled > a,\n",
".dropdown-menu > .disabled > a:hover,\n",
".dropdown-menu > .disabled > a:focus {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" font-weight: normal;\n",
" color: #aaaaaa;\n",
" padding: none;\n",
" display: block;\n",
" clear: both;\n",
" line-height: 1.2;\n",
" white-space: nowrap;\n",
"}\n",
".dropdown-submenu > a:after {\n",
" color: #303030;\n",
" margin-right: -16px;\n",
"}\n",
".dropdown-submenu:hover > a:after,\n",
".dropdown-submenu:active > a:after,\n",
".dropdown-submenu:focus > a:after,\n",
".dropdown-submenu:visited > a:after {\n",
" color: #ff7823;\n",
" margin-right: -16px;\n",
"}\n",
"div.kse-dropdown > .dropdown-menu,\n",
".kse-dropdown > .dropdown-menu {\n",
" min-width: 0;\n",
" top: 94%;\n",
"}\n",
".btn,\n",
".btn-default {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" color: #303030;\n",
" background: #ebebeb;\n",
" background-color: #ebebeb;\n",
" border: 2px solid #e8e8e8;\n",
" font-weight: normal;\n",
" box-shadow: none;\n",
" text-shadow: none;\n",
" border-radius: 2px;\n",
" font-size: inherit;\n",
"}\n",
".btn:hover,\n",
".btn:active:hover,\n",
".btn.active:hover,\n",
".btn-default:hover,\n",
".open > .dropdown-toggle.btn-default:hover,\n",
".open > .dropdown-toggle.btn:hover {\n",
" color: #2f2f2f;\n",
" background-color: #e4e4e4;\n",
" background: #e4e4e4;\n",
" border-color: #e4e4e4;\n",
" background-image: none;\n",
" box-shadow: none !important;\n",
" border-radius: 2px;\n",
"}\n",
".btn:active,\n",
".btn.active,\n",
".btn:active:focus,\n",
".btn.active:focus,\n",
".btn:active.focus,\n",
".btn.active.focus,\n",
".btn-default:focus,\n",
".btn-default.focus,\n",
".btn-default:active,\n",
".btn-default.active,\n",
".btn-default:active:hover,\n",
".btn-default.active:hover,\n",
".btn-default:active:focus,\n",
".btn-default.active:focus,\n",
".btn-default:active.focus,\n",
".btn-default.active.focus,\n",
".open > .dropdown-toggle.btn:focus,\n",
".open > .dropdown-toggle.btn.focus,\n",
".open > .dropdown-toggle.btn-default {\n",
" color: #1c1c1c;\n",
" background-color: #e4e4e4;\n",
" background: #e4e4e4;\n",
" border-color: #e4e4e4;\n",
" background-image: none;\n",
" box-shadow: none !important;\n",
" border-radius: 1px;\n",
"}\n",
".item_buttons > .btn,\n",
".item_buttons > .btn-group,\n",
".item_buttons > .input-group {\n",
" margin-left: 5px;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: 1px solid #eeeeee;\n",
"}\n",
".item_buttons > .btn:hover,\n",
".item_buttons > .btn-group:hover,\n",
".item_buttons > .input-group:hover {\n",
" margin-left: 5px;\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border: 1px solid #e9e9e9;\n",
"}\n",
".btn-group > .btn-mini,\n",
".btn-sm,\n",
".btn-group-sm > .btn,\n",
".btn-xs,\n",
".btn-group-xs > .btn,\n",
".alternate_upload .btn-upload,\n",
".btn-group,\n",
".btn-group-vertical {\n",
" font-size: 12.0pt;\n",
" font-weight: normal;\n",
"}\n",
".btn-xs,\n",
".btn-group-xs > .btn {\n",
" font-size: 12.0pt;\n",
" background-image: none;\n",
" font-weight: normal;\n",
" text-shadow: none;\n",
" display: inline-table;\n",
"}\n",
".btn-group > .btn:first-child {\n",
" margin-left: 3px;\n",
"}\n",
".alternate_upload .btn-upload {\n",
" display: none;\n",
"}\n",
"button.close {\n",
" border: 0px none;\n",
" font-family: sans-serif;\n",
" font-size: 25pt;\n",
"}\n",
".dynamic-buttons {\n",
" font-size: inherit;\n",
" padding-top: 0px;\n",
" display: inline-block;\n",
"}\n",
".close {\n",
" color: #de143d;\n",
" opacity: .5;\n",
" text-shadow: none;\n",
"}\n",
".close:hover {\n",
" color: #de143d;\n",
" opacity: 1;\n",
"}\n",
"div.btn.btn-default.output_collapsed {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-color: #eeeeee;\n",
"}\n",
"div.btn.btn-default.output_collapsed:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border-color: #e9e9e9;\n",
"}\n",
"div.nbext-enable-btns .btn[disabled],\n",
"div.nbext-enable-btns .btn[disabled]:hover,\n",
".btn-default.disabled,\n",
".btn-default[disabled],\n",
".btn-default.disabled:hover,\n",
".btn-default[disabled]:hover,\n",
"fieldset[disabled] .btn-default:hover,\n",
".btn-default.disabled:focus,\n",
".btn-default[disabled]:focus,\n",
"fieldset[disabled] .btn-default:focus,\n",
".btn-default.disabled.focus,\n",
".btn-default[disabled].focus,\n",
"fieldset[disabled] .btn-default.focus {\n",
" color: #4a4a4a;\n",
" background: #e8e8e8;\n",
" background-color: #e8e8e8;\n",
" border-color: #e8e8e8;\n",
"}\n",
".input-group-addon {\n",
" padding: 2px 5px;\n",
" font-size: 12.0pt;\n",
" font-weight: normal;\n",
" height: auto;\n",
" color: #303030;\n",
" text-align: center;\n",
" background-color: #ffffff;\n",
" border: none;\n",
"}\n",
".btn-group > .btn + .dropdown-toggle {\n",
" padding-left: 8px;\n",
" padding-right: 8px;\n",
" height: 100%;\n",
" border-left: 2px solid #ff7823 !important;\n",
"}\n",
".btn-group > .btn + .dropdown-toggle:hover {\n",
" border-left: 2px solid #ff7823 !important;\n",
"}\n",
".input-group-btn {\n",
" position: relative;\n",
" font-size: inherit;\n",
" white-space: nowrap;\n",
"}\n",
".input-group-btn:first-child > .btn,\n",
".input-group-btn:first-child > .btn-group {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: 1px solid #ebebeb;\n",
" margin: 2px;\n",
" font-size: inherit;\n",
"}\n",
".input-group-btn:first-child > .btn:hover,\n",
".input-group-btn:first-child > .btn-group:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border: 1px solid #e9e9e9;\n",
" margin: 2px;\n",
" font-size: inherit;\n",
"}\n",
"div.modal .btn-group > .btn:first-child {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: 1px solid #ebebeb;\n",
" margin-top: 0px !important;\n",
" margin-left: 0px;\n",
" margin-bottom: 2px;\n",
"}\n",
"div.modal .btn-group > .btn:first-child:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border: 1px solid #e9e9e9;\n",
"}\n",
"div.modal > button,\n",
"div.modal-footer > button {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-color: #eeeeee;\n",
"}\n",
"div.modal > button:hover,\n",
"div.modal-footer > button:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border-color: #e9e9e9;\n",
"}\n",
".modal-content {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" position: relative;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: none;\n",
" border-radius: 1px;\n",
" background-clip: padding-box;\n",
" outline: none;\n",
"}\n",
".modal-header {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" color: #303030;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-color: rgba(180,180,180,.30);\n",
" padding: 12px;\n",
" min-height: 16.4286px;\n",
"}\n",
".modal-content h4 {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 16pt;\n",
" color: #303030;\n",
" padding: 5px;\n",
"}\n",
".modal-body {\n",
" background-color: #ffffff;\n",
" position: relative;\n",
" padding: 15px;\n",
"}\n",
".modal-footer {\n",
" padding: 10px;\n",
" text-align: right;\n",
" background-color: #fafafa;\n",
" border-top: 1px solid rgba(180,180,180,.30);\n",
"}\n",
".alert-info {\n",
" background-color: #fdfdfd;\n",
" border-color: rgba(180,180,180,.30);\n",
" color: #303030;\n",
"}\n",
".modal-header .close {\n",
" margin-top: -5px;\n",
" font-size: 25pt;\n",
"}\n",
".modal-backdrop,\n",
".modal-backdrop.in {\n",
" opacity: 0.85;\n",
" background-color: #d6d6d6;\n",
"}\n",
"div.panel,\n",
"div.panel-default,\n",
".panel,\n",
".panel-default {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" background-color: #fafafa;\n",
" color: #303030;\n",
" margin-bottom: 14px;\n",
" border: 0;\n",
" box-shadow: none;\n",
"}\n",
"div.panel > .panel-heading,\n",
"div.panel-default > .panel-heading {\n",
" font-size: 14pt;\n",
" color: #303030;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: 0;\n",
"}\n",
".modal .modal-dialog {\n",
" min-width: 950px;\n",
" margin: 50px auto;\n",
"}\n",
"div.container-fluid {\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
" padding-left: 7px;\n",
" padding-right: 12px;\n",
"}\n",
"div.form-control,\n",
".form-control {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: inherit;\n",
" color: #303030;\n",
" background-color: #ffffff;\n",
" border: 2px solid #e7e7e7;\n",
" margin-left: 2px;\n",
" height: auto;\n",
" box-shadow: none;\n",
" padding: 6px 12px;\n",
" transition: border-color 0.15s ease-in-out 0s, box-shadow 0.15s ease-in-out 0s;\n",
"}\n",
".form-group.list-group-item {\n",
" color: #303030;\n",
" background-color: #fafafa;\n",
" border-color: rgba(180,180,180,.30);\n",
" margin-bottom: 0px;\n",
"}\n",
"input,\n",
"button,\n",
"select,\n",
"textarea {\n",
" background-color: #ffffff;\n",
" font-weight: normal;\n",
" border: 1px solid rgba(180,180,180,.30);\n",
"}\n",
"select.form-control.select-xs {\n",
" height: auto;\n",
"}\n",
"div.output.output_scroll {\n",
" box-shadow: none;\n",
"}\n",
"::-webkit-scrollbar-track {\n",
" -webkit-box-shadow: inset 0 0 6px rgba(0,0,0,0.11);\n",
" background-color: #d0d0d0;\n",
" border-radius: 6px;\n",
"}\n",
"::-webkit-scrollbar {\n",
" width: 14px;\n",
" height: 20px;\n",
" background-color: #d0d0d0;\n",
" border-radius: 6px;\n",
"}\n",
"::-webkit-scrollbar-thumb {\n",
" background-color: #ffffff;\n",
" background-image: -webkit-gradient(linear,40% 0%,75% 86%,from(#ff6b0f ),color-stop(0.5,#ff8b42 ),to(#ff6b0f ));\n",
" min-height: 100px;\n",
" border-radius: 2px;\n",
"}\n",
"div.input_area {\n",
" background-color: #efefef;\n",
" padding-right: 1.2em;\n",
" border: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-top-right-radius: 2px;\n",
" border-bottom-left-radius: 0px;\n",
" border-bottom-right-radius: 0px;\n",
"}\n",
"div.cell {\n",
" padding: 0px;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
" border: medium solid #ffffff;\n",
" border-top-right-radius: 2px;\n",
" border-top-left-radius: 2px;\n",
"}\n",
"div.cell.selected {\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
" border: medium solid #ff7823;\n",
" padding: 0px;\n",
" border-top-right-radius: 2px;\n",
" border-top-left-radius: 2px;\n",
"}\n",
".edit_mode div.cell.selected {\n",
" padding: 0px;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
" border: medium solid #ffd5bb;\n",
" border-top-right-radius: 2px;\n",
" border-top-left-radius: 2px;\n",
"}\n",
"div.cell.edit_mode {\n",
" padding: 0px;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
" border: medium solid #ffd5bb;\n",
" border-top-right-radius: 2px;\n",
" border-top-left-radius: 2px;\n",
"}\n",
"div.prompt,\n",
".prompt {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 9.5pt;\n",
" font-weight: normal;\n",
" color: #aaaaaa;\n",
" line-height: 170%;\n",
" padding: 0px;\n",
" padding-top: 4px;\n",
" padding-left: .25em;\n",
" text-align: left !important;\n",
" min-width: 12ex;\n",
" width: 12ex;\n",
"}\n",
"div.prompt.input_prompt {\n",
" background-color: #efefef;\n",
" border-right: 2px solid rgba(240,147,43,.50);\n",
" border-top-left-radius: 2px;\n",
" border-top-right-radius: 0px;\n",
" border-bottom-left-radius: 0px;\n",
" border-bottom-right-radius: 0px;\n",
" min-width: 12ex;\n",
" width: 12ex !important;\n",
"}\n",
"div.output_wrapper {\n",
" background-color: #ffffff;\n",
" border: 0px;\n",
" margin-bottom: 0em;\n",
" margin-top: 0em;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-bottom-left-radius: 2px;\n",
" border-bottom-right-radius: 2px;\n",
"}\n",
"div.output_subarea.output_text.output_stream.output_stdout,\n",
"div.output_subarea.output_text {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 10.0pt;\n",
" line-height: 150% !important;\n",
" background-color: #ffffff;\n",
" color: #303030;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-bottom-left-radius: 2px;\n",
" border-bottom-right-radius: 2px;\n",
"}\n",
"div.output_area pre {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 10.0pt;\n",
" line-height: 150% !important;\n",
" color: #303030;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-bottom-left-radius: 2px;\n",
" border-bottom-right-radius: 2px;\n",
"}\n",
"div.output_area {\n",
" display: -webkit-box;\n",
"}\n",
"div.output_html {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 10.0pt;\n",
" color: #353535;\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
"}\n",
"div.output_subarea {\n",
" overflow-x: auto;\n",
" padding: .8em;\n",
" -webkit-box-flex: 1;\n",
" -moz-box-flex: 1;\n",
" box-flex: 1;\n",
" flex: 1;\n",
" max-width: 90%;\n",
"}\n",
"div.prompt.output_prompt {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 9.5pt;\n",
" background-color: #ffffff;\n",
" color: #ffffff;\n",
" border-bottom-left-radius: 2px;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-bottom-right-radius: 0px;\n",
" min-width: 12ex;\n",
" width: 12ex;\n",
"}\n",
"div.out_prompt_overlay.prompt {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 9.5pt;\n",
" background-color: #ffffff;\n",
" border-bottom-left-radius: 2px;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" border-bottom-right-radius: 0px;\n",
" min-width: 12ex;\n",
" width: 12ex;\n",
"}\n",
"div.out_prompt_overlay.prompt:hover {\n",
" background-color: #ffffff;\n",
" box-shadow: #e8e8e8 2px 1px 2px 2.5px inset;\n",
" border-bottom-left-radius: 2px;\n",
" -webkit-border-: 2px;\n",
" -moz-border-radius: 2px;\n",
" border-top-right-radius: 0px;\n",
" border-top-left-radius: 0px;\n",
" min-width: 12ex;\n",
" width: 12ex !important;\n",
"}\n",
"div.text_cell,\n",
"div.text_cell_render pre,\n",
"div.text_cell_render {\n",
" font-family: \"Lora\", serif;\n",
" font-size: 20pt;\n",
" line-height: 170% !important;\n",
" color: #353535;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border-radius: 2px;\n",
" min-height: 500px;\n",
"}\n",
"div.cell.text_cell.rendered.selected {\n",
" font-family: \"Lora\", serif;\n",
" border: medium solid #126dce;\n",
" line-height: 170% !important;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border-radius: 2px;\n",
" \n",
"}\n",
"div.cell.text_cell.unrendered.selected {\n",
" font-family: \"Lora\", serif;\n",
" line-height: 170% !important;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border: medium solid #126dce;\n",
" border-radius: 2px;\n",
"}\n",
"div.cell.text_cell.selected {\n",
" font-family: \"Lora\", serif;\n",
" line-height: 170% !important;\n",
" border: medium solid #126dce;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border-radius: 2px;\n",
"}\n",
".edit_mode div.cell.text_cell.selected {\n",
" font-family: \"Lora\", serif;\n",
" line-height: 170% !important;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border: medium solid #87b0db;\n",
" border-radius: 2px;\n",
"}\n",
"div.text_cell.unrendered,\n",
"div.text_cell.unrendered.selected,\n",
"div.edit_mode div.text_cell.unrendered {\n",
" font-family: \"Lora\", serif;\n",
" line-height: 170% !important;\n",
" background: #ffffff;\n",
" background-color: #ffffff;\n",
" border-radius: 2px;\n",
"}\n",
"div.cell.text_cell.rendered .input_prompt {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 9.5pt;\n",
" font-weight: normal;\n",
" color: #aaaaaa;\n",
" text-align: left !important;\n",
" min-width: 0ex;\n",
" width: 0ex !important;\n",
" background-color: #ffffff;\n",
" border-right: 2px solid transparent;\n",
"}\n",
"div.cell.text_cell.unrendered .input_prompt {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 9.5pt;\n",
" font-weight: normal;\n",
" color: #aaaaaa;\n",
" text-align: left !important;\n",
" min-width: 0ex;\n",
" width: 0ex !important;\n",
" border-right: 2px solid transparent;\n",
"}\n",
"div.rendered_html code {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" padding-top: 3px;\n",
" color: #303030;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
"}\n",
"pre,\n",
"code,\n",
"kbd,\n",
"samp {\n",
" white-space: pre-wrap;\n",
"}\n",
"code {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt !important;\n",
" line-height: 170% !important;\n",
" color: #353535;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
"}\n",
"kbd {\n",
" padding: 4px;\n",
" font-size: 11pt;\n",
" color: #303030;\n",
" background-color: #efefef;\n",
" border: 0;\n",
" box-shadow: none;\n",
"}\n",
"pre {\n",
" display: block;\n",
" padding: 8.5px;\n",
" margin: 0 0 9px;\n",
" font-size: 12.0pt;\n",
" line-height: 1.42857143;\n",
" color: #303030;\n",
" background-color: #efefef;\n",
" border: 1px solid #e7e7e7;\n",
" border-radius: 2px;\n",
"}\n",
"div.rendered_html {\n",
" color: #353535;\n",
"}\n",
"div.rendered_html pre,\n",
"div.text_cell_render pre {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt !important;\n",
" line-height: 170% !important;\n",
" color: #353535;\n",
" background: #efefef;\n",
" background-color: #efefef;\n",
" border: 2px #e7e7e7 solid;\n",
" max-width: 86%;\n",
" border-radius: 2px;\n",
" padding: 5px;\n",
" min-height: 1px;\n",
"}\n",
"div.text_cell_render h1,\n",
"div.rendered_html h1,\n",
"div.text_cell_render h2,\n",
"div.rendered_html h2,\n",
"div.text_cell_render h3,\n",
"div.rendered_html h3,\n",
"div.text_cell_render h4,\n",
"div.rendered_html h4,\n",
"div.text_cell_render h5,\n",
"div.rendered_html h5 {\n",
" font-family: \"Exo_2\", sans-serif;\n",
"}\n",
".rendered_html h1:first-child,\n",
".rendered_html h2:first-child,\n",
".rendered_html h3:first-child,\n",
".rendered_html h4:first-child,\n",
".rendered_html h5:first-child,\n",
".rendered_html h6:first-child {\n",
" margin-top: 0.2em;\n",
"}\n",
".rendered_html h1,\n",
".text_cell_render h1 {\n",
" color: #126dce;\n",
" font-size: 220%;\n",
" text-align: center;\n",
" font-weight: lighter;\n",
"}\n",
".rendered_html h2,\n",
".text_cell_render h2 {\n",
" text-align: left;\n",
" font-size: 170%;\n",
" color: #126dce;\n",
" font-style: normal;\n",
" font-weight: lighter;\n",
"}\n",
".rendered_html h3,\n",
".text_cell_render h3 {\n",
" font-size: 150%;\n",
" color: #126dce;\n",
" font-weight: lighter;\n",
" text-decoration: italic;\n",
" font-style: normal;\n",
"}\n",
".rendered_html h4,\n",
".text_cell_render h4 {\n",
" font-size: 120%;\n",
" color: #126dce;\n",
" font-weight: underline;\n",
" font-style: normal;\n",
"}\n",
".rendered_html h5,\n",
".text_cell_render h5 {\n",
" font-size: 100%;\n",
" color: #2f2f2f;\n",
" font-weight: lighter;\n",
" text-decoration: underline;\n",
"}\n",
".rendered_html table,\n",
".rendered_html tr,\n",
".rendered_html td {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 10.0pt !important;\n",
" line-height: 150% !important;\n",
" border: 1px solid #d6d6d6;\n",
" color: #353535;\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
"}\n",
"table.dataframe,\n",
".rendered_html tr,\n",
".dataframe * {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 10.0pt !important;\n",
" border: 1px solid #d6d6d6;\n",
"}\n",
".dataframe th,\n",
".rendered_html th {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 11pt !important;\n",
" font-weight: bold;\n",
" border: 1px solid #c4c4c4;\n",
" background: #eeeeee;\n",
"}\n",
".dataframe td,\n",
".rendered_html td {\n",
" font-family: \"Fira Mono\", monospace;\n",
" font-size: 10.0pt !important;\n",
" color: #353535;\n",
" background: #ffffff;\n",
" border: 1px solid #d6d6d6;\n",
" text-align: left;\n",
" min-width: 4em;\n",
"}\n",
".dataframe-summary-row tr:last-child,\n",
".dataframe-summary-col td:last-child {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 11pt !important;\n",
" font-weight: bold;\n",
" color: #353535;\n",
" border: 1px solid #d6d6d6;\n",
" background: #eeeeee;\n",
"}\n",
"div.widget-area {\n",
" background-color: #ffffff;\n",
" background: #ffffff;\n",
" color: #303030;\n",
"}\n",
"div.widget-area a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" font-weight: normal;\n",
" font-style: normal;\n",
" color: #303030;\n",
" text-shadow: none !important;\n",
"}\n",
"div.widget-area a:hover,\n",
"div.widget-area a:focus {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12.0pt;\n",
" font-weight: normal;\n",
" font-style: normal;\n",
" color: #2f2f2f;\n",
" background: rgba(180,180,180,.14);\n",
" background-color: rgba(180,180,180,.14);\n",
" border-color: transparent;\n",
" background-image: none;\n",
" text-shadow: none !important;\n",
"}\n",
"div.widget_item.btn-group > button.btn.btn-default.widget-combo-btn,\n",
"div.widget_item.btn-group > button.btn.btn-default.widget-combo-btn:hover {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border: 2px solid #eeeeee !important;\n",
" font-size: inherit;\n",
" z-index: 0;\n",
"}\n",
"div.jupyter-widgets.widget-hprogress.widget-hbox,\n",
"div.widget-hbox,\n",
".widget-hbox {\n",
" display: inline-table;\n",
"}\n",
"div.jupyter-widgets.widget-hprogress.widget-hbox .widget-label,\n",
"div.widget-hbox .widget-label,\n",
".widget-hbox .widget-label {\n",
" font-size: 11pt;\n",
" min-width: 100%;\n",
" padding-top: 5px;\n",
" padding-right: 10px;\n",
" text-align: left;\n",
" vertical-align: text-top;\n",
"}\n",
".progress {\n",
" overflow: hidden;\n",
" height: 20px;\n",
" margin-bottom: 10px;\n",
" padding-left: 10px;\n",
" background-color: #c6c6c6;\n",
" border-radius: 4px;\n",
" -webkit-box-shadow: none;\n",
" box-shadow: none;\n",
"}\n",
".rendered_html :link {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 100%;\n",
" color: #2c85f7;\n",
" text-decoration: underline;\n",
"}\n",
".rendered_html :visited,\n",
".rendered_html :visited:active,\n",
".rendered_html :visited:focus {\n",
" color: #2e6eb2;\n",
"}\n",
".rendered_html :visited:hover,\n",
".rendered_html :link:hover {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 100%;\n",
" color: #eb6a18;\n",
"}\n",
"a.anchor-link:link:hover {\n",
" font-size: inherit;\n",
" color: #eb6a18;\n",
"}\n",
"a.anchor-link:link {\n",
" font-size: inherit;\n",
" text-decoration: none;\n",
" padding: 0px 20px;\n",
" visibility: none;\n",
" color: #126dce;\n",
"}\n",
".navbar-text {\n",
" margin-top: 4px;\n",
" margin-bottom: 0px;\n",
"}\n",
"div#nbextensions-configurator-container.container,\n",
"#nbextensions-configurator-container.container {\n",
" width: 100%;\n",
" margin-right: auto;\n",
" margin-left: auto;\n",
"}\n",
"div.nbext-selector > nav > .nav > li > a {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12pt;\n",
"}\n",
"div.nbext-readme > .nbext-readme-contents > .rendered_html {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 12pt;\n",
" line-height: 145%;\n",
" padding: 1em 1em;\n",
" color: #353535;\n",
" background-color: #ffffff;\n",
" -webkit-box-shadow: none;\n",
" -moz-box-shadow: none;\n",
" box-shadow: none;\n",
"}\n",
".nbext-icon,\n",
".nbext-desc,\n",
".nbext-compat-div,\n",
".nbext-enable-btns,\n",
".nbext-params {\n",
" margin-bottom: 8px;\n",
" font-size: 12pt;\n",
"}\n",
"div.nbext-readme > .nbext-readme-contents {\n",
" padding: 0;\n",
" overflow-y: hidden;\n",
"}\n",
"div.nbext-readme > .nbext-readme-contents:not(:empty) {\n",
" margin-top: 0.5em;\n",
" margin-bottom: 2em;\n",
" border: none;\n",
" border-top-color: rgba(180,180,180,.30);\n",
"}\n",
".nbext-showhide-incompat {\n",
" padding-bottom: 0.5em;\n",
" color: #4a4a4a;\n",
" font-size: 12.0pt;\n",
"}\n",
".shortcut_key,\n",
"span.shortcut_key {\n",
" display: inline-block;\n",
" width: 16ex;\n",
" text-align: right;\n",
" font-family: monospace;\n",
"}\n",
"mark,\n",
".mark {\n",
" background-color: #ffffff;\n",
" color: #353535;\n",
" padding: .15em;\n",
"}\n",
"a.text-warning,\n",
"a.text-warning:hover {\n",
" color: #aaaaaa;\n",
"}\n",
"a.text-warning.bg-warning {\n",
" background-color: #ffffff;\n",
"}\n",
"span.bg-success.text-success {\n",
" background-color: transparent;\n",
" color: #009e07;\n",
"}\n",
"span.bg-danger.text-danger {\n",
" background-color: #ffffff;\n",
" color: #de143d;\n",
"}\n",
".has-success .input-group-addon {\n",
" color: #009e07;\n",
" border-color: transparent;\n",
" background: inherit;\n",
" background-color: rgba(83,180,115,.10);\n",
"}\n",
".has-success .form-control {\n",
" border-color: #009e07;\n",
" -webkit-box-shadow: inset 0 1px 1px rgba(0,0,0,0.025);\n",
" box-shadow: inset 0 1px 1px rgba(0,0,0,0.025);\n",
"}\n",
".has-error .input-group-addon {\n",
" color: #de143d;\n",
" border-color: transparent;\n",
" background: inherit;\n",
" background-color: rgba(192,57,67,.10);\n",
"}\n",
".has-error .form-control {\n",
" border-color: #de143d;\n",
" -webkit-box-shadow: inset 0 1px 1px rgba(0,0,0,0.025);\n",
" box-shadow: inset 0 1px 1px rgba(0,0,0,0.025);\n",
"}\n",
".kse-input-group-pretty > kbd {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" color: #303030;\n",
" font-weight: normal;\n",
" background: transparent;\n",
"}\n",
".kse-input-group-pretty > kbd {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" color: #303030;\n",
" font-weight: normal;\n",
" background: transparent;\n",
"}\n",
"div.nbext-enable-btns .btn[disabled],\n",
"div.nbext-enable-btns .btn[disabled]:hover,\n",
".btn-default.disabled,\n",
".btn-default[disabled] {\n",
" background: #e8e8e8;\n",
" background-color: #e8e8e8;\n",
" color: #282828;\n",
"}\n",
"label#Keyword-Filter {\n",
" display: none;\n",
"}\n",
".nav-pills > li.active > a,\n",
".nav-pills > li.active > a:hover,\n",
".nav-pills > li.active > a:focus {\n",
" color: #ffffff;\n",
" background-color: #126dce;\n",
"}\n",
".input-group .nbext-list-btn-add,\n",
".input-group-btn:last-child > .btn-group > .btn {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-color: #eeeeee;\n",
"}\n",
".input-group .nbext-list-btn-add:hover,\n",
".input-group-btn:last-child > .btn-group > .btn:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border-color: #e9e9e9;\n",
"}\n",
"#notebook-container > div.cell.code_cell.rendered.selected > div.widget-area > div.widget-subarea > div > div.widget_item.btn-group > button.btn.btn-default.dropdown-toggle.widget-combo-carrot-btn {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-color: #eeeeee;\n",
"}\n",
"#notebook-container > div.cell.code_cell.rendered.selected > div.widget-area > div.widget-subarea > div > div.widget_item.btn-group > button.btn.btn-default.dropdown-toggle.widget-combo-carrot-btn:hover {\n",
" background: #e9e9e9;\n",
" background-color: #e9e9e9;\n",
" border-color: #e9e9e9;\n",
"}\n",
"input.raw_input {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt !important;\n",
" color: #303030;\n",
" background-color: #efefef;\n",
" border-color: #ececec;\n",
" background: #ececec;\n",
" width: auto;\n",
" vertical-align: baseline;\n",
" padding: 0em 0.25em;\n",
" margin: 0em 0.25em;\n",
" -webkit-box-shadow: none;\n",
" box-shadow: none;\n",
"}\n",
"audio,\n",
"video {\n",
" display: inline;\n",
" vertical-align: middle;\n",
" align-content: center;\n",
" margin-left: 20%;\n",
"}\n",
".cmd-palette .modal-body {\n",
" padding: 0px;\n",
" margin: 0px;\n",
"}\n",
".cmd-palette form {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
"}\n",
".typeahead-field input:last-child,\n",
".typeahead-hint {\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" z-index: 1;\n",
"}\n",
".typeahead-field input {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" color: #303030;\n",
" border: none;\n",
" font-size: 28pt;\n",
" display: inline-block;\n",
" line-height: inherit;\n",
" padding: 3px 10px;\n",
" height: 70px;\n",
"}\n",
".typeahead-select {\n",
" background-color: #eeeeee;\n",
"}\n",
"body > div.modal.cmd-palette.typeahead-field {\n",
" display: table;\n",
" border-collapse: separate;\n",
" background-color: #fafafa;\n",
"}\n",
".typeahead-container button {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 28pt;\n",
" background-color: #d0d0d0;\n",
" border: none;\n",
" display: inline-block;\n",
" line-height: inherit;\n",
" padding: 3px 10px;\n",
" height: 70px;\n",
"}\n",
".typeahead-search-icon {\n",
" min-width: 40px;\n",
" min-height: 55px;\n",
" display: block;\n",
" vertical-align: middle;\n",
" text-align: center;\n",
"}\n",
".typeahead-container button:focus,\n",
".typeahead-container button:hover {\n",
" color: #2f2f2f;\n",
" background-color: #ff7823;\n",
" border-color: #ff7823;\n",
"}\n",
".typeahead-list > li.typeahead-group.active > a,\n",
".typeahead-list > li.typeahead-group > a,\n",
".typeahead-list > li.typeahead-group > a:focus,\n",
".typeahead-list > li.typeahead-group > a:hover {\n",
" display: none;\n",
"}\n",
".typeahead-dropdown > li > a,\n",
".typeahead-list > li > a {\n",
" color: #303030;\n",
" text-decoration: none;\n",
"}\n",
".typeahead-dropdown,\n",
".typeahead-list {\n",
" font-family: \"Exo_2\", sans-serif;\n",
" font-size: 13pt;\n",
" color: #303030;\n",
" background-color: #ffffff;\n",
" border: none;\n",
" background-clip: padding-box;\n",
" margin-top: 0px;\n",
" padding: 3px 2px 3px 0px;\n",
" line-height: 1.7;\n",
"}\n",
".typeahead-dropdown > li.active > a,\n",
".typeahead-dropdown > li > a:focus,\n",
".typeahead-dropdown > li > a:hover,\n",
".typeahead-list > li.active > a,\n",
".typeahead-list > li > a:focus,\n",
".typeahead-list > li > a:hover {\n",
" color: #2f2f2f;\n",
" background-color: #fafafa;\n",
" border-color: #fafafa;\n",
"}\n",
".command-shortcut:before {\n",
" content: \"(command)\";\n",
" padding-right: 3px;\n",
" color: #aaaaaa;\n",
"}\n",
".edit-shortcut:before {\n",
" content: \"(edit)\";\n",
" padding-right: 3px;\n",
" color: #aaaaaa;\n",
"}\n",
"ul.typeahead-list i {\n",
" margin-left: 1px;\n",
" width: 18px;\n",
" margin-right: 10px;\n",
"}\n",
"ul.typeahead-list {\n",
" max-height: 50vh;\n",
" overflow: auto;\n",
"}\n",
".typeahead-list > li {\n",
" position: relative;\n",
" border: none;\n",
"}\n",
"div.input.typeahead-hint,\n",
"input.typeahead-hint,\n",
"body > div.modal.cmd-palette.in > div > div > div > form > div > div.typeahead-field > span.typeahead-query > input.typeahead-hint {\n",
" color: #aaaaaa !important;\n",
" background-color: transparent;\n",
" padding: 3px 10px;\n",
"}\n",
".typeahead-dropdown > li > a,\n",
".typeahead-list > li > a {\n",
" display: block;\n",
" padding: 5px;\n",
" clear: both;\n",
" font-weight: 400;\n",
" line-height: 1.7;\n",
" border: 1px solid #ffffff;\n",
" border-bottom-color: rgba(180,180,180,.30);\n",
"}\n",
"body > div.modal.cmd-palette.in > div {\n",
" min-width: 750px;\n",
" margin: 150px auto;\n",
"}\n",
".typeahead-container strong {\n",
" font-weight: bolder;\n",
" color: #ff7823;\n",
"}\n",
"#find-and-replace #replace-preview .match,\n",
"#find-and-replace #replace-preview .insert {\n",
" color: #ffffff;\n",
" background-color: #ff7823;\n",
" border-color: #ff7823;\n",
" border-style: solid;\n",
" border-width: 1px;\n",
" border-radius: 0px;\n",
"}\n",
"#find-and-replace #replace-preview .replace .match {\n",
" background-color: #de143d;\n",
" border-color: #de143d;\n",
" border-radius: 0px;\n",
"}\n",
"#find-and-replace #replace-preview .replace .insert {\n",
" background-color: #009e07;\n",
" border-color: #009e07;\n",
" border-radius: 0px;\n",
"}\n",
"div.CodeMirror,\n",
"div.CodeMirror pre {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" line-height: 170%;\n",
" color: #303030;\n",
"}\n",
"div.CodeMirror-lines {\n",
" padding-bottom: .6em;\n",
" padding-left: .5em;\n",
" padding-right: 1.5em;\n",
" padding-top: 4px;\n",
"}\n",
"span.ansiblack {\n",
" color: #dc4384;\n",
"}\n",
"span.ansiblue {\n",
" color: #009e07;\n",
"}\n",
"span.ansigray {\n",
" color: #ff7823;\n",
"}\n",
"span.ansigreen {\n",
" color: #333333;\n",
"}\n",
"span.ansipurple {\n",
" color: #653bc5;\n",
"}\n",
"span.ansicyan {\n",
" color: #055be0;\n",
"}\n",
"span.ansiyellow {\n",
" color: #ff7823;\n",
"}\n",
"span.ansired {\n",
" color: #de143d;\n",
"}\n",
"div.output-stderr {\n",
" background-color: #ebb5b7;\n",
"}\n",
"div.output-stderr pre {\n",
" color: #000000;\n",
"}\n",
"div.js-error {\n",
" color: #de143d;\n",
"}\n",
".ipython_tooltip {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" line-height: 170%;\n",
" border: 2px solid #dadada;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" border-radius: 2px;\n",
" overflow-x: visible;\n",
" overflow-y: visible;\n",
" box-shadow: none;\n",
" position: absolute;\n",
" z-index: 1000;\n",
"}\n",
".ipython_tooltip .tooltiptext pre {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" line-height: 170%;\n",
" background: #eeeeee;\n",
" background-color: #eeeeee;\n",
" color: #303030;\n",
" overflow-x: visible;\n",
" overflow-y: visible;\n",
" max-width: 900px;\n",
"}\n",
"div#tooltip.ipython_tooltip {\n",
" overflow-x: wrap;\n",
" overflow-y: visible;\n",
" max-width: 800px;\n",
"}\n",
"div.tooltiptext.bigtooltip {\n",
" overflow-x: visible;\n",
" overflow-y: scroll;\n",
" height: 400px;\n",
" max-width: 800px;\n",
"}\n",
".cm-s-ipython.CodeMirror {\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" background: #efefef;\n",
" color: #303030;\n",
" border-radius: 2px;\n",
" font-style: normal;\n",
" font-weight: normal;\n",
"}\n",
".cm-s-ipython div.CodeMirror-selected {\n",
" background: #e0e1e3;\n",
"}\n",
".cm-s-ipython .CodeMirror-gutters {\n",
" background: #e0e1e3;\n",
" border: none;\n",
" border-radius: 0px;\n",
"}\n",
".cm-s-ipython .CodeMirror-linenumber {\n",
" color: #aaaaaa;\n",
"}\n",
".cm-s-ipython .CodeMirror-cursor {\n",
" border-left: 2px solid #ff711a;\n",
"}\n",
".cm-s-ipython span.cm-comment {\n",
" color: #8d8d8d;\n",
" font-style: italic;\n",
"}\n",
".cm-s-ipython span.cm-atom {\n",
" color: #055be0;\n",
"}\n",
".cm-s-ipython span.cm-number {\n",
" color: #ff8132;\n",
"}\n",
".cm-s-ipython span.cm-property {\n",
" color: #e22978;\n",
"}\n",
".cm-s-ipython span.cm-attribute {\n",
" color: #de143d;\n",
"}\n",
".cm-s-ipython span.cm-keyword {\n",
" color: #713bc5;\n",
" font-weight: normal;\n",
"}\n",
".cm-s-ipython span.cm-string {\n",
" color: #009e07;\n",
"}\n",
".cm-s-ipython span.cm-meta {\n",
" color: #aa22ff;\n",
"}\n",
".cm-s-ipython span.cm-operator {\n",
" color: #055be0;\n",
"}\n",
".cm-s-ipython span.cm-builtin {\n",
" color: #e22978;\n",
"}\n",
".cm-s-ipython span.cm-variable {\n",
" color: #303030;\n",
"}\n",
".cm-s-ipython span.cm-variable-2 {\n",
" color: #de143d;\n",
"}\n",
".cm-s-ipython span.cm-variable-3 {\n",
" color: #aa22ff;\n",
"}\n",
".cm-s-ipython span.cm-def {\n",
" color: #e22978;\n",
" font-weight: normal;\n",
"}\n",
".cm-s-ipython span.cm-error {\n",
" background: rgba(191,97,106,.40);\n",
"}\n",
".cm-s-ipython span.cm-tag {\n",
" color: #e22978;\n",
"}\n",
".cm-s-ipython span.cm-link {\n",
" color: #ff7823;\n",
"}\n",
".cm-s-ipython span.cm-storage {\n",
" color: #055be0;\n",
"}\n",
".cm-s-ipython span.cm-entity {\n",
" color: #e22978;\n",
"}\n",
".cm-s-ipython span.cm-quote {\n",
" color: #009e07;\n",
"}\n",
"div.CodeMirror span.CodeMirror-matchingbracket {\n",
" color: #1c1c1c;\n",
" background-color: rgba(30,112,199,.30);\n",
"}\n",
"div.CodeMirror span.CodeMirror-nonmatchingbracket {\n",
" color: #1c1c1c;\n",
" background: rgba(191,97,106,.40) !important;\n",
"}\n",
"div.cell.text_cell .cm-s-default .cm-header {\n",
" color: #126dce;\n",
"}\n",
"div.cell.text_cell .cm-s-default span.cm-variable-2 {\n",
" color: #353535;\n",
"}\n",
"div.cell.text_cell .cm-s-default span.cm-variable-3 {\n",
" color: #aa22ff;\n",
"}\n",
".cm-s-default span.cm-comment {\n",
" color: #8d8d8d;\n",
"}\n",
".cm-s-default .cm-tag {\n",
" color: #009fb7;\n",
"}\n",
".cm-s-default .cm-builtin {\n",
" color: #e22978;\n",
"}\n",
".cm-s-default .cm-string {\n",
" color: #009e07;\n",
"}\n",
".cm-s-default .cm-keyword {\n",
" color: #713bc5;\n",
"}\n",
".cm-s-default .cm-number {\n",
" color: #ff8132;\n",
"}\n",
".cm-s-default .cm-error {\n",
" color: #055be0;\n",
"}\n",
".CodeMirror-cursor {\n",
" border-left: 2px solid #ff711a;\n",
" border-right: none;\n",
" width: 0;\n",
"}\n",
".cm-s-default div.CodeMirror-selected {\n",
" background: #e0e1e3;\n",
"}\n",
".cm-s-default .cm-selected {\n",
" background: #e0e1e3;\n",
"}\n",
".completions {\n",
" position: absolute;\n",
" z-index: 110;\n",
" overflow: hidden;\n",
" border: medium solid #ff7823;\n",
" line-height: 1;\n",
"}\n",
".completions select {\n",
" background: #efefef;\n",
" outline: none;\n",
" border: none;\n",
" padding: 0px;\n",
" margin: 0px;\n",
" overflow: auto;\n",
" font-family: \"Droid Sans Mono\", monospace;\n",
" font-size: 11pt;\n",
" color: #303030;\n",
" width: auto;\n",
"}\n",
"/**\n",
"div#maintoolbar {\n",
"# display: none !important;\n",
"#}\n",
"##header-container {\n",
"# display: none !important;\n",
"#}\n",
"**/\n",
"\n",
"\n",
"/**********************************\n",
" MathJax Settings and Style Script\n",
"**********************************/\n",
".MathJax_Display,\n",
".MathJax nobr>span.math>span {\n",
" border: 0 !important;\n",
" font-size: 110% !important;\n",
" text-align: center !important;\n",
" margin: 0em !important;\n",
"}\n",
"/* Prevents MathJax from jittering */\n",
"/* cell position when cell is selected */\n",
".MathJax:focus, body :focus .MathJax {\n",
" display: inline-block !important;\n",
"}\n",
"\n",
"</style>\n",
"\n",
"\n",
"<script>\n",
" MathJax.Hub.Config({\n",
" \"HTML-CSS\": {\n",
" preferredFont: \"TeX\",\n",
" availableFonts: [\"STIX\",\"TeX\"],\n",
" styles: {\n",
" scale: 110,\n",
" \".MathJax_Display\": {\n",
" \"font-size\": \"110%\",\n",
" }\n",
" }\n",
" }\n",
"});\n",
"\n",
"$([IPython.events]).on('notebook_loaded.Notebook',function(){\n",
" $('#header').hide();\n",
" IPython.keyboard_manager.command_shortcuts.add_shortcut('ctrl-`',function (event) {\n",
" if (IPython.notebook.mode == 'command') {\n",
" $('#header').toggle();\n",
" return false;\n",
" }\n",
" return true;\n",
" });\n",
"});\n",
"\n",
"</script>\n",
"\n"
],
"text/plain": [
"<IPython.core.display.HTML object>"
]
},
"execution_count": 1,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"from IPython.core.display import HTML\n",
"HTML(open('../custom.css').read())"
]
}
],
"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.7.3"
}
},
"nbformat": 4,
"nbformat_minor": 1
}