{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wprowadzenie\n",
    "\n",
    "Poniższy notatnik prezentuje podstawowe operacje na grafach z wykorzystaniem biblioteki `NetworkX`, w tym tworzenie grafów skierowanych i nieskierowanych, budowę macierzy i listy sąsiedztwa, a także omówienie podobieństw i różnic między tymi reprezentacjami."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import bibliotek"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "import torch as th\n",
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import torch_geometric as pyg\n",
    "\n",
    "import sys\n",
    "sys.path.append('..')\n",
    "import utils.vis_utils as vis_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Podstawy budowy grafów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Graf nieskierowany:\n",
      "Wierzchołki: [0, 1, 2, 3, 4]\n",
      "Krawędzie: [(0, 1), (1, 2), (1, 3), (2, 3), (3, 4)]\n",
      "\n",
      "Graf skierowany:\n",
      "Wierzchołki: [0, 1, 2, 3, 4]\n",
      "Krawędzie: [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)]\n"
     ]
    }
   ],
   "source": [
    "# Przykład grafu nieskierowanego\n",
    "G_undirected = nx.Graph()\n",
    "# Dodajemy krawędzie do grafu nieskierowanego.\n",
    "# W grafie nieskierowanym krawędź {u, v} oznacza, że u i v są połączone symetrycznie.\n",
    "G_undirected.add_edge(0, 1)\n",
    "G_undirected.add_edge(1, 2)\n",
    "G_undirected.add_edge(2, 3)\n",
    "G_undirected.add_edge(3, 4)\n",
    "G_undirected.add_edge(3, 1)\n",
    "\n",
    "print(\"Graf nieskierowany:\")\n",
    "print(\"Wierzchołki:\", list(G_undirected.nodes()))\n",
    "print(\"Krawędzie:\", list(G_undirected.edges()))\n",
    "\n",
    "# Przykład grafu skierowanego\n",
    "G_directed = nx.DiGraph()\n",
    "# Dodajemy krawędzie do grafu skierowanego.\n",
    "# W grafie skierowanym krawędź e_uv jest interpretowana jako informacja przekazywana od wierzchołka u do wierzchołka v.\n",
    "G_directed.add_edge(0, 1)\n",
    "G_directed.add_edge(1, 2)\n",
    "G_directed.add_edge(2, 3)\n",
    "G_directed.add_edge(3, 1)  # Przykład krawędzi powrotnej.\n",
    "G_directed.add_edge(3, 4)\n",
    "print(\"\\nGraf skierowany:\")\n",
    "print(\"Wierzchołki:\", list(G_directed.nodes()))\n",
    "print(\"Krawędzie:\", list(G_directed.edges()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 29012 characters]",
      "text/plain": [
       "<Figure size 472.441x393.701 with 2 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "fig, (ax1, ax2) = plt.subplots(1, 2, figsize=vis_utils.image_size_in_cm(12, 10))\n",
    "\n",
    "# Rysowanie grafu nieskierowanego\n",
    "pos_undirected = nx.spring_layout(G_undirected, seed=123)\n",
    "nx.draw(G_undirected, ax=ax1, pos=pos_undirected, with_labels=True, node_color='lightblue', edge_color='gray')\n",
    "ax1.set_title('Graf nieskierowany')\n",
    "\n",
    "# Rysowanie grafu skierowanego\n",
    "nx.draw(G_directed, ax=ax2, with_labels=True, pos=pos_undirected, node_color='lightgreen', edge_color='red', font_size=12)\n",
    "ax2.set_title('Graf skierowany')\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.savefig('rys_2.1.tiff', pil_kwargs={\"compression\": \"tiff_lzw\"})\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Lista i macierz sąsiedztwa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "A_undirected = nx.adjacency_matrix(G_undirected).todense()\n",
    "A_directed = nx.adjacency_matrix(G_directed).todense()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 0, 0, 0],\n",
       "       [1, 0, 1, 1, 0],\n",
       "       [0, 1, 0, 1, 0],\n",
       "       [0, 1, 1, 0, 1],\n",
       "       [0, 0, 0, 1, 0]])"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_undirected"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 0, 0, 0],\n",
       "       [0, 0, 1, 0, 0],\n",
       "       [0, 0, 0, 1, 0],\n",
       "       [0, 1, 0, 0, 1],\n",
       "       [0, 0, 0, 0, 0]])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_directed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Stopnie wierzchołka"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stopnie wierzchołków w grafie nieskierowanym:\n",
      "Wbudowana funkcja: [(0, 1), (1, 3), (2, 2), (3, 3), (4, 1)]\n",
      "Ręczne obliczenie: [1 3 2 3 1]\n",
      "\n",
      "Stopnie wierzchołków w grafie skierowanym:\n",
      "Wbudowana funkcja: [(0, 1), (1, 3), (2, 2), (3, 3), (4, 1)]\n",
      "Ręczne obliczenie: [1 3 2 3 1]\n"
     ]
    }
   ],
   "source": [
    "# Wbudowana funkcja:\n",
    "deg_undirected = nx.degree(G_undirected)\n",
    "deg_directed = nx.degree(G_directed)\n",
    "\n",
    "# Ręczne obliczenie stopni wierzchołków\n",
    "## Podniesienie macierzy sąsiedztwa do 2 potęgi w grafie nieskierowanym\n",
    "deg_undirected_manual = np.diag(np.linalg.matrix_power(A_undirected, 2))\n",
    "\n",
    "## Sumowanie krawędzi wchodzących i wychodzących w grafie skierowanym\n",
    "deg_directed_manual = A_directed.sum(0) + A_directed.sum(1)\n",
    "\n",
    "print(\"Stopnie wierzchołków w grafie nieskierowanym:\")\n",
    "print(\"Wbudowana funkcja:\", deg_undirected)\n",
    "print(\"Ręczne obliczenie:\", deg_undirected_manual)\n",
    "\n",
    "print(\"\\nStopnie wierzchołków w grafie skierowanym:\")\n",
    "print(\"Wbudowana funkcja:\", deg_directed)\n",
    "print(\"Ręczne obliczenie:\", deg_directed_manual)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "adj_list_undirected = nx.generate_adjlist(G_undirected)\n",
    "adj_list_directed =  nx.generate_adjlist(G_directed)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['0 1', '1 2 3', '2 3', '3 4', '4']"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(adj_list_undirected)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Lista sąsiedztwa w grafie nieskierowanym PyG:\n",
      "tensor([[0, 1, 1, 1, 2, 2, 3, 3, 3, 4],\n",
      "        [1, 0, 2, 3, 1, 3, 2, 4, 1, 3]])\n"
     ]
    }
   ],
   "source": [
    "G_undirected_pyg = pyg.utils.from_networkx(G_undirected)\n",
    "print(\"Lista sąsiedztwa w grafie nieskierowanym PyG:\")\n",
    "print(G_undirected_pyg.edge_index)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Lista sąsiedztwa w grafie skierowanym PyG:\n",
      "tensor([[0, 1, 2, 3, 3],\n",
      "        [1, 2, 3, 1, 4]])\n"
     ]
    }
   ],
   "source": [
    "G_directed_pyg = pyg.utils.from_networkx(G_directed)\n",
    "print(\"\\nLista sąsiedztwa w grafie skierowanym PyG:\")\n",
    "print(G_directed_pyg.edge_index)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Ścieżki o zadanej długości"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 0, 1, 1, 0],\n",
       "       [0, 3, 1, 1, 1],\n",
       "       [1, 1, 2, 1, 1],\n",
       "       [1, 1, 1, 3, 0],\n",
       "       [0, 1, 1, 0, 1]])"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.linalg.matrix_power(A_undirected, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([1, 3, 2, 3, 1])"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "A_directed.sum(-1) + A_directed.sum(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[1 0 1 1 0]\n",
      " [0 3 1 1 1]\n",
      " [1 1 2 1 1]\n",
      " [1 1 1 3 0]\n",
      " [0 1 1 0 1]]\n"
     ]
    }
   ],
   "source": [
    "A_und = nx.adjacency_matrix(G_undirected).todense()\n",
    "A_und2 = np.linalg.matrix_power(A_und, 2)\n",
    "print(A_und2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 3 1 1 1]\n",
      " [3 2 4 5 1]\n",
      " [1 4 2 4 1]\n",
      " [1 5 4 2 3]\n",
      " [1 1 1 3 0]]\n"
     ]
    }
   ],
   "source": [
    "A_und3 = np.linalg.matrix_power(A_und, 3)\n",
    "print(A_und3)"
   ]
  }
 ],
 "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
}
