Lab_JurjenVerbruggen_ALG2.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms & Data Structures 2\n",
    "Jurjen Verbruggen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph generation\n",
    "\n",
    "Below you can find several sliders to generate a nice graph. $n$ = the amount of nodes in the graph, and $p$ is the probability of generating an edge between any two nodes. Click on the Update button to generate a new graph given the two parameters, and click on Connect to join a disconnected graph together."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import display, Markdown, clear_output\n",
    "import ipywidgets as widgets\n",
    "from vertex_manipulations import *\n",
    "import random\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "# from vcover import *\n",
    "from vcover_algorithms import *\n",
    "from graph import LabGraph\n",
    "from graph_factory import *\n",
    "from ipywidgets_debounce import *\n",
    "\n",
    "debug_mode = False\n",
    "default_n = 21\n",
    "default_p = 0.8\n",
    "default_k = 17\n",
    "\n",
    "n_input = widgets.IntSlider(value = default_n, min=1, max=100, step=1, description=\"n\")\n",
    "p_input = widgets.FloatSlider(value = default_p, min=0, max=1, step=0.01, description=\"p\")\n",
    "reroll_button = widgets.Button(description=\"Reroll\")\n",
    "connect_button = widgets.Button(description=\"Connect\")\n",
    "\n",
    "pendant_plus_button = widgets.Button(description=\"p++\")\n",
    "pendant_minus_button = widgets.Button(description=\"p--\")\n",
    "tops_plus_button = widgets.Button(description=\"t++\")\n",
    "tops_minus_button = widgets.Button(description=\"t--\")\n",
    "highlight_kernelization_button = widgets.Button(description=\"Refresh\")\n",
    "\n",
    "k_vcover_input_max = n_input.value\n",
    "k_vcover_input = widgets.IntSlider(value=default_k, min=1, max=k_vcover_input_max, step=1, description=\"k\")\n",
    "calculate_k_vcover_button = widgets.Button(description=\"Calculate\")\n",
    "calculated_text = widgets.Textarea(description=\"calculated\")\n",
    "calculated_one_text = widgets.Textarea()\n",
    "progressbar_spec = widgets.Label(description=\"spec\")\n",
    "vcover_progressbar = widgets.IntProgress(min=0, max=1, value=0, description=\"progress\")\n",
    "\n",
    "calculate_vcover_mode_buttons = widgets.RadioButtons(\n",
    "    options=['brute force', 'enhanced brute force', 'greedy', 'take-2'],\n",
    "    value='brute force',\n",
    "    description='Mode'\n",
    ")\n",
    "out_graph = widgets.Output()\n",
    "matrix_widget = widgets.Output()\n",
    "\n",
    "debug_view = widgets.Output(layout={'border': '1px solid black'})\n",
    "logger_area = widgets.Textarea(description=\"log\")\n",
    "\n",
    "class State:\n",
    "    displayed_graph = GraphFactory.generate_networkx_matrix(default_n, default_p)\n",
    "    vcover_interrupt = 0\n",
    "    ui_update_debounce = 0 # Set before start of algorithm\n",
    "    ui_update_debounce_state = ui_update_debounce\n",
    "\n",
    "    progress_value = 0\n",
    "\n",
    "    def debounce():\n",
    "        if State.ui_update_debounce_state <= 0:\n",
    "            State.ui_update_debounce_state = State.ui_update_debounce\n",
    "            return False\n",
    "        else:\n",
    "            State.ui_update_debounce_state -= 1\n",
    "            return True\n",
    "\n",
    "    def set_update_debounce(x: int):\n",
    "        State.ui_update_debounce = x\n",
    "        State.ui_update_debounce_state = x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a8860b03dbd344ba8a8a39a0c134d1fd",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "VBox(children=(IntSlider(value=21, description='n', min=1), FloatSlider(value=0.8, description='p', max=1.0, s…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "generator_controls = widgets.VBox([n_input, p_input, widgets.HBox([reroll_button, connect_button])])\n",
    "generator_controls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0327c7ef4d8543a880db40fa05a2bdde",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Output()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def draw_nx(graph):\n",
    "    color_map = graph.get_color_map(k_vcover_input.value)\n",
    "    nx.draw(graph, node_color=color_map, pos=nx.spring_layout(graph, seed = 1))\n",
    "    nx.draw_networkx_labels(graph, pos=nx.spring_layout(graph, seed = 1))\n",
    "    k_vcover_input.max = len(graph.nodes())\n",
    "\n",
    "out_graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "a5a82de654bf4008a178496640ec7a86",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "Output()"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "matrix_widget"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def update_matrix():\n",
    "    with matrix_widget:\n",
    "        clear_output()\n",
    "        graph = State.displayed_graph\n",
    "        result = graph.print_matrix()\n",
    "        print(result)\n",
    "\n",
    "def on_connect():\n",
    "    with out_graph:\n",
    "        graph = State.displayed_graph\n",
    "        if graph is not None:\n",
    "            clear_output()\n",
    "            graph.connect()\n",
    "            draw_nx(graph)\n",
    "            plt.show()\n",
    "    update_matrix()\n",
    "\n",
    "def on_reroll():\n",
    "    with out_graph:\n",
    "        clear_output()\n",
    "        connect_button.disabled = False\n",
    "        n = n_input.value\n",
    "        p = p_input.value\n",
    "        graph = GraphFactory.generate_networkx_matrix(n, p)\n",
    "        State.displayed_graph = graph\n",
    "        calculate_k_vcover_button.disabled = False\n",
    "        draw_nx(State.displayed_graph)\n",
    "        plt.show()\n",
    "    update_matrix()\n",
    "\n",
    "def on_connect_button(_):\n",
    "    on_connect()\n",
    "\n",
    "def on_reroll_button(_):\n",
    "    on_reroll()\n",
    "\n",
    "reroll_button.on_click(on_reroll_button)\n",
    "connect_button.on_click(on_connect_button)\n",
    "\n",
    "def refresh_outputs():\n",
    "    with out_graph:\n",
    "        dg = State.displayed_graph\n",
    "        if dg is not None:\n",
    "            clear_output()\n",
    "            color_map = dg.get_color_map(k_vcover_input.value)\n",
    "            draw_nx(dg)\n",
    "            plt.show()\n",
    "            update_matrix()\n",
    "\n",
    "def refresh_with_coloring():\n",
    "    refresh_outputs()\n",
    "\n",
    "def on_pendant_plus_button(_):\n",
    "    State.displayed_graph.add_pendant()\n",
    "    refresh_with_coloring()\n",
    "\n",
    "def on_pendant_minus_button(_):\n",
    "    State.displayed_graph.remove_pendant()\n",
    "    refresh_with_coloring()\n",
    "\n",
    "def on_tops_plus_button(_):\n",
    "    k = k_vcover_input.value\n",
    "    State.displayed_graph.add_tops(k)\n",
    "    refresh_with_coloring()\n",
    "\n",
    "def on_tops_minus_button(_):\n",
    "    k = k_vcover_input.value\n",
    "    State.displayed_graph.remove_tops(k)\n",
    "    refresh_with_coloring()\n",
    "\n",
    "def on_highlight_kernelization_button(_):\n",
    "    refresh_with_coloring()\n",
    "\n",
    "pendant_plus_button.on_click(on_pendant_plus_button)\n",
    "pendant_minus_button.on_click(on_pendant_minus_button)\n",
    "tops_plus_button.on_click(on_tops_plus_button)\n",
    "tops_minus_button.on_click(on_tops_minus_button)\n",
    "highlight_kernelization_button.on_click(on_highlight_kernelization_button)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2894cf99e73142eaa859db5b6596a0b4",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "HBox(children=(VBox(children=(HBox(children=(IntSlider(value=17, description='k', max=21, min=1), Button(descr…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "def on_update_k_slider(_):\n",
    "    refresh_with_coloring()\n",
    "\n",
    "def set_progressbar(val, force=False):\n",
    "    State.progress_value = val\n",
    "    if not force and State.debounce():\n",
    "        return\n",
    "\n",
    "    max = vcover_progressbar.max\n",
    "    quo = val/max*100\n",
    "    progressbar_spec.value = \"%.2f\" % quo + \"% (\" + str(val) + \"/\" + str(max) + \")\"\n",
    "    if val > max: return\n",
    "    vcover_progressbar.value = val\n",
    "\n",
    "def complete_progressbar():\n",
    "    set_progressbar(vcover_progressbar.max, force=True)\n",
    "    State.ui_update_debounce_state = State.ui_update_debounce\n",
    "\n",
    "def update_progressbar(x: int):\n",
    "    val = State.progress_value\n",
    "    set_progressbar(x+val)\n",
    "    \n",
    "def update_calculated_text(x: str):\n",
    "    calculated_text.value = x\n",
    "\n",
    "def on_calculate_k_vcover_button(_):\n",
    "    calculate_k_vcover_button.disabled = True\n",
    "    if State.displayed_graph == None:\n",
    "        return\n",
    "\n",
    "    State.progress_value = 0\n",
    "    g = State.displayed_graph\n",
    "    nodes = list(g.nodes())\n",
    "    edges = list(g.edges())\n",
    "    k = k_vcover_input.value\n",
    "    n = len(nodes)\n",
    "    algorithm_mode = calculate_vcover_mode_buttons.value\n",
    "\n",
    "    vcover_progressbar.value = 0\n",
    "    vcovers = None\n",
    "\n",
    "    pbar_incr = lambda x : update_progressbar(x)\n",
    "    pbar_desc = lambda _ : _ # Old code that I refuse to remove\n",
    "    # pbar_desc = lambda x : update_calculated_text(x)\n",
    "\n",
    "    update_calculated_text(\"Calculating...\")\n",
    "    calculated_one_text.value = \"\"\n",
    "    if algorithm_mode == \"enhanced brute force\":\n",
    "        complx = 2**k\n",
    "        State.set_update_debounce(int(complx/100))\n",
    "        vcover_progressbar.max = complx\n",
    "\n",
    "        vcovers = VCoverEnhanced(nodes, edges, k, pbar_incr, pbar_desc).find_vcovers()\n",
    "    elif algorithm_mode == \"brute force\":\n",
    "        complx = 2**(n+1)\n",
    "        State.set_update_debounce(int(complx/100))\n",
    "        vcover_progressbar.max = complx\n",
    "        vcovers = VCoverBruteForce(nodes, edges, n, k, pbar_incr, pbar_desc).find_vcovers()\n",
    "    elif algorithm_mode == \"greedy\":\n",
    "        complx = n**2\n",
    "        State.set_update_debounce(int(complx/100))\n",
    "        vcover_progressbar.max = complx\n",
    "        vcovers = VCoverGreedy(edges).find_vcovers()\n",
    "    elif algorithm_mode == \"take-2\":\n",
    "        complx = n**2\n",
    "        State.set_update_debounce(int(complx/100))\n",
    "        vcover_progressbar.max = complx\n",
    "        vcovers = VCoverTakeTwo(edges).find_vcovers()\n",
    "    \n",
    "    complete_progressbar()\n",
    "    if vcovers == None or len(vcovers) == 0:\n",
    "        update_calculated_text(\"No v-cover possible for k=\" + str(k))\n",
    "    else:\n",
    "        update_calculated_text(\"Possible v-covers: \\n\" + str(vcovers))\n",
    "        vcover = vcovers[0]\n",
    "        calculated_one_text.value = str(vcover)\n",
    "    \n",
    "    calculate_k_vcover_button.disabled = False\n",
    "\n",
    "calculate_k_vcover_button.on_click(on_calculate_k_vcover_button)\n",
    "\n",
    "box_week2 = widgets.VBox([\n",
    "    widgets.HBox([k_vcover_input, highlight_kernelization_button]), \n",
    "    widgets.HBox([calculate_vcover_mode_buttons, calculate_k_vcover_button]), \n",
    "    widgets.HBox([calculated_text, calculated_one_text]), \n",
    "    vcover_progressbar, \n",
    "    progressbar_spec,\n",
    "    widgets.HBox([pendant_plus_button, pendant_minus_button]),\n",
    "    widgets.HBox([tops_plus_button, tops_minus_button])\n",
    "])\n",
    "cpanel = widgets.HBox([\n",
    "    box_week2,\n",
    "    widgets.VBox([\n",
    "        logger_area\n",
    "    ])\n",
    "])\n",
    "\n",
    "if debug_mode:\n",
    "    on_calculate_k_vcover_button(1)\n",
    "cpanel"
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "883c4abf4a0508d0816d710d3d2bf12d5dead1f2acd091a24a7c12c2b379361b"
  },
  "kernelspec": {
   "display_name": "Python 3.9.7 64-bit",
   "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.9.7"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}