{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wprowadzenie\n",
    "\n",
    "Ten notatnik prezentuje zagadnienie badania izomorfizmu grafów za pomocą testu Weisfeilera-Lehmana."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import bibliotek"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import numpy as np\n",
    "\n",
    "import sys\n",
    "sys.path.append('..')\n",
    "import utils.vis_utils as vis_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Przygotowanie danych"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Zbudujmy dwa bardzo podobne grafy, które są od siebie nieodróżnialne, gdy stosuje się proste metody."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 27712 characters]",
      "text/plain": [
       "<Figure size 472.441x393.701 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "g1 = nx.Graph()\n",
    "g1.add_edges_from((\n",
    "    ('a', 'c'),\n",
    "    ('b', 'c'),\n",
    "    ('d', 'c'),\n",
    "    ('c', 'e'),\n",
    "    ('e', 'f'),\n",
    "    ('e', 'd'),\n",
    "    ('f', 'd')\n",
    "))\n",
    "\n",
    "g2 = nx.Graph()\n",
    "g2.add_edges_from((\n",
    "    ('a', 'c'),\n",
    "    ('b', 'd'),\n",
    "    ('d', 'c'),\n",
    "    ('c', 'e'),\n",
    "    ('c', 'f'),\n",
    "    ('e', 'f'),\n",
    "    ('f', 'd')\n",
    "))\n",
    "\n",
    "fig, axes = plt.subplots(1, 2, figsize=vis_utils.image_size_in_cm(12, 10))\n",
    "\n",
    "pos = nx.spring_layout(g1, seed=111)\n",
    "\n",
    "nx.draw(g1, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, ax=axes[0], font_size=12)\n",
    "axes[0].set_title(\"Graf 1\")\n",
    "axes[0].axis(\"off\")\n",
    "\n",
    "# Plotting the second graph\n",
    "nx.draw(g2, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, ax=axes[1], font_size=12)\n",
    "axes[1].set_title(\"Graf 2\")\n",
    "axes[1].axis(\"off\")\n",
    "plt.tight_layout()\n",
    "plt.savefig(\"rys_2.4.tiff\", pil_kwargs={\"compression\": \"tiff_lzw\"})\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test WL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Uproszczona implementacja"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def wl_naive_impl(\n",
    "    g: nx.Graph, \n",
    "    pos=None,\n",
    "    iters: int = 4, \n",
    "    plot: bool = False, \n",
    "    plot_title: str = \"Test WL\", \n",
    "    plot_name: str = \"iteracja_wl.tiff\"):\n",
    "\n",
    "    # Inicjalizacja kolorów dla każdego wierzchołka, na początku wszystkie wierzchołki mają kolor 1\n",
    "    colors = {node: 1 for node in g.nodes}\n",
    "    \n",
    "    # Jeśli wyświetlanie wykresu jest włączone, przygotuj układ i rysowanie grafu\n",
    "    if plot:\n",
    "        # Jeśli nie podano pozycji wierzchołków, użyj układu sprężynowego\n",
    "        pos = nx.spring_layout(g, seed=111) if pos is None else pos\n",
    "        num_plots = iters + 1  # liczba wykresów\n",
    "        \n",
    "        # Ustalamy dwie kolumny i dwie lub więcej rzędy: ceil(num_plots / 2) rzędów\n",
    "        cols = 2\n",
    "        rows = (num_plots + 1) // 2\n",
    "\n",
    "        # Całkowita szerokość dla wszystkich wykresów razem = 12 cm\n",
    "        fig_width_cm = 12.0\n",
    "        # Dostosuj wysokość: np. 6 cm na rząd\n",
    "        fig_height_per_row_cm = 6\n",
    "        fig_height_cm = fig_height_per_row_cm * rows\n",
    "\n",
    "        fig, axes = plt.subplots(rows, cols, figsize=vis_utils.image_size_in_cm(fig_width_cm, fig_height_cm))\n",
    "        axes = axes.flatten() if num_plots > 1 else [axes]\n",
    "\n",
    "        # Etykiety wierzchołków zawierające nazwę wierzchołka i jego kolor\n",
    "        labels = {node: f'{node}, {color}' for node, color in colors.items()}\n",
    "        # Rysowanie grafu dla iteracji 0\n",
    "        nx.draw(\n",
    "            g, pos, with_labels=True, labels=labels, \n",
    "            edge_color='gray', node_color='lightgrey', node_size=500, \n",
    "            ax=axes[0], font_size=12\n",
    "        )\n",
    "        axes[0].set_title('Iteracja 0')\n",
    "        axes[0].axis('off')\n",
    "    \n",
    "    # K kolejnych iteracji\n",
    "    for it in range(iters):\n",
    "        new_colors = {}\n",
    "        # Aktualizacja kolorów dla każdego wierzchołka\n",
    "        for node in g.nodes:\n",
    "            neighbors = g.neighbors(node)\n",
    "            neighbor_colors = [colors[neighbor] for neighbor in neighbors]\n",
    "            # Nowy kolor to suma kolorów sąsiadów i własnego koloru\n",
    "            new_colors[node] = sum([colors[node]] + neighbor_colors)\n",
    "        # Jeśli kolory się nie zmieniły, zakończ iteracje\n",
    "        if colors == new_colors:\n",
    "            break\n",
    "        colors = new_colors\n",
    "        # Jeśli wyświetlanie wykresu jest włączone, rysuj graf dla każdej iteracji\n",
    "        if plot:\n",
    "            ax_idx = it + 1\n",
    "            if ax_idx < len(axes):\n",
    "                ax = axes[ax_idx]\n",
    "            else:\n",
    "                ax = plt.gca()\n",
    "            labels = {node: f'{node}, {color}' for node, color in colors.items()}\n",
    "            nx.draw(\n",
    "                g, pos, with_labels=True, labels=labels, \n",
    "                edge_color='gray', node_color='lightgrey', node_size=500, \n",
    "                ax=ax, font_size=12\n",
    "            )\n",
    "            ax.set_title(f'Iteracja {it + 1}')\n",
    "            ax.axis('off')\n",
    "    \n",
    "    # Wyłączanie nieużywanych osi, jeśli wyświetlanie wykresu jest włączone\n",
    "    if plot:\n",
    "        # Wyłącz nieużywane osie\n",
    "        for ax in axes[it+2:]:\n",
    "            ax.axis('off')\n",
    "        fig.suptitle(plot_title)\n",
    "        plt.tight_layout()\n",
    "        plt.savefig(plot_name, pil_kwargs={\"compression\": \"tiff_lzw\"})\n",
    "        plt.show()\n",
    "    \n",
    "    # Zwrócenie końcowych kolorów wierzchołków\n",
    "    return colors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 37716 characters]",
      "text/plain": [
       "<Figure size 472.441x472.441 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "{'a': 7, 'c': 17, 'b': 7, 'd': 16, 'e': 16, 'f': 11}"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wl_naive_impl(g1, iters=2, plot=True, plot_title=\"\", plot_name=\"rys_2.5.tiff\", pos=pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 40768 characters]",
      "text/plain": [
       "<Figure size 472.441x472.441 with 4 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "{'a': 7, 'c': 18, 'b': 6, 'd': 15, 'e': 12, 'f': 16}"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "wl_naive_impl(g2, iters=2, plot=True, plot_title=\"\", plot_name=\"rys_2.6.tiff\", pos=pos)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "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.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
