0_introduction_to_graph.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## What is a graph?\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graphs are all around us; real world objects are often defined in terms of their connections to other things.\n",
    "\n",
    "But what is a graph?\n",
    "\n",
    "*A graph represents the relations (edges) between a collection of entities (nodes).* What makes graphs special is that they represent relationships.\n",
    "\n",
    "<p align=\"center\">\n",
    "<img src=\"./images/graph.png\" width=\"40%\"/>\n",
    "</p>\n",
    "\n",
    "Formally, let the graph $\\mathcal{G}=(\\mathcal{V},\\mathcal{E})$ be represented as a set of $n$ nodes $v_i \\in \\mathcal{V}$ with node feature matrix $X \\in \\mathbb{R}^{d\\times n}$, edges $(v_i, v_j) \\in \\mathcal{E}$ (binary or weighted)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Who started the graph study (theory)?\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p align=\"justify\">\n",
    "Königsberg (now Kaliningrad, Russia) was a city from the old Kingdom of Prussia spanning along both sides of the Pregel river. The city had two islands that were connected to the mainland through bridges. The smaller island was connected with two bridges to either side of the river, while the bigger island was connected with only one. Additionally, there was one bridge connecting both islands. \n",
    "</p>\n",
    "<center><img src=\"images/Koenigsberg.jpeg\" width=\"500\"/></center>\n",
    "<center><small>image from https://www.xomnia.com/post/graph-theory-and-its-uses-with-examples-of-real-life-problems/</small></center>\n",
    "\n",
    "<p align=\"justify\">\n",
    "Imagine that you are a tourist and want to cross *all 7 bridges* because they are the main attraction of the city. However, you are a bit lazy and do not want to walk too much. So, you do not want to cross the same bridge more than one time. Is there a path through the city that does this? *No  matter how many paths you try, you will not find a solution!*\n",
    "</p>\n",
    "<p align=\"justify\">\n",
    "Leonhard Euler, a famous  mathematician, realized this, and explained why it was impossible to make this path through the city. \n",
    "He realized the only important part to consider for the problem was the connections between the different landmasses. He drew dots to represent the landmasses and lines connecting these dots to represent the bridges. The location of the dots and the shape of the lines are not relevant for the problem, only their relation. In the end, he had an abstraction of the problem with only dots and lines, which  is now called a graph.\n",
    "</p>\n",
    "<center><img src=\"images/Koenigsberg2.png\" width=\"700\"></center>\n",
    "<center><small>image from https://www.xomnia.com/post/graph-theory-and-its-uses-with-examples-of-real-life-problems/</small></center>\n",
    "\n",
    "<p align=\"justify\">\n",
    "He thought that in order to walk through a landmass you need to enter through a bridge and exit from a different bridge. This means that the dot representing that landmass needs two lines connecting it to represent the enter and exit line. More generally, the dot can have any even number of lines as connections. This does not necessarily apply for two dots, which are the first and last landmass in the path. This proves that it is impossible to make a path that crosses through all bridges.\n",
    "By abstracting the problem, Euler started the field of graph theory and his solution became the first theorem of this field.\n",
    "</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Types of graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graphs come in various types, each suited to different applications and possessing unique properties. Here are some common types of graphs:\n",
    "\n",
    "1. Undirected Graph:\n",
    "\n",
    "    - Definition: A graph where edges have no direction. The edge $(v_i, v_j)$ is identical to $(v_j, v_i)$.\n",
    "    - Use Case: Social networks, where friendships are mutual.\n",
    "2. Directed Graph:\n",
    "\n",
    "    - Definition: A graph where edges have a direction. The edge $(v_i, v_j)$ is different from $(v_j, v_i)$.\n",
    "    - Use Case: Web page linking (where a link goes from one page to another).\n",
    "\n",
    "3. Weighted Graph:\n",
    "\n",
    "    - Definition: A graph where edges have weights representing costs, similarities or distances.\n",
    "    - Use Case: Road networks with distances or travel times, network routing.\n",
    "\n",
    "4. Unweighted Graph:\n",
    "\n",
    "    - Definition: A graph where all edges have the same weight, typically treated as 1.\n",
    "    - Use Case: Basic connectivity scenarios, simple social networks.\n",
    "\n",
    "<p align=\"justify\">\n",
    "And several other types of graphs, such as: Multigraph (graph with multiple edges between the same set of vertices), cyclic graph (graph with at least one cycle), Complete graph (a graph in which every pair of vertices is connected by a unique edge), Bipartite graph (a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to a vertex in the other), Planar graph (a graph that can be embedded in the plane so that no edges cross each other), Sparse graph and dense graph.\n",
    "</p>\n",
    "<center><img src=\"images/types_graphs.png\" width=\"500\"> </center>\n",
    "<center><small>image from https://neo4j.com/blog/graph-algorithms-neo4j-graph-algorithm-concepts</small></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Applications of graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graph is used in vast area of science and technologies. Some of them are given below:\n",
    "\n",
    "- <p align=\"justify\"><b>Computer networks</b> are extremely popular in today's life. In computer networks nodes are connected to each other via links.\n",
    "<center><img src=\"images/computer_network.jpg\", width=\"500\"></center></p>\n",
    "\n",
    "- <p align=\"justify\"><b>World wide web</b> is an example of a directed graph. It is also the basic idea behind the Google ranking system. In the World Wide Web system, every website and web app is treated as a node or vertices, and the links from one website to another are considered the edge.\n",
    "<center><img src=\"images/WWW.png\", width=\"500\"></center></p>\n",
    "\n",
    "- <p align=\"justify\">Graphs are used to model <b>molecule structures </b>for computer processing. Here atoms can be considered as vertices of a graph the bonds that connects them are represented as edges between them. This structures are created based on the properties of compounds and are taken for analysis and processing.</p>\n",
    "<center><img src=\"images/molicul.png\", width=\"500\"></center>\n",
    "\n",
    "- <p align=\"justify\"><b>Scocial networks</b> such as Facebook and Twitter. Graphs that represent who knows whom, who communicates with whom, who influences whom or other relationships in social structures. An example is the twitter graph of who follows whom. These can be used to determine how information flows, how topics become hot, how communities develop, or even who might be a good match for who.</p>\n",
    "<center><img src=\"images/social_networks.jpg\", width=\"500\"></center>\n",
    "\n",
    "- <p align=\"justify\"><b> Transportation networks </b>. In road networks vertices are intersections and edges are the road segments between them, and for public transportation networks vertices are stops and edges are the links between them. Such networks are used by many map programs such as Google maps to find the best routes between locations. They are also used for studying traffic patterns, traffic light timings, and many aspects of transportation.</p>\n",
    "\n",
    "<center><img src=\"images/transportation_network.jpeg\", width=\"500\"></center>\n",
    "\n",
    "- <p align=\"justify\"><b>Protein-protein interactions graphs</b>. Vertices represent proteins and edges represent interactions between them that carry out some biological function in the cell. These graphs can be used, for example, to study molecular pathways—chains of molecular interactions in a cellular process. Humans have over 120K proteins with millions of interactions among them.</p>\n",
    "\n",
    "<center><img src=\"images/protein.png\", width=\"500\"></center>\n",
    "<center><small>image from https://string-db.org/</small></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Different types of machine learning tasks with graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " what tasks do we want to perform on this data? \n",
    " \n",
    " There are Four general types of prediction tasks on graphs: graph-level, node-level, edge-level and subgraph level.\n",
    "\n",
    " <center><img src=\"images/type_tasks.png\", width=\"500\"></center>\n",
    "\n",
    " #### Graph-level task:\n",
    "\n",
    "<p align=\"justify\">\n",
    "In a graph-level task, our goal is to predict the property of an entire graph. For example, for a molecule represented as a graph, we might want to predict what the molecule smells like, or whether it will bind to a receptor implicated in a disease. This is analogous to image classification problems with MNIST and CIFAR, where we want to associate a label to an entire image. With text, a similar problem is sentiment analysis where we want to identify the mood or emotion of an entire sentence at once.\n",
    "</p>\n",
    "\n",
    "<center><img src=\"images/graph_level.png\", width=\"800\"></center>\n",
    "<center><small>image from https://distill.pub/2021/gnn-intro/</small></center>\n",
    "\n",
    "#### Node-level task:\n",
    "\n",
    "Node-level tasks are concerned with predicting the identity or role of each node within a graph.\n",
    "<p align=\"justify\">\n",
    "A classic example of a node-level prediction problem is Zach’s karate club.\n",
    "The dataset is a single social network graph made up of individuals that have sworn allegiance to one of two karate clubs after a political rift. As the story goes, a feud between Mr. Hi (Instructor) and John H (Administrator) creates a schism in the karate club. The nodes represent individual karate practitioners, and the edges represent interactions between these members outside of karate. The prediction problem is to classify whether a given member becomes loyal to either Mr. Hi or John H, after the feud. In this case, distance between a node to either the Instructor or Administrator is highly correlated to this label.\n",
    "</p>\n",
    "<p align=\"justify\">\n",
    "Following the image analogy, node-level prediction problems are analogous to image segmentation, where we are trying to label the role of each pixel in an image. With text, a similar task would be predicting the parts-of-speech of each word in a sentence (e.g. noun, verb, adverb, etc).\n",
    "</p>\n",
    "<center><img src=\"images/node_level.png\", width=\"800\"></center>\n",
    "<center><small>image from https://distill.pub/2021/gnn-intro/</small></center>\n",
    "\n",
    "#### Edge-level task:\n",
    "\n",
    "<p align=\"justify\">\n",
    "One example of edge-level inference is in image scene understanding. Beyond identifying objects in an image, deep learning models can be used to predict the relationship between them. We can phrase this as an edge-level classification: given nodes that represent the objects in the image, we wish to predict which of these nodes share an edge or what the value of that edge is. If we wish to discover connections between entities, we could consider the graph fully connected and based on their predicted value prune edges to arrive at a sparse graph.\n",
    "</p>\n",
    "<center><img src=\"images/edge_level.png\", width=\"600\"></center>\n",
    "<center><small>image from https://distill.pub/2021/gnn-intro/</small></center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Creating & visualizing Graphs in python using *networkx*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An example creating an undirected weighted Graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{('a', 'b'): Text(-0.7217811851358968, 0.6422233254162557, '0.6'),\n",
       " ('a', 'c'): Text(-0.08518630917943518, 0.029239798355424756, '0.2'),\n",
       " ('a', 'd'): Text(-0.11547431609693005, 0.5890666348070571, '0.3'),\n",
       " ('c', 'd'): Text(0.24290174499542833, 0.14362888249976455, '0.1'),\n",
       " ('c', 'f'): Text(0.18614216918202614, -0.6807610098594172, '0.9'),\n",
       " ('c', 'e'): Text(0.5659270228713658, -0.5212891520084707, '0.7')}"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAgMAAAGFCAYAAABg2vAPAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjcuMSwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/bCgiHAAAACXBIWXMAAA9hAAAPYQGoP6dpAABCEElEQVR4nO3dd3hUZd7G8e+UJCRDOk2EUKRpiIUiiAIbRMACiqsCgugqawHeS1mwsS6KsoDKLruriF1fqeq+oqwVkCILCFEsNCWAEKQkkkAqJEx5/zgmIUIKMMmZmXN/risXkzntl92Yc89znmLz+Xw+RERExLLsZhcgIiIi5lIYEBERsTiFAREREYtTGBAREbE4hQERERGLUxgQERGxOIUBERERi3PWZCev18v+/fuJjo7GZrPVdk0iIiLiBz6fj/z8fJo2bYrdXvnn/xqFgf3799O8eXO/FSciIiJ1Z+/evTRr1qzS7TUKA9HR0WUni4mJ8U9lIiIiUqvy8vJo3rx52X28MjUKA6WPBmJiYhQGREREgkx1j/jVgVBERMTiFAZEREQsTmFARETE4hQGRERELE5hQERExOIUBkRERCxOYUBERMTiFAZEREQsTmFARETE4hQGRERELE5hQERExOIUBkRERCxOYUBERMTiFAZEREQsTmFARETE4hQGRERELM5pdgH+VFjsZnd2ISVuL+FOOy0TXbgiQupHFBER8bugv1OmZ+Yzb30GK37MIiOnCN8J22xAUkIUqe0bMbxbEm0bR5tVpoiISMCy+Xw+X3U75eXlERsbS25uLjExMXVRV7X25hQxcdEmVu84hMNuw+Ot/Mco3d6zTQOmDk6heUJUHVYqIiJijprev4Oyz8DCtAz6zlzF2l3ZAFUGgRO3r92VTd+Zq1iYllHrNYqIiASLoHtM8PyKdGYs2X5Gx3q8PjxeH4+8t4lDBcWMTW3r5+pERESCT1C1DCxMyzhlEDiyeh57pl+Hpyi3xueasWQ7b6uFQEREJHjCwN6cIh5fvMWv55y0eAt7c4r8ek4REZFgEzRhYOKiTbir6RtwutxeHxMXbfLrOUVERIJNUISB9Mx8Vu84VG1HwdPl8fpYveMQO7Ly/XpeERGRYBIUHQjnrc+odvgggPdoHjlLZnN019fY7E5cyb8jPvUP2JzhlR7jsNuY+2UGTwxK9nfZIiIiQSEoWgZW/JhVo1aBX95/Gp+7hPjetxN5Xhfyv/4P2Z88V+UxHq+PFduz/FWqiIhI0An4loGCYjcZNezk54xtTKOb/gJAdOfrsEVEUbDxI2K63Uh4o1aVHpeRXURhsVtTF4uIiCUFfMvAnuxCatpTILrztRW+j+l8HQBHd35V5XE+YHd24RlUJyIiEvwCPgyUuL013tcZ37Ti93HngM2OOzfTr9cREREJJQEfBsKdZ1GizVY31xEREQliAX8HbJnooqa3dPfh/Sd/7/PijG1c5XG2X68jIiJiRQEfBlwRTpJquMpg/tcfVfg+7+sPAYhs3bnK45ISo9R5UERELCso7oCp7RsxZ/2eaocXunMzyfr3k0S27kzxvh8o3LKCqAt6E964daXHOHxeUhuG+btkERGRoBHwLQMAw7sl1WiegYbXP4zNEcbhlW9ydGca0Z2uo8E191d5jMdmZ8SEW+Hmm2HjRn+VLCIiEjRsPp+v2rtsXl4esbGx5ObmEhMTUxd1neS219azdle2X6ckdng99NjzHXPenlT+Zv/+MHEi9Ox5Wh0QRSR4FBa72Z1dSInbS7jTTstElx4VSkiq6f07aMLA3pwi+s5cRbEfhwBGOO0sc/1I838+DQcPVtzYo4cRCq65RqFAJASkZ+Yzb30GK37MIiOnqML8JTYgKSGK1PaNGN4tibaNo80qU8SvQi4MACxMy+CR9/y3yuDTN6YwpGsSHDsGb74JzzwDP/1UcacLL4RHHzUeIzgcfru2iNSNvTlFTFy0idU7DlW7xknp9p5tGjB1cArNa9h5WSRQ1fT+HRR9BkoN7ZrEhH7t/HKuB/u1N4IAQL16cO+9sH07zJ0LyScsWvT99zBsGHToAK++CsXFfrm+iNS+hWkZ9J25irW7sgGqfcxYun3trmz6zlzFwrSMWq9RJBAEVRgAGJvaluk3phDhtOOwn17zvcNuI8Jp5+kbUxiT2ubkHZxOGD7cCADvvw+XXlq+bccO+OMfoXVrmDkTCgrO7gcRkVr1/Ip0HnlvE8Vu72n3NfJ4fRS7vTzy3iaeX5FeSxWKBI6gCwNgtBAsG9ebHq0TAaoNBaXbe7ROZNm43uUtApWx2+H66+HLL+Hzz6Fv3/Jt+/fDn/4ELVrAk09CTs5Z/Swi4n8L0zKYsWT7aR1zZPU89ky/7qT3ZyzZzttqIZAQF5RhAKB5QhRz7urG0gd6cVu3FrRIjDpppkIb0CIxitu6tWDZuF7Muavb6T0DtNmgTx9YuhTWr4cbbijflpMDjz9uhIIHH4QDB/zwU4nI2dqbU8Tji7f49ZyTFm9hbw1XTxUJRkHVgbA6dTJcaMsWePppmD8fPJ7y9yMi4A9/MIJB68onORKR2nWmw5CPrJ5H7poFtHjkw5O2Oew2erROZM5d3fxVpkidCMkOhNVxRThJbhrLJUnxJDeNrZ1xw8nJ8NZbkJ4Oo0cbIQCMjoUvvgjt2sGIEbB5s/+vLSJVSs/MZ/WOQ36djwSMPgSrdxxiR1a+X88rEihCKgzUqVatYNYs2L0bHnoIon8dl+zxwLx5kJJi9DtYv97UMkWsZN76jBp1LD62dwsH3hzHnmcHs+/FUeR/80m1xzjsNuZ+qb4DEpoUBs5WkybGY4M9e+CppyAxsXzb4sXQvTtceSUsWwbVP5ERkbOw4sesalsFSrJ2k/X2JDxFR4i74lZcKX058t95FG1fV+VxHq+PFduz/FmuSMBQGPCX+Hh47DEjFPzjH3DuueXbli+Hq66Cbt2MIYte/82iKCKGgmI3GTXo5Hdk9VzAR5PhTxN72c3EXT6UJsOmcfxQ9Z/6M7KLKCx2+6FakcCiMOBvLhfcfz/s2mVMUtS2bfm2tDQYPNh4hDBnDhw/bl6dIiFmT3Yh1bW9+bwejv30DZFtu+OMbVT2fliD5kS27lTtNXzA7uzCsytUJAApDNSW8HC46y7Ytg3efhsuuqh829atMHKk0dnwhRfg6FHz6hQJESU1WLfEW5SHz11MWHzTk7Y5E849xRFndh2RYKMwUNscDrjlFvjmG/j4Y7jiivJtu3fDmDFGZ8RnnoG8PNPKFAl24c66+XNWV9cRqUv6ra4rNhtcfTWsXg1ffGG8LpWZCQ8/bExgNGdOtacqKCjg448/5m9/+xvbtm2rxaJFgkfLRNdJE4/9lj0qBpszguOH95+0zZ2zr9pr2H69jkioURgwQ8+eRivBxo3GaoilSyQfOWI8OnBX3kFp/fr1jBw5kqFDh/Lpp5/SuXNnxowZQ0lJSd3ULhJIjh0zZgh98EFc119HkrvqNUNsdgf1Wl3C0fQvceeWjww4fmgvR3dtrPZySYlRtTN/iYjJFAbMdMkl8M47Rr+CO++E1FRjxIGz8j82d999Nx6Ph0WLFrF06VLee+89vvjiCzZrkiOxAp/PmAV05kyjM+6QIfDdd0YfnE8+IbVnx2rnGYjrORyAg/MeJvfLf5O79m0OLniUsAZVr1nisNtIbdeoyn1EgpUibiBo3x5ee834lOPxGP0MTuGll15i586dvPrqq3Tt2hWAAQMGMGLECNauXUunTtX3hhYJOocOGfN0LFliLBSWnAz9+sE990BUxbVGhndL4s11u6s8XXijVjS65UkOL3+VI6vn4oxuQNwVw/EU5JD7S+XHerw+RnSvZpEzkSClMBBI6tWrcvOzzz7LqFGj6NKlS9l7e/fupWHDhoSFhZ3yGJ/Ph812eks9i5jq+HFYt864+X/9NSQkGCuHPvVUxfk7TqFt42h6tmlQ7doE9ZI6cs4d/zjp/dJWg98qXZugTaPo0/pRRIKFwkCQWLVqFRkZGYwcObLCzX3NmjVER0eT+OvMh7+9+Ze+/vnnn2nWrFndFi1SUzt2GDf/5cuNFrLLLjNWCZ08udKWsspMHZxC35mr/Lo+gdNuY+rgFL+dTyTQKAwEieXLl9OjRw/OPeGTUU5ODqtWrcJut3P1CaMTvF4vdrsdt9vNBx98wCuvvEJhYSEHDhxg5MiRPPbYY9jt6i4iJsrNNW78S5bATz9BmzZG0/8bb5Sv83GGmidEMXlQMo+8t8lPxcKTg5JPb/lzkSCjMBAkkpKSSE9PJzw8vOy9xYsXs3HjRm6++WZcLldZCChtDfjrX//K3LlzGTlyJL1792b//v089dRTbNy4kdmzZ3POOeeY9eOI1Xg88NVXxs1//XrjWX+fPrW25PfQrkkcKihmxpLtZ32uB/u1Z0hX9RWQ0KYwECQ6depEYmIi//3vf0lNTSUtLY0pU6bQvXt3Ro0aVbafx+PB4XDw8ccfM3/+fK688kp69uzJBRdcQK9evRgwYABr1qyhXjX9E0TO2t698Nln8PnnxoRaXboYn/4ffbTKETP+Mja1LQ3qR/D44i24vb7TemzgsNtw2m08OShZQUAsQWEgSKSkpHDTTTdx880306pVK3Jzc7n88suZOnUqcXFxABWa/l944QXS09OJiYlh9+7dpKWl8dhjj3H//ffTp08fIiMjTfpJJGQVFsKqVcan/x9+gObNjZv/rFlGJ0ATDO2axOXnNWDiok2s3nEIh91WZSgo3d6jdSJTB6fo0YBYhs3nq35d3by8PGJjY8nNzSUmJqYu6pJK5OXl8Z///IdLLrmE8847j4iICN566y06duxYNrTwyy+/ZPDgwVx44YW89dZb1K9fn08//ZTJkyfzzjvv0KFDB5N/CjHTzz//TE5ODh06dKjw2Om0eb3w/ffGp/81a4xP+7/7nREA2rcvn0wrQKRn5jNvfQYrtmeRkV1UYVEjG8aEQqntGjGie5JGDUjIqOn9Wy0DQSYmJobhw8uHP23fvp1HH32UgQMHMnv2bGw2G9u2bSMyMpJx48bRuHFjADp37szRo0dZsWKFwoAFbd26lVmzZrF48WKKioo477zzaNWqFX//+98rdEqt1sGDxox/S5fCL78YC3D16wcPPAAREbVWvz+0bRzNE4OSeYJkCovd7M4upMTtJXz8OFrOfVUzC4ql6bc/yLVr147nn3+e+Pj4so6DcXFxZGZm0r9//7L9HA4HPp+P478um6z5B6yjqKiITz/9lJycHJ577jm6d+/Od999x1133cVLL73E5MmTK/9dOHbM+NT/2WdGK0DjxsbN/9lnjddByhXhJLlprPHNsWxQEBCL038BIWDw4MEVvm/RogUtWrRg2bJlXHXVVRw5coT33nuPjIwM7rjjDqB8/gF8voBrzpXTV1BQQP369U+5LSoqin79+jFs2LCyESRNmjShSZMmFBQUVB4M//pX2LDBWGlz+HB4+mn9roiEKIWBEJSSksIVV1zB0KFDufPOO9mwYQMHDx5k0qRJxMTElA1BBIw/7nffDcOGGc979cc+aGRnZ/P000/z9ttvExMTw0033cT9999f1qH0RB07dqzw/bvvvkvDhg257bbbsNvtJwcCrxceeggqmdlSREKLZp4JQWFhYbz88svMmzePQ4cO0bt3b1599VUefvhh4IRRB8ePw0cfwSuvGGO+L7sMFi82bgQS8F588UW++OILpk+fzv3338+//vUvHnjgAQ4ePAgYj4J+67PPPsNut3P33Xdz4MABHn74YbZu3Xpyy4Ddbp0gEB4OxcVmVyFiKoWBEDZgwADeeOMNJk+eTM+ePU9evyAsDN58s/z79evh+uuNTmHz5lW5lLKYa//+/SxYsIArr7ySYcOGMWrUKObNm8fXX3/NggULgFOHgR49epCWlsbOnTuZP38+ERER3Hffffzyyy91/SMEjoQEOHzY7CpETKUwYAFVdhRcsADmz4eUE+Zd37wZRowwhoe99JLRiUwCyr59+ygqKqJv375l7/Xo0YNu3brx4YcfApxyyuno6Gg6d+5MXFwcF1xwAffccw/Z2dnWXgI7IQFycsyuQsRUCgNW53Qa/QW++w7+8x/jUUGpXbvg3nuhVSuYMQPy882rUyo4//zz2bNnT9noEDCGnV588cUcPHiQbdu2AeCupHWnNCgsW7aMgoICWrRoUftFB6r4eLUMiOUpDIjBZoPrrjOGka1caQwfK3XwoDGHfIsW8PjjkJ1tWpliqF+/Pi1atGDDhg0V3j/vvPOoX78+33//PQDOE6b9PXr0KP/973/5+eef+fbbb5k0aRJpaWk8+eSTtK6F9QGChloGRBQG5DdsNujd2xhX/tVX8Pvfl48wOHwYnnzSCAXjx8O+febWanF9+/blo48+Ijc3t+y91q1bc/iET7mfffYZ//d//wcYwWDu3LkMGDCAXr16sWbNGsaMGcOQIUPqvPaAopYBEYUBqULnzvDvf8PWrXDHHeWLyxQWwt//bqw2d/fdxlr04n8+H+zcWenmO++8k82bN7N8+fKy9/Lz89mxY0fZ1NTTp09nxowZ/PLLL4SFhXHfffcxd+5c8vLy+Pzzz7n11luJCPCZA2udWgZEtDaBnIY9e4y+A6++WrFTod0Ot9xirEZ34YXm1RcKMjPLp/vNyoJOneCpp4z/jU/h9ttvZ+XKlUyZMoWLLrqIv/zlL9SvX59Zs2YRFxfH4sWLqV+/Pr17966wvLWcYONGeP99o9VLJMTU9P6tMCCnLzMT/vlPYzW6vLyK2667zggFPXqYU1uwKS42+mksWWJ04mzYEK66yvhq0qTaw7Ozs5k2bRorV65ky5Yt9OjRg5kzZ3KhQlnN7d4Nf/sbPPec2ZWI+J3CgNS+3Fx44QWYOdNYtOZEvXsboaBfP81qeCKfD3780bj5r1xpzOVw+eXQv7/RqlJJC0DVp/Sxd+9emjdvrk/+ZyI3F0aPNubWEAkxCgNSd4qK4LXXjMVr9u6tuK1TJ5g4EQYPPqMbXWUqrDrntNMy0RW4q84dPgzLlhkBYO9e6NDBCEm9e4PLZXZ14vMZk20tXmx2JSJ+pzAgda+kxJjAaPp049PviTp0gIcfNha8OcNpbsvWo/8xi4ycU6xHnxBFavtGDO+WRNvGJq5H73YbszkuWQJpaRAbC1deaQSApCTz6pLKDRxozLMhEmIUBsQ8Ho/RIWvqVKNz1omSkmDCBLjrLoiKqtHp9uYUMXHRJlbvOITDbsPjrfxXtnR7zzYNmDo4heYJNbvGWfvpJ2M45vLlRktJt27Gzb9LF3A46qYGOXMKAxKiFAbEfD6f0St+6lRYtaritoYNYdw441ltbGylp1iYlsHji7fg9vqqDAG/5bDbcNptTB6UzNCutfBpPD8fVqwwPv2npxvDLPv1MxZ8quLnkQClMCAhSmFAAsuaNTBtmrFK4oliYmDMGHjgAWjUqMKm51ekM2PJ9rO+9IR+7Rib2vbsTuL1Gq0cn30G69ZBZCSkphoB4Lzz1Eky2A0aBB98oP8fJeQoDEhg+u47o0/BO+9UXCq5Xj0YNcp4hNCiBQvTMnjkvU1+u+zTN6Yw5HRbCPbtMz75L1tmdALs1Mm4+V92mXWW97WK4cNh9mwjnIqEEIUBCWw7dsAzzxhLKJ+w2A5OJ3tvv5u+Ta6l2FPzxwLViXDaWTaud9V9CI4ehS++MD79b90K555r3PyvvBIaNPBbLRKAxo4tX39DJITU9P4doGOxJOS1aQMvvwyTJhlTG7/0ktHxzu1mYkET3CXHweG/X0+318fERZuYc1e38jd9PmO55s8+g9WrjaGPvXoZnRsvuEBNxlZSOiWxwoBYlMKAmKtZMyMMTJwIzz1H+pz/Y3WrTpXu7s7NIvfLf3Nsz3d48n7B5oygXosLiU+9E2dc40qP83h9rN5xiB3b9tDmm19n/MvMhI4djU//Y8cajyrEmuLjtT6BWJrCgASGBg1g8mTmXXgDjq/24eHUn8qLD2yneN82XOf3whGdiDs3i4JvPubg/Edp+scXsIdVfkN3+LzMnfUeT1yaaHRmPOec2vppJNgkJGjlQrE0hQEJKCt2Hak0CABEntcVV4crKrwX1eZSDs6ZQNGPa6nfsU+lx3psdla0vJgnRqb6rV4JEfHxcPCg2VWImEZLGEvAKCh2k5FTVOU+9rDy5XZ9Hjeeo3k448/BHuGi5GDly/2WysguorDYfda1SohRy4BYnFoGJGDsyS6kuvED3uPF5K17l4JNy/DkZ8MJR3iLC6u9hg/YnV1IclNNDCQnKO1AKGJRCgMSMErc3mr3Obz0JQo2LSO6yyAizu2APcIFNhuHPnjGGB3gp+uIxcTHq2VALE1hQAJGuLP6p1aFP67B1bEPCVeOKnvP5y7Be6zAr9cRi9FoArE4/VWUgNEy0VVF10GDzXbyr2ze1/8BX80+7dt+vY5IBfXqQXGx2VWImEYtAxIwXBFOkhKi2FNFJ8LINl0p3Lwce0QUYQ2SKN73A8d2f4s9smYzYyYlRuGK0K+9iMiJ1DIgASW1fSMc9srbBxL63o2rYx8Kt6zk8PLX8BTk0HjoFGxVzC9QymG3kdquUbX7iYhYjT4iSUAZ3i2JN9ftrnS7vV59Glz7wEnvNxv9erXn9nh9jOheC8sZi4gEObUMSEBp2zianm0aVNk6cCYcdhs92zSgTaNov55XQojTWXHRLBELURiQgDN1cApOP4cBp93G1MEpfj2nhJj4eDhyxOwqREyhMCABp3lCFJMHJfv1nE8OSq56+WIRDS8UC1MYkIA0tGsSE/q188u5Hty3liGe/X45l4QwTUksFqYwIAFrbGpbpt+YQoTTftp9CBx2GxFOO0/fmMKY5x+GyZNhzZpaqlRCgqYkFgtTGJCANrRrEsvG9aZH60SAakNB6fYerRNZNq43Q7omQUwMvPMOTJ0Kq1bVes0SpDQlsViYhhZKwGueEMWcu7qRnpnPvPUZrNieRUZ2UYVFjWwYEwqltmvEiO5JJ48aiI42AsHQoeDxQJ/KlzoWi0pIgB9/NLsKEVMoDEjQaNs4micGJfMEyRQWu9mdXUiJ20u4007LRFf1Mwu6XPD22zBsGLjd0K9f3RQuwUEdCMXCFAYkKLkinGe2DHFUlBEIbr3VCATXXOP/4iQ4qQOhWJjCgFhPvXqwYAEMH248Mhg40OyKJBCoZUAsTB0IxZoiImD+fJg7FxYtMrsaCQSxsZCba3YVIqZQGBDrCg83wsC77xpfYm0OB3hrthS2SKhRGBBrCwuDt96CxYuNRwciIhakMCDidMIbb8Bnn8GcOWZXIyJS5xQGRMAIBK+9ZkxK9Hr1yyFLCPP5qt9HJMQoDIiUcjjg5ZdhwwbjX7EelwuKisyuQqTOKQyInMhuhxdegO+/h1mzzK5G6pqmJBaLUhgQ+S27HZ57DtLT4Z//NLsaqUtarEgsSmFA5FRsNpg5E/buhRkzzK5G6oomHhKLUhgQqYzNBs8+C9nZMG2a2dVIXdCUxGJRCgMiVbHZjKWPjx6FJ580uxqpbWoZEItSGBCpjs1WHgQmTdLQs1CmlgGxKIUBkZqaNAkiI2HiRAWCUKUOhGJRCgMip+PRRyExER56SIEgFGlooViUwoDI6ZowAc49F8aNUyAINWoZEItSGBA5Ew88AG3bwv/8j1a6CyWRkZqBUCxJYUDkTI0ZAxdeCKNHKxCECpvN7ApETKEwIHI27r4bLr3U+NfjMbsaEZEzojAgcrbuvBN69YJRoxQIRCQoKQyI+MPIkXDVVXDHHeB2m12NnA27XaFOLEdhQMRfbr0VBg0ygsHx42ZXI2cqLg5yc82uQqROKQyI+NPNN8NNN8GIEVBSYnY1ciY0JbFYkMKAiL/deCMMH258FRebXY2cLk1JLBbkNLsAkZA0aBA4nTBsGMyfD/XqmV2R1JQmHhILUhgQqS3XXGMEgqFDjUAQFWV2RVITmpJYLEhhQKQ29etnBIIhQ2DhQnC5zK5IqnPhhZCXZ3YVInVKYUCktvXpYwSCW24xAkF0tNkVSVVSUjSjpFiOwoBIXejVCxyO8haCmBizK5Kq2NW3WqxFv/EideXyy2HSJKOF4MgRs6sRESmjMCBSl7p3hylTjECgHusiEiAUBkTqWpcu8PTTxiOD7GyzqxERURgQMcUll8CMGUYg+OUXs6uR0+Dz+cwuQcTv1IFQxCwXXQT/+Ef5PASNG5tdkQAej4f09HQ2b97MDz/8QFZWFm63myZNmnDTTTdxwQUXmF2iiN/ZfDWIuXl5ecTGxpKbm0uMekGL+Ne2bTB2LMydC+ecY3Y1ljd79mxefPFFDh48SIMGDUhISMDhcHD8+HH27dvHtGnTGDJkCHaNOJAgUNP7t1oGRMx2/vkwe7axlsFbb0GzZmZXZFnz5s3jscce495772XkyJE0a9aM8PBwiouLycrK4oUXXmDatGl069aN1q1bm12uiN+oZUAkUOzcCX/8I7z5JiQlmV2NJfXq1YurrrqKv/zlL5Xu07JlS1555RWuuuqqOqxM5MzU9P6tdi6RQHHeefDaa3DHHbB7t9nVWJLP58Pj8VS6fcuWLdhstir3EQlGekwgEkhatTJaBu64A155xQgIUmcGDhzI/Pnzadq0Kb1798bj8XD8+HGys7PZtGkTM2bMoGfPnnTv3t3sUkX8SmFAJNAkJRl9B0aOhBdfhHbtzK7IMsaNG0d2djYPPfQQSUlJNGrUiOLiYtxuN8ePH2fQoEGMHz+euLg4s0sV8Sv1GRAJVPv3w223waxZ0KGD2dVYyr59+1i8eDFZWVmEh4fTpEkT2rdvT5cuXQgPDze7PJEaq+n9W2FAJJBlZsKtt8K//gXJyWZXE/I8Hg8HDx4kOjpaf+skJKgDoUgoaNzYWOXw/vvh++/NribkrVmzhksvvZRXX30VgJKSEjweD16vVzMPSkhTGBAJdA0bGoFg/Hj45huzqwlpzZo144YbbqDDr49lwsPDcTgc2O12bDabydWJ1B49JhAJFjk5xtTFU6caix2JiFRDjwlEQk1CArzzDjz2GKxfb3Y1luTz+fj555/J0fLTEmIUBkSCSVycEQieeALWrDG7mpDj8/lYu3YthYWF+Hw+vF4vXq+3rN9ASUkJL7/8MtOnTze7VBG/UhgQCTYxMUYgmDoVvvjC7GpCis1m44orrmDPnj3YbDbsdjt2u72s30BERAQpKSl8+OGHeL1es8sV8RtNOiQSjKKjjUAwdCi43dCnj9kVhYzIyEi++uorcnNzyc7OLvvKyckhJyeH9PR0fvjhB/Ly8jT5kIQMhQGRYOVywdtvw7Bh4PGAFs7xi/j4eMaOHUtiYiJOp5OIiAgiIyOJiorC5XLRqFEjhg0bpqGGElIUBkSCWVSUEQhuvRW8Xujf3+yKgl5ERATDhw/n5ptvJiIignr16hEZGUm9evWIiIggPDycsLAwYmNjzS5VxG8UBkSCXb16sGABbNkCPh9UMR7e5/NpvHw1oqKi6NChA3306EUsRB0IRUJBRARcckmVQQAoCwJut7suqgpKN910E+eeey5ghKcTv0RClSYdErGIDRs28Mknn5CWlkazZs245557uOSSS8wuS0RqkSYdEpEy77zzDn369GHt2rVERkbi9Xrp2bMnaWlpZpcmIgFAfQZEQtzcuXO54447+NOf/sT//M//0Lx5cwCKiop46aWX6NKli/oRiFicwoBICPviiy+4/fbbefTRR3nssceoV69e2bb4+Hi2bt2K1+vF4XCYWKWImE2PCURC1OHDh/nzn//MsGHDmDBhQoUgsG/fPpYuXUr37t0VBEREYUAkVB0+fJjdu3dzww03EBcXV9YbPjs7mxdeeIG4uDhSU1NNrjKA5eTAX/9qdhUidUJhQCREFRYWEhkZSceOHQFjWGFmZiazZ89m8eLF9OvXj759+5pcZQBzuWDjRrOrEKkTCgMiIapZs2aEhYXx/PPPs2vXLrZs2cKf/vQn3n//ffr168eTTz4JcNKCOwcOHCAzM9OMkgNLRASUlJhdhUidUBgQCVHx8fEsWrSIjz/+mBtuuIGUlBQyMzO5/fbb+dvf/gaAx+PBbi//M7Bnzx7GjBnDH//4Rz788EOzSheROqbRBCIhrF27dnz11Vfs3buXI0eO0Lt377JtJSUlhIeHV9i/RYsWjB07lnXr1jFixAhmzZrF8OHD67psEaljCgMiIS4hIYGEhISy7+fOnctNN91UYXQBlK9b0KdPH/r06UPr1q2ZOHEiF198McnJyXVdtojUIT0mELGQadOmMX78eBYtWgRw0pz7pWsWuN1u+vbti8vlsnb/gbAwOH7c7CpEap1aBkQs5L777sPhcJSNIjhx5kGbzYbTafxJcDqd/Pzzz2zdupXjVr4ZxsfD4cPQqJHZlYjUKoUBEQuJi4vjoYceAmDr1q388MMP2Gw2cnNzqVevHh6Ph59//pnMzExee+01hg4dymWXXWZy1SZKSDDmG1AYkBCnMCBiMaWPBiZMmMCnn35Kt27dyMnJISYmhvr163PkyBFatGjBlClTGDx4sLVXKo2PN8KASIhTGBCxGJvNhs1m491336VXr140bNiQlStXEhERARjDDTVF8a8SEozHBCIhTh0IRSzK5XKxevVqNm/ezM0331zWkdBms1XoVGhpahkQi1AYELGwqKgotm3bxpYtW+jXrx8+nw+73a4ljUupZUAsQmFAxOIiIiL48ccfad68OevXrze7nMCilgGxCPUZEBGcTievv/76qTd6PGC3gxVbC9QyIBahlgERqdqxYzB6tDUX7SkdWigS4hQGRKRqLhdcfTUMHw7FxWZXU7diYiA31+wqRGqdHhOISPUGDQKnE269FebNg9+saxCy7HbQyAqxAIUBEamZa64xAsHQobBgAURGml2RiPiJwoCI1Fy/fuBwwJAhRiBwucyuSET8QGFARE7PlVcaLQRDhsDChVC/vtkV1T6fz5qjKcQyFAZE5PT17m20ENxyixEIQnn9gvr1obDQGqFHLEujCUTkzFxxBUyaZASCUO5xr4mHxAIUBkTkzHXvDk89ZQSCUJ2cRxMPiQUoDIjI2enaFaZNMwJBdrbZ1fifJh4SC1AYEJGz16kTzJhhdCr85Rezq/Gv+Hi1DEjIUxgQEf+46CL4xz9g2DDIzDS7Gv9Ry4BYgMKAiPhPx47w3HPGTIUHDphdjX+oZUAsQGFARPzr/PPhhReMtQz27TO7mrOnlgGxAIUBEfG/9u3h5ZfhttsgI8Psas6OhhaKBSgMiEjtaNMGXnsN7rgDdu82u5ozp6GFYgEKAyJSe1q1gjfegDvvhJ07za7mzERGwtGjZlchUqsUBkSkdrVoAW+9BX/8I6Snm12NiJyCwoCI1L5mzWDuXLj3XvjhB7OrEZHfUBgQkbrRtCnMmwdjxsCWLWZXIyInUBgQkbrTpAksWAD33w/ff292NTXncIDHY3YVIrVGYUBE6lajRsayx+PHw7ffml1NzcTFwZEjZlchUmsUBkSk7jVoAG+/DQ89BF9/bXY11dPEQxLiFAZExBwJCfDOOzBxIqxfb3Y1VdOUxBLiFAZExDxxcUYgeOIJWLvW7Goqp5YBCXEKAyJirthYIxD89a+werXZ1ZyapiSWEOc0uwAREaKjjUAwdCi43ZCaanZFFSUkBO8MiiI1oDAgIoHB5TI6FQ4bZgzj69vX7IrKqWVAQpzCgIgEjqgoY9jhrbcaLQQDBphdkUGLFUmIUxgQkcASGWlMTDRihBEIrrvO7IrUgVBCnjoQikjgqVcP5s+HOXPg/ffNrkaTDknIUxgQkcAUHm4sbvT22/Dvf5tbi6YjlhCnMCAigSsszFj++IMPjFAgIrVCYUBEAltYGLzxBnzyidFSICJ+pzAgIoHP6YTXXoMVK+DNN82uRiTkKAyISHBwOOCVV2DdOnj11bq/fmQkHD1a99cVqQMKAyISPOx2mD0bvvnG+LcuaeIhCWEKAyISXOx2eP55+OEHeO65uruuJh6SEKYwICLBx2aDf/wDdu+Gv/+9bq6plgEJYQoDIhKcbDaYMQOysuDpp2v/emoZkBCmMCAiwctmg2nToKAApkyp3WtpSmIJYQoDIhLcbDZ46inweuGJJ8Dnq53rxMerZUBClsKAiISGSZOMKYwfe6x2AoFaBiSEKQyISOiYONFYVOiRR/wfCNSBUEKYwoCIhJYHH4QmTWD8eP8GAnUglBCmMCAioWfcOGjdGu6/33+BwOUyOiqKhCCFAREJTWPHQnIyjBljdC48Wzbb2Z9DJEApDIhI6LrnHujcGe691z+BQCREKQyISGi76y64/HIYNQo8HrOrEQlICgMiEvpuvx369oU77wS3+8zPY7OphUFCksKAiFjDrbfCtdfCHXfA8eNndo7YWMjL82tZIoFAYUBErOOWW2DwYLjtNigpOf3jNfGQhCiFARGxlt//HoYNgxEjoLj49I7VlMQSohQGRMR6rr/e6Edw661w7FjNj1PLgIQop9kFiIiY4tprwek0Wgnmz4fIyGoPKYyNZ/fPRyjJOEy4007LRBeuCP0ZleCn32IRsa7+/Y1AMGQILFwIUVEn7ZKemc+89Rms+DGLjJwEfADb1wJgA5ISokht34jh3ZJo2zi6TssX8Rebz1f9XJ15eXnExsaSm5tLTExMXdQlIlJ3Vq6EGTOMQFC/PgB7c4qYuGgTq3ccwmG34fFW/qeydHvPNg2YOjiF5gknhwoRM9T0/q0+AyIiv/udsdLhLbdAfj4L0zLoO3MVa3dlA1QZBE7cvnZXNn1nrmJhWkZtVyziV2oZEBEptW4dz7/0ETPOueysTzWhXzvGprb1Q1EiZ04tAyIip2mh81y/BAGAGUu287ZaCCRIKAyIiGD0EXh88Ra/nnPS4i3szSny6zlFaoPCgIgIMHHRJtzV9A04XW6vj4mLNvn1nCK1QUMLRcTy0jPzWb3jULX7ufMPcWT1PI7t+hrP0Twc9ROJbN2JhL53Y3OEnbS/x+tj9Y5D7MjKp00jDTuUwKUwICKWN299RrXDB9352Rz83z/hLS6k/kUDCEtshic/m6If1+A7XnzKMADGsMO5X2bwxKDk2ipf5KwpDIiI5a34Mava4YNHVv0vnsIjNBn5NyLOKR8lENdrBFUNyvJ4fazYnsUTKAxI4FKfARGxtIJiNxnVdPLz+bwUpX9JZJtLKwSBUjabrcrjM7KLKCx2n1WdIrVJYUBELG1PdiHVdRv0FuXiKy4irGGLM7qGD9idXXhGx4rUBYUBEbG0Erc3pK4jciYUBkTE0sKd1f8ZtEfFYouI4vgve2r1OiJm0W+niFhay0QXVT/xB5vNTlTb7hzdsYHiA+knba9uVnebz0fLO4YaiyFt2QLVzwIvUqcUBkTE0lwRTpJqsMpgXO+ROKJiyZz/CDnLXiH/20858t/57H91NL7iqvsDJB0+gGvpp/Dgg9CxI7RoAXffDe+9B3l5/vpRRM6YwoCIWF5q+0Y47FW3DzijG9Bk5N+Ian85hVtXkrP0JQo3L6deUgq2sIhKj3P4vKQe2l7xzb174ZVX4Pe/h8REY9XE6dPhu+/UaiCm0KqFImJ56Zn5XPWPL2rt/Mse6EWbI/vhk0/g009h5UooLj71zuecAwMGGF9XXQXx8bVWl4S+mt6/FQZERIDbXlvP2l3Z1U4+dDocdhs9Wicy565uFTcUFcGqVeXhIP3kfggA2O3QvTtcfbURDjp1Mt4TqSGFARGR07A3p4i+M1dR7MchgBFOO8vG9aZ5dX0Sdu40QsEnn8Dy5XD06Kn3a9gQ+vc3wkG/ftCggd9qldCkMCAicpoWpmXwyHv+W2Xw6RtTGNI16fQOOnYMVq8ubzXYtu3U+9ls0LWr0WJw9dXGa4fj7IuWkKIwICJyBp5fkc6MJdur37EaD/Zrz5jUNmdf0O7d8NlnRjj4/HMoKDj1fgkJRmtBaX+Dxo3P/toS9BQGRETO0MK0DB7/YDPukuN4HDVfz81ht+G023hyUPLptwjUREkJrFlT/khhUxWtGJ06lbcadO8OTq1LZ0UKAyIiZ2Hvw48zcY+T1a064cCHp4qpiUqXP+7ZpgFTB6dU30fAX/btM4LBp5/C0qWQm3vq/WJjoW/f8o6I555bw9Pv49///jebNm3immuuYeDAgYSFnXqpZglMCgMiImfq2DFo1gyys0lv3Ip5/3ybFXsLyMguqrCokQ1ISowitV0jRnRPok2jaLMqhuPHYf368r4GGzdWvm9KCkyZAgMHGn0PTmHNmjWMHz+eo0ePcvHFF7N8+XIGDRrEc889h10jGoKGwoCIyJl66y24/Xbj9a23wrx5ABQWu9mdXUiJ20u4007LRBeuiABtfj94EJYsMcLBkiWQk1Nx+6efGq0FlXQ67N69O+eeey6TJ0+mY8eOrF69moEDBzJ37lyuu+66sv18Ph82mw2v16uQEIBqev8O0N9iERETzZpV/nrMmLKXrggnyU1jTSjoDDRpAiNHGl8eD6SlVexr8LvfVRoEvv32WzZs2MDSpUvp2LEjAD179iQhIYGdO3ee8phnnnmGOXPm0L9/f0aMGEGnTp1q6yeTWqAYJyJyoq++gg0bjNcXXwyXXWZqOX7hcBidCJ94wniUcOAARFQ+hfLChQtJTk7m0ksvLXtv//79tGnThn379lXY1/brY4Z77rmHcePGsW3bNnr37k1UVBS33HILn3zyCV6vlm8OdGoZEBE50QsvlL8ePbrSZ+pBLbbq1o2lS5eSmppKdHR5H4iMjAwKCwtp2LAhwEmPBeLj4xk1ahSjRo0C4KOPPmLgwIEcPnyYPn36EFFF+BDzqWVARKRUdjYsWGC8jo01+gtY0L59+0hOTsbn85Utz7x582aOHDnC5ZdfXulxbre77PgPPviAtm3b8vrrrysIBAGFARGRUm+8YYwkAPjDH8DlMrceE2RnZ5OSksJPP/2EzWYrewzw+eefk5SUVPbo4FSdBR2/9kH4+9//zsqVK3n88cdp3rw5NeinLiZTGBARAfB6Yfbs8u/vu8+8Wkzi8/lITEykU6dOLFmyhMOHD3Ps2DGeffZZVq9ezdChQ3FWMXmRzWZj+fLlPP/88zzwwAPceOONZe9LYFOfARERMKb83bXLeH3VVdCunbn1mODEzoAbNmygXbt2tGjRguzsbEaPHs3tt9/O/v37CQsLK+s7AOXDC7dt28bDDz9Mamoqo0ePNuvHkDOgMCAiApUOJ7Si1q1bs2LFClavXs0333xD//79ad26NQDjx4+noKCAl156iaZNm5Z1JMzNzWXixIkATJ8+HQCPx1P26KDMnj3GcMfSqZIvuig0O2kGGYUBEZGffoKPPzZeJyXBCZPqWFnPnj3p2bNn2fcej4c2bdpw5MgRzjnnHKC8NeGZZ55hw4YNzJ07l4svvhjg5CBw/Dj85z/wxRfG18SJxnwIpYsrXXWVseCS1DmFARGR2bOhtJPbPfdoKeBKOBwOnnrqqQrv2Ww2li1bxrRp05gxYwapqamVnyAsDL7/vuJ7Bw/Cm28aX3Y7dOtWvoZC587GewEkqGahPA2ajlhErO3oUWMdgpwcCA+HvXuhUSOzqwoqx44dY/Xq1fTq1atmwwh37ixfYGn5cigqOvV+DRpA//5GOOjXD07op1CX0jPzmbc+gxU/ZpGRc4r1KRKiSG3fiOHdkmjb2MT1KU5BaxOIiNTE//4v3HGH8Xr4cJg719RyLOfYMfjvf8sXWNq69dT72WzQpUt5q8Gll9Z6C87enCImLtrE6h2HylamrIxpK1dWQ2FARKQmLr3UmLcfYO3a0Jh+OJjt2WOM7PjkE1i2DAoKTr1ffLzRWnD11UbrQZMmfi1jYVoGjy/egtvrqzIE/JbDbsNptzF5UDJDuyb5taYzoTAgIlKdtDQjDICxDsHGjerZHkhKSoyAVrrA0m/7G5zokkvKRyh07270TzhDz69IZ8aS7Wd8fKkJ/doxNrXtWZ/nbCgMiIhU5w9/MDquAbzyCvw6r74EqP37y/saLFkCubmn3i8mxhiZUDpKoVmzGl9iYVoGj7y3yU8Fw9M3pjDExBYChQERkapkZxs3iWPHIC4O9u2DqMB4zis14HYbKzCW9jX4+uvK9+3YsbyvwRVXGB1FT2FvThF9Z66i2O2/VRYjnHaWjettWh+Cmt6/A2vMhohIXVm+HIqLjdd/+IOCQLBxOuHyy2HKFGPZ6YMH4a23YNiwk+cq2LwZnn0WrrwSEhPh+uvhxRdh9+4Ku01ctAn3afQPqAm318fERf5raagtahkQEevx+Yy+AT/9BP/6F4wdC+edZ3ZV4i8ejxEQSvsabNhQPo/Eb3XoAAMGkN5rAFdtcNdaScvG9aJNo7ofdqjHBCIi1fH+2hwcYBPbiJ8dOgRLlxrB4LPPICvrpF2e6Hs3czpdi8de9XBFd/4hjnwxl6M7v8JbXEBYfFNiut5A/Yv6VXqMw27jtm4teGJQ8ln/KKerpvfv4J82SUTkTCkEWEODBsbjg2HDjAD4zTflrQbr1oHXy4rzulQbBDyFhzn41gSw2YjufC2OqFiO7vya7E/+hbfkKDFdrz/1cV4fK7Zn8QR1HwZqSmFARESsw243pjnu3Bn+/Gc4fJiCz5aR8W1ktYceWTUHfF7OufN5HJHGp+zoS67hlw+e4ch/51P/4gHYw049A2NGdhGFxe6AnbpYsVhELKEGT0TFiuLj2dOrH75q5pfw+XwU/biGyDaXgs+Hpyi37CuyVSd8xYWUZO6s/Hhgd3ahn4v3n8CMKCIifla6up7X68Vms5V9L1JSg6GE3qJcvMWFFHz7KQXffnrqfQqPnPV1zKIwICIhKysri7Vr1/LTTz8RFxfHLbfcgsvlMrssCTDhzho0kv/asuRKTsWVcuWpz9Ow5dlfxyQKAyISkj788ENmzZrFunXr6Nq1K+vXr2f06NEMHjyYRx99lJSUFLNLlADRMtGFDajqQZI9KgZbeCQ+n5fIlhef9jVsv14nUAVuTBEROQsTJkyge/fu7N69m7lz5zJ8+HASEhLYs2cPQ4cO5cMPPzS7RAkQrggnSdXMEGizO4hqfzlFP66h5JfdJ233FFUyNfKvkhKjArbzICgMiEgI2rx5MwUFBdx///3ExcXRuHFjpk+fTrNmzZgwYQIXXHABjzzyCD///LPZpUqASG3fCIe96n4k8b+7HYcrgYNvjSdn2cvkf/spueve5Zf3p7P/5XsqPc5ht5HarpG/S/YrhQERCTl5eXk0aNCAjRs3lr23ZcsWduzYweDBg1mwYAG5ubkVtou1De+WVO1SxQ5XPOfc/nfqp/SlaPs6cpa8SP5Xi/EezSfud3dUepzH62NEd/OXM65K4LZZiIicoW7dutGwYUNeffVVXC4XBw4cYMqUKdx8882AMaLgsssuY9WqVQwaNMjkaiUQtG0cTc82DVi7K7vKUOBwxZHQ7z4S+t1Xo/M67DZ6tE40ZSri06GWAREJOQ6Hg/Hjx5OWlsbAgQMZN24czZs359lnnwUgPDycrVu3cv7555tcqQSSqYNTcFbzqOB0Oe02pg4O/M6qahkQkZA0YMAA0tPTWbt2LWFhYVxyySU4nU4KCwuZM2cO+/btY9SoUWaXKQGkeUIUkwcl88h7/ltl8MlByaYtX3w6FAZEJCR5PB4cDgc9evSo8H52djbHjx8vayUQOdHQrkkcKihmxpLtZ32uB/u1Z0jXwO4rUEqrFopISPL5fNhstrJ/T5SXl4fL5cLhqHphGrGuhWkZPL54C26vr9qOhSdy2G047TaeHJQcEEGgpvdv9RkQkZBUGgR8Ph/eX5cqzs/PByAmJkZBQKo0tGsSy8b1pkfrRIBqhx2Wbu/ROpFl43oHRBA4HXpMICIhY+fOnZSUlHDgwAFSUlJo2LBhhVaBqVOnkp+fz1NPPUV8fLyJlUowaJ4QxZy7upGemc+89Rms2J5FRnZRhZkKbRgTCqW2a8SI7kkBP2qgMgoDIhIS/vznP/Paa69RUFBAhw4dcDqddOnShdtvv52uXbtSWFjIrl27yM3NVRCQ09K2cTRPDErmCZIpLHazO7uQEreXcKedlomugJ5ZsKbUZ0BEgt7s2bN5+umnmTZtGl27dmXdunVs2bKF9evXc+zYMYYMGcIDDzwAQGZmJo0bNza3YJE6UtP7d/DHGRGxvDfffJMxY8YwbNgwANq0acPx48fZuHEjb731FlOmTCEqKoq7775bQUDkFBQGRCSoFRcX0759ezZtqjg2PCwsjG7dutGtWzccDgcLFizgtttuIzIy0qRKRQKXRhOISFCLiIjg2muvZeXKlbz55ptlIwZONGLECLZv387BgwdNqFAk8CkMiEjQu+6667j++usZPXo0t912G0uXLiUrK4ujR49y9OhRli9fTlRUFK1atTK7VJGApDAgIkHP5XLx3HPP8dFHH3H48GH69+/P5Zdfzp133knbtm159913mTp1qtlligQsjSYQkZCza9cu5s+fz969e+nQoQNXXnklF154odllidS5mt6/FQZERERClKYjFhERkRpRGBCR0OD1gtttdhUiQUlhQESCX1ERXHghTJ0Khw6ZXY1I0FEYEJHgt3AhbNkCjz8ODz5odjUiQUdhQESCm88Hs2aVf3/vvebVIhKkFAZEJLht2AAbNxqvO3eGSy81tx6RIKQwICLB7cRWgTFjwGYzrxaRIKUwICLB65df4O23jdfx8TBkiLn1iAQphQERCV6vvQYlJcbrO++EqChz6xEJUgoDIhKcPB548UXjtc0G991nbj0iQUxhQESC08cfw549xusBA+C888ytRySIKQyISHA6sePg6NHm1SESAhQGRCT4pKfDZ58Zr1u2hKuvNrUckWCnMCAiwae0rwAYfQUcDvNqEQkBCgMiElyKiuD1143XERHGKAIROSsKAyISXBYsgCNHjNdDhkCDBqaWIxIKFAZEJHj8dh2CMWPMq0UkhCgMiEjwWL8evvnGeN2li9YhEPEThQERCR5qFRCpFQoDIhIcsrLgnXeM1wkJWodAxI8UBkQkOLz+esV1CCIjza1HJIQ4zS5AROREhcVudmcXUuL2Eu600zLRhctpq7gOwb33mlukSIhRGBAR06Vn5jNvfQYrfswiI6cI3wnbbEBShI/Utv0ZXvAJbS/tqHUIRPxMYUBETLM3p4iJizaxeschHHYbHq/vpH18wJ5iG3M6XcubXQbRMw6m5hTRPEHLFYv4i/oMiIgpFqZl0HfmKtbuygY4ZRA4kcduTDm8Ns9G35mrWJiWUes1iliFWgZEpM49vyKdGUu2n9GxHq8Pj9fHI+9t4lBBMWNT2/q5OhHrURgQkTq1MC2jRkGg+MB2Di97mZKsn/AdL+acP/yL8MatK+wzY8l2GtaPYEjXpNoqV8QSFAZEpM7szSni8cVbqt3P53Hzy6Lp2JzhxF/5R2zOCByxjU6576TFW+hxXgP1IRA5C+ozICJ1ZuKiTbir6RsA4D5yAE9eFjHdBhN98QDqd0zFUa/+qff1+pi4aJO/SxWxFIUBEakT6Zn5rN5xqNqOggCewlwA7BGu6vf1+li94xA7svLPukYRq1IYEJE6MW99Bg67rdr9Dn04k8z5jxiv35/OnunXcXDeI1Ue47DbmPulRheInCn1GRCROrHix6watQpEXzIAR3QieeveIbrzQMLPaYfDFVflMR6vjxXbs3iCZD9VK2ItCgMiUusKit1k5BTVaN+Ic8/H5z5O3rp3iGiejKvDFTU6LiO7iMJiN64I/VkTOV16TCAitW5PdiHVtwmcHR+wO7uwlq8iEpoUBkSk1pW4vSF1HZFQozAgIrUu3Fk3f2rq6joioUb/5YhIrWuZ6KL6cQRnx/brdUTk9CkMiEitc0U4SarlGQKTEqPUeVDkDCkMiEidSG3fqEbzDJwJh91GartTT1csItVTGBCROjG8W1KN5hk4Ex6vjxHdtViRyJlSm5qI1Im2jaPp2aYBa3dlVxsK6rW4kBaPfFij8zrsNnq0TqRNo2h/lCliSWoZEJE6M3VwCk4/Pypw2m1MHZzi13OKWI3CgIjUmeYJUUwe5N8pg58clKzli0XOksKAiNSpoV2TmNCvnV/O9WC/9gzpqr4CImdLfQZEpM6NTW1Lg/oRPL54C26v77Q6FjrsNpx2G08OSlYQEPETtQyIiCmGdk1i2bje9GidCFDtsMPS7T1aJ7JsXG8FARE/UsuAiJimeUIUc+7qRnpmPvPWZ7BiexYZ2UUVFjWyYUwolNquESO6J2nUgEgtsPl8vmrb5/Ly8oiNjSU3N5eYmJi6qEtELKqw2M3u7EJK3F7CnXZaJro0s6DIGarp/Vv/hYlIQHFFOEluGmt2GSKWoj4DIiIiFqcwICIiYnEKAyIiIhanMCAiImJxCgMiIiIWpzAgIiJicQoDIiIiFqcwICIiYnEKAyIiIhanMCAiImJxCgMiIiIWpzAgIiJicQoDIiIiFqcwICIiYnEKAyIiIhanMCAiImJxzprs5PP5AMjLy6vVYkRERMR/Su/bpffxytQoDOTn5wPQvHnzsyxLRERE6lp+fj6xsbGVbrf5qosLgNfrZf/+/URHR2Oz2fxaoIiIiNQOn89Hfn4+TZs2xW6vvGdAjcKAiIiIhC51IBQREbE4hQERERGLUxgQERGxOIUBERERi1MYEBERsTiFAREREYtTGBAREbG4/we4b8XQdpgI1AAAAABJRU5ErkJggg==",
      "text/plain": [
       "<Figure size 640x480 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import networkx as nx\n",
    "\n",
    "#create a graph\n",
    "G1 = nx.Graph()\n",
    "#define edges with weights \n",
    "G1.add_edges_from([('a','b',{\"weight\":0.6}),('a','c',{\"weight\":0.2}),('c','d',{\"weight\":0.1}),('d','a',{\"weight\":0.3}),('c','f',{\"weight\":0.9}),('c','e',{\"weight\":0.7})])\n",
    "#position of nodes for visualization\n",
    "pos = nx.spring_layout(G1)\n",
    "#extract edges\n",
    "strong_edges = [(v1,v2) for v1,v2,w in G1.edges(data=True) if w[\"weight\"]>=0.5]\n",
    "weak_edges = [(v1,v2) for v1,v2,w in G1.edges(data=True) if w[\"weight\"]<0.5]\n",
    "\n",
    "# nodes\n",
    "nx.draw_networkx_nodes(G1, pos)\n",
    "# nodes labels\n",
    "nx.draw_networkx_labels(G1,pos)\n",
    "# edges\n",
    "nx.draw_networkx_edges(G1, pos,edgelist=strong_edges,width=2,edge_color=\"red\")\n",
    "nx.draw_networkx_edges(G1, pos, edgelist=weak_edges,width=0.5,edge_color=\"red\")\n",
    "# weights on the edges\n",
    "nx.draw_networkx_edge_labels(G1,pos, edge_labels=nx.get_edge_attributes(G1,\"weight\"))\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Resources\n",
    "\n",
    "- https://www.xomnia.com/post/graph-theory-and-its-uses-with-examples-of-real-life-problems/\n",
    "- https://distill.pub/2021/gnn-intro/\n",
    "- https://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/lectures/graphs.pdf"
   ]
  }
 ],
 "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.11.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}