examples/basic_searches.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import interactive_visualization\n",
    "from interactive_visualization.graph_utils import Graph, Arc, Node"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "from interactive_visualization.animation_utils import animate_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "arcs = [\n",
    "    Arc(0, 1),\n",
    "    Arc(1, 2),\n",
    "    Arc(1, 3),\n",
    "    Arc(2, 4),\n",
    "    Arc(1, 4),\n",
    "    Arc(3, 4)\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = Graph(arcs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n",
       " -->\r\n",
       "<!-- Pages: 1 -->\r\n",
       "<svg width=\"260pt\" height=\"110pt\"\r\n",
       " viewBox=\"0.00 0.00 260.00 109.80\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 105.8)\">\r\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-105.8 256,-105.8 256,4 -4,4\"/>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node1\" class=\"node\">\r\n",
       "<title>0</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\">\r\n",
       "<title>1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\">\r\n",
       "<title>0:&#45;&gt;1:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.3,-29.8C44.02,-29.8 53.29,-29.8 61.89,-29.8\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-29.8 61.9,-34.3 66.9,-29.8 61.9,-29.8 61.9,-29.8 61.9,-29.8 66.9,-29.8 61.9,-25.3 71.9,-29.8 71.9,-29.8\"/>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\">\r\n",
       "<title>2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-83.8\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-80.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge2\" class=\"edge\">\r\n",
       "<title>1:&#45;&gt;2:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M104.83,-40.47C114.61,-48.01 127.92,-58.28 139.13,-66.93\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"147.2,-73.15 136.53,-70.61 143.24,-70.1 139.28,-67.05 139.28,-67.05 139.28,-67.05 143.24,-70.1 142.03,-63.48 147.2,-73.15 147.2,-73.15\"/>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node4\" class=\"node\">\r\n",
       "<title>3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;3 -->\r\n",
       "<g id=\"edge3\" class=\"edge\">\r\n",
       "<title>1:&#45;&gt;3:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-29.8C116.02,-29.8 125.29,-29.8 133.89,-29.8\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-29.8 133.9,-34.3 138.9,-29.8 133.9,-29.8 133.9,-29.8 133.9,-29.8 138.9,-29.8 133.9,-25.3 143.9,-29.8 143.9,-29.8\"/>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\">\r\n",
       "<title>4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\">\r\n",
       "<title>1:&#45;&gt;4:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M105.57,-20C115.82,-13.71 130.14,-6.13 144,-2.8 159.56,0.93 164.44,0.93 180,-2.8 190.28,-5.27 200.82,-10.08 209.77,-14.97\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"218.43,-20 207.52,-18.87 214.11,-17.49 209.78,-14.98 209.78,-14.98 209.78,-14.98 214.11,-17.49 212.04,-11.09 218.43,-20 218.43,-20\"/>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;4 -->\r\n",
       "<g id=\"edge5\" class=\"edge\">\r\n",
       "<title>2:&#45;&gt;4:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M176.83,-73.13C186.61,-65.59 199.92,-55.32 211.13,-46.67\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"219.2,-40.45 214.03,-50.12 215.24,-43.5 211.28,-46.56 211.28,-46.56 211.28,-46.56 215.24,-43.5 208.53,-42.99 219.2,-40.45 219.2,-40.45\"/>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;4 -->\r\n",
       "<g id=\"edge6\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;4:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180.3,-29.8C188.02,-29.8 197.29,-29.8 205.89,-29.8\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"215.9,-29.8 205.9,-34.3 210.9,-29.8 205.9,-29.8 205.9,-29.8 205.9,-29.8 210.9,-29.8 205.9,-25.3 215.9,-29.8 215.9,-29.8\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x26face95f70>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph.Visualize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Базовые обходы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Обход в глубину (Depth first search, dfs)\n",
    "Суть обхода в глубину заключается в следующей задаче: в связном неориентированном графе найти такой цикл (возможно с повторением вершин), который проходит через все вершины. При условии отсутствия повторений эта задача становится гораздо более сложной (поиск гамильтонова цикла), но без этого ограничения оказывается, что решить довольно просто с помощью рекурсивной логики. Допустим мы хотим реализовать функцию $dfs(v)$ строит нам такой цикл, начиная с вершины $v$. Тогда рекуррентное правило для такой функции можно выразить как-то так: если $u_1, \\ldots, u_k$ -- соседи $v$, то $dfs(v)=v, dfs(u_1), v, dfs(u_2), v, \\ldots, v, dfs(u_k), v$. Иначе говоря, мы просто обходим по очереди каждого соседа, добавляя к получившемуся циклу переходы $v\\rightarrow u_i$ вначале и $u_i\\rightarrow v$ вконце. Если никак не ограничить возможность переходов, то описанное выше правило создает бесконечную рекурсию. Обычно это решается довольно простым способом: прерывать повторные вызовы $dfs(v)$ для одних и тех же вершин. В итоге алгоритм выглядит следующим образом (все функции выше $dfs$ используются только для визуализации)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def enter_node(node):\n",
    "    node.SetColor('blue')\n",
    "    \n",
    "def enter_arc(node, arc):\n",
    "    node.SetColor('green')\n",
    "    arc.attributes['style'] = 'dashed'\n",
    "    arc.attributes['color'] = 'green'\n",
    "    \n",
    "def return_from_arc(node, arc):\n",
    "    arc.attributes['style'] = 'solid'\n",
    "    arc.attributes['color'] = 'red'\n",
    "    node.SetColor('blue')\n",
    "    \n",
    "def ignore_arc(arc):\n",
    "    arc.attributes['color'] = 'blue'\n",
    "    \n",
    "def leave_node(node):\n",
    "    node.SetColor('red')\n",
    "    \n",
    "def dfs(graph, node_id, visited, outlist, path):\n",
    "    visited.add(node_id)\n",
    "    path.append(node_id)\n",
    "    enter_node(graph.nodes[node_id])\n",
    "    outlist.append(graph.Visualize())\n",
    "    for arc in graph.nodes[node_id].arcs:\n",
    "        if arc.end not in visited:\n",
    "            enter_arc(graph.nodes[node_id], arc)\n",
    "            dfs(graph, arc.end, visited, outlist, path) \n",
    "            return_from_arc(graph.nodes[node_id], arc)\n",
    "            path.append(node_id)\n",
    "        else:\n",
    "            ignore_arc(arc)\n",
    "        outlist.append(graph.Visualize())      \n",
    "    leave_node(graph.nodes[node_id])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 4, 2, 1, 3, 1, 0]\n"
     ]
    }
   ],
   "source": [
    "graph = Graph(arcs)\n",
    "visited = set()\n",
    "dfs_outlist = []\n",
    "path = []\n",
    "dfs_outlist.append(graph.Visualize())\n",
    "dfs(graph, 0, visited, dfs_outlist, path)\n",
    "dfs_outlist.append(graph.Visualize())\n",
    "print(path)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "35fb516143254053875e86e25f1a1d6b",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ef29fba1792d469f89349da217f5945a",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=12), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "animate_list(dfs_outlist);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Примеры\n",
    "### Выделение компонент связности\n",
    "Компонента связности в неориентированном графе -- это множество вершин, в котором каждая пара вершин соединена путем, и при этом нет пути из вершины из этого множества в вершину не из этого множества. $dfs$ (ровно как и $bfs$, описанный далее) обходит ровно одну компоненту связности, при этом в $visited$ запоминаются вершины, которые посетил наш обход. Если запустить $dfs$ с сохранением $visited$ из каждой вершины, то в результате можно получить разбиение графа на компоненты связности"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Components:\n",
      "{0, 1, 2}\n",
      "{3, 4, 5}\n"
     ]
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "3e12305088834cc8952030cf1bfb900d",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "bc4f8198d3ff4e5eafdc85436e86f8e6",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=17), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = Graph([\n",
    "    Arc(0, 1),\n",
    "    Arc(1, 0),\n",
    "    Arc(1, 2),\n",
    "    Arc(2, 1),\n",
    "    Arc(3, 4),\n",
    "    Arc(4, 3),\n",
    "    Arc(3, 5),\n",
    "    Arc(5, 3)\n",
    "])\n",
    "visited = set()\n",
    "components_outlist = []\n",
    "print(\"Components:\")\n",
    "for node_id in graph.nodes:\n",
    "    if node_id in visited:\n",
    "        continue\n",
    "    path = []\n",
    "    components_outlist.append(graph.Visualize())\n",
    "    dfs(graph, node_id, visited, components_outlist, path)\n",
    "    components_outlist.append(graph.Visualize())\n",
    "    print(set(path))\n",
    "animate_list(components_outlist);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Топологическая сортировка и поиск циклов\n",
    "В ориентированном графе всегда выполняется одно из двух: 1) вершины графа могут быть пронумерованы так, что ребра идут из вершины с меньшим номером в вершину с большим номером; 2) В графе есть цикл. Довольно очевидно, что при выполнении 2) невозможно 1). Чуть менее очевидно, что если 2) не выполняется, то обязательно выполняется 1). Сортировка вершин согласно 1) обычно называется <i><b>топологической сортировкой</b></i>. В визуализации $dfs$ использовались три цвета: черный для вершин, которые еще не посетили; зеленый для вершин, в которые вошли, но еще не вышли; красный для вершин, из которых уже вышли. Оказывается, что если в графе есть цикл, в $dfs$ обязательно в какой-то момент мы будем обрабатывать ребро, ведущее в зеленую вершину. С помощью $dfs$ также довольно легко получить топологический порядок: если из $v$ есть переходы в $u_1, \\ldots, u_k$, то нужно сначала обойти и пронумеровать все $u_i$, а потом уже пронумеровать $v$ номером, меньшим, чем пронумерованные ранее. Обычно это удобно делать задом наперед."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def top_sort(graph, node_id, visited, stack, reversed_top_order):\n",
    "    visited[node_id] = 'green'\n",
    "    stack.append(node_id)\n",
    "    for arc in graph.nodes[node_id].arcs:\n",
    "        if arc.end in visited:\n",
    "            if visited[arc.end] == 'green':\n",
    "                for i, v in enumerate(stack):\n",
    "                    if v == arc.end:\n",
    "                        return stack[i:]\n",
    "        else:\n",
    "            result = top_sort(graph, arc.end, visited, stack, reversed_top_order)\n",
    "            if result is not None:\n",
    "                return result\n",
    "    reversed_top_order.append(node_id)\n",
    "    stack = stack[:-1]\n",
    "    visited[node_id] = 'blue'\n",
    "    return None\n",
    "\n",
    "def try_top_sort(graph):\n",
    "    visited = dict()\n",
    "    stack = []\n",
    "    reversed_top_order = []\n",
    "    for node_id in graph.nodes:\n",
    "        if node_id in visited:\n",
    "            continue\n",
    "        has_cycle = top_sort(graph, node_id, visited, stack, reversed_top_order)\n",
    "        if has_cycle is not None:\n",
    "            print (\"Cycle detecetd:\", has_cycle)\n",
    "            return\n",
    "    result = list(reversed(reversed_top_order))\n",
    "    print(\"No cycles, proper ordering:\", result)\n",
    "    return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "No cycles, proper ordering: [7, 8, 3, 0, 5, 6, 1, 2]\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n",
       " -->\r\n",
       "<!-- Pages: 1 -->\r\n",
       "<svg width=\"260pt\" height=\"152pt\"\r\n",
       " viewBox=\"0.00 0.00 260.00 152.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 148)\">\r\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-148 256,-148 256,4 -4,4\"/>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node1\" class=\"node\">\r\n",
       "<title>3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-41.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\">\r\n",
       "<title>1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-68.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;1:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.24,-51.26C43.63,-54.5 54.07,-58.53 63.5,-62.17\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.85,-65.77 61.9,-66.37 68.19,-63.97 63.52,-62.17 63.52,-62.17 63.52,-62.17 68.19,-63.97 65.14,-57.97 72.85,-65.77 72.85,-65.77\"/>\r\n",
       "</g>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node4\" class=\"node\">\r\n",
       "<title>0</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;0 -->\r\n",
       "<g id=\"edge2\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;0:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.24,-38.74C43.63,-35.5 54.07,-31.47 63.5,-27.83\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.85,-24.23 65.14,-32.03 68.19,-26.03 63.52,-27.83 63.52,-27.83 63.52,-27.83 68.19,-26.03 61.9,-23.63 72.85,-24.23 72.85,-24.23\"/>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\">\r\n",
       "<title>2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-68.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge3\" class=\"edge\">\r\n",
       "<title>1:&#45;&gt;2:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-72C116.02,-72 125.29,-72 133.89,-72\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-72 133.9,-76.5 138.9,-72 133.9,-72 133.9,-72 133.9,-72 138.9,-72 133.9,-67.5 143.9,-72 143.9,-72\"/>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node5\" class=\"node\">\r\n",
       "<title>5</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">5</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;5 -->\r\n",
       "<g id=\"edge4\" class=\"edge\">\r\n",
       "<title>0:&#45;&gt;5:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-18C116.02,-18 125.29,-18 133.89,-18\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-18 133.9,-22.5 138.9,-18 133.9,-18 133.9,-18 133.9,-18 138.9,-18 133.9,-13.5 143.9,-18 143.9,-18\"/>\r\n",
       "</g>\r\n",
       "<!-- 6 -->\r\n",
       "<g id=\"node6\" class=\"node\">\r\n",
       "<title>6</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">6</text>\r\n",
       "</g>\r\n",
       "<!-- 5&#45;&gt;6 -->\r\n",
       "<g id=\"edge5\" class=\"edge\">\r\n",
       "<title>5:&#45;&gt;6:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180.3,-18C188.02,-18 197.29,-18 205.89,-18\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"215.9,-18 205.9,-22.5 210.9,-18 205.9,-18 205.9,-18 205.9,-18 210.9,-18 205.9,-13.5 215.9,-18 215.9,-18\"/>\r\n",
       "</g>\r\n",
       "<!-- 7 -->\r\n",
       "<g id=\"node7\" class=\"node\">\r\n",
       "<title>7</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-126\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-122.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">7</text>\r\n",
       "</g>\r\n",
       "<!-- 8 -->\r\n",
       "<g id=\"node8\" class=\"node\">\r\n",
       "<title>8</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-126\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-122.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">8</text>\r\n",
       "</g>\r\n",
       "<!-- 7&#45;&gt;8 -->\r\n",
       "<g id=\"edge6\" class=\"edge\">\r\n",
       "<title>7:&#45;&gt;8:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.3,-126C44.02,-126 53.29,-126 61.89,-126\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-126 61.9,-130.5 66.9,-126 61.9,-126 61.9,-126 61.9,-126 66.9,-126 61.9,-121.5 71.9,-126 71.9,-126\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x26facebbf70>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = Graph([\n",
    "    Arc(3, 1),\n",
    "    Arc(1, 2), \n",
    "    Arc(3, 0),\n",
    "    Arc(0, 5),\n",
    "    Arc(5, 6),\n",
    "    Arc(7, 8)\n",
    "])\n",
    "order = try_top_sort(graph)\n",
    "inv_order = dict()\n",
    "for i, value in enumerate(order):\n",
    "    inv_order[value] = i\n",
    "graph.Visualize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n",
       " -->\r\n",
       "<!-- Pages: 1 -->\r\n",
       "<svg width=\"260pt\" height=\"152pt\"\r\n",
       " viewBox=\"0.00 0.00 260.00 152.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 148)\">\r\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-148 256,-148 256,4 -4,4\"/>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node1\" class=\"node\">\r\n",
       "<title>2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-45\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-41.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n",
       "</g>\r\n",
       "<!-- 6 -->\r\n",
       "<g id=\"node2\" class=\"node\">\r\n",
       "<title>6</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-68.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">6</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;6 -->\r\n",
       "<g id=\"edge1\" class=\"edge\">\r\n",
       "<title>2:&#45;&gt;6:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.24,-51.26C43.63,-54.5 54.07,-58.53 63.5,-62.17\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.85,-65.77 61.9,-66.37 68.19,-63.97 63.52,-62.17 63.52,-62.17 63.52,-62.17 68.19,-63.97 65.14,-57.97 72.85,-65.77 72.85,-65.77\"/>\r\n",
       "</g>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node3\" class=\"node\">\r\n",
       "<title>3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;3 -->\r\n",
       "<g id=\"edge2\" class=\"edge\">\r\n",
       "<title>2:&#45;&gt;3:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M35.24,-38.74C43.63,-35.5 54.07,-31.47 63.5,-27.83\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"72.85,-24.23 65.14,-32.03 68.19,-26.03 63.52,-27.83 63.52,-27.83 63.52,-27.83 68.19,-26.03 61.9,-23.63 72.85,-24.23 72.85,-24.23\"/>\r\n",
       "</g>\r\n",
       "<!-- 7 -->\r\n",
       "<g id=\"node4\" class=\"node\">\r\n",
       "<title>7</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-68.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">7</text>\r\n",
       "</g>\r\n",
       "<!-- 6&#45;&gt;7 -->\r\n",
       "<g id=\"edge3\" class=\"edge\">\r\n",
       "<title>6:&#45;&gt;7:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-72C116.02,-72 125.29,-72 133.89,-72\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-72 133.9,-76.5 138.9,-72 133.9,-72 133.9,-72 133.9,-72 138.9,-72 133.9,-67.5 143.9,-72 143.9,-72\"/>\r\n",
       "</g>\r\n",
       "<!-- 4 -->\r\n",
       "<g id=\"node5\" class=\"node\">\r\n",
       "<title>4</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;4 -->\r\n",
       "<g id=\"edge4\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;4:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-18C116.02,-18 125.29,-18 133.89,-18\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-18 133.9,-22.5 138.9,-18 133.9,-18 133.9,-18 133.9,-18 138.9,-18 133.9,-13.5 143.9,-18 143.9,-18\"/>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node6\" class=\"node\">\r\n",
       "<title>5</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">5</text>\r\n",
       "</g>\r\n",
       "<!-- 4&#45;&gt;5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\">\r\n",
       "<title>4:&#45;&gt;5:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M180.3,-18C188.02,-18 197.29,-18 205.89,-18\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"215.9,-18 205.9,-22.5 210.9,-18 205.9,-18 205.9,-18 205.9,-18 210.9,-18 205.9,-13.5 215.9,-18 215.9,-18\"/>\r\n",
       "</g>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node7\" class=\"node\">\r\n",
       "<title>0</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-126\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-122.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node8\" class=\"node\">\r\n",
       "<title>1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-126\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-122.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;1 -->\r\n",
       "<g id=\"edge6\" class=\"edge\">\r\n",
       "<title>0:&#45;&gt;1:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.3,-126C44.02,-126 53.29,-126 61.89,-126\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-126 61.9,-130.5 66.9,-126 61.9,-126 61.9,-126 61.9,-126 66.9,-126 61.9,-121.5 71.9,-126 71.9,-126\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x26face71490>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "arcs_ordered = []\n",
    "for node in graph.nodes.values():\n",
    "    arcs_ordered.extend([Arc(inv_order[arc.beginning], inv_order[arc.end]) for arc in node.arcs])\n",
    "graph_ordered = Graph(arcs_ordered)\n",
    "graph_ordered.Visualize()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Cycle detecetd: [3, 1, 2, 6]\n"
     ]
    },
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n",
       "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n",
       " \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n",
       "<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n",
       " -->\r\n",
       "<!-- Pages: 1 -->\r\n",
       "<svg width=\"260pt\" height=\"170pt\"\r\n",
       " viewBox=\"0.00 0.00 260.00 169.99\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n",
       "<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 165.99)\">\r\n",
       "<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-165.99 256,-165.99 256,4 -4,4\"/>\r\n",
       "<!-- 3 -->\r\n",
       "<g id=\"node1\" class=\"node\">\r\n",
       "<title>3</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-35.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-32.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n",
       "</g>\r\n",
       "<!-- 1 -->\r\n",
       "<g id=\"node2\" class=\"node\">\r\n",
       "<title>1</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-89.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-86.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;1 -->\r\n",
       "<g id=\"edge1\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;1:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M32.83,-46.66C42.61,-54.21 55.92,-64.47 67.13,-73.12\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"75.2,-79.35 64.53,-76.8 71.24,-76.29 67.28,-73.24 67.28,-73.24 67.28,-73.24 71.24,-76.29 70.03,-69.68 75.2,-79.35 75.2,-79.35\"/>\r\n",
       "</g>\r\n",
       "<!-- 0 -->\r\n",
       "<g id=\"node4\" class=\"node\">\r\n",
       "<title>0</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-35.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-32.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n",
       "</g>\r\n",
       "<!-- 3&#45;&gt;0 -->\r\n",
       "<g id=\"edge2\" class=\"edge\">\r\n",
       "<title>3:&#45;&gt;0:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.3,-35.99C44.02,-35.99 53.29,-35.99 61.89,-35.99\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-35.99 61.9,-40.49 66.9,-35.99 61.9,-35.99 61.9,-35.99 61.9,-35.99 66.9,-35.99 61.9,-31.49 71.9,-35.99 71.9,-35.99\"/>\r\n",
       "</g>\r\n",
       "<!-- 2 -->\r\n",
       "<g id=\"node3\" class=\"node\">\r\n",
       "<title>2</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-89.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-86.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n",
       "</g>\r\n",
       "<!-- 1&#45;&gt;2 -->\r\n",
       "<g id=\"edge3\" class=\"edge\">\r\n",
       "<title>1:&#45;&gt;2:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-89.99C116.02,-89.99 125.29,-89.99 133.89,-89.99\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-89.99 133.9,-94.49 138.9,-89.99 133.9,-89.99 133.9,-89.99 133.9,-89.99 138.9,-89.99 133.9,-85.49 143.9,-89.99 143.9,-89.99\"/>\r\n",
       "</g>\r\n",
       "<!-- 6 -->\r\n",
       "<g id=\"node6\" class=\"node\">\r\n",
       "<title>6</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-39.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"234\" y=\"-36.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">6</text>\r\n",
       "</g>\r\n",
       "<!-- 2&#45;&gt;6 -->\r\n",
       "<g id=\"edge4\" class=\"edge\">\r\n",
       "<title>2:&#45;&gt;6:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M177.17,-79.88C186.75,-73.03 199.61,-63.85 210.57,-56.02\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"218.86,-50.1 213.33,-59.57 214.79,-53 210.72,-55.91 210.72,-55.91 210.72,-55.91 214.79,-53 208.1,-52.25 218.86,-50.1 218.86,-50.1\"/>\r\n",
       "</g>\r\n",
       "<!-- 5 -->\r\n",
       "<g id=\"node5\" class=\"node\">\r\n",
       "<title>5</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-35.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"162\" y=\"-32.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">5</text>\r\n",
       "</g>\r\n",
       "<!-- 0&#45;&gt;5 -->\r\n",
       "<g id=\"edge5\" class=\"edge\">\r\n",
       "<title>0:&#45;&gt;5:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M108.3,-35.99C116.02,-35.99 125.29,-35.99 133.89,-35.99\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-35.99 133.9,-40.49 138.9,-35.99 133.9,-35.99 133.9,-35.99 133.9,-35.99 138.9,-35.99 133.9,-31.49 143.9,-35.99 143.9,-35.99\"/>\r\n",
       "</g>\r\n",
       "<!-- 6&#45;&gt;3 -->\r\n",
       "<g id=\"edge6\" class=\"edge\">\r\n",
       "<title>6:&#45;&gt;3:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M219.09,-29.07C208.9,-21.8 194.4,-12.9 180,-8.99 133.67,3.56 118.67,2.21 72,-8.99 61.72,-11.46 51.18,-16.28 42.23,-21.17\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"33.57,-26.19 39.96,-17.28 37.89,-23.68 42.22,-21.17 42.22,-21.17 42.22,-21.17 37.89,-23.68 44.48,-25.07 33.57,-26.19 33.57,-26.19\"/>\r\n",
       "</g>\r\n",
       "<!-- 7 -->\r\n",
       "<g id=\"node7\" class=\"node\">\r\n",
       "<title>7</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-143.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"18\" y=\"-140.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">7</text>\r\n",
       "</g>\r\n",
       "<!-- 8 -->\r\n",
       "<g id=\"node8\" class=\"node\">\r\n",
       "<title>8</title>\r\n",
       "<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-143.99\" rx=\"18\" ry=\"18\"/>\r\n",
       "<text text-anchor=\"middle\" x=\"90\" y=\"-140.29\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">8</text>\r\n",
       "</g>\r\n",
       "<!-- 7&#45;&gt;8 -->\r\n",
       "<g id=\"edge7\" class=\"edge\">\r\n",
       "<title>7:&#45;&gt;8:</title>\r\n",
       "<path fill=\"none\" stroke=\"black\" d=\"M36.3,-143.99C44.02,-143.99 53.29,-143.99 61.89,-143.99\"/>\r\n",
       "<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-143.99 61.9,-148.49 66.9,-143.99 61.9,-143.99 61.9,-143.99 61.9,-143.99 66.9,-143.99 61.9,-139.49 71.9,-143.99 71.9,-143.99\"/>\r\n",
       "</g>\r\n",
       "</g>\r\n",
       "</svg>\r\n"
      ],
      "text/plain": [
       "<graphviz.dot.Digraph at 0x26face70460>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph = Graph([\n",
    "    Arc(3, 1),\n",
    "    Arc(1, 2), \n",
    "    Arc(3, 0),\n",
    "    Arc(0, 5),\n",
    "    Arc(6, 3),\n",
    "    Arc(7, 8),\n",
    "    Arc(2, 6)\n",
    "])\n",
    "try_top_sort(graph)\n",
    "graph.Visualize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Топологическая сортировка графа, если она возможна, помогает во многих друих задачах, например нахождении кратчайших расстояний в графе. Вычислительные графы, использующиеся в pytorch, tensorflow и т.п., также ацикличны, топологическая сортировка для них выдает порядок, в котором должны быть произведены вычисления. Мы также сталкивались с довольно интересной ситуацией: в конфигурационных файлах вычислительных графов для нейронных сетей в калди могут быть циклы из-за особенностей реализации реккурентных связей. Для дого, чтобы проанализировать граф из калди и перевести его в другой формат (cntk) необходимо было выделить <i><b>компоненты сильной связности</b></i>, для чего обычно используется более хитрый [алгоритм Тарьяна](https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A2%D0%B0%D1%80%D1%8C%D1%8F%D0%BD%D0%B0), основанный на идеях, использующихся в топологической сортировке."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Анализ\n",
    "Во всез указанных выше примерах просмотр исходящих из вершины ребер осуществляется только один раз. `path` пополняется при входе в вершину и при просмотре ребра, ведущего в еще не посещенную вершину. Общий размер `path` -- это $2N-C$, где $N$ -- количество вершин, $C$ -- количество компонент связности"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Обход в ширину (breadth first search, bfs)\n",
    "Основная задача для обхода в ширину: дана вершина $s$, для всех остальных вершин посчитать, какое минимальное количество переходов по ребрам нужно сделать, чтобы добраться из $s$ в эту вершину? По сути это самая простая разновидность задачи о кратчайших путях, где все ребра имеют одинаковую длину. Идея довольно проста: последовательно находим множества вершин, для которых расстояние $0, 1, 2, \\ldots$. Если обозначить за $V_d$ -- множество вершин на расстояние $d$, то оно состоит из соседей вериш из $V_{d-1}$, которые не содержатся в $V_1\\cup \\ldots \\cup V_{d-1}$. Несмотря на схожую с $dfs$ рекуррентную структуру из-за необходимости работы с множествами для эффективной реализации подсчета всех этих расстояний используют механизм с очередью. Изачально в очереди находится единственный элемент -- $s$, т.е. очередь содержит множество $V_0$. Одна итерация алгоритма заключается в вытаскивании из очереди вершины, просматриванию её соседей, и добавлении в очередь этого соседа, если ранее эта вершина не была обработана. Если мы достаем вершину с расстоянием $d$, то её соседи будут иметь расстояние $d+1$ или меньше, при этом положим мы в очередь соседа только если расстояние $d+1$. Таким образом на каждой итерации алгоритма соблюдается инвариант, что сначала в очереди идут несколько вершин с растоеним $d$, а потом с расстоянием $d+1$, другими словами мы в процессе вычисления $V_{d+1}$. В какие-то моменты у нас остается только вершины с одинаковым расстоянием, это означает, что мы только что закончили просматривать вершины из $V_d$ для формирования $V_{d+1}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "import queue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def process_arc(arc):\n",
    "    arc.attributes['color'] = 'blue'\n",
    "\n",
    "def put_node_in_queue(node):\n",
    "    node.SetColor('green')\n",
    "    \n",
    "def process_node(node):\n",
    "    node.SetColor('blue')\n",
    "\n",
    "def ignore_arc(arc):\n",
    "    arc.attributes['color'] = 'red'\n",
    "\n",
    "def bfs(graph, s, outlist):\n",
    "    dist = dict()\n",
    "    q = queue.Queue()\n",
    "    q.put(s)\n",
    "    dist[s] = 0\n",
    "    while not q.empty():\n",
    "        cur = q.get()\n",
    "        v = graph.nodes[cur]\n",
    "        d = dist[cur]\n",
    "        process_node(v)\n",
    "        outlist.append(graph.Visualize())\n",
    "        for arc in v.arcs:\n",
    "            process_arc(arc)\n",
    "            if arc.end not in dist:\n",
    "                put_node_in_queue(graph.nodes[arc.end])\n",
    "                dist[arc.end] = d + 1\n",
    "                q.put(arc.end)\n",
    "            else:\n",
    "                ignore_arc(arc)\n",
    "                \n",
    "        outlist.append(graph.Visualize())       \n",
    "    return dist          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 0, 3: 1, 4: 1, 5: 1, 2: 2, 6: 2, 7: 3}\n"
     ]
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "fc56eb9a47264b4ab2de50a851b7edb0",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(Button(description='Prev', style=ButtonStyle()), Button(description='Next', style=ButtonStyle()…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e606d91cd81e42c2bfcb30044efd8321",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='step', max=14), Output()), _dom_classes=('widget-interac…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = Graph([\n",
    "    Arc(1, 3),\n",
    "    Arc(1, 4),\n",
    "    Arc(4, 3),\n",
    "    Arc(4, 5),\n",
    "    Arc(1, 5),\n",
    "    Arc(6, 4),\n",
    "    Arc(5, 6),\n",
    "    Arc(6, 7),\n",
    "    Arc(7, 2),\n",
    "    Arc(4, 2),\n",
    "    Arc(3, 2)\n",
    "])\n",
    "bfs_outlist = []\n",
    "bfs_outlist.append(graph.Visualize())\n",
    "dist = bfs(graph, 1, bfs_outlist)\n",
    "print(dist)\n",
    "animate_list(bfs_outlist);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Примеры\n",
    "Обход в ширину явлется базисом для \"сканирующего метода\" (также известен как Generic SSSP) для поиска кратчайших путей в графе. Частными случаями этогометода являются Поиск кратчайшего пути в ациклическом графе, алгоритм Дейкстры, алгоритм Форда-Беллмана. На обходе в ширину построены большинство операцией с WFST."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Анализ\n",
    "Каждая вершина помещается в очередь (и удаляется из нее) ровно один раз, каждое ребро просматривается ровно один раз"
   ]
  }
 ],
 "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.8.5"
  },
  "widgets": {
   "application/vnd.jupyter.widget-state+json": {
    "state": {
     "09dee0046296404fabf3dd18a1c2a9c1": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_5a617351922144f08429e7133742d1c2",
       "max": 12,
       "style": "IPY_MODEL_bd6a7c51c58b451abb64bd0e6b50fd91"
      }
     },
     "16962980e07540f182f5b29aa8e37e39": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "1d520f7dd253492896f6b3f9b11f6818": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_542eb9566df640dbae6ef971e62b0d91",
       "max": 17,
       "style": "IPY_MODEL_287f95ba7fe14bdfaaec4dc38e6a501f"
      }
     },
     "20ca3cecbe5042d4a522fc56569047c7": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "20f289e5fe5a484f9e2a917d02f2736c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_5c228c2a20dd4caf9a9b5197666aab8a",
       "style": "IPY_MODEL_77cb02b48aff4360812b60694a2a4d69"
      }
     },
     "2322a87ad0b84d34b8e0393e8909d8ac": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "287f95ba7fe14bdfaaec4dc38e6a501f": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "34ae258025c549daa37bd48b3d8813a2": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "3583e400df094b2db96b4867bba89403": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "35fb516143254053875e86e25f1a1d6b": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_93532b3956fb4a1592ec67d0558ccabe",
        "IPY_MODEL_20f289e5fe5a484f9e2a917d02f2736c"
       ],
       "layout": "IPY_MODEL_bc1f1f0d4ecc4b6d86ec56d8e8329114"
      }
     },
     "3a56f563c65643d7924660929db7e6d3": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "3e12305088834cc8952030cf1bfb900d": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_ff45139710fa49f09af3c8747443de31",
        "IPY_MODEL_83411ef8c9364305a8bd9ccf74af2e1d"
       ],
       "layout": "IPY_MODEL_9722dccd9120459f922335d74bbceaf1"
      }
     },
     "414d8e28607040ccb5d445d9479c537e": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "4a87275cd5064ae3b7231a63919ec404": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "517c058e3a184329bd511f77d36c3e93": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "542eb9566df640dbae6ef971e62b0d91": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "5a30a874d188458daa4dde762b17d9eb": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_414d8e28607040ccb5d445d9479c537e",
       "outputs": [
        {
         "data": {
          "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n -->\r\n<!-- Pages: 1 -->\r\n<svg width=\"404pt\" height=\"174pt\"\r\n viewBox=\"0.00 0.00 404.00 174.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 170)\">\r\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-170 400,-170 400,4 -4,4\"/>\r\n<!-- 1 -->\r\n<g id=\"node1\" class=\"node\">\r\n<title>1</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"18\" y=\"-88.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n</g>\r\n<!-- 3 -->\r\n<g id=\"node2\" class=\"node\">\r\n<title>3</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-148\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"162\" y=\"-144.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n</g>\r\n<!-- 1&#45;&gt;3 -->\r\n<g id=\"edge1\" class=\"edge\">\r\n<title>1:&#45;&gt;3:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M34.01,-100.44C44.46,-106.12 58.84,-113.54 72,-119 92.58,-127.53 116.64,-135.24 134.55,-140.57\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"144.32,-143.41 133.46,-144.93 139.52,-142.01 134.72,-140.61 134.72,-140.61 134.72,-140.61 139.52,-142.01 135.98,-136.29 144.32,-143.41 144.32,-143.41\"/>\r\n</g>\r\n<!-- 4 -->\r\n<g id=\"node3\" class=\"node\">\r\n<title>4</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-92\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"90\" y=\"-88.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n</g>\r\n<!-- 1&#45;&gt;4 -->\r\n<g id=\"edge2\" class=\"edge\">\r\n<title>1:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M36.3,-92C44.02,-92 53.29,-92 61.89,-92\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-92 61.9,-96.5 66.9,-92 61.9,-92 61.9,-92 61.9,-92 66.9,-92 61.9,-87.5 71.9,-92 71.9,-92\"/>\r\n</g>\r\n<!-- 5 -->\r\n<g id=\"node4\" class=\"node\">\r\n<title>5</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"162\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">5</text>\r\n</g>\r\n<!-- 1&#45;&gt;5 -->\r\n<g id=\"edge3\" class=\"edge\">\r\n<title>1:&#45;&gt;5:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M34.2,-84.08C58.62,-71.35 106.86,-46.22 136.28,-30.88\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"145.48,-26.09 138.69,-34.7 141.05,-28.4 136.61,-30.71 136.61,-30.71 136.61,-30.71 141.05,-28.4 134.53,-26.72 145.48,-26.09 145.48,-26.09\"/>\r\n</g>\r\n<!-- 2 -->\r\n<g id=\"node7\" class=\"node\">\r\n<title>2</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"378\" cy=\"-102\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"378\" y=\"-98.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n</g>\r\n<!-- 3&#45;&gt;2 -->\r\n<g id=\"edge4\" class=\"edge\">\r\n<title>3:&#45;&gt;2:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M180,-144.98C209.44,-139.67 271.8,-128.07 324,-116 332.7,-113.99 342.15,-111.57 350.62,-109.31\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"360.36,-106.68 351.88,-113.63 355.53,-107.99 350.7,-109.29 350.7,-109.29 350.7,-109.29 355.53,-107.99 349.53,-104.95 360.36,-106.68 360.36,-106.68\"/>\r\n</g>\r\n<!-- 4&#45;&gt;3 -->\r\n<g id=\"edge5\" class=\"edge\">\r\n<title>4:&#45;&gt;3:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M104.5,-102.8C114.47,-110.78 128.25,-121.8 139.7,-130.96\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"147.54,-137.24 136.92,-134.5 143.64,-134.11 139.74,-130.99 139.74,-130.99 139.74,-130.99 143.64,-134.11 142.55,-127.47 147.54,-137.24 147.54,-137.24\"/>\r\n</g>\r\n<!-- 4&#45;&gt;5 -->\r\n<g id=\"edge6\" class=\"edge\">\r\n<title>4:&#45;&gt;5:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M103.19,-79.11C113.83,-67.86 129.45,-51.35 141.77,-38.32\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"148.95,-30.74 145.34,-41.1 145.51,-34.37 142.07,-38.01 142.07,-38.01 142.07,-38.01 145.51,-34.37 138.81,-34.91 148.95,-30.74 148.95,-30.74\"/>\r\n</g>\r\n<!-- 4&#45;&gt;2 -->\r\n<g id=\"edge7\" class=\"edge\">\r\n<title>4:&#45;&gt;2:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M108.03,-92.6C155.71,-94.26 290.82,-98.99 349.37,-101.03\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"359.69,-101.39 349.54,-105.54 354.7,-101.22 349.7,-101.05 349.7,-101.05 349.7,-101.05 354.7,-101.22 349.86,-96.55 359.69,-101.39 359.69,-101.39\"/>\r\n</g>\r\n<!-- 6 -->\r\n<g id=\"node5\" class=\"node\">\r\n<title>6</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-56\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"234\" y=\"-52.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">6</text>\r\n</g>\r\n<!-- 5&#45;&gt;6 -->\r\n<g id=\"edge8\" class=\"edge\">\r\n<title>5:&#45;&gt;6:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M178.19,-26.25C187.18,-31.13 198.77,-37.42 208.97,-42.96\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"217.84,-47.77 206.91,-46.95 213.45,-45.39 209.05,-43 209.05,-43 209.05,-43 213.45,-45.39 211.2,-39.04 217.84,-47.77 217.84,-47.77\"/>\r\n</g>\r\n<!-- 6&#45;&gt;4 -->\r\n<g id=\"edge9\" class=\"edge\">\r\n<title>6:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M216.1,-60.28C191.67,-66.48 146.25,-77.99 117.38,-85.31\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"107.57,-87.8 116.15,-80.98 112.41,-86.57 117.26,-85.34 117.26,-85.34 117.26,-85.34 112.41,-86.57 118.37,-89.7 107.57,-87.8 107.57,-87.8\"/>\r\n</g>\r\n<!-- 7 -->\r\n<g id=\"node6\" class=\"node\">\r\n<title>7</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"306\" cy=\"-56\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"306\" y=\"-52.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">7</text>\r\n</g>\r\n<!-- 6&#45;&gt;7 -->\r\n<g id=\"edge10\" class=\"edge\">\r\n<title>6:&#45;&gt;7:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M252.3,-56C260.02,-56 269.29,-56 277.89,-56\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"287.9,-56 277.9,-60.5 282.9,-56 277.9,-56 277.9,-56 277.9,-56 282.9,-56 277.9,-51.5 287.9,-56 287.9,-56\"/>\r\n</g>\r\n<!-- 7&#45;&gt;2 -->\r\n<g id=\"edge11\" class=\"edge\">\r\n<title>7:&#45;&gt;2:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M321.5,-65.53C330.89,-71.7 343.31,-79.86 354.02,-86.9\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"362.51,-92.48 351.69,-90.75 358.34,-89.74 354.16,-86.99 354.16,-86.99 354.16,-86.99 358.34,-89.74 356.63,-83.23 362.51,-92.48 362.51,-92.48\"/>\r\n</g>\r\n</g>\r\n</svg>\r\n",
          "text/plain": "<graphviz.dot.Digraph at 0x26face427c0>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "5a617351922144f08429e7133742d1c2": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "5c228c2a20dd4caf9a9b5197666aab8a": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "6238af5a53204c32bff1fd68ec86801e": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_6887aae03b3444efad14377df86e51b7",
       "style": "IPY_MODEL_34ae258025c549daa37bd48b3d8813a2"
      }
     },
     "63e03084be334aa1ae002346f8cebb4b": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "6887aae03b3444efad14377df86e51b7": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "77cb02b48aff4360812b60694a2a4d69": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "798b3b9273014b3398a0b808fbe47877": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "8251a79322774455b71f311962522f63": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "83411ef8c9364305a8bd9ccf74af2e1d": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_dc9766dcd3db458697316ee4ae9052de",
       "style": "IPY_MODEL_3583e400df094b2db96b4867bba89403"
      }
     },
     "93532b3956fb4a1592ec67d0558ccabe": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_517c058e3a184329bd511f77d36c3e93",
       "style": "IPY_MODEL_b9f8fd95255740afb8628a36923617eb"
      }
     },
     "9722dccd9120459f922335d74bbceaf1": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "9cd2f9bbda1c4a9883872de9cf07fd31": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "a46e03461e6c49b8b0ee2f9888541ba4": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "a5741e99f75d45aab49d4c6e68b635b9": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_c12790323ed84768b2d62a8247e4e635",
       "outputs": [
        {
         "data": {
          "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n -->\r\n<!-- Pages: 1 -->\r\n<svg width=\"188pt\" height=\"152pt\"\r\n viewBox=\"0.00 0.00 188.00 152.00\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 148)\">\r\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-148 184,-148 184,4 -4,4\"/>\r\n<!-- 0 -->\r\n<g id=\"node1\" class=\"node\">\r\n<title>0</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"18\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n</g>\r\n<!-- 1 -->\r\n<g id=\"node2\" class=\"node\">\r\n<title>1</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"90\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n</g>\r\n<!-- 0&#45;&gt;1 -->\r\n<g id=\"edge1\" class=\"edge\">\r\n<title>0:&#45;&gt;1:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M35.24,-12.2C43.36,-11.29 53.41,-11.03 62.61,-11.43\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"72.85,-12.21 62.54,-15.94 67.87,-11.83 62.88,-11.46 62.88,-11.46 62.88,-11.46 67.87,-11.83 63.22,-6.97 72.85,-12.21 72.85,-12.21\"/>\r\n</g>\r\n<!-- 1&#45;&gt;0 -->\r\n<g id=\"edge2\" class=\"edge\">\r\n<title>1:&#45;&gt;0:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M72.85,-23.79C64.74,-24.71 54.7,-24.97 45.49,-24.57\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"35.24,-23.8 45.54,-20.06 40.22,-24.17 45.21,-24.55 45.21,-24.55 45.21,-24.55 40.22,-24.17 44.87,-29.04 35.24,-23.8 35.24,-23.8\"/>\r\n</g>\r\n<!-- 2 -->\r\n<g id=\"node3\" class=\"node\">\r\n<title>2</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-18\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"162\" y=\"-14.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n</g>\r\n<!-- 1&#45;&gt;2 -->\r\n<g id=\"edge3\" class=\"edge\">\r\n<title>1:&#45;&gt;2:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M107.24,-12.2C115.36,-11.29 125.41,-11.03 134.61,-11.43\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"144.85,-12.21 134.54,-15.94 139.87,-11.83 134.88,-11.46 134.88,-11.46 134.88,-11.46 139.87,-11.83 135.22,-6.97 144.85,-12.21 144.85,-12.21\"/>\r\n</g>\r\n<!-- 2&#45;&gt;1 -->\r\n<g id=\"edge4\" class=\"edge\">\r\n<title>2:&#45;&gt;1:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M144.85,-23.79C136.74,-24.71 126.7,-24.97 117.49,-24.57\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"107.24,-23.8 117.54,-20.06 112.22,-24.17 117.21,-24.55 117.21,-24.55 117.21,-24.55 112.22,-24.17 116.87,-29.04 107.24,-23.8 107.24,-23.8\"/>\r\n</g>\r\n<!-- 3 -->\r\n<g id=\"node4\" class=\"node\">\r\n<title>3</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-99\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"18\" y=\"-95.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n</g>\r\n<!-- 4 -->\r\n<g id=\"node5\" class=\"node\">\r\n<title>4</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-126\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"90\" y=\"-122.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n</g>\r\n<!-- 3&#45;&gt;4 -->\r\n<g id=\"edge5\" class=\"edge\">\r\n<title>3:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M36.3,-99.76C45.29,-102.3 56.39,-106.43 66.08,-110.78\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"75.18,-115.16 64.21,-114.88 70.67,-112.99 66.17,-110.82 66.17,-110.82 66.17,-110.82 70.67,-112.99 68.12,-106.77 75.18,-115.16 75.18,-115.16\"/>\r\n</g>\r\n<!-- 5 -->\r\n<g id=\"node6\" class=\"node\">\r\n<title>5</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-72\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"90\" y=\"-68.3\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">5</text>\r\n</g>\r\n<!-- 3&#45;&gt;5 -->\r\n<g id=\"edge6\" class=\"edge\">\r\n<title>3:&#45;&gt;5:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M32.83,-88.16C41.26,-83.77 52.31,-79.15 62.37,-75.69\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"71.98,-72.68 63.79,-79.97 67.21,-74.18 62.44,-75.67 62.44,-75.67 62.44,-75.67 67.21,-74.18 61.09,-71.38 71.98,-72.68 71.98,-72.68\"/>\r\n</g>\r\n<!-- 4&#45;&gt;3 -->\r\n<g id=\"edge7\" class=\"edge\">\r\n<title>4:&#45;&gt;3:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M71.98,-125.32C62.97,-122.8 51.77,-118.64 42,-114.25\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"32.83,-109.84 43.79,-110.12 37.33,-112.01 41.84,-114.18 41.84,-114.18 41.84,-114.18 37.33,-112.01 39.89,-118.23 32.83,-109.84 32.83,-109.84\"/>\r\n</g>\r\n<!-- 5&#45;&gt;3 -->\r\n<g id=\"edge8\" class=\"edge\">\r\n<title>5:&#45;&gt;3:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M75.18,-82.84C66.81,-87.19 55.87,-91.78 45.87,-95.22\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"36.3,-98.24 44.48,-90.94 41.07,-96.74 45.84,-95.23 45.84,-95.23 45.84,-95.23 41.07,-96.74 47.19,-99.52 36.3,-98.24 36.3,-98.24\"/>\r\n</g>\r\n</g>\r\n</svg>\r\n",
          "text/plain": "<graphviz.dot.Digraph at 0x26facebb0d0>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "b9f8fd95255740afb8628a36923617eb": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonStyleModel",
      "state": {}
     },
     "bc1f1f0d4ecc4b6d86ec56d8e8329114": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "bc4f8198d3ff4e5eafdc85436e86f8e6": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_1d520f7dd253492896f6b3f9b11f6818",
        "IPY_MODEL_a5741e99f75d45aab49d4c6e68b635b9"
       ],
       "layout": "IPY_MODEL_8251a79322774455b71f311962522f63"
      }
     },
     "bd6a7c51c58b451abb64bd0e6b50fd91": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "c12790323ed84768b2d62a8247e4e635": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "cc40d2daa8d5498886c5c685cedf6685": {
      "model_module": "@jupyter-widgets/output",
      "model_module_version": "1.0.0",
      "model_name": "OutputModel",
      "state": {
       "layout": "IPY_MODEL_3a56f563c65643d7924660929db7e6d3",
       "outputs": [
        {
         "data": {
          "image/svg+xml": "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>\r\n<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 1.1//EN\"\r\n \"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd\">\r\n<!-- Generated by graphviz version 2.44.2~dev.20200826.1453 (20200826.1453)\r\n -->\r\n<!-- Pages: 1 -->\r\n<svg width=\"260pt\" height=\"110pt\"\r\n viewBox=\"0.00 0.00 260.00 109.80\" xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\">\r\n<g id=\"graph0\" class=\"graph\" transform=\"scale(1 1) rotate(0) translate(4 105.8)\">\r\n<polygon fill=\"white\" stroke=\"transparent\" points=\"-4,4 -4,-105.8 256,-105.8 256,4 -4,4\"/>\r\n<!-- 0 -->\r\n<g id=\"node1\" class=\"node\">\r\n<title>0</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"18\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"18\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">0</text>\r\n</g>\r\n<!-- 1 -->\r\n<g id=\"node2\" class=\"node\">\r\n<title>1</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"90\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"90\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">1</text>\r\n</g>\r\n<!-- 0&#45;&gt;1 -->\r\n<g id=\"edge1\" class=\"edge\">\r\n<title>0:&#45;&gt;1:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M36.3,-29.8C44.02,-29.8 53.29,-29.8 61.89,-29.8\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"71.9,-29.8 61.9,-34.3 66.9,-29.8 61.9,-29.8 61.9,-29.8 61.9,-29.8 66.9,-29.8 61.9,-25.3 71.9,-29.8 71.9,-29.8\"/>\r\n</g>\r\n<!-- 2 -->\r\n<g id=\"node3\" class=\"node\">\r\n<title>2</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-83.8\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"162\" y=\"-80.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">2</text>\r\n</g>\r\n<!-- 1&#45;&gt;2 -->\r\n<g id=\"edge2\" class=\"edge\">\r\n<title>1:&#45;&gt;2:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M104.83,-40.47C114.61,-48.01 127.92,-58.28 139.13,-66.93\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"147.2,-73.15 136.53,-70.61 143.24,-70.1 139.28,-67.05 139.28,-67.05 139.28,-67.05 143.24,-70.1 142.03,-63.48 147.2,-73.15 147.2,-73.15\"/>\r\n</g>\r\n<!-- 3 -->\r\n<g id=\"node4\" class=\"node\">\r\n<title>3</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"162\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"162\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">3</text>\r\n</g>\r\n<!-- 1&#45;&gt;3 -->\r\n<g id=\"edge3\" class=\"edge\">\r\n<title>1:&#45;&gt;3:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M108.3,-29.8C116.02,-29.8 125.29,-29.8 133.89,-29.8\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"143.9,-29.8 133.9,-34.3 138.9,-29.8 133.9,-29.8 133.9,-29.8 133.9,-29.8 138.9,-29.8 133.9,-25.3 143.9,-29.8 143.9,-29.8\"/>\r\n</g>\r\n<!-- 4 -->\r\n<g id=\"node5\" class=\"node\">\r\n<title>4</title>\r\n<ellipse fill=\"none\" stroke=\"black\" cx=\"234\" cy=\"-29.8\" rx=\"18\" ry=\"18\"/>\r\n<text text-anchor=\"middle\" x=\"234\" y=\"-26.1\" font-family=\"Times New Roman,serif\" font-size=\"14.00\">4</text>\r\n</g>\r\n<!-- 1&#45;&gt;4 -->\r\n<g id=\"edge4\" class=\"edge\">\r\n<title>1:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M105.57,-20C115.82,-13.71 130.14,-6.13 144,-2.8 159.56,0.93 164.44,0.93 180,-2.8 190.28,-5.27 200.82,-10.08 209.77,-14.97\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"218.43,-20 207.52,-18.87 214.11,-17.49 209.78,-14.98 209.78,-14.98 209.78,-14.98 214.11,-17.49 212.04,-11.09 218.43,-20 218.43,-20\"/>\r\n</g>\r\n<!-- 2&#45;&gt;4 -->\r\n<g id=\"edge5\" class=\"edge\">\r\n<title>2:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M176.83,-73.13C186.61,-65.59 199.92,-55.32 211.13,-46.67\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"219.2,-40.45 214.03,-50.12 215.24,-43.5 211.28,-46.56 211.28,-46.56 211.28,-46.56 215.24,-43.5 208.53,-42.99 219.2,-40.45 219.2,-40.45\"/>\r\n</g>\r\n<!-- 3&#45;&gt;4 -->\r\n<g id=\"edge6\" class=\"edge\">\r\n<title>3:&#45;&gt;4:</title>\r\n<path fill=\"none\" stroke=\"black\" d=\"M180.3,-29.8C188.02,-29.8 197.29,-29.8 205.89,-29.8\"/>\r\n<polygon fill=\"black\" stroke=\"black\" points=\"215.9,-29.8 205.9,-34.3 210.9,-29.8 205.9,-29.8 205.9,-29.8 205.9,-29.8 210.9,-29.8 205.9,-25.3 215.9,-29.8 215.9,-29.8\"/>\r\n</g>\r\n</g>\r\n</svg>\r\n",
          "text/plain": "<graphviz.dot.Digraph at 0x26face1cd30>"
         },
         "metadata": {},
         "output_type": "display_data"
        }
       ]
      }
     },
     "cd0fbf6dcbde4bca853c2a862cfcbf7c": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "IntSliderModel",
      "state": {
       "description": "step",
       "layout": "IPY_MODEL_63e03084be334aa1ae002346f8cebb4b",
       "max": 14,
       "style": "IPY_MODEL_eda6559f8cbb40e1ae2e43c328402e19"
      }
     },
     "dc9766dcd3db458697316ee4ae9052de": {
      "model_module": "@jupyter-widgets/base",
      "model_module_version": "1.2.0",
      "model_name": "LayoutModel",
      "state": {}
     },
     "e606d91cd81e42c2bfcb30044efd8321": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_cd0fbf6dcbde4bca853c2a862cfcbf7c",
        "IPY_MODEL_5a30a874d188458daa4dde762b17d9eb"
       ],
       "layout": "IPY_MODEL_4a87275cd5064ae3b7231a63919ec404"
      }
     },
     "eda6559f8cbb40e1ae2e43c328402e19": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "SliderStyleModel",
      "state": {
       "description_width": ""
      }
     },
     "ef29fba1792d469f89349da217f5945a": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "VBoxModel",
      "state": {
       "_dom_classes": [
        "widget-interact"
       ],
       "children": [
        "IPY_MODEL_09dee0046296404fabf3dd18a1c2a9c1",
        "IPY_MODEL_cc40d2daa8d5498886c5c685cedf6685"
       ],
       "layout": "IPY_MODEL_798b3b9273014b3398a0b808fbe47877"
      }
     },
     "f364b98a5dbe455fbf4a48bbe33db294": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Next",
       "layout": "IPY_MODEL_16962980e07540f182f5b29aa8e37e39",
       "style": "IPY_MODEL_9cd2f9bbda1c4a9883872de9cf07fd31"
      }
     },
     "fc56eb9a47264b4ab2de50a851b7edb0": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "HBoxModel",
      "state": {
       "children": [
        "IPY_MODEL_6238af5a53204c32bff1fd68ec86801e",
        "IPY_MODEL_f364b98a5dbe455fbf4a48bbe33db294"
       ],
       "layout": "IPY_MODEL_20ca3cecbe5042d4a522fc56569047c7"
      }
     },
     "ff45139710fa49f09af3c8747443de31": {
      "model_module": "@jupyter-widgets/controls",
      "model_module_version": "1.5.0",
      "model_name": "ButtonModel",
      "state": {
       "description": "Prev",
       "layout": "IPY_MODEL_a46e03461e6c49b8b0ee2f9888541ba4",
       "style": "IPY_MODEL_2322a87ad0b84d34b8e0393e8909d8ac"
      }
     }
    },
    "version_major": 2,
    "version_minor": 0
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}