day 81 - topological sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "from collections import deque\n",
    "from bokeh.plotting import figure, show, output_notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def topological_sort(graph):\n",
    "    topology = []\n",
    "    degree = {n: graph.in_degree(n) for n in graph.nodes()}\n",
    "\n",
    "    # nodes without incoming edges\n",
    "    queue = deque(n for n, d in degree.items() if not d)\n",
    "    \n",
    "    while queue:\n",
    "        n = queue.popleft()\n",
    "        topology.append(n)\n",
    "\n",
    "        # remove node's edges\n",
    "        for m in list(graph[n]):\n",
    "            degree[m] -= 1\n",
    "\n",
    "            # enqueue nodes with no incoming edges\n",
    "            if not degree[m]:\n",
    "                queue.append(m)\n",
    "\n",
    "    if len(topology) < len(graph):\n",
    "        raise ValueError('graph contains cycle')\n",
    "\n",
    "    return topology"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## run"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "graph = nx.DiGraph([\n",
    "    ('A', 'B'),\n",
    "    ('A', 'D'),\n",
    "    ('B', 'C'),\n",
    "    ('B', 'E'),\n",
    "    ('C', 'D'),\n",
    "    ('C', 'E'),\n",
    "    ('D', 'E'),\n",
    "    ('F', 'G'),\n",
    "])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['A', 'F', 'B', 'G', 'C', 'D', 'E']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "topology = topological_sort(graph)\n",
    "topology"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## plot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "n = len(topology)\n",
    "x = range(n)\n",
    "q = []\n",
    "\n",
    "for u, v in graph.edges():\n",
    "    x0 = topology.index(u)\n",
    "    x1 = topology.index(v)\n",
    "    yc = 0 if abs(x0 - x1) == 1 else -.7 if x0 & 1 else .7\n",
    "    q.append([x0, 0, x1, 0, (x0 + x1) / 2, yc])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <a href=\"http://bokeh.pydata.org\" target=\"_blank\" class=\"bk-logo bk-logo-small bk-logo-notebook\"></a>\n",
       "        <span id=\"69b50d06-2af0-443b-9604-e06bec647c92\">Loading BokehJS ...</span>\n",
       "    </div>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/javascript": [
       "\n",
       "(function(global) {\n",
       "  function now() {\n",
       "    return new Date();\n",
       "  }\n",
       "\n",
       "  var force = true;\n",
       "\n",
       "  if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "    window._bokeh_onload_callbacks = [];\n",
       "    window._bokeh_is_loading = undefined;\n",
       "  }\n",
       "\n",
       "\n",
       "  \n",
       "  if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "    window._bokeh_timeout = Date.now() + 5000;\n",
       "    window._bokeh_failed_load = false;\n",
       "  }\n",
       "\n",
       "  var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "     \"<div style='background-color: #fdd'>\\n\"+\n",
       "     \"<p>\\n\"+\n",
       "     \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "     \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "     \"</p>\\n\"+\n",
       "     \"<ul>\\n\"+\n",
       "     \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "     \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "     \"</ul>\\n\"+\n",
       "     \"<code>\\n\"+\n",
       "     \"from bokeh.resources import INLINE\\n\"+\n",
       "     \"output_notebook(resources=INLINE)\\n\"+\n",
       "     \"</code>\\n\"+\n",
       "     \"</div>\"}};\n",
       "\n",
       "  function display_loaded() {\n",
       "    if (window.Bokeh !== undefined) {\n",
       "      var el = document.getElementById(\"69b50d06-2af0-443b-9604-e06bec647c92\");\n",
       "      el.textContent = \"BokehJS \" + Bokeh.version + \" successfully loaded.\";\n",
       "    } else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(display_loaded, 100)\n",
       "    }\n",
       "  }\n",
       "\n",
       "  function run_callbacks() {\n",
       "    window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "    delete window._bokeh_onload_callbacks\n",
       "    console.info(\"Bokeh: all callbacks have finished\");\n",
       "  }\n",
       "\n",
       "  function load_libs(js_urls, callback) {\n",
       "    window._bokeh_onload_callbacks.push(callback);\n",
       "    if (window._bokeh_is_loading > 0) {\n",
       "      console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "      return null;\n",
       "    }\n",
       "    if (js_urls == null || js_urls.length === 0) {\n",
       "      run_callbacks();\n",
       "      return null;\n",
       "    }\n",
       "    console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "    window._bokeh_is_loading = js_urls.length;\n",
       "    for (var i = 0; i < js_urls.length; i++) {\n",
       "      var url = js_urls[i];\n",
       "      var s = document.createElement('script');\n",
       "      s.src = url;\n",
       "      s.async = false;\n",
       "      s.onreadystatechange = s.onload = function() {\n",
       "        window._bokeh_is_loading--;\n",
       "        if (window._bokeh_is_loading === 0) {\n",
       "          console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "          run_callbacks()\n",
       "        }\n",
       "      };\n",
       "      s.onerror = function() {\n",
       "        console.warn(\"failed to load library \" + url);\n",
       "      };\n",
       "      console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "      document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "    }\n",
       "  };var element = document.getElementById(\"69b50d06-2af0-443b-9604-e06bec647c92\");\n",
       "  if (element == null) {\n",
       "    console.log(\"Bokeh: ERROR: autoload.js configured with elementid '69b50d06-2af0-443b-9604-e06bec647c92' but no matching script tag was found. \")\n",
       "    return false;\n",
       "  }\n",
       "\n",
       "  var js_urls = [\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.js\", \"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.js\"];\n",
       "\n",
       "  var inline_js = [\n",
       "    function(Bokeh) {\n",
       "      Bokeh.set_log_level(\"info\");\n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "    },\n",
       "    \n",
       "    function(Bokeh) {\n",
       "      \n",
       "      document.getElementById(\"69b50d06-2af0-443b-9604-e06bec647c92\").textContent = \"BokehJS is loading...\";\n",
       "    },\n",
       "    function(Bokeh) {\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-0.12.5.min.css\");\n",
       "      console.log(\"Bokeh: injecting CSS: https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n",
       "      Bokeh.embed.inject_css(\"https://cdn.pydata.org/bokeh/release/bokeh-widgets-0.12.5.min.css\");\n",
       "    }\n",
       "  ];\n",
       "\n",
       "  function run_inline_js() {\n",
       "    \n",
       "    if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "      for (var i = 0; i < inline_js.length; i++) {\n",
       "        inline_js[i](window.Bokeh);\n",
       "      }if (force === true) {\n",
       "        display_loaded();\n",
       "      }} else if (Date.now() < window._bokeh_timeout) {\n",
       "      setTimeout(run_inline_js, 100);\n",
       "    } else if (!window._bokeh_failed_load) {\n",
       "      console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "      window._bokeh_failed_load = true;\n",
       "    } else if (force !== true) {\n",
       "      var cell = $(document.getElementById(\"69b50d06-2af0-443b-9604-e06bec647c92\")).parents('.cell').data().cell;\n",
       "      cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "    }\n",
       "\n",
       "  }\n",
       "\n",
       "  if (window._bokeh_is_loading === 0) {\n",
       "    console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "    run_inline_js();\n",
       "  } else {\n",
       "    load_libs(js_urls, function() {\n",
       "      console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "      run_inline_js();\n",
       "    });\n",
       "  }\n",
       "}(this));"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "\n",
       "\n",
       "    <div class=\"bk-root\">\n",
       "        <div class=\"bk-plotdiv\" id=\"69f390bf-eb11-4808-bc62-94006a2b2cc4\"></div>\n",
       "    </div>\n",
       "<script type=\"text/javascript\">\n",
       "  \n",
       "  (function(global) {\n",
       "    function now() {\n",
       "      return new Date();\n",
       "    }\n",
       "  \n",
       "    var force = false;\n",
       "  \n",
       "    if (typeof (window._bokeh_onload_callbacks) === \"undefined\" || force === true) {\n",
       "      window._bokeh_onload_callbacks = [];\n",
       "      window._bokeh_is_loading = undefined;\n",
       "    }\n",
       "  \n",
       "  \n",
       "    \n",
       "    if (typeof (window._bokeh_timeout) === \"undefined\" || force === true) {\n",
       "      window._bokeh_timeout = Date.now() + 0;\n",
       "      window._bokeh_failed_load = false;\n",
       "    }\n",
       "  \n",
       "    var NB_LOAD_WARNING = {'data': {'text/html':\n",
       "       \"<div style='background-color: #fdd'>\\n\"+\n",
       "       \"<p>\\n\"+\n",
       "       \"BokehJS does not appear to have successfully loaded. If loading BokehJS from CDN, this \\n\"+\n",
       "       \"may be due to a slow or bad network connection. Possible fixes:\\n\"+\n",
       "       \"</p>\\n\"+\n",
       "       \"<ul>\\n\"+\n",
       "       \"<li>re-rerun `output_notebook()` to attempt to load from CDN again, or</li>\\n\"+\n",
       "       \"<li>use INLINE resources instead, as so:</li>\\n\"+\n",
       "       \"</ul>\\n\"+\n",
       "       \"<code>\\n\"+\n",
       "       \"from bokeh.resources import INLINE\\n\"+\n",
       "       \"output_notebook(resources=INLINE)\\n\"+\n",
       "       \"</code>\\n\"+\n",
       "       \"</div>\"}};\n",
       "  \n",
       "    function display_loaded() {\n",
       "      if (window.Bokeh !== undefined) {\n",
       "        var el = document.getElementById(\"69f390bf-eb11-4808-bc62-94006a2b2cc4\");\n",
       "        el.textContent = \"BokehJS \" + Bokeh.version + \" successfully loaded.\";\n",
       "      } else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(display_loaded, 100)\n",
       "      }\n",
       "    }\n",
       "  \n",
       "    function run_callbacks() {\n",
       "      window._bokeh_onload_callbacks.forEach(function(callback) { callback() });\n",
       "      delete window._bokeh_onload_callbacks\n",
       "      console.info(\"Bokeh: all callbacks have finished\");\n",
       "    }\n",
       "  \n",
       "    function load_libs(js_urls, callback) {\n",
       "      window._bokeh_onload_callbacks.push(callback);\n",
       "      if (window._bokeh_is_loading > 0) {\n",
       "        console.log(\"Bokeh: BokehJS is being loaded, scheduling callback at\", now());\n",
       "        return null;\n",
       "      }\n",
       "      if (js_urls == null || js_urls.length === 0) {\n",
       "        run_callbacks();\n",
       "        return null;\n",
       "      }\n",
       "      console.log(\"Bokeh: BokehJS not loaded, scheduling load and callback at\", now());\n",
       "      window._bokeh_is_loading = js_urls.length;\n",
       "      for (var i = 0; i < js_urls.length; i++) {\n",
       "        var url = js_urls[i];\n",
       "        var s = document.createElement('script');\n",
       "        s.src = url;\n",
       "        s.async = false;\n",
       "        s.onreadystatechange = s.onload = function() {\n",
       "          window._bokeh_is_loading--;\n",
       "          if (window._bokeh_is_loading === 0) {\n",
       "            console.log(\"Bokeh: all BokehJS libraries loaded\");\n",
       "            run_callbacks()\n",
       "          }\n",
       "        };\n",
       "        s.onerror = function() {\n",
       "          console.warn(\"failed to load library \" + url);\n",
       "        };\n",
       "        console.log(\"Bokeh: injecting script tag for BokehJS library: \", url);\n",
       "        document.getElementsByTagName(\"head\")[0].appendChild(s);\n",
       "      }\n",
       "    };var element = document.getElementById(\"69f390bf-eb11-4808-bc62-94006a2b2cc4\");\n",
       "    if (element == null) {\n",
       "      console.log(\"Bokeh: ERROR: autoload.js configured with elementid '69f390bf-eb11-4808-bc62-94006a2b2cc4' but no matching script tag was found. \")\n",
       "      return false;\n",
       "    }\n",
       "  \n",
       "    var js_urls = [];\n",
       "  \n",
       "    var inline_js = [\n",
       "      function(Bokeh) {\n",
       "        (function() {\n",
       "          var fn = function() {\n",
       "            var docs_json = {\"17f1c127-e84a-4631-a9b2-19b5de7fc8f1\":{\"roots\":{\"references\":[{\"attributes\":{},\"id\":\"a9a94d31-d291-46ba-aa23-bf6744c495a4\",\"type\":\"BasicTicker\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"78a6da67-010e-4d4f-83c6-e2a8293db54e\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"a23fd330-de1b-4dde-ae78-c65cb4182150\",\"type\":\"Grid\"},{\"attributes\":{\"formatter\":{\"id\":\"4a135b2b-17fa-49e6-84cd-e685a6df27d5\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"a9a94d31-d291-46ba-aa23-bf6744c495a4\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"2dbd0812-5ed8-4d70-a582-369f9b56c417\",\"type\":\"LinearAxis\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"2336ea08-1a9a-485c-8be2-d7809686afff\",\"type\":\"HelpTool\"},{\"attributes\":{},\"id\":\"4a135b2b-17fa-49e6-84cd-e685a6df27d5\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"de13928c-a3da-4c1a-b25f-f9bcf0bc9b61\",\"type\":\"ResetTool\"},{\"attributes\":{\"cx\":{\"field\":\"cx\"},\"cy\":{\"field\":\"cy\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"fec2f081-af75-4461-8b8d-29d5c4db7202\",\"type\":\"Quadratic\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\",\"text\"],\"data\":{\"text\":[\"A\",\"F\",\"B\",\"G\",\"C\",\"D\",\"E\"],\"x\":[0,1,2,3,4,5,6]}},\"id\":\"d873cbf3-8e10-4212-a94c-7ab2e68d7ac6\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"data_source\":{\"id\":\"d873cbf3-8e10-4212-a94c-7ab2e68d7ac6\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"1e60b925-d533-49b6-8ebc-5047bb93623f\",\"type\":\"Text\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"88dca901-ee3e-4407-9d0a-e53ce5b9dae7\",\"type\":\"Text\"},\"selection_glyph\":null},\"id\":\"9d98ba92-d774-4273-a0f4-c3a840a4e154\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"fill_color\":{\"value\":\"#1f77b4\"},\"line_color\":{\"value\":\"#1f77b4\"},\"size\":{\"units\":\"screen\",\"value\":30},\"x\":{\"field\":\"x\"},\"y\":{\"value\":0}},\"id\":\"9a34765c-6144-44d6-9beb-3c3b131a25a2\",\"type\":\"Circle\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x0\",\"y0\",\"x1\",\"y1\",\"cx\",\"cy\"],\"data\":{\"cx\":[1.0,2.5,3.0,4.0,5.5,4.5,5.0,2.0],\"cy\":[0.7,0.7,0.7,0.7,0,0,0.7,-0.7],\"x0\":[0,0,2,2,5,4,4,1],\"x1\":[2,5,4,6,6,5,6,3],\"y0\":[0,0,0,0,0,0,0,0],\"y1\":[0,0,0,0,0,0,0,0]}},\"id\":\"9431f3c1-b260-43ad-a142-9e45036aff30\",\"type\":\"ColumnDataSource\"},{\"attributes\":{\"fill_alpha\":{\"value\":0.1},\"fill_color\":{\"value\":\"#1f77b4\"},\"line_alpha\":{\"value\":0.1},\"line_color\":{\"value\":\"#1f77b4\"},\"size\":{\"units\":\"screen\",\"value\":30},\"x\":{\"field\":\"x\"},\"y\":{\"value\":0}},\"id\":\"e5532764-2356-46b5-993b-a58de0a22543\",\"type\":\"Circle\"},{\"attributes\":{\"data_source\":{\"id\":\"c09e06ee-ca34-4af7-b4f0-fed8f6206c20\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"9a34765c-6144-44d6-9beb-3c3b131a25a2\",\"type\":\"Circle\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"e5532764-2356-46b5-993b-a58de0a22543\",\"type\":\"Circle\"},\"selection_glyph\":null},\"id\":\"17ddc4ff-92e6-4a6f-8be2-5f9a5e3dc3da\",\"type\":\"GlyphRenderer\"},{\"attributes\":{\"data_source\":{\"id\":\"9431f3c1-b260-43ad-a142-9e45036aff30\",\"type\":\"ColumnDataSource\"},\"glyph\":{\"id\":\"ed0be939-056c-41ef-9ffd-2c760367d4cf\",\"type\":\"Quadratic\"},\"hover_glyph\":null,\"muted_glyph\":null,\"nonselection_glyph\":{\"id\":\"fec2f081-af75-4461-8b8d-29d5c4db7202\",\"type\":\"Quadratic\"},\"selection_glyph\":null},\"id\":\"0f30d393-13f9-4eba-9474-1752e23da03e\",\"type\":\"GlyphRenderer\"},{\"attributes\":{},\"id\":\"63401e76-9d4c-436d-82c9-ef622c15b5b5\",\"type\":\"BasicTickFormatter\"},{\"attributes\":{\"callback\":null,\"column_names\":[\"x\"],\"data\":{\"x\":[0,1,2,3,4,5,6]}},\"id\":\"c09e06ee-ca34-4af7-b4f0-fed8f6206c20\",\"type\":\"ColumnDataSource\"},{\"attributes\":{},\"id\":\"78a6da67-010e-4d4f-83c6-e2a8293db54e\",\"type\":\"BasicTicker\"},{\"attributes\":{\"text_align\":\"center\",\"text_baseline\":\"middle\",\"text_color\":{\"value\":\"yellow\"},\"x\":{\"field\":\"x\"},\"y\":{\"value\":0}},\"id\":\"1e60b925-d533-49b6-8ebc-5047bb93623f\",\"type\":\"Text\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"7c3ca6aa-c53d-4d97-b710-604fcb1cfbfe\",\"type\":\"SaveTool\"},{\"attributes\":{\"active_drag\":\"auto\",\"active_scroll\":\"auto\",\"active_tap\":\"auto\",\"tools\":[{\"id\":\"0d78015c-2eb4-4226-93c7-bbda51ef5ae1\",\"type\":\"PanTool\"},{\"id\":\"87895425-4665-4b1b-afe4-1082a9cd75bd\",\"type\":\"WheelZoomTool\"},{\"id\":\"e7e12293-50b8-4956-af17-d4b8c5cd3f27\",\"type\":\"BoxZoomTool\"},{\"id\":\"7c3ca6aa-c53d-4d97-b710-604fcb1cfbfe\",\"type\":\"SaveTool\"},{\"id\":\"de13928c-a3da-4c1a-b25f-f9bcf0bc9b61\",\"type\":\"ResetTool\"},{\"id\":\"2336ea08-1a9a-485c-8be2-d7809686afff\",\"type\":\"HelpTool\"}]},\"id\":\"bbb1d065-1eb4-4653-a7cf-b8922b968faf\",\"type\":\"Toolbar\"},{\"attributes\":{\"plot\":null,\"text\":\"\"},\"id\":\"1860d363-8359-44eb-8164-1304044442e9\",\"type\":\"Title\"},{\"attributes\":{\"formatter\":{\"id\":\"63401e76-9d4c-436d-82c9-ef622c15b5b5\",\"type\":\"BasicTickFormatter\"},\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"78a6da67-010e-4d4f-83c6-e2a8293db54e\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"9465c2e3-d4c2-431a-9009-ca874d21f89e\",\"type\":\"LinearAxis\"},{\"attributes\":{\"below\":[{\"id\":\"9465c2e3-d4c2-431a-9009-ca874d21f89e\",\"type\":\"LinearAxis\"}],\"left\":[{\"id\":\"2dbd0812-5ed8-4d70-a582-369f9b56c417\",\"type\":\"LinearAxis\"}],\"plot_height\":300,\"renderers\":[{\"id\":\"9465c2e3-d4c2-431a-9009-ca874d21f89e\",\"type\":\"LinearAxis\"},{\"id\":\"a23fd330-de1b-4dde-ae78-c65cb4182150\",\"type\":\"Grid\"},{\"id\":\"2dbd0812-5ed8-4d70-a582-369f9b56c417\",\"type\":\"LinearAxis\"},{\"id\":\"c140ea52-582c-4cac-94ec-f6f1e08ec455\",\"type\":\"Grid\"},{\"id\":\"d4b84a7a-2f7c-4734-8917-af9e7ac8c640\",\"type\":\"BoxAnnotation\"},{\"id\":\"0f30d393-13f9-4eba-9474-1752e23da03e\",\"type\":\"GlyphRenderer\"},{\"id\":\"17ddc4ff-92e6-4a6f-8be2-5f9a5e3dc3da\",\"type\":\"GlyphRenderer\"},{\"id\":\"9d98ba92-d774-4273-a0f4-c3a840a4e154\",\"type\":\"GlyphRenderer\"}],\"title\":{\"id\":\"1860d363-8359-44eb-8164-1304044442e9\",\"type\":\"Title\"},\"tool_events\":{\"id\":\"0da65285-c74f-4864-92cf-cadd9134eeea\",\"type\":\"ToolEvents\"},\"toolbar\":{\"id\":\"bbb1d065-1eb4-4653-a7cf-b8922b968faf\",\"type\":\"Toolbar\"},\"x_range\":{\"id\":\"18864459-a820-4e96-9fac-711567a71bd3\",\"type\":\"Range1d\"},\"y_range\":{\"id\":\"ba442d71-3c8b-4c86-8896-5cf9b6873ff9\",\"type\":\"Range1d\"}},\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"},{\"attributes\":{\"callback\":null,\"end\":7,\"start\":-1},\"id\":\"18864459-a820-4e96-9fac-711567a71bd3\",\"type\":\"Range1d\"},{\"attributes\":{\"callback\":null,\"start\":-1},\"id\":\"ba442d71-3c8b-4c86-8896-5cf9b6873ff9\",\"type\":\"Range1d\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"87895425-4665-4b1b-afe4-1082a9cd75bd\",\"type\":\"WheelZoomTool\"},{\"attributes\":{\"overlay\":{\"id\":\"d4b84a7a-2f7c-4734-8917-af9e7ac8c640\",\"type\":\"BoxAnnotation\"},\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"e7e12293-50b8-4956-af17-d4b8c5cd3f27\",\"type\":\"BoxZoomTool\"},{\"attributes\":{},\"id\":\"0da65285-c74f-4864-92cf-cadd9134eeea\",\"type\":\"ToolEvents\"},{\"attributes\":{\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"}},\"id\":\"0d78015c-2eb4-4226-93c7-bbda51ef5ae1\",\"type\":\"PanTool\"},{\"attributes\":{\"dimension\":1,\"plot\":{\"id\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\",\"subtype\":\"Figure\",\"type\":\"Plot\"},\"ticker\":{\"id\":\"a9a94d31-d291-46ba-aa23-bf6744c495a4\",\"type\":\"BasicTicker\"},\"visible\":false},\"id\":\"c140ea52-582c-4cac-94ec-f6f1e08ec455\",\"type\":\"Grid\"},{\"attributes\":{\"text_align\":\"center\",\"text_alpha\":{\"value\":0.1},\"text_baseline\":\"middle\",\"text_color\":{\"value\":\"black\"},\"x\":{\"field\":\"x\"},\"y\":{\"value\":0}},\"id\":\"88dca901-ee3e-4407-9d0a-e53ce5b9dae7\",\"type\":\"Text\"},{\"attributes\":{\"bottom_units\":\"screen\",\"fill_alpha\":{\"value\":0.5},\"fill_color\":{\"value\":\"lightgrey\"},\"left_units\":\"screen\",\"level\":\"overlay\",\"line_alpha\":{\"value\":1.0},\"line_color\":{\"value\":\"black\"},\"line_dash\":[4,4],\"line_width\":{\"value\":2},\"plot\":null,\"render_mode\":\"css\",\"right_units\":\"screen\",\"top_units\":\"screen\"},\"id\":\"d4b84a7a-2f7c-4734-8917-af9e7ac8c640\",\"type\":\"BoxAnnotation\"},{\"attributes\":{\"cx\":{\"field\":\"cx\"},\"cy\":{\"field\":\"cy\"},\"line_color\":{\"value\":\"red\"},\"x0\":{\"field\":\"x0\"},\"x1\":{\"field\":\"x1\"},\"y0\":{\"field\":\"y0\"},\"y1\":{\"field\":\"y1\"}},\"id\":\"ed0be939-056c-41ef-9ffd-2c760367d4cf\",\"type\":\"Quadratic\"}],\"root_ids\":[\"128caed9-f213-4e4a-8f6d-5c8dab218bca\"]},\"title\":\"Bokeh Application\",\"version\":\"0.12.5\"}};\n",
       "            var render_items = [{\"docid\":\"17f1c127-e84a-4631-a9b2-19b5de7fc8f1\",\"elementid\":\"69f390bf-eb11-4808-bc62-94006a2b2cc4\",\"modelid\":\"128caed9-f213-4e4a-8f6d-5c8dab218bca\"}];\n",
       "            \n",
       "            Bokeh.embed.embed_items(docs_json, render_items);\n",
       "          };\n",
       "          if (document.readyState != \"loading\") fn();\n",
       "          else document.addEventListener(\"DOMContentLoaded\", fn);\n",
       "        })();\n",
       "      },\n",
       "      function(Bokeh) {\n",
       "      }\n",
       "    ];\n",
       "  \n",
       "    function run_inline_js() {\n",
       "      \n",
       "      if ((window.Bokeh !== undefined) || (force === true)) {\n",
       "        for (var i = 0; i < inline_js.length; i++) {\n",
       "          inline_js[i](window.Bokeh);\n",
       "        }if (force === true) {\n",
       "          display_loaded();\n",
       "        }} else if (Date.now() < window._bokeh_timeout) {\n",
       "        setTimeout(run_inline_js, 100);\n",
       "      } else if (!window._bokeh_failed_load) {\n",
       "        console.log(\"Bokeh: BokehJS failed to load within specified timeout.\");\n",
       "        window._bokeh_failed_load = true;\n",
       "      } else if (force !== true) {\n",
       "        var cell = $(document.getElementById(\"69f390bf-eb11-4808-bc62-94006a2b2cc4\")).parents('.cell').data().cell;\n",
       "        cell.output_area.append_execute_result(NB_LOAD_WARNING)\n",
       "      }\n",
       "  \n",
       "    }\n",
       "  \n",
       "    if (window._bokeh_is_loading === 0) {\n",
       "      console.log(\"Bokeh: BokehJS loaded, going straight to plotting\");\n",
       "      run_inline_js();\n",
       "    } else {\n",
       "      load_libs(js_urls, function() {\n",
       "        console.log(\"Bokeh: BokehJS plotting callback run at\", now());\n",
       "        run_inline_js();\n",
       "      });\n",
       "    }\n",
       "  }(this));\n",
       "</script>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "output_notebook()\n",
    "\n",
    "plot = figure(x_range = (-1, n), y_range = (-1, 1), plot_width=600, plot_height=300)\n",
    "plot.grid.visible = False\n",
    "plot.axis.visible = False\n",
    "\n",
    "plot.quadratic(*zip(*q), color='red')\n",
    "plot.circle(x, 0, size=30)\n",
    "plot.text(x, 0, text=topology, text_color='yellow', text_align='center', text_baseline='middle')\n",
    "\n",
    "show(plot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}