parositas.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Parositasi algoritmus Paros grafokban\n",
    "\n",
    "A paros graf szomszedsagi matrix sorai betuvel oszlopai szamokkal vannak jelolve"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os\n",
    "from shutil import rmtree\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "# from sage.graphs.graph_plot import GraphPlot\n",
    "# from shapely.geometry import LineString\n",
    "from copy import deepcopy\n",
    "#from networkx.drawing.nx_pydot import graphviz_layout\n",
    "from networkx.drawing.nx_agraph import graphviz_layout\n",
    "from ipywidgets import HBox,VBox\n",
    "from ipywidgets.widgets import IntSlider,Textarea,Label,interactive,Button, Dropdown\n",
    "from matplotlib.ticker import AutoMinorLocator\n",
    "from networkx.drawing.nx_agraph import graphviz_layout\n",
    "from IPython.display import HTML\n",
    "from IPython.display import display, FileLink"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<script>\n",
       "code_show=true; \n",
       "function code_toggle() {\n",
       " if (code_show){\n",
       " $('div.input').hide();\n",
       " } else {\n",
       " $('div.input').show();\n",
       " }\n",
       " code_show = !code_show\n",
       "} \n",
       "$( document ).ready(code_toggle);\n",
       "</script>\n",
       "The raw code for this IPython notebook is by default hidden for easier reading.\n",
       "To toggle on/off the raw code, click <a href=\"javascript:code_toggle()\">here</a>."
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "HTML('''<script>\n",
    "code_show=true; \n",
    "function code_toggle() {\n",
    " if (code_show){\n",
    " $('div.input').hide();\n",
    " } else {\n",
    " $('div.input').show();\n",
    " }\n",
    " code_show = !code_show\n",
    "} \n",
    "$( document ).ready(code_toggle);\n",
    "</script>\n",
    "The raw code for this IPython notebook is by default hidden for easier reading.\n",
    "To toggle on/off the raw code, click <a href=\"javascript:code_toggle()\">here</a>.''')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "algoritmus = [\n",
    "    u'Az aktuális párosítás, Javító út keresés indítása!',\n",
    "    u'\\t BFS-t indítunk az M-fedetlen A-beliekből', \n",
    "    u'\\t B-beliek fertőznek minden M-menti szomszédot', \n",
    "    u'\\t A-beliek fertőznek mindenkit, akit lehet', \n",
    "    u'Van-e javító út?', \n",
    "    u'\\tVan javító út.',\n",
    "    u'\\t  Javítsuk M-et és Vissza az eléjere', \n",
    "    u'\\tNincs javító út. Lefogó ponthalmaz kiszámítása!'\n",
    "]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def plot_all(index):\n",
    "    \n",
    "    data = d_movie[index]\n",
    "    \n",
    "    fig = plt.figure(figsize=(15,12))\n",
    "    gs = fig.add_gridspec(2, 3,hspace=0.01)\n",
    "    \n",
    "    ax1 = fig.add_subplot(gs[0, 0])\n",
    "    ax0 = fig.add_subplot(gs[0, 1:3])\n",
    "    ax2 = fig.add_subplot(gs[1, 0:2])\n",
    "    ax3 = fig.add_subplot(gs[1, 2])\n",
    "    ax = [ax0,ax1,ax2,ax3]\n",
    "    \n",
    "    # FIG 0\n",
    "        \n",
    "    for i,line in enumerate(algoritmus):\n",
    "        tab_offset=0.1\n",
    "        dy=0.07\n",
    "        starting_height=(len(A_class)+1)*dy\n",
    "        if i!=data[\"code_index\"]:\n",
    "            if line[0]==\"\\t\":\n",
    "                ax[0].annotate(line[1:],(0+tab_offset,starting_height-dy*i),fontsize=12)\n",
    "            else:\n",
    "                ax[0].annotate(line,(0,starting_height-dy*i),fontsize=12)\n",
    "        else:\n",
    "            if line[0]==\"\\t\":\n",
    "                ax[0].annotate(line[1:],(0+tab_offset,starting_height-dy*i),fontsize=12,weight=\"bold\")\n",
    "            else:\n",
    "                ax[0].annotate(line,(0,starting_height-dy*i),fontsize=12,weight=\"bold\")\n",
    "    ax[0].set_axis_off()\n",
    "    \n",
    "    # FIG 1\n",
    "    # adjacency matrix\n",
    "    ax[1].imshow(A,interpolation=\"nearest\",cmap=\"Greys\")\n",
    "    ax[1].xaxis.tick_top()\n",
    "    ax[1].set_xticks([e for e in range(len(B_class))])\n",
    "    ax[1].set_xticklabels(B_class,fontdict={\"fontsize\":15})\n",
    "    ax[1].set_yticks([e for e in range(len(A_class))])\n",
    "    ax[1].set_yticklabels(A_class,fontdict={\"fontsize\":15})\n",
    "    ax[1].minorticks_on()\n",
    "    ax[1].set_ylabel(\"A osztály\",fontdict={\"fontsize\":15})\n",
    "    ax[1].set_xlabel(\"B osztály\",fontdict={\"fontsize\":15},labelpad=10)\n",
    "    ax[1].xaxis.set_label_position('top') \n",
    "\n",
    "    # placing 1 minor tick between 2 major ticks\n",
    "    aml = AutoMinorLocator(2)\n",
    "    ax[1].xaxis.set_minor_locator(aml)\n",
    "    ax[1].yaxis.set_minor_locator(aml)\n",
    "    ax[1].xaxis.set_tick_params(which='both', length=0,pad=7)\n",
    "    ax[1].yaxis.set_tick_params(which='both', length=0,pad=7)\n",
    "    ax[1].grid(which=\"minor\")\n",
    "\n",
    "    # adding colored circles for a certain matching\n",
    "    for edge in data[\"matching\"]:\n",
    "        ax[1].plot(B_class.index(edge[1]),A_class.index(edge[0]),'ro',markersize=14)\n",
    "\n",
    "    # adding colored lines for a certain covering\n",
    "    A_lefogo = ['a','b','e']\n",
    "    B_lefogo = [4,7,8]\n",
    "\n",
    "    if data[\"lefogo_A\"][0]:\n",
    "        for elem in data[\"lefogo_A\"][1]:\n",
    "            ax[1].plot([0-0.5,len(B_class)-0.5],[A_class.index(elem),A_class.index(elem)],'b-',lw=3)\n",
    "    if data[\"lefogo_B\"][0]:\n",
    "        for elem in data[\"lefogo_B\"][1]:\n",
    "            ax[1].plot([B_class.index(elem),B_class.index(elem)],[0-0.5,len(A_class)-0.5],'b-',lw=3)\n",
    "\n",
    "    # highlighting tick labels for selected nodes (in both classes)\n",
    "    if data[\"selected_A\"][0]:\n",
    "        for elem in data[\"selected_A\"][1]:\n",
    "            ax[1].get_yticklabels()[A_class.index(elem)].set_color(\"red\")\n",
    "    if data[\"selected_B\"][0]:\n",
    "        for elem in data[\"selected_B\"][1]:\n",
    "            ax[1].get_xticklabels()[B_class.index(elem)].set_color(\"red\")\n",
    "            \n",
    "    if data[\"matching_torolni\"][0]:\n",
    "        for edge in data[\"matching_torolni\"][1]:\n",
    "            ax[1].plot(B_class.index(edge[1]),A_class.index(edge[0]),'wx',markersize=14,mew=4)\n",
    "            \n",
    "    if data[\"matching_ujak\"][0]:\n",
    "        for edge in data[\"matching_ujak\"][1]:\n",
    "            ax[1].plot(B_class.index(edge[1]),A_class.index(edge[0]),'wo',markersize=10)\n",
    "        \n",
    "            \n",
    "    ax[1].set_aspect(1)\n",
    "            \n",
    "    # FIG 2\n",
    "    \n",
    "    if data[\"alternalo_javito_ut\"][0]:\n",
    "        x = [elem[0] for elem in data[\"alternalo_javito_ut\"][1]]\n",
    "        y = [elem[1] for elem in data[\"alternalo_javito_ut\"][1]]\n",
    "        ax[2].plot(x,y,'-',lw=15,color='orange',alpha=0.5)\n",
    "        \n",
    "    if data[\"segedgraf\"][0]:\n",
    "        G_info = data[\"segedgraf\"][1]\n",
    "        T = G_info[\"graf\"]\n",
    "        nx.draw_networkx_nodes(T,G_info[\"position\"],ax=ax[2],node_size=400,node_color=\"red\")\n",
    "        for color in G_info[\"edge_color\"]:\n",
    "            nx.draw_networkx_edges(\n",
    "                T,\n",
    "                G_info[\"position\"],\n",
    "                ax=ax[2],\n",
    "                edgelist=G_info[\"edge_color\"][color],\n",
    "                edge_color='black',\n",
    "                width=6\n",
    "            )\n",
    "            if color==\"black\":\n",
    "                nx.draw_networkx_edges(\n",
    "                    T,\n",
    "                    G_info[\"position\"],\n",
    "                    ax=ax[2],\n",
    "                    edgelist=G_info[\"edge_color\"][color],\n",
    "                    edge_color='white',\n",
    "                    width=3\n",
    "                )\n",
    "        nx.draw_networkx_labels(T,G_info[\"position\"],ax=ax[2])\n",
    "        xpadding=(G_info[\"xlim\"][1]-G_info[\"xlim\"][0])*0.15\n",
    "        ypadding=(G_info[\"ylim\"][1]-G_info[\"ylim\"][0])*0.15\n",
    "        ax[2].set_xlim(G_info[\"xlim\"][0]-xpadding,G_info[\"xlim\"][1]+xpadding)\n",
    "        ax[2].set_ylim(G_info[\"ylim\"][0]-ypadding,G_info[\"ylim\"][1]+ypadding)\n",
    "        ax[2].set_aspect(np.sqrt((G_info[\"xlim\"][1]-G_info[\"xlim\"][0])/(G_info[\"ylim\"][1]-G_info[\"ylim\"][0])))\n",
    "    ax[2].set_axis_off()\n",
    " \n",
    "    \n",
    "    # FIG 3\n",
    "    \n",
    "    ax[3].annotate(u\"Fertőzhető csúcsok:\",(0,0.7),fontsize=15)\n",
    "    ax[3].annotate(\"A osztály: \",(0.1,0.6),fontsize=15)\n",
    "    ax[3].annotate(\"B osztály: \",(0.1,0.5),fontsize=15)\n",
    "    \n",
    "    if data[\"fertozottek\"][0]:\n",
    "        dx=0.07\n",
    "\n",
    "        for i,elem in enumerate(A_class):\n",
    "            if elem not in data[\"fertozottek\"][1]:\n",
    "                ax[3].annotate(str(elem),(0.5+i*dx,0.6),fontsize=15)\n",
    "        \n",
    "        for i,elem in enumerate(B_class):\n",
    "            if elem not in data[\"fertozottek\"][1]:\n",
    "                ax[3].annotate(str(elem),(0.5+i*dx,0.5),fontsize=15)\n",
    "\n",
    "\n",
    "    ax[3].set_axis_off()\n",
    "    \n",
    "    return fig"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "ab0d29f1009847328c5e10edc75d5667",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Dropdown(description='Gráfválasztás:', layout=Layout(width='max-content'), options=(('Jegyzet 2.14', 0), ('Gy7…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph_select=Dropdown(\n",
    "    options=[('Jegyzet 2.14', 0), ('Gy7/1',1),('Gy7/1_T', 2), ('Gy7/3', 3),('Gy7/9',4),('Szabad',5)],\n",
    "    value=0,\n",
    "    description='Gráfválasztás:',\n",
    "    layout={'width': 'max-content'},\n",
    "    style={'description_width': 'initial'}\n",
    ")\n",
    "\n",
    "pelda_grafok={0:'a:1,7,9,10\\nb:2,5\\nc:3,5,6,8,9\\nd:4,7,8,9\\ne:1,4,5\\nf:6,7,8,10\\ng:2,3,4\\nh:2,3\\ni:2,3',\n",
    "              1:'1:B,F\\n2:A,B,C,D,E,G\\n3:B,E,F\\n4:A,C,D,F,G\\n5:E,F,G\\n6:B,E',\n",
    "              2:'A:2,4\\nB:1,2,3,6\\nC:2,4\\nD:2,4\\nE:2,3,5,6\\nF:2,3,4,5\\nG:2,4,5',\n",
    "              3:'A:1,4,7,9\\nB:1,3,5,6,7,9\\nC:1,2,4,5,8,9\\nD:1,4,7,9\\nE:1,7,9\\nF:2,3,5,8\\nG:4,7,9\\nH:2,5,6,8\\nI:1,4,7',\n",
    "              4:'A:2,3,5,7\\nB:4,5,8\\nC:1,4,5,8\\nD:1,2,5,6,7\\nE:1,5,8\\nF:1,4,5,8\\nG:4,5,8\\nH:1,2,3,5,6\\nI:1,4',\n",
    "              5:''}\n",
    "def trig(b):\n",
    "    input_graph.value=pelda_grafok[graph_select.value]\n",
    "graph_select.observe(trig ,names='value')\n",
    "graph_select"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "label_graph = Label(\"Gráf szomszédsági lista.\\n Példasor:\\n\\ta:1,2,3\")\n",
    "input_graph = Textarea(value=pelda_grafok[graph_select.value],layout={'height': '55mm'})\n",
    "\n",
    "label_matching = Label(\"Párosítás.\\n Példasor: a,1\")\n",
    "input_matching = Textarea(layout={'height': '55mm'})\n",
    "\n",
    "input_display = HBox([VBox([label_graph,input_graph]),VBox([label_matching,input_matching])])\n",
    "\n",
    "def textarea_reader(input_text,mode=\"matching\"):\n",
    "    if mode==\"matching\":\n",
    "        if len(input_text)==0:\n",
    "            return []\n",
    "        edgelist = []\n",
    "        split = input_text.split(\"\\n\")\n",
    "        for elem in split:\n",
    "            if len(elem)!=3 and len(elem)!=4:\n",
    "                print(\"Figyelj a bemenetre! Üres/hosszú sorok?\")\n",
    "                return\n",
    "            else:\n",
    "                a,b = elem.split(\",\")\n",
    "                try:\n",
    "                    #b = int(b)\n",
    "                    edgelist.append((a,b))\n",
    "                except:\n",
    "                    print(\"Először a betűvel, utána a számokkal jelölt osztályt sorold fel!\")\n",
    "                    return\n",
    "        return edgelist\n",
    "    if mode==\"graph\":\n",
    "        if len(input_text)<4:\n",
    "            print(\"Üres/rövid bemenet!\")\n",
    "            return\n",
    "        d_inc = {}\n",
    "        split = input_text.split(\"\\n\")\n",
    "        for elem in split:\n",
    "            if \":\" not in elem:\n",
    "                print(\"Túl rövid/üres sor, van kettőspont?\")\n",
    "                return\n",
    "            a,b_list = elem.split(\":\")\n",
    "            if b_list==\"\":\n",
    "                b_list=[]\n",
    "                d_inc[a]=b_list\n",
    "            else:\n",
    "                try:\n",
    "                    #b_list = [int(e) for e in b_list.split(\",\")]\n",
    "                    b_list = [e for e in b_list.split(\",\")]\n",
    "                    d_inc[a]=b_list\n",
    "                except:\n",
    "                    print(\"Rossz formátum!\")\n",
    "                    return\n",
    "        return d_inc"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def init_globals():\n",
    "    \n",
    "    d_inc = textarea_reader(input_graph.value,mode=\"graph\")\n",
    "    initial_matching = textarea_reader(input_matching.value,mode=\"matching\")\n",
    "    if d_inc is None or initial_matching is None:\n",
    "        return\n",
    "    else:\n",
    "        A_class=sorted(list(d_inc.keys()))\n",
    "        try:\n",
    "            A_class=[str(a) for a in sorted([int(e) for e in A_class])]\n",
    "        except:\n",
    "            A_class=A_class\n",
    "        B_class=sorted(list(set([u for v in d_inc.keys() for u in d_inc[v]])))\n",
    "        try:\n",
    "            B_class=[str(a) for a in sorted([int(e) for e in B_class])]\n",
    "        except:\n",
    "            B_class=B_class\n",
    "        G=nx.Graph(d_inc)\n",
    "        A=np.zeros((len(A_class),len(B_class)))\n",
    "        for k,v in d_inc.items():\n",
    "            a = A_class.index(k)\n",
    "            for elem in v:\n",
    "                b = B_class.index(elem)\n",
    "                A[a,b]=1\n",
    "        return G,A,A_class,B_class,initial_matching"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e0829f2e873247648fc003c53f4439e7",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(VBox(children=(Label(value='Gráf szomszédsági lista.\\n Példasor:\\n\\ta:1,2,3'), Textarea(value='…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "input_display"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "G,A,A_class,B_class,M = init_globals()\n",
    "d_movie={}\n",
    "szamlalo=0\n",
    "Fontos_Index=[]\n",
    "\n",
    "eps=0.5\n",
    "b_found_alternating_path=True\n",
    "\n",
    "while(b_found_alternating_path):\n",
    "    MG=nx.Graph(M)\n",
    "    \n",
    "    Fedett=[u for e in M for u in e]\n",
    "    \n",
    "    Fedetlen_A=[u for u in A_class if u not in Fedett]\n",
    "    \n",
    "    #BFS starting from Fedetlen_A\n",
    "    Q=Fedetlen_A\n",
    "    volt={u:False for u in A_class+B_class}\n",
    "    tav={u:0 for u in A_class+B_class}\n",
    "    honnan={u:'*' for u in A_class+B_class}\n",
    "    \n",
    "    d_seged={'matching':M,\n",
    "             'selected_A':(False,[]),\n",
    "             'selected_B':(False,[]),\n",
    "             'segedgraf':(False,[]),\n",
    "             'fertozottek':(False,[]),\n",
    "             'alternalo_javito_ut':(False,[]),\n",
    "             'lefogo_A':(False,[]),\n",
    "             \"lefogo_B\":(False,[]),\n",
    "             'code_index':0,\n",
    "             'matching_torolni':(False,[]),\n",
    "             'matching_ujak':(False,[])}\n",
    "    d_movie[szamlalo]=deepcopy(d_seged)\n",
    "    Fontos_Index.append(szamlalo)\n",
    "    szamlalo+=1\n",
    "    \n",
    "    b_found_alternating_path=False\n",
    "    for u in Q:\n",
    "        volt[u]=True\n",
    "    #print(Q)\n",
    "    while((len(Q)>0) ):# and (b_found_alternating_path==False)):\n",
    "        akt=Q.pop(0)\n",
    "        \n",
    "        if tav[akt]%2==0: #akt is in A\n",
    "            l_seged=[u for u in G.neighbors(akt) if volt[u]==False]\n",
    "            Q+=l_seged\n",
    "            for u in l_seged:\n",
    "                volt[u]=True\n",
    "                tav[u]=tav[akt]+1\n",
    "                honnan[u]=akt\n",
    "        else:\n",
    "            if akt in Fedett:\n",
    "                l_seged=[u for u in MG.neighbors(akt)]\n",
    "                Q+=l_seged\n",
    "                for u in l_seged:\n",
    "                    volt[u]=True\n",
    "                    tav[u]=tav[akt]+1\n",
    "                    honnan[u]=akt\n",
    "            else:\n",
    "                if b_found_alternating_path==False:\n",
    "                    fedetlen_veg=akt\n",
    "                b_found_alternating_path=True\n",
    "                \n",
    "\n",
    "    T=nx.DiGraph([(u,honnan[u]) for u in honnan if volt[u]==True])\n",
    "    pos_T={}\n",
    "    if len(T.nodes())>0:\n",
    "        pos_T= {k:(v[1],-v[0]) for k,v in graphviz_layout(T,prog='dot',root=['*']).items()}\n",
    "        T=nx.to_undirected(T)\n",
    "        T = nx.Graph(T)\n",
    "        T.remove_node('*')     \n",
    "        del(pos_T[\"*\"])\n",
    "        \n",
    "        boundaries={\n",
    "            'xlim':(min([pos_T[u][0] for u in T.nodes()]),max([pos_T[u][0] for u in T.nodes()])),\n",
    "            'ylim':(min([pos_T[u][1] for u in T.nodes()]),max([pos_T[u][1] for u in T.nodes()]))}\n",
    "        \n",
    "        T_coloring_edges1={\n",
    "            'black': [e for e in T.edges() if min([tav[v] for v in e])%2==0 ], \n",
    "            'blue': [e for e in T.edges() if min([tav[v] for v in e])%2==1] }\n",
    "        for j in range(max(tav[u] for u in T.nodes())+1):\n",
    "            T2=deepcopy(T)\n",
    "            L_f=[u for u in T.nodes() if tav[u]<j+1]\n",
    "#             print(len(L_f))\n",
    "            T2.remove_nodes_from([u for u in T.nodes() if u not in L_f])\n",
    "            pos_T2={u:pos_T[u] for u in T2.nodes()}\n",
    "            T2_coloring_edges={\n",
    "                'black': [e for e in T2.edges() if min([tav[v] for v in e])%2==0 ], \n",
    "                'blue': [e for e in T2.edges() if min([tav[v] for v in e])%2==1] }\n",
    "            \n",
    "            d_seged['fertozottek']=(True,tuple(L_f))\n",
    "            d_seged['segedgraf']=(True,{\n",
    "                'graf':T2,\n",
    "                'position':pos_T2,\n",
    "                'thickness':3,\n",
    "                'edge_color':T2_coloring_edges,\n",
    "                'xlim':boundaries['xlim'],\n",
    "                'ylim':boundaries['ylim']\n",
    "            })\n",
    "            if j%2==0:\n",
    "                d_seged['selected_A']=(True,[u for u in T2.nodes() if tav[u]==j])\n",
    "                d_seged['selected_B']=(False,[])\n",
    "                if j==0:\n",
    "                    d_seged['code_index']=1\n",
    "                else:\n",
    "                    d_seged['code_index']=3\n",
    "            else:\n",
    "                d_seged['selected_A']=(False,[])\n",
    "                d_seged['selected_B']=(True,[u for u in T2.nodes() if tav[u]==j])\n",
    "                d_seged['code_index']=2\n",
    "            d_movie[szamlalo]=deepcopy(d_seged)\n",
    "            szamlalo+=1\n",
    "        d_seged['selected_A']=(False,[])\n",
    "        d_seged['selected_B']=(False,[])\n",
    "        d_seged['code_index']=4\n",
    "        d_movie[szamlalo]=deepcopy(d_seged)\n",
    "        Fontos_Index.append(szamlalo)\n",
    "        szamlalo+=1\n",
    "        \n",
    "    else:\n",
    "        d_seged['code_index']=4\n",
    "        d_seged['fertozottek']=(True,[])\n",
    "        d_movie[szamlalo]=deepcopy(d_seged)\n",
    "        Fontos_Index.append(szamlalo)\n",
    "        szamlalo+=1\n",
    "        \n",
    "    if b_found_alternating_path: #we found\n",
    "        #plt.figure()\n",
    "        #T=nx.Graph([(u,honnan[u]) for u in honnan if volt[u]==True])\n",
    "        #pos = graphviz_layout(T, prog=\"dot\",root='*')\n",
    "        #print(list(T.nodes))\n",
    "        #nx.draw_networkx(T, pos)\n",
    "\n",
    "        #print(T.edges(labels=False,sort=False))\n",
    "        #T.show(pos=pos_d)\n",
    "        \n",
    "        # GRAPH PLOTTING!!!\n",
    "        #T.show(pos=pos_T,edge_colors=T_coloring_edges1,edge_thickness=3)\n",
    "        \n",
    "        L=[fedetlen_veg]\n",
    "        akt=fedetlen_veg\n",
    "        while honnan[akt]!='*':\n",
    "            akt=honnan[akt]\n",
    "            L.append(akt)\n",
    "        L.reverse()\n",
    "        \n",
    "        if len(T.nodes())>0:\n",
    "            L_pv=[pos_T[u] for u in L]\n",
    "            d_seged['alternalo_javito_ut']=(True,L_pv)\n",
    "            d_seged['code_index']=5\n",
    "            d_movie[szamlalo]=deepcopy(d_seged)\n",
    "            Fontos_Index.append(szamlalo)\n",
    "            szamlalo+=1\n",
    "            \n",
    "#             C=line([(a,b) for a,b in L_pv],color='red',thickness=10,alpha=0.6)\n",
    "            \n",
    "            #C+=line([(a,b-eps) for a,b in L_pv],color='orange')\n",
    "            #C+=circle(L_pv[0],eps, color='orange')\n",
    "            #C+=circle(L_pv[-1],eps, color='orange')\n",
    "#             C+=T.plot(pos=pos_T,edge_colors=T_coloring_edges1,edge_thickness=3)\n",
    "#             C.show(axes=False)\n",
    "\n",
    "        #T_coloring_edges2={'red':[]}\n",
    "        \n",
    "#         d_seged['alternalo_javito_ut']=(True,L)\n",
    "        \n",
    "        M_torolni=[(L[i+1],L[i]) for i in range(1,len(L),2) if i+1<len(L)]\n",
    "        M_uj=[(L[i],L[i+1]) for i in range(0,len(L),2) if i+1<len(L)]\n",
    "        \n",
    "        d_seged['matching_torolni']=(True,M_torolni)\n",
    "        d_seged['matching_ujak']=(True,M_uj)\n",
    "        d_seged['code_index']=6\n",
    "        d_movie[szamlalo]=deepcopy(d_seged)\n",
    "        Fontos_Index.append(szamlalo)        \n",
    "        szamlalo+=1\n",
    "        \n",
    "        M=[e for e in M if e not in M_torolni]+M_uj\n",
    "    else:\n",
    "        Lefogo_A=[u for u in A_class if volt[u]==False]\n",
    "        Lefogo_B=[u for u in B_class if volt[u]==True]\n",
    "        Lefogo=Lefogo_A+Lefogo_B\n",
    "        d_seged['lefogo_A']=(True,Lefogo_A)\n",
    "        d_seged['lefogo_B']=(True,Lefogo_B)\n",
    "        d_seged['code_index']=7\n",
    "        d_movie[szamlalo]=deepcopy(d_seged)\n",
    "        Fontos_Index.append(szamlalo)\n",
    "        szamlalo+=1\n",
    "\n",
    "# print(M)\n",
    "# print(len(M))\n",
    "# print(len(Lefogo))\n",
    "\n",
    "# L=[(u,(i,0)) for i, u in enumerate(A_class)]+[(u,(i,1)) for i, u in enumerate(B_class)]\n",
    "# pos_G={u:p for u,p in L}\n",
    "# sG=Graph(G)\n",
    "# G_coloring={'red':[u for u in sG.vertices(sort=False) if u in Lefogo], 'blue':[u for u in sG.vertices(sort=False) if u not in Lefogo]}\n",
    "# sG.show(pos=pos_G,figsize=(10,10),vertex_colors=G_coloring)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def next_big_step(change):\n",
    "    global w\n",
    "    i = w.children[0].value\n",
    "    ind=0\n",
    "    while(ind<(len(Fontos_Index)-1) and Fontos_Index[ind]<=i):\n",
    "        ind+=1\n",
    "    w.children[0].value=Fontos_Index[ind]\n",
    "\n",
    "def previous_big_step(change):\n",
    "    global w\n",
    "    i = w.children[0].value\n",
    "    ind=len(Fontos_Index)-1\n",
    "    while(ind>0 and Fontos_Index[ind]>=i):\n",
    "        ind-=1\n",
    "    w.children[0].value=Fontos_Index[ind]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "e6602b39aff2483caa21b7c25a5c07ca",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Button(description='<Prev', style=ButtonStyle())"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a555bfda31f44d4697b81811909b5b75",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Button(description='Next>', style=ButtonStyle())"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "b180d0445717441b890ba6ba52e18122",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='index', max=89), Output()), _dom_classes=('widget-intera…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "w = interactive(plot_all,index=IntSlider(0,0,len(d_movie.keys())-1,1))\n",
    "prev = Button(description=\"<Prev\")\n",
    "prev.on_click(previous_big_step)\n",
    "nexxt= Button(description=\"Next>\")\n",
    "nexxt.on_click(next_big_step)\n",
    "display(prev)\n",
    "display(nexxt)\n",
    "display(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def create_movie_pdf(handler):\n",
    "    if 'figs' in os.listdir('.'):\n",
    "        rmtree('figs')\n",
    "    os.mkdir('figs')\n",
    "    for kepsorszam in d_movie:\n",
    "        fig=plot_all(kepsorszam)\n",
    "        fig.savefig('figs/k_'+str(kepsorszam).zfill(3)+'.pdf',density=300)\n",
    "        plt.close()\n",
    "\n",
    "    os.system('qpdf --empty --pages figs/k*.pdf -- k_movie.pdf')\n",
    "\n",
    "    local_file = FileLink('./k_movie.pdf', result_html_prefix=\"Összefűzött képek egy PDF-ben: \")\n",
    "    display(local_file)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a47a8eb7d3a7417ca1072de767a19f0b",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Button(description='Fűzd össze!', style=ButtonStyle())"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "b = Button(description = \"Fűzd össze!\")\n",
    "b.on_click(create_movie_pdf)\n",
    "b"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}