{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Wprowadzenie\n",
    "\n",
    "Poniższy notatnik prezentuje podstawowe własności liczbowe grafów, oraz wierzchołków, przydatne w procesie analizy - zarówno klasycznej, jak i z wykorzystaniem sieci GNN."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import bibliotek"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import networkx as nx\n",
    "import matplotlib.pyplot as plt\n",
    "import pandas as pd\n",
    "\n",
    "import sys\n",
    "sys.path.append('..')\n",
    "import utils.vis_utils as vis_utils"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Przygotowanie danych\n",
    "\n",
    "Będziemy pracować na przykładowym grafie, dobrze ilustrującym omawiane koncepcje."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "[encoded data, 21012 characters]",
      "text/plain": [
       "<Figure size 472.441x393.701 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Konstruujemy prosty graf nieskierowany\n",
    "G = nx.Graph()\n",
    "# Dodajemy krawędzie, w których wierzchołek 0 pełni rolę centralnego:\n",
    "# z 0 wychodzą bezpośrednie połączenia do 1, 2, 3\n",
    "G.add_edges_from([(0, 1), (0, 2), (0, 3)])\n",
    "# Alternatywne ścieżki od centralnego poprzez różne wierzchołki do 4\n",
    "G.add_edges_from([(1, 4), (2, 4), (3, 4)])\n",
    "# Kolejne połączenie tworzy ścieżkę wychodzącą z 4 do 5\n",
    "G.add_edge(4, 5)\n",
    "\n",
    "# Wizualizacja grafu\n",
    "fig, ax = plt.subplots(figsize=vis_utils.image_size_in_cm(12, 10))\n",
    "pos = nx.spring_layout(G, seed=42)\n",
    "nx.draw_networkx(G, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=500, font_size=12)\n",
    "plt.axis(\"off\")\n",
    "plt.tight_layout()\n",
    "plt.savefig(\"rys_2.2.tiff\",  pil_kwargs={\"compression\": \"tiff_lzw\"})\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wierzchołek 0 - stopień 3\n",
      "Wierzchołek 1 - stopień 2\n",
      "Wierzchołek 2 - stopień 2\n",
      "Wierzchołek 3 - stopień 2\n",
      "Wierzchołek 4 - stopień 4\n",
      "Wierzchołek 5 - stopień 1\n"
     ]
    }
   ],
   "source": [
    "for node, deg in G.degree():\n",
    "    print(f\"Wierzchołek {node} - stopień {deg}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Miary centralności wierzchołków"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centralność stopnia"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\Centralność stopnia (Degree Centrality):\n",
      "Wierzchołek 0: 0.60\n",
      "Wierzchołek 1: 0.40\n",
      "Wierzchołek 2: 0.40\n",
      "Wierzchołek 3: 0.40\n",
      "Wierzchołek 4: 0.80\n",
      "Wierzchołek 5: 0.20\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "<>:3: SyntaxWarning: invalid escape sequence '\\C'\n",
      "<>:3: SyntaxWarning: invalid escape sequence '\\C'\n",
      "/tmp/ipykernel_19532/266312755.py:3: SyntaxWarning: invalid escape sequence '\\C'\n",
      "  print(\"\\Centralność stopnia (Degree Centrality):\")\n"
     ]
    }
   ],
   "source": [
    "# Obliczenie stopnia centralności za pomocą funkcji degree_centrality\n",
    "degree_centrality = nx.degree_centrality(G)\n",
    "print(\"\\Centralność stopnia (Degree Centrality):\")\n",
    "for node, value in degree_centrality.items():\n",
    "    print(f\"Wierzchołek {node}: {value:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Pośrednictwo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Pośrednictwo (Betweenness Centrality):\n",
      "Wierzchołek 0: 0.15\n",
      "Wierzchołek 1: 0.07\n",
      "Wierzchołek 2: 0.07\n",
      "Wierzchołek 3: 0.07\n",
      "Wierzchołek 4: 0.55\n",
      "Wierzchołek 5: 0.00\n"
     ]
    }
   ],
   "source": [
    "betweenness_centrality = nx.betweenness_centrality(G, normalized=True)\n",
    "print(\"\\nPośrednictwo (Betweenness Centrality):\")\n",
    "for node, value in betweenness_centrality.items():\n",
    "    print(f\"Wierzchołek {node}: {value:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sprawdzenie wyniku dla wierzchołka \"0\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Manualne Pośrednictwo (Betweenness Centrality):\n",
      "Wierzchołek 0: 0.14\n",
      "Wierzchołek 1: 0.09\n",
      "Wierzchołek 2: 0.09\n",
      "Wierzchołek 3: 0.09\n",
      "Wierzchołek 4: 0.41\n",
      "Wierzchołek 5: 0.00\n"
     ]
    }
   ],
   "source": [
    "# Inicjalizacja słownika do przechowywania pośrednictwa\n",
    "betweenness_centrality_manual = {node: 0 for node in G.nodes()}\n",
    "\n",
    "# Obliczenie wszystkich najkrótszych ścieżek między wszystkimi parami wierzchołków.\n",
    "# BARDZO KOSZTOWNE OBLICZENIOWO I NIEEFEKTYWNE!\n",
    "all_shortest_paths = dict(nx.all_pairs_all_shortest_paths(G))\n",
    "\n",
    "total_paths = 0\n",
    "\n",
    "# Zliczanie, ile najkrótszych ścieżek przechodzi przez każdy wierzchołek\n",
    "for source, target_paths in all_shortest_paths.items():\n",
    "    for target, paths in target_paths.items():\n",
    "        if source == target:\n",
    "            continue\n",
    "        total_paths += len(paths)\n",
    "        for path in paths:\n",
    "            for node in path[1:-1]:\n",
    "                betweenness_centrality_manual[node] += 1\n",
    "\n",
    "# Wyliczenie pośrednictwa\n",
    "for node in betweenness_centrality_manual:\n",
    "    betweenness_centrality_manual[node] /= total_paths\n",
    "\n",
    "print(\"Manualne Pośrednictwo (Betweenness Centrality):\")\n",
    "for node, value in betweenness_centrality_manual.items():\n",
    "    print(f\"Wierzchołek {node}: {value:.2f}\")\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Centralność sąsiedztwa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Centralność sąsiedztwa (Closeness Centrality):\n",
      "Wierzchołek 0: 0.62\n",
      "Wierzchołek 1: 0.62\n",
      "Wierzchołek 2: 0.62\n",
      "Wierzchołek 3: 0.62\n",
      "Wierzchołek 4: 0.83\n",
      "Wierzchołek 5: 0.50\n"
     ]
    }
   ],
   "source": [
    "# Obliczenie centralności sąsiedztwa\n",
    "closeness_centrality = nx.closeness_centrality(G)\n",
    "print(\"\\nCentralność sąsiedztwa (Closeness Centrality):\")\n",
    "for node, value in closeness_centrality.items():\n",
    "    print(f\"Wierzchołek {node}: {value:.2f}\")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Wierzchołek 0: 0.62\n",
      "Wierzchołek 1: 0.62\n",
      "Wierzchołek 2: 0.62\n",
      "Wierzchołek 3: 0.62\n",
      "Wierzchołek 4: 0.83\n",
      "Wierzchołek 5: 0.50\n"
     ]
    }
   ],
   "source": [
    "# Inicjalizacja słownika do przechowywania centralności sąsiedztwa\n",
    "closeness_centralities_manual = {node: 0 for node in G.nodes()}\n",
    "\n",
    "# Iteracja przez wszystkie pary wierzchołków i ich najkrótsze ścieżki\n",
    "# Najkrótsze ścieżki między parami wierzchołków wyznaczamy \n",
    "# za pomocą wbudowanej funkcji NetworkX.\n",
    "for source, target_paths in list(nx.all_pairs_shortest_path_length(G)):\n",
    "    # Suma długości wszystkich najkrótszych ścieżek od źródła do wszystkich \n",
    "    # innych wierzchołków\n",
    "    shortest_path_lengths = sum(target_paths.values())\n",
    "    # Liczba wierzchołków osiągalnych z danego źródła\n",
    "    reachable = len(target_paths)\n",
    "    # Obliczenie centralności sąsiedztwa dla danego wierzchołka\n",
    "    closeness_centralities_manual[source] = (reachable - 1) / shortest_path_lengths\n",
    "\n",
    "# Wyświetlenie wyników centralności sąsiedztwa dla każdego wierzchołka\n",
    "for node, value in closeness_centralities_manual.items():\n",
    "    print(f\"Wierzchołek {node}: {value:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Charkterystyki grafu"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Wykorzystujące stopnie wierzchołków"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Średni stopień wierzchołka: 2.33\n"
     ]
    }
   ],
   "source": [
    "# Wyliczenie średniego stopnia wierzchołka\n",
    "average_degree = sum(dict(G.degree()).values()) / len(G.nodes())\n",
    "print(f\"Średni stopień wierzchołka: {average_degree:.2f}\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Częstość wyst. stopni: [0, 1, 3, 1, 1]\n",
      "Znormalizowana częstość wyst. stopni: [0.   0.17 0.5  0.17 0.17]\n"
     ]
    },
    {
     "data": {
      "image/png": "[encoded data, 13968 characters]",
      "text/plain": [
       "<Figure size 472.441x393.701 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "degree_counts = nx.degree_histogram(G)\n",
    "degree_norm = np.array(degree_counts) / nx.number_of_nodes(G)\n",
    "degrees = range(len(degree_counts))\n",
    "print(\"Częstość wyst. stopni:\", degree_counts)\n",
    "print(\"Znormalizowana częstość wyst. stopni:\", degree_norm.round(2))\n",
    "\n",
    "plt.figure(figsize=vis_utils.image_size_in_cm(12, 10))\n",
    "# Użycie odcienia szarości zamiast koloru niebieskiego\n",
    "bars = plt.bar(degrees, degree_norm, color='lightgrey', edgecolor='black')\n",
    "\n",
    "plt.xlabel('Stopień')\n",
    "plt.ylabel('Częstość')\n",
    "\n",
    "\n",
    "ax = plt.gca()\n",
    "vis_utils.change_plot_comma_separator(ax, y_change=True, x_change=False)\n",
    "\n",
    "plt.tight_layout()\n",
    "plt.savefig(\"rys_2.3.tiff\", pil_kwargs={\"compression\": \"tiff_lzw\"})\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Metryki oparte o długośc ścieżki"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Średnica grafu\n",
    "nx.diameter(G)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.average_shortest_path_length(G)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Nieodróżnialność grafów"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "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": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Graf 1</th>\n",
       "      <th>Graf 2</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>Ropzkład stopni</th>\n",
       "      <td>[0, 2, 1, 2, 1]</td>\n",
       "      <td>[0, 2, 1, 2, 1]</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Średni stopień</th>\n",
       "      <td>2.333</td>\n",
       "      <td>2.333</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Promień</th>\n",
       "      <td>3</td>\n",
       "      <td>3</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>Średnia dł. najkr.ścieżki</th>\n",
       "      <td>1.667</td>\n",
       "      <td>1.667</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "                                    Graf 1           Graf 2\n",
       "Ropzkład stopni            [0, 2, 1, 2, 1]  [0, 2, 1, 2, 1]\n",
       "Średni stopień                       2.333            2.333\n",
       "Promień                                  3                3\n",
       "Średnia dł. najkr.ścieżki            1.667            1.667"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def graph_properties(graph):\n",
    "    \"\"\"\n",
    "    Funkcja wyznacza podstawowe własności grafu:\n",
    "    - histogram stopni wierzchołków,\n",
    "    - średni stopień wierzchołka,\n",
    "    - średnicę grafu.\n",
    "\n",
    "    Parametry:\n",
    "    graph (networkx.Graph): Graf, dla którego wyznaczane są własności.\n",
    "\n",
    "    Zwraca:\n",
    "    dict: Słownik zawierający histogram stopni, średni stopień oraz średnicę grafu.\n",
    "    \"\"\"\n",
    "    # Wyliczenie histogramu stopni wierzchołków\n",
    "    degree_histogram = nx.degree_histogram(graph)\n",
    "    \n",
    "    # Wyliczenie średniego stopnia wierzchołka\n",
    "    avg_degree = sum(dict(graph.degree()).values()) / len(graph.nodes())\n",
    "    \n",
    "    # Wyliczenie średnicy grafu\n",
    "    diameter = nx.diameter(graph)\n",
    "    \n",
    "    avg_shortest_path_length = nx.average_shortest_path_length(graph)\n",
    "    \n",
    "   \n",
    "    return {\n",
    "        'Ropzkład stopni': degree_histogram,\n",
    "        'Średni stopień': avg_degree,\n",
    "        'Promień': diameter,\n",
    "        \"Średnia dł. najkr.ścieżki\": avg_shortest_path_length\n",
    "    }\n",
    "\n",
    "properties_g1 = graph_properties(g1)\n",
    "properties_g2 = graph_properties(g2)\n",
    "\n",
    "pd.DataFrame([properties_g1, properties_g2], index=['Graf 1', 'Graf 2']).round(3).T"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.4166666666666667"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nx.average_clustering(g1)"
   ]
  }
 ],
 "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
}
