A quick analysis of contracting networks in NetworkX

contracted_networks.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "2df2cd61",
   "metadata": {},
   "source": [
    "# Exploring network contraction\n",
    "\n",
    "I recently got thinking about the idea of networks at different levels of resolution. In a number of computational science methods, it can be useful to have a network that is in some ways redundant, because a section of the network is just a straight line. However, often a user doesn't want to think about these intermediate steps, because they are typically a sort of \"implementation detail\" that isn't important to the overall science. I started to think about the following ideas:\n",
    "\n",
    "1. If we use that full network as the underlying network, how hard is it to contract it to a network that doesn't include these linear sections? Basically, remove any node that only has two nodes as its only partners, and have it instead point to the next nodes in the sequence.\n",
    "\n",
    "2. What if we futher identified certain nodes as \"blessed\" by the user -- nodes that the user actually wants to think about. Can we create the network that implicitly exists between these nodes?\n",
    "\n",
    "Important side note on this is the cost as the size of the graph increases. We measure this in terms of number of nodes (vertices) $V$ and number of edges $E$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "dcc4a565",
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "1f08e20c",
   "metadata": {},
   "outputs": [],
   "source": [
    "# we have a three representation of the underlying:\n",
    "\n",
    "# 1. Level the user cares about, denoted by lower-case Greek letters\n",
    "# 2. Implicit level that is essential to deep graph structure, includes Greek and Hebrew letters\n",
    "# 3. Deep underlying \"truth\", which included redundant nodes (Latin letters) as well as the others\n",
    "truth = [\n",
    "    (\"α\", \"A\"),\n",
    "    (\"A\", \"B\"),\n",
    "    (\"B\", \"א\"),\n",
    "    (\"א\", \"C\"),\n",
    "    (\"א\", \"D\"),\n",
    "    (\"C\", \"β\"),\n",
    "    (\"D\", \"γ\"),\n",
    "]\n",
    "\n",
    "# really, the user just inputs the nodes, but this is the effective graph that comes out\n",
    "user = [\n",
    "    (\"α\", \"β\"),\n",
    "    (\"α\", \"γ\"),\n",
    "    (\"β\", \"γ\"),\n",
    "]\n",
    "\n",
    "implicit = [\n",
    "    (\"α\", \"א\"),\n",
    "    (\"א\", \"β\"),\n",
    "    (\"א\", \"γ\"),    \n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3bc5cb02",
   "metadata": {},
   "source": [
    "The goal here is to be able to efficiently generate `implicit` and `user` from `truth`, with only the `user` nodes labeled as being of interest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "a43cda8a",
   "metadata": {},
   "outputs": [],
   "source": [
    "import logging\n",
    "logger = logging.getLogger('local')"
   ]
  },
  {
   "cell_type": "raw",
   "id": "3575d76e",
   "metadata": {},
   "source": [
    "# standard simple logging setup; switch between raw and code to enable/disable\n",
    "logger.setLevel(logging.DEBUG)\n",
    "ch = logging.StreamHandler()\n",
    "ch.setLevel(logging.DEBUG)\n",
    "formatter = logging.Formatter('%(asctime)s - %(levelname)s - %(message)s')\n",
    "ch.setFormatter(formatter)\n",
    "logger.addHandler(ch)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "b968d986",
   "metadata": {},
   "outputs": [],
   "source": [
    "# stuff to build graphs\n",
    "def nodes_from_edges(edges):\n",
    "    return set(\"\".join([n1 + n2 for n1, n2 in edges]))\n",
    "\n",
    "USER_NODES = nodes_from_edges(user)\n",
    "\n",
    "def build_graph(edges):\n",
    "    all_nodes = nodes_from_edges(edges)\n",
    "    is_user_node = {node: node in USER_NODES for node in all_nodes}\n",
    "    graph = nx.Graph()\n",
    "    for node in all_nodes:\n",
    "        graph.add_node(node, is_user=is_user_node[node])\n",
    "    \n",
    "    graph.add_edges_from(edges)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "232eea2c",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAmyklEQVR4nO3de1yUdd438M81B2Y4iHggD8GtETHjEYNMe0o55CEBa59dO5ltz9Om7UNHC9NENlchZTE7ra7l3X3vbrZly+523yKrqSDVbVjhGRmUzIJVEEiCAWaYw/X84TIrzaAoM1wyv8/79drXa3euay6++nqxH7+/63eQZFmWQUREJAiV0gUQERH1JQYfEREJhcFHRERCYfAREZFQGHxERCQUBh8REQmFwUdEREJh8BERkVAYfEREJBQGHxERCUXj6x/QYLYiv6wGptpmNFvsCNVrYBweinvjIzAkROfrH09ERNSF5Ku9Og9XN2HD3iqUnKgHAFjtTtc1vUYFGUCiIRzpCdGIjQzzRQlERERufBJ8W0pPI6fQBIvdgUs9XZIAvUaNzBQjFkwd7e0yiIiI3Hh9qPNC6FWg3ea87L2yDLTbHMgprAAAhh8REfmcVye3HK5uQk6hqUehd7F2mxM5hSYcqWnyZjlERERuvBp8G/ZWwWJ3XNV3LXYHNu6t8mY5REREbrwWfA1mK0pO1Ht8p2etrcLZPyzGd+vvxbn81bC3NKBm4//Fxa8XZRkorqxHo9nqrZKIiIjceC348stqPH7utFlRn78KIZPuQuQzfwJkB+r/+jICo+IhSVKXeyUA+Qc8P4eIiMgbvBZ8ptrmLksWOnWcqYTsdCJk4kxIai2CJ8xAx9kTCIq5ze1ei90J09kWb5VERETkxmvB12yxe/zc0XoemoHhkKQLPyrguhsgBQRCP2piN8+xeaskIiIiN14LvlC955UR6uBBcFrMrv9ta6y58EJP5fn+UL3WWyURERG58VrwGYeHQqdxf1zASAOc1jZYao4DAFoOFgKQ0VH3tdu9eo0KxhEDvFUSERGRG6/t3NJgtuL23CKP7/ks3x3F+aJ3INs7oA0fhWDjNJzf+3sMSX0W+oixrvsCNCp8vjSZe3gSEZHPeHXLskXvfoVdFXWX3KasW7ITqDmCNalRuP/++6FS8eAIIiLyPq+myxOJ0dBr1Ff13cAALVbedxvWr1+PKVOmoKSkxJulERERAfBy8MVGhiEzxYhA7ZU9NlCrQmaKEf/n7mTs378fzz33HB555BHcc889MJlM3iyRiIgE5/XxxAVTRyMzZQwCtWr8aH26G0kCArVqZKaMcW1QrVKp8OCDD8JkMmHatGmYNm0a0tPTUVdX5+1SiYhIQD55kbZg6mhsXTQVs8cOg06jgv5Hsz31GhV0GhVmjx2GrYumejyVQa/XIyMjAyaTCTqdDuPGjUNOTg7a2tp8UTIREQnCZwfRdmo0W5F/oAamsy1ottgQqtfCOGIA5sVd2QnsX3/9NZYvX459+/Zh1apV+PnPfw61+ureJxIRkbh8HnzeVlpaioyMDLS0tCAvLw+zZs1SuiQiIupH+l3wAYAsy/jb3/6GZcuW4YYbbkBeXh4mTvS8BRoREdHF+uViOUmS8NOf/hTl5eWYO3cuZs2ahUcffRT/+Mc/lC6NiIiucf0y+DpptVo8+eSTqKysxLBhwzBx4kSsWLECLS084YGIiDzr18HXaeDAgVizZg0OHTqE6upqxMTE4He/+x1sNp70QEREXfXLd3yXc/DgQSxZsgQ1NTX4zW9+g7lz57odektERGLyy+ADLkyA2bFjB5YsWYIhQ4Zg3bp1mDx5stJlERGRwvxiqNMTSZIwZ84cHDp0CA8//DB+8pOfYP78+Th9+rTSpRERkYL8Nvg6aTQaPPbYY6isrITBYEB8fDwyMjJw/vx5pUsjIiIF+H3wdQoJCcFLL72EY8eOoaWlBQaDAa+++iqsVqvSpRERUR8SJvg6jRgxAm+99RaKi4uxZ88ejB07Fh9++CH89FUnERH9iN9ObumpoqIiZGRkICAgAOvWrcMdd9yhdElERORDwgcfADidTvzpT39CZmYm4uPjsXbtWsTExChdFhER+YBwQ52eqFQqLFiwACaTCVOmTMHtt9+OJ598EvX19UqXRkREXsbgu0hgYCCWLl2KiooKqNVqjBkzBmvWrEF7e7vSpRERkZcw+DwYOnQoXn/9dXz++ecoKyuDwWDAH//4RzidTqVLIyKiXuI7vh7Yt28fMjIy0N7ejry8PMyYMUPpkoiI6Cox+HpIlmX85S9/wbJlyxATE4Pf/OY3GD9+/GW/12C2Ir+sBqbaZjRb7AjVa2AcHop746/sBHoiIvIOBt8V6ujowKZNm5CdnY27774bq1atwsiRI93uO1zdhA17q1By4sIEGav9X8Okeo0KMoBEQzjSE6IRGxnWR9UTERHf8V2hgIAAPP300zhx4gSGDBmCCRMm4KWXXoLZbHbds6X0NB7YXIpdFXWw2p1dQg8ALP/87OPjdXhgcym2lJ7u4z8FEZG42PH10rfffovMzEwUFRVh5cqV0I2bgbU7K9Fu6xp2te8tg+3cN4h4agskjbbLtUCtCpkpY7Bg6ug+rJyISEwMPi8pKyvDUyvX4YzxPkAT0OWavakO/3hrIVS6IAy+60kEG913hwnUqrF10VRMjAjro4qJiMTEoU4viY+Px/j7nof0o9ADAPOxIuhGGhA84U60Ht3j8fsWuwMb91b5ukwiIuEx+LykwWxFyYl6eGqfW48VIXhcIoLHJaH9mwNwtLofiSTLQHFlPRrNPC2CiMiXGHxekl9W4/FzS3U57M3nEGS8A7rh0dCEjUBreYnHeyUA+Qc8P4eIiLyDweclptpmt9mbANB6bA8Cb7gZ6qCBAIDgsQkwH+tuuNMJ09kWn9ZJRCQ6jdIF+Itmi93tM6fNilbTZ4DTieo3F1z40G6D09qKjrpTCBgW5eE5Nl+XSkQkNAafl4Tq3f8q20+WQpJUGPHYbyGp/7WEof6jtTAfK8JgD8EXqte6fUZERN7DoU4vMQ4PhU7T9a/TfHQPgifMgGbgdVCHDHL9Z0B8GlqP74XsdHS5X69RwThiQF+WTUQkHK7j85IGsxW35xZ5fM/XUyrZgcLH42C8IcKLlRER0cXY8XnJ0BAdEmLCIUlX930JwHBnA+6YPAnZ2dlobW31an1ERHQBg8+LnkiMhl6jvqrv6rVqbHr6p/jiiy9w7NgxGAwGvPPOO3A4HJf/MhER9RiDz4tiI8OQmWJEoPbK/lov7NVpxMSIMERFReGDDz7AX//6V/zhD39AbGwsCgsLwRFpIiLv4Ds+H9hSeho5hSZY7A5c6m9XkgC9Ro3MFKPHDaplWca2bduwdOlSjBw5Enl5eYiLi/Nd4UREAmDw+ciRmiZs3FuF4sp6SLiwOL1T53l8SYZwpCdGX3ZjarvdjnfeeQe//vWvceeddyI7OxujRo3yaf1ERP6KwedjjWYr8g/UwHS2Bc0WG0L1WhhHDMC8uCs/gb2lpQXr1q3Db3/7W/ziF7/Aiy++iEGDBvmociIi/8Tg64fOnDmDlStX4qOPPsKLL76I9PR06HRXFqJERKLi5JZ+aOTIkXj77bdRXFyMoqIijBkzBlu3buUEGCKiHmDH5weKi4uxZMkSqFQqrFu3DtOnT1e6JCKiaxaDz084nU588MEHWL58OWJjY7F27VqMGTNG6bKIiK45HOr0EyqVCvPnz4fJZML06dMxffp0/PKXv0Rtba3SpRERXVMYfH5Gr9fj+eefR2VlJUJCQjB+/HisWrWKW6AREf0Tg89PDR48GOvWrcOXX34Jk8mEmJgYbN68GXa7+7mBREQi4Ts+QXz11VfIyMhAfX09cnNzkZqaCulqd9QmIurHGHwCkWUZ27dvxwsvvIBhw4YhLy8Pt9xyi9JlERH1KQ51CkSSJKSlpeHIkSOYP38+7r77bsyfPx+nT59WujQioj7D4BOQRqPBwoULceLECRgMBsTHxyMjIwPnz59XujQiIp9j8AksJCQEL730EsrLy2E2m2EwGPDKK6/AarUqXRoRkc8w+AjDhw/Hpk2bUFJSgpKSEhiNRrz//vtwOp2X/zIRUT/DyS3kpqSkBEuWLIEsy8jLy0NiYqLSJREReQ2DjzxyOp348MMPsXz5cowbNw65ubkYO3as0mUREfUahzrJI5VKhQceeAAVFRVITk5GYmIiFi1ahLNnzypdGhFRrzD46JJ0Oh0WL16MyspKDBw4EOPHj8fKlSthNpuVLo2I6Kow+KhHBg0ahLy8PJSVlaGqqgoxMTF46623uAUaEfU7fMdHV6WsrAxLlixBbW0tcnNzkZaWxi3QiKhfYPDRVZNlGX//+9/xwgsvYOjQocjLy8PkyZOVLouI6JIYfNRrdrsdv//97/HSSy9h+vTpyMnJQVRUlNJlEVE/0GC2Ir+sBqbaZjRb7AjVa2AcHop74yMwJETnk5/J4COvaW1txfr16/H666/j5z//OVasWIHBgwcrXRYRXYMOVzdhw94qlJyoBwBY7f/aMEOvUUEGkGgIR3pCNGIjw7z6szm5hbwmODgYWVlZKC8vh8VigcFgQF5eHiwWi9KlEdE1ZEvpaTywuRS7KupgtTu7hB4AWP752cfH6/DA5lJsKT3t1Z/Pjo98xmQyYdmyZTh06BBycnLw4IMPQqXq2b+1lBj+ICLf21J6GjmFFWi3XQg7e0sjGgvWw1p7EpqQIRg085cIHB3b5TuBWhUyU8ZgwdTRXqmBwUc+9+mnnyIjIwN2ux15eXlITk7u9l4lhz+IyLcOVzfhgc2laLc5XJ81FL4OZ3sLwu9ZCmttFRr+KxcRT/ze7buBWjW2LpqKiRFhva6DQ53kc9OmTUNpaSmWLl2KhQsXIjU1FeXl5W73KT38QUS+tWFvFSx2R5fPOs6eRMj4ZEgaLfQRYyA77XC0/eD2XYvdgY17q7xSB4OP+oQkSbjvvvtw/PhxzJo1C8nJyXjsscdw5swZABcPfzhwuTEIWQbabQ7kFFYw/Ij6iQazFSUn6t1+v53WNki6IACAbLfBaTFDUqndvi/LQHFlPRrNvT82TdPrJxBdAZ1Oh2eeeQaPPPII1qxZgwkTJuD+//cCiqSJsFzU4dVsfBTOtiZAUkFSqaGLGIPBs5+AJjTcdU+7zYmcQhMmRoR5ZfiDiHwnv6zmktedHe1oKvkjtEMiodKHeLxHApB/oAaPT7+xV7Ww4yNFhIWFITc3FwcPHsR+cxjaO9y3Pguf9yv82/P5iHjqXaiCwvD9rrfc7vHm8AcR+Y6pttnt9cXFat5cgJaybdBHjocse77PYnfCdLal17Uw+EhRQYOHwTzg3yBdYranpAlAsPF22Bq+c7vmzeEPIvKdZsul9/WNXPwhRjz6Jqw1x/HDZ+9f4jm2XtfC4CNFXW74AwCcNgtaKz6FbqTB4/XO4Q8iunaF6i/9Zk1SqRFw3Q0IHp+MjtqTl3iOtte18B0fKepSwx/1f8kGVGrIHe1QB4fhuvtWebzPW8MfRORddrsd+/btQ0FBAbabzJANMyFpAtzuMx/ZhYBhN0JSqdFe9QUCRsZ4fJ5eo4JxxIBe18XgI0Vdavgj/GcrEDh6EmSnA+0n96PuT8sw8rHfQR0yyMNzej/8QUS919DQgB07dqCgoAAff/wxRo8ejbS0NGzI+N94aleTx3/oOpobcOathQAk6G+YhIFT5nl8tgxgXlxEr2tk8JGiLjf8AVwYAgky/C807vgtLDXlCDbe4eE5vR/+IKIrJ8syjhw5gu3bt6OgoADl5eVISkpCWloa1q9fj5EjR7ruTfj2K+yqqHNb0jDwjgcROHrSJX+OJAFJhnCv7NzE4CNFGYeHQqepveRsL1mW0X5yP5wWM7RDIt2ue2v4g4h6pq2tDXv27MH27duxfft2BAQEIDU1FStXrkRCQgJ0Os/h9ERiND492dBl55ae0mvUSE+M7m3pABh8pLB58RF4dfcJj9fq81cBkgqQJGhCwzEkbTECwke53eet4Q8i6t7p06ddQffZZ58hPj4eqamp2LVrFwwGQ48Ooo6NDENmirHLXp09cWGvTqPX1utyr05S3KJ3PQ9/9IjTCe25CmycfzNmzpzp9dqIRGW32/H5559fmJiyfTvOnTuHOXPmIDU1FbNmzUJYWNhVP/vCTk0mWOyX3qlJki50epkpRq9tUA0w+Oga4Gnj2p4K1KqxMKoVv8tZhtGjR2Pt2rWIj4/3QZVE/q+xsbHLxJRRo0YhNTUVqampmDx5MtRq963ErtaRmiZs3FuF4sp6SECXnZs6N6RPMoQjPTHa6zszMfjomvDjo0p64uKjSmw2G/793/8dq1evRkJCArKzs3Hjjb3b1ojI38myjKNHj7omphw9etQ1MSUlJQXXX3+9z2toNFuRf6AGprMtaLbYEKrXwjhiAObF8QR2EoA3hj/MZjNee+01vPbaa3jwwQeRlZWF6667zreFE/UjbW1tKCoqcr2v02g0SE1NRVpaGhISEqDX65Uu0ecYfHRN8dbwR319PXJycvDuu+/iqaeewvPPP48BAzjzk8T07bffuoLu008/RVxcnCvsjEZjjyam+BMGH12TvDX88c033yArKwu7d+/GihUrsGjRIgQEuO8cQeRPOiemdIZdbW2ta2LK7NmzezUxxR8w+EgIBw8exIsvvoiTJ08iJycH9913H1SX2BibqDcazFbkl9XAVNuMZosdoXoNjMNDcW+8795bff/9966JKTt37kRkZCTS0tKQmpqKW2+91asTU/o7Bh8JZc+ePVi6dClkWUZubi5mzJihdEnkRw5XN2HD3iqUnKgHgC4bM3QO1ScawpGeEI3YyLBe/SxZlnHs2DHXxJQjR44gMTHRNTElIoJrW7vD4CPhOJ1O5OfnY/ny5YiKisLatWsRFxendFnUz/XF2rT29vYuE1NUKpXrXV1iYqIQE1O8gcFHwrLZbNi8eTNWr16NpKQkZGdnIyoqSumyqB/q7XKcS/nuu+9cQffJJ5/g5ptvdoXdmDFjhJuY4g0MPhKe2WzGq6++itdeew0PPfQQVqxYwSUQ1GPdbcDQWr4XzV9+BFtjDVQBgdAOi8LA2+6DPnKc655ArRpbF03tMkPZbrejtLTUFXZnzpzpMjFl0CD300noyjD4iP7p3LlzyMnJwZYtW/D000/jueee4xIIuixPW+41f/E3/FCajyGzn4D+hjhIag3aT5XBWl2OQcmPuu6TJGD22GF4OSUKO3fudE1MiYiIcO2YMmXKFE5M8TIGH9GPnDp1CllZWSgqKsKKFSuwcOFCLoEgjxrMVtyeW9RlEovT0oqaDY9gSOqzHo/QcuO04/x/pmP6lDjXxJTISPdTSMh7OJ+b6EeioqLw3nvvobCwEP/93/+NsWPHYuvWrXA6e/7+hsSQX1bj9pn1jAmyvQNBMbf16BlajQY57+/Btm3b8PjjjzP0+gCDj6gbN998M3bu3IlNmzYhLy8Pt956K/bs2aN0WXQNMdU2u50l6WhvhiooFJKqZ8OTNifwdYPFF+VRNxh8RJcxY8YMfPHFF1iyZAkef/xxzJ49GwcPHlS6LLoGNFvsbp+pA0PhbGuG7Oz5aSPNFps3y6LLYPAR9YBKpcL999+P48eP45577kFKSgoeeughnDp1SunSSEGhevezvHUjjZA0AWg78fkVPEfrzbLoMhh8RFcgICAA6enpOHnyJAwGAyZPnoxnnnkG9fX1SpdGfejUqVN444038Om2rZBt1i7XVPpghE17CN9/vAltJz6H02aB7LCj/euvcL74P9yepdeoYBzB2cN9ibM6iXrh3LlzyM7OxnvvvYdnnnkGzz33HEJCQpQui7zMbrdj3759KCgoQEFBARobG5GamorEu+Yi+4gOHQ73/xs1lxej5cv/gq2xGlJAIHTDoxF62/3QR4zpcp9Oo8K+pck+28OT3DH4iLzg66+/RlZWFoqLi5GVlYWFCxdCq+XwVX92/vx516bPO3bswKhRo5CWloa0tDTccsstrk3OPa3j66nOdXybFtzi5erpUhh8RF504MABLFu2DN988w1ycnIwb948ngLRT8iyjMrKSldXd+DAASQkJLhOOOhu0+fudm7pCU87t5DvMfiIfGDXrl1YtmwZVCoVcnNzkZycrHRJ5EFHRwc+/fRTFBQUYNu2bbBYLK6uLjk5GUFBQT16ji/36iTvY/AR+YjT6cSf//xnLF++HDfddBPWrl2LSZMmKV2W8Orr61FYWIiCggLs2rULBoMBc+fORVpaGmJjY6960+e+OJ2BvIPBR+RjHR0drlMgZsyYgdWrV+OGG25QuixhyLKMo0ePuoYwy8vLMWPGDNf2YMOGDfPazzpS04SNe6tQXFkPCYDFw3l8SYZwpCdGc3hTQQw+oj7S0tKC9evX44033sDDDz+MzMxMhIeHK12WX7JYLCguLnaFnUqlcnV1CQkJ0Ol8O4Oy0WxF/oEamM62oNliQ6heC+OIAZgX57sT2KnnGHxEfayurg7Z2dl4//338eyzz2Lx4sUIDg5Wuqx+78yZM67TyIuLixEbG+sKO55bRxdj8BEppKqqCllZWSgpKUFWVhYee+wxLoG4Ak6nEwcOHHB1dadOncLs2bORlpaGu+66C0OGDFG6RLpGMfiIFFZWVoZly5bh9OnTePnllzFv3jx2J91obW3F7t27UVBQgO3btyM0NNQ1C/P222/nPxyoRxh8RNeIXbt2YenSpdBoNMjNzUVSUpLSJV0Tvv32W1dX99lnn+HWW291hd1NN92kdHnUDzH4iK4hTqcTH374ITIzMxETE4O1a9ciNjZW6bL6lMPhwP79+11hd/bsWcyZMwdz587FrFmzMHDgQKVLpH6OwUd0Dero6MDbb7+N7OxszJw5E6tXr8bo0aOVLstnfvjhB3z88ccoKChAYWEhRowY4erqpkyZArW6Z2fbEfUEg4/oGtbS0oJXXnkFb775pt8tgaiqqnJ1dfv378cdd9zh2h7Mn0OelMfgI+oH6urqsHr1arz//vtYvHhxv1wCYbPZsG/fPmzbtg0FBQX44YcfkJqairlz5+LOO+/kqRbUZxh8RP1IVVUVVqxYgU8++QS/+tWv8Itf/KLHMxkbzFbkl9XAVNuMZosdoXoNjMNDcW+87xZVNzY2uk442LlzJ6KiolxDmHFxcdzAmxTB4CPqh7766issXboU1dXVePnll/Gzn/2s2yUQh6ubsGFvFUpOXDgs1+phG61EQzjSE6IRGxnWq7pkWUZFRYVrCPPQoUNISkpybQ92/fXX9+r5RN7A4CPqp2RZdi2BCAgIQG5uLhITE7vc0xcbJ1utVnzyySeuIUy73e7q6pKSkhAYGHjlfzgiH2LwEfVzTqcTH3zwAVasWAGj0Yg1a9YgNjbWp0fl1NXVuU442L17N8aOHYu0tDTMnTsXEyZM4AJ8uqYx+Ij8REdHB9566y1kZ2fjttQHUHH9bFjtV/7r7elwVFmWcfjwYdcQpslkwsyZM5GWloY5c+bguuuu8+KfhMi3GHxEfqa5uRlpa/8L3zrCIF3F5BFJAmaPHYZXfzYORUVFrrALCAhwbfo8ffp0BAQE+KB6It/TKF0AEXlXh0qHOvVQSLL7EOf54v9ER+1JDHvwZQCAvakO/9j8S4xa8jfXPbIM7Dz6Dwx/7h5MGhONtLQ014GtHMIkf8DgI/Iz+WU13V4Lm/YQzvzHU2g5/DEGxM6CDBmSxn05hFqtxso/7sDiuyb4slQiRXARDZGfMdU2d1mycDFJE4CQiTPRVPQO7Obv4WhpgGag+wnkdlnCdz84fF0qkSLY8RH5mWaLvdtrrabP0Hq8BPobb8H3f38TTmsbBkya081zbL4qkUhR7PiI/Eyovvt/z5oP7UDY7Q9iyOwn0HHuGwQMj8aAuJRunsOz7cg/MfiI/IxxeCh0Gs+/2vYfzkEdMhgqXRAGz05HW8UncFjMbvfpNSoYRwzwdalEimDwEfmZefER3V6THf8aBg2KvhW6f5uA87s3u98HYF5c988h6s+4jo/IDy169yvsqqi75DZl3elcx7dpwS3eL4zoGsCOj8gPPZEYDb3m6g5v1WvUSE+M9nJFRNcOBh+RH4qNDENmihGB2iv7Fb+wV6exy3ZlRP6GyxmI/FTnRtO+Pp2BqL/hOz4iP3ekpgkb91ahuLIeEgCLh/P4kgzhSE+MZqdHQmDwEQmi0WxF/oEamM62oHB3MSZPGo9pE6IwL853J7ATXYsYfEQCSkpKQlZWFpKTk5UuhajPcXILkYB0Oh2sVqvSZRApgsFHJCC9Xg+LxaJ0GUSKYPARCYgdH4mMwUckIHZ8JDIGH5GA2PGRyBh8RAJix0ciY/ARCYgdH4mMwUckIHZ8JDIGH5GA2PGRyBh8RAJix0ciY/ARCYgdH4mMwUckIL1ez+AjYTH4iASk0+k41EnCYvARCYgdH4mMwUckIHZ8JDIGH5GA2PGRyBh8RAJix0ciY/ARCYgdH4mMwUckIHZ8JDIGH5GA2PGRyBh8RAJix0ciY/ARCYgdH4mMwUckIHZ8JDIGH5GAuEk1iUySZVlWuggi6lt2ux06nQ4Oh0PpUoj6HDs+IgFpNBoAFwKQSDQMPiJB8TBaEhWDj0hQfM9HomLwEQmKHR+JisFHJCh2fCQqBh+RoNjxkagYfESCYsdHomLwEQmKHR+JisFHJCh2fCQqBh+RoNjxkagYfESCYsdHomLwEQmKRxORqBh8RILi0UQkKgYfkaDY8ZGoGHxEgmLHR6Ji8BEJih0fiYrBRyQodnwkKgYfkaDY8ZGoGHxEgmLHR6Ji8BEJih0fiYrBRyQodnwkKgYfkaDY8ZGoGHxEgmLHR6Ji8BEJiptUk6gYfESC4rFEJCoGH5Gg2PGRqBh8RIJix0eiYvARCYodH4mKwUckKHZ8JCoGH5Gg2PGRqDRKF0BEfa/BbMVfjjfDFj8fj/7hS4TqNTAOD8W98REYEqJTujwin5JkWZaVLoKI+sbh6iZs2FuFkhP1kGUZHY5//frrNSrIABIN4UhPiEZsZJhidRL5EoOPSBBbSk8jp9AEi92BS/3WSxKg16iRmWLEgqmj+6w+or7CoU4iAVwIvQq025yXvVeWgXabAzmFFQDA8CO/w46PyM8drm7CA5tL0W5zAABqNj4KZ1sToFIDkgoBQyMRPD4ZIZPugiR1ne8WqFVj66KpmBgR1veFE/kIOz4iP7dhbxUsdkeXz8Ln/QqBoyfBaWmFpfoYvt/9NqxnTmBo6rNd7rPYHdi4twqbFtzShxUT+RaXMxD5sQaz9Z8TWTxfV+mDEXTTFITf8wJaj+5BR/3pLtdlGSiurEejmcseyH8w+Ij8WH5ZTY/u0400QB06FNbq427XJAD5B3r2HKL+gMFH5MdMtc2w2i8/oQUA1CGD4bS0uH1usTthOuv+OVF/xeAj8mPNFnuP73W0NEKlH9DNc2zeKolIcQw+Ij8Wqu/Z/DXr2RNwtDRCFzG2m+dovVkWkaI4q5PIjxmHh0Knqe12uNNpbYOl+hjO734bweMSEXDdaLd79BoVjCM8d4JE/RGDj8iPzYuPwKu7T7h9Xp+/6p/r+CRoh0QidPJPEHLzHI/PkAHMi4vwcaVEfYfBR+THhobokBATjl0Vda4lDRHp/9Hj70sSkGQI58bV5Ff4jo/Izz2RGA29Rn1V39Vr1EhPjPZyRUTKYvAR+bnYyDBkphgRqL2yX/dArQqZKUZuV0Z+h0OdRALo3GiapzMQcZNqIqEcqWnCxr1VKK6sh4QLi9M7dZ7Hl2QIR3piNDs98lsMPiIBNZqtyD9Qgz9//D9od0q4NXYCjCMGYF4cT2An/8ehTiIBDQnR4fHpN8L85Uc4c+YMXrn/YaVLIuoznNxCJLCgoCC0tbUpXQZRn2LwEQmMwUciYvARCSwoKAitra1Kl0HUpxh8RAJjx0ciYvARCYzBRyJi8BEJjMFHImLwEQmMwUciYvARCSw4OJjBR8Jh8BEJjB0fiYjBRyQwBh+JiMFHJLDAwEC0tbWBW/aSSBh8RALTarVQqVSw2WxKl0LUZxh8RILj7i0kGgYfkeD4no9Ew+AjEhyDj0TD4CMSHIOPRMPgIxIcg49Ew+AjEhx3byHRMPiIBMeOj0TD4CMSHIOPRMPgIxIcg49Ew+AjEhwXsJNoGHxEgmPHR6Jh8BEJjsFHomHwEQmOwUeiYfARCY7BR6Jh8BEJjgvYSTQMPiLBseMj0TD4iATH4CPRMPiIBMfgI9Ew+IgEx+Aj0TD4iATHnVtINAw+IsGx4yPRMPiIBMfgI9Ew+IgEx+Aj0TD4iATH4CPRMPiIBKfT6WC322G325UuhahPMPiIBCdJEoKCgtDe3q50KUR9gsFHRBzuJKEw+IiIwUdCYfARERexk1AYfETEjo+EwuAjIgYfCUWjdAFEpJwGsxX5ZTU4b7wH675sxUd1B2EcHop74yMwJESndHlEPiHJsiwrXQQR9a3D1U3YsLcKJSfqAQBWu9N1Ta9RQQaQaAhHekI0YiPDlCmSyEcYfESC2VJ6GjmFJljsDlzqt1+SAL1GjcwUIxZMHd1n9RH5Goc6iQRyIfQq0G5zXvZeWQbabQ7kFFYAAMOP/AYntxAJ4nB1E3IKTT0KvYu125zIKTThSE2Tbwoj6mMMPiJBbNhbBYvdcVXftdgd2Li3yssVESmDwUckgAazFSUn6t3e6Z39/bOo/+vLuPhV//ni/0Rj4Rtd7pNloLiyHo1ma1+US+RTDD4iAeSX1Xj8fNhDa9FRfxrW6nIAgOx0oLW8GMHjk93ulQDkH/D8HKL+hMFHJABTbXOXJQudVFo9gscnoa3yfwAAlm8OAmotdJHj3O612J0wnW3xea1EvsbgIxJAs6X7s/aCYm5D28lSyLIM89E9CBmXBEmSunmOzVclEvUZBh+RAEL13a9cCggfDUmtgeWbA2iv2o/gCe7DnP96jtYX5RH1KQYfkQCMw0Oh03T/6x50021o3PFbBAy7EdpBIz3eo9eoYBwxwFclEvUZBh+RAObFR1zyemDMbXA013uc1NJJBjAv7tLPIeoPGHxEAhgaokNCTDi6eXUH3fUGAIB+1ESP1yUJSDKEc+Nq8gsMPiJBPJEYDb1G7fGaJKk6/4vH63qNGumJ0b4qjahPMfiIBBEbGYbMFCMCtVf2ax+oVSEzxYiJEWG+KYyoj/F0BiLB8HQGEh2Dj0hAR2qasHFvFYor6yHhwuL0Tp3n8SUZwpGeGM1Oj/wOg49IYI1mK/IP1MB0tgXNFhtC9VoYRwzAvDiewE7+i8FHRERC4eQWIiISCoOPiIiEwuAjIiKhMPiIiEgoDD4iIhIKg4+IiITC4CMiIqEw+IiISCgMPiIiEsr/B4x6MVlowgoAAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "graph = build_graph(truth)\n",
    "nx.draw(graph, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72698c54",
   "metadata": {},
   "source": [
    "## Problem 1: Contract from `truth` to `implicit`\n",
    "\n",
    "This is a common and trivial problem. From the solution, it is clear that it is $O(V)$. This implementation is based on a [Stack Overflow answer](https://stackoverflow.com/a/54287434)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "a52eccff",
   "metadata": {},
   "outputs": [],
   "source": [
    "def make_implicit(graph):\n",
    "    graph = graph.copy()\n",
    "    for node in list(graph.nodes):\n",
    "        if graph.degree(node) == 2 and not graph.nodes[node]['is_user']:\n",
    "            logger.debug(f\"Preparing to remove node: {node}\")\n",
    "            (_, from_node), (_, to_node) = graph.edges(node)\n",
    "            logger.debug(f\"Creating edge from {from_node} to {to_node}\")\n",
    "            graph.add_edge(from_node, to_node)\n",
    "            graph.remove_node(node)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "c615bcc7",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAdWUlEQVR4nO3de3RV9d3n8c9JTpITSAIhRIKAoERIuIaLEC7mxqgjS+swS5fT6lqt09VW6QhoF31qsY5a0VrXouCFWW2ZPjNeni4t65k+dmTqo+QCBAIVJCAhxCi3cNEkEJKYnMO5zR+QbUIuEHJO9jl7v19/ac45+3xdC/zk99v79/06gsFgUAAA2ESM2QUAADCYCD4AgK0QfAAAWyH4AAC2QvABAGyF4AMA2ArBBwCwFYIPAGArBB8AwFYIPgCArTjD/QUNrR5t3lun6rPNanb7lOJyKisjRQ/MGau0pIRwfz0AAF04wtWrs/Jkk94orVVZTb0kyeMLGK+5nDEKSiqYnK7l+ZmaOW54OEoAAKCbsATf2xXHtHZLtdw+v/q6usMhuZyxWrM0Sw/nTgh1GQAAdBPyrc5LoXdY7d5LKzxfS6Ma/+86ec5+LmdSmlLveFSJE2ZKkoJBqd3r19othyWJ8AMAhF1IH26pPNmktVuqjdCTpKbtb8sRn6hxj7+jEXevUOMHv+v2uXZvQGu3VOtAXVMoywEAoJuQBt8bpbVy+/xdfnbxzOdKmlYkhzNOrrHZCgZ88rdd6PZZt8+vjaW1oSwHAIBuQhZ8Da0eldXUd7unF/C0yZEwRJIU9HkVcLfKERPb7fPBoFRypF6NrZ5QlQQAQDchC77Ne+v6fD1wsV3nS/6kuLRxinEl9fgeh6TN+/q+DgAAAxGyh1uqzzZ3ObJwpbrXHlbQ61HynHsVDAbkcHTPXLcvoOozLaEqCQCAbkK24mt2+/p8fdwT72n0f31NnroqXdjx5z6u4w1VSQAAdBOy4Etx9b14dMTEKv6GmzV0WpEunv28j+vEhaokAAC6CVnwZWWkKMHZ8+VaD3wkf3uLAp42tdfuUdwNN/f4PpczRlmjk0NVEgAA3YQs+O6fM7bX1/zNDTr9+x/p1P/4oWKGpGjY/Pt7fF9Q0v2ze78OAAADFbKHW0YmJSh/Uro+OvxVtyMNwxZ/V4kTcvr8fDAQ0JCm4/rm3FdKS7opVGUBANBFSA+w/7QgUy5n9zN61yIxwalFqa2aNWuWnnvuObW1tYWyNAAAJIU4+GaOG641S7OUGNe/yybGxejppdl6/fmfa9++faqqqlJ2drbee+89hWl4BADApiJ2OkNZWZlWrlypYcOGacOGDcrJyQl1mQAAGwrbPL4DdU3aWFqrkiP1cujS4fQOHfP4Ciena3lBpmaMHd7jNfx+vzZt2qRnnnlGy5Yt069//Wulp6eHo1wAgE2ELfg6NLZ6tHlfnarPtKjZ7VWKK05Zo5N1/+xrn8B+/vx5Pffcc3rnnXf09NNPa/ny5YqL47wfAKD/wh58oVRVVaVVq1aprq5O69ev15133ml2SQCAKBNVwSdJwWBQ77//vp588klNmzZN69at08SJE80uCwAQJUL6VOdgcDgcuu+++1RVVaUFCxZo/vz5euqpp9TSQnNrAMDVRV3wdUhISNAvfvELHThwQKdPn1ZWVpbefPNNBQK9T4gAACDqtjp7U1FRoZUrV8rhcGjDhg2aP3++2SUBACJQ1K74rpSbm6tdu3bpscce07Jly/SDH/xAZ86cMbssAECEsUzwSVJMTIy+//3v68iRI8rIyND06dP18ssvy+PxmF0aACBCWCr4OiQnJ+s3v/mNKioqtHPnTk2dOlXvv/8+7c8AANa5x9eXDz/8UE888YTGjRun3/3ud5oyZYrZJQEATGLJFd+V7rrrLlVWVuruu+9Wfn6+Vq1apaamJrPLAgCYwBbBJ0lxcXFatWqVqqqq1N7erqysLP3hD3+Q3+83uzQAwCCyxVZnTz799FOtXLlSLS0t2rBhg/Ly8swuCQAwCGwbfNKl9mfvvfeeVq9erQULFuiVV17RTTcx/R0ArMw2W509cTgcevDBB1VdXa3s7GymvwOADdg6+DoMGTJEzz77LNPfAcAGbL3V2RumvwOAdbHi60F+fr727t2r733ve7rrrrv06KOPqr6+3uyyAAAhQPD1IjY2Vj/5yU9UXV0tl8ulKVOmaMOGDfJ6vWaXBgAYALY6rxHT3wHAGgi+fmD6OwBEP7Y6+4Hp7wAQ/Qi+68D0dwCIXmx1hgDT3wEgerDiCwGmvwNA9CD4QoTp7wAQHQi+EGP6OwBENu7xhVnn6e/r169Xdna22SUBgK2x4guzjunvS5cuVV5eHtPfAcBkrPgGUX19vX71q1/pr3/9q55//nn98Ic/VGxsrNllAYBpGlo92ry3TtVnm9Xs9inF5VRWRooemDNWaUkJYflOgs8E+/fv14oVK5j+DsC2Kk826Y3SWpXVXBoA4PF9ew7a5YxRUFLB5HQtz8/UzHHDQ/rdBJ9JmP4OwK7erjimtVuq5fb51VcCORySyxmrNUuz9HDuhJB9P/f4TML0dwB2dCn0Dqvd23foSVIwKLV7/Vq75bDerjgWshoIPpMx/R2AXVSebNLaLdVq9/avvWO7N6C1W6p1oK4pJHUQfBFi/Pjxevfdd/Xmm2/qxRdfVEFBgfbv3292WQAQMm+U1srt83f5medsrc787yd0Yt0D+nrzr+VraVDdxke6/fLv9vm1sbQ2JHUQfBGmp+nvDQ0NZpcFAAPS0OpRWU19l+3NgNej+s3PKynnP2rcyn+Rgn7V/+uLSrxljhwOR5fPB4NSyZF6NbYOvBsWwReBrpz+np2dzfR3AFFt8966bj+7ePqIgoGAkmbcIUdsnIZO/w+6eKZGQyYt6PEaDkmb93W/Tn8RfBEsNTVV69evV1lZmT744APl5OToo48+MrssAOi36rPNXY4sSJL/m/NyDkuXw3EpiuJvuFmO+ES5xs/o8RpuX0DVZwY+/5TgiwJTpkzRhx9+qJdeekmPPfaY7rvvPn3xxRdmlwUA16y5vfuOVezQVAXcrca/exvrLu1pxjh7v4574DtfBF+UcDgc+s53vqNDhw4x/R1AxAsGg6qtrdXvf/97Pfjgg/r3D/6t23vib5ysgKdN7roqSVLLp1skBXXxq95/sU9xxQ24NoIvyjD9HUCkOnXqlN566y098sgjGj9+vPLz81VeXq67775b/+3h/6wEZ9fIiYlLUPp/+oXOf/wHnd60XDEJQzTynp+p4d9+a4RhZy5njLJGJw+4Tjq3RDmmvwMwy7lz51RSUqLi4mJt3bpV9fX1KiwsVFFRkZYsWaJJkyYZT2c2tHq06OXibvf5+iPBGaOd/1Q04B6evW+kIip0TH9/6623tGzZMt1555166aWXNHr0aLNLA2Axra2t2r59uxF0tbW1Wrx4sYqKivTnP/9ZM2fOVExMzxuJI5MSlD8pXR8d/uqqHVt64nBIhZPTQ9K4mhWfhbS0tGjt2rXatGmTVq9erVWrVikhITzdzQFYn8fjUUVFhRF0+/fv19y5c40V3W233ab4+Phrvl7lySb9lz9WqN3rv/qbr5AYF6t3f5yrGWOH9/uzVyL4LKi2tlY/+9nPdOjQIa1bt0733ntvt8OgAHAlv9+vTz/9VFu3btXWrVu1a9cuZWdnG0G3aNEiDRkyZEDf8W2vzmvf8kyMi9Gapdkha1RN8FkY098B9CUYDKqqqkrFxcUqLi5WWVmZbrzxRiPo8vLylJqaGvLvNXs6A8FncV6vVxs3btQLL7yghx56SM8++6yGDx9udlkATHLs2DFjRVdcXKzExEQtWbJES5YsUWFhoTIyMgaljgN1TdpYWquSI/Vy6NLh9A4d8/gKJ6dreUFmSLY3OyP4bILp74A9ffXVV8aKbuvWrWpra1NRUZGxqrv55ptNra+x1aPN++pUfaZFzW6vUlxxyhqdrPtnM4EdIcL0d8DampqaVFZWZgTdqVOnlJ+fbwTdlClTbH/Pn+CzIaa/A9bR1tam8vJyI+gOHz6sBQsWGEE3a9YsOZ2cXOuM4LOxtrY2/fa3v9Vrr72mFStWaPXq1QN+YgtAeHm9Xu3Zs8cIuk8++UQ5OTlG0OXm5nKM6SoIPuj48eP6+c9/roqKCr3yyit64IEHbL8VAkSKQCCgyspKI+h27NihzMxMI+gWL16s5OSBt/GyE4IPhrKyMq1cuVLDhg3Thg0blJOTY3ZJgO0Eg0HV1NQYQVdaWqqRI0caQVdQUKC0tDSzy4xqBB+68Pv92rRpk5555hktW7ZML7zwgkaOHGl2WYClnTx50gi64uJiORyOLkcMxo4da3aJlkLwoUfnz5/Xc889p3feeUdPP/20li9frri4gY8DASA1NDSopKTECLrz58+rsLBQS5YsUVFRkTIzM7ndEEYEH/pUVVWlVatW6dSpU1q/fr3uuOMOs0sCok5LS4u2bdtmrOqOHj2q22+/3Qi66dOn99rcGaFH8OGqgsGg/va3v+nJJ5/U1KlTtW7dOk2cONHssoCI5Xa7tWvXLiPoDhw4oHnz5hlBN3fuXHZQTETw4Zp5PB6tX79er7zyin70ox/pl7/8JU+TAZJ8Pp/27t1rBN3u3bs1depUI+gWLlyoxMREs8vEZQQf+u306dN66qmn9PHHH+ull17Sww8/zDYNbCUYDOqzzz4zgm7btm266aabjKDLy8vTsGHDzC4TvSD4cN12796tFStWMP0dlhcMBvXll18aQVdSUqLk5GQj6AoLC3XDDTeYXSauEcGHAQkEAnrrrbf01FNPMf0dlnLmzJkuRwwuXrxonKUrKirS+PHjzS4R14ngQ0gw/R3R7vz58yotLTWC7uzZsyooKDCCLisriyMGFkHwIaQ6pr9XVVVp3bp1uueee/ifBSLSN998ox07dhirupqaGi1cuNAIupycHEZ3WRTBh7Bg+jsizcWLF7V7924j6Pbt26fZs2cbQTd//nzFx8ebXSYGAcGHsGH6O8zk9/u1f/9+I+h27typSZMmGUG3ePFiDR061OwyYQKCD2HH9HcMhmAwqOrq6i7NnTMyMoygKygoUGpqqtllIgIQfBg0TH9HqB0/frzLk5fx8fFG0BUVFfGEMXpE8GFQBYNB/eUvf9Hq1auVm5vL9Hf0y9dff92luXNLS4sRckuWLNHNN9/Mw1S4KoIPpmD6O67FhQsXtG3bNiPoTpw4ofz8fCPopk6dStCh3wg+mIrp7+isvb1dO3fuNILu0KFDys3NNYJu9uzZcjqdZpeJKEfwISJ0TH8fPny4NmzYoJkzZ5pdEgaB1+vVJ598YgTdP/7xD02fPt0YwpqbmyuXy2V2mbAYgg8Rg+nv1hcIBHTw4EEj6LZv365bbrnFuE+Xl5fHxA+EHcGHiMP0d+sIBoOqra3t0tw5NTXVWNEVFBTwyw0GHcGHiMX09+h06tSpLkcMAoFAlyMG48aNM7tE2BzBh4jG9PfI19jY2KW5c0NDgwoLC40HUm699VYeWEJEIfgQFZj+HjlaW1u1fft2I+i++OILLV682Ai6GTNmMJgYEY3gQ1Rh+vvg83g8qqioMIKusrJSc+fONYLutttu4x4sogrBh6jUefr7q6++qnnz5pldkmX4/X7t27fPCLpdu3ZpypQpRtAtXLiQZgOIagQfohbT30MjGAyqqqrKCLqysjKNHTvWCLq8vDymasBSCD5EPaa/99/Ro0eNoCsuLtbQoUONoCssLNSoUaPMLhEIG4IPlsH0996dPXu2S3Pn9vZ2I+iKioo0YcIEs0sEBg3BB8th+rvU1NSksrIyI+hOnz6t/Px8I+iys7P5pQC2RfDBkuw2/b2trU3l5eVG0FVXV2vBggXGqm7WrFkM/wUuI/hgaVad/u71erVnzx4j6Pbu3aucnBwj6ObPn899TqAXBB9sIdqnvwcCAVVWVhpBV15erszMTCPoFi9erKSkJLPLBKICwQfbuN7p7w2tHm3eW6fqs81qdvuU4nIqKyNFD8wZq7Sk8KyqgsGgampqjKArLS1Venq6EXT5+flKS0sLy3cDVkfwwXY6pr+//vrrevzxx3ud/l55sklvlNaqrKZekuTxBYzXXM4YBSUVTE7X8vxMzRw3fMB1nTx5sssRg5iYGGOKQWFhocaMGTPg7wBA8MHGTpw4odWrV/c4/f3timNau6Vabp9fff0NcTgklzNWa5Zm6eHcCf36/vr6eqO589atW9XU1NTliMHEiRN58hIIA4IPtnfl9PeD7cO0dsthtXsDV//wZYlxMVqzNLvP8Gtubu7S3PnYsWO6/fbbjaCbNm0afUeBQUDwAfp2+vt/f/VPGnLvLxVwOPt9jcS4WL3741zNGDtckuR2u7Vr1y4j6A4ePKh58+YZQTd37lw5nf3/HgADQ/ABnTzyp10qqWmQHN+uvM6X/LMunv1co777oiTJ1/SVTv3xUY1f/X+6fNbhkG7LiFdO6z9UXFys3bt3a9q0aUbQLVy4UC6Xa1D/ewB0x6+bwGUNrR7tPNrUJfQkafjtD+n0nx5XS+W/K3nmnQoqKIez+xieYFDaU/eN0n0XtGrVKuXl5SklJWWQqgdwrQg+4LLNe+t6/LnDGa+kGXeoqfh/KnHiXPlbGuQc1nMTZ1dCgmbc82Pdk8eUeCBSEXzAZdVnm7scWejwTfUOfVNVJtfEuTr3/15TwNOm5Jy7e7yG2xdQ9ZmWcJcKYAB4hAy4rNnt6/Hnrfv/ruGLvqu0u36qi18fVXxGppJnL+3jOt5wlQggBAg+4LIUV88bIL4LXys2aYRiEoZoxF3L1XZ4m/zu1j6u0/3+H4DIQfABl2VlpCjB2f2vRND/7UpwSOY8Jdw0Xec//mOP13A5Y5Q1OjlsNQIYOI4zAJc1tHq06OXiHu/zXasEZ4x2/lNR2Hp4Ahg4VnzAZSOTEpQ/KV3X2yXM4ZAKJ6cTekCEI/iATn5akCmX8/rm9bmcsVpekBniigCEGsEHdDJz3HCtWZqlxLj+/dW41Kszy2hXBiBycY4PuEJHo+lwT2cAYA4ebgF6caCuSRtLa/X3A3WKj4/XRf+3f1U65vEVTk7X8oJMVnpAFCH4gD6cOnVKM+ct0gv/8rGOnG1Vs9urFFecskYn6/7Z4ZvADiB82OoE+lBeXq6Fc2bo0XweWgGsgodbgD6Ul5dr0aJFZpcBIIQIPqAPBB9gPdzjA3rR2tqqUaNGqbGxkQGygIWw4gN6sWfPHs2cOZPQAyyG4AN6wTYnYE0EH9ALgg+wJu7xAT3w+/1KS0tTTU2NbrjhBrPLARBCrPiAHnz22WcaNWoUoQdYEMEH9IBtTsC6CD6gBwQfYF0EH9ADgg+wLoIPuMKpU6fU2tqqyZMnm10KgDAg+IArlJeXa+HChXI4HGaXAiAMCD7gCmxzAtZG8AFXIPgAa+MAO9AJjakB62PFB3Sye/du5eTkEHqAhRF8QCdscwLWR/ABnRB8gPVxjw+4zO/3a8SIEaqtrVV6errZ5QAIE1Z8wGWfffaZMjIyCD3A4gg+4DK2OQF7IPiAywg+wB4IPuAygg+wB4IPkFRXV0djasAmCD5A3672aEwNWB/BB4htTsBOCD5ABB9gJxxgh+3RmBqwF1Z8sD0aUwP2QvDB9tjmBOyF4IPtEXyAvXCPD7ZGY2rAfljxwdYOHjyo0aNHE3qAjRB8sDW2OQH7IfhgawQfYD8EH2yN4APsh+CDbdXV1amtrU2TJk0yuxQAg4jgg22Vl5dr4cKFNKYGbIbgg22xzQnYE8EH2yL4AHviADtsqaWlRRkZGTp37pwSEhLMLgfAIGLFB1vavXu3Zs2aRegBNkTwwZbY5gTsi+CDLRF8gH1xjw+209GY+osvvtDIkSPNLgfAIGPFB9vpaExN6AH2RPDBdtjmBOyN4IPtEHyAvRF8sJ0dO3Zo8eLFZpcBwCQEH2zl5MmTcrvduvXWW80uBYBJCD7YCo2pARB8sBXu7wEg+GArBB8ADrDDNmhMDUBixQcboTE1AIngg42wzQlAIvhgIzt27CD4AHCPD/bg8/k0YsQIffnll/ToBGyOFR9s4eDBgxozZgyhB4Dggz1wfw9AB4IPtkDwAehA8MEWCD4AHQg+WB6NqQF0RvDB8mhMDaAzgg+WxzYngM4IPlgeg2cBdMYBdlhaS0uLRo8ercbGRnp0ApDEig8WV1FRQWNqAF0QfLA07u8BuBLBB0sj+ABciXt8sKyOxtRHjx5VWlqa2eUAiBCs+GBZHY2pCT0AnRF8sCy2OQH0hOCDZTF4FkBPCD5YVnl5OQfXAXRD8MGSTpw4IY/Ho8zMTLNLARBhCD5YUsf9PRpTA7gSwQdL4sEWAL0h+GBJBB+A3nCAHZZDY2oAfWHFB8uhMTWAvhB8sBy2OQH0heCD5TB4FkBfuMcHS+loTH3s2DGNGDHC7HIARCBWfLCUAwcOaOzYsYQegF4RfLAU7u8BuBqCD5ZC8AG4GoIPlkLwAbgagg+WQWNqANeC4INl0JgawLUg+GAZDJ4FcC0IPlgGg2cBXAsOsMMSmpubdeONN+rcuXOKj483uxwAEYwVHyyhoqJCs2fPJvQAXBXBB0vgGAOAa0XwwRIIPgDXint8iHo0pgbQH6z4EPVoTA2gPwg+RD22OQH0B8GHqMfgWQD9QfAhqgWDQVZ8APqF4ENUO3HihLxeryZOnGh2KQCiBMGHqEZjagD9RfAhqrHNCaC/CD5ENYIPQH9xgB1Ri8bUAK4HKz5ELRpTA7geBB+iFuf3AFwPgg9Ri/t7AK4H9/gQlXw+n1JTU3X8+HF6dALoF1Z8iEqVlZW66aabCD0A/UbwISqxzQngehF8iEoEH4DrRfAh6tCYGsBAEHyIOjSmBjAQBB+iDo2pAQwEwYeow8F1AANB8CHqcH8PwEBwgB1R5cKFCxozZgyNqQFcN1Z8iCoVFRWaM2cOoQfguhF8iCpscwIYKIIPUYXgAzBQ3OND1KAxNYBQYMWHqEFjagChQPAhanB+D0AoEHyIGtzfAxAKBB+iAo2pAYQKwYeocPz4cfn9ft1yyy1mlwIgyhF8iAo0pgYQKgQfogLbnABCheBDVCD4AIQKB9gR8WhMDSCUWPEh4u3atYvG1ABChuBDxCsvL+fgOoCQIfgQ8bi/ByCUuMeHiOb1ejVixAidOHFCqampZpcDwAJY8SGiVVZWavz48YQegJAh+BDR2OYEEGpOswsAOmto9Wjz3jpVn21Ws9unys8dmj15iRpbPUpLSjC7PAAWwD0+RITKk016o7RWZTX1kiSPL2C8Fh/rkMPhUMHkdC3Pz9TMccNNqhKAFRB8MN3bFce0dku13D6/+vrT6HBILmes1izN0sO5EwatPgDWwlYnTHUp9A6r3Ru46nuDQand69faLYclifADcF14uAWmqTzZpLVbqq8p9Dpr9wa0dku1DtQ1hacwAJZG8ME0b5TWyu3zX9dn3T6/NpbWhrgiAHZA8MEUDa0eldXUd7und+Z/rVL9v76ozreez5f8sxq3vNrlfcGgVHKkXo2tnsEoF4CFEHwwxea9dT3+fNRDv9HF+mPynDwkSQoG/PrmUImGTivq9l6HpM37er4OAPSG4IMpqs82dzmy0CEmzqWh0wrVdqRckuQ++qkUG6eEcVO7vdftC6j6TEvYawVgLQQfTNHs9vX62pBJC9T2eYWCwaBaD25V0tRCORyOXq7jDVeJACyK4IMpUly9n6SJT58gR6xT7qP71F67W0Ond9/m/PY6ceEoD4CFEXwwRVZGihKcvf/xG3LrAjX+/XXFj5qouNQbe3yPyxmjrNHJ4SoRgEURfDDF/XPG9vl64qQF8jfX9/hQS4egpPtn930dALgSwQdTjExKUP6kdPVy604JYyZLklzjZ/T4usMhFU5Op3E1gH4j+GCanxZkyuWM7fE1hyOm4x96fN3ljNXygsxwlQbAwgg+mGbmuOFaszRLiXH9+2OYGBejNUuzNGPs8PAUBsDSmM4A0zGdAcBgIvgQEQ7UNWljaa1KjtTLoUuH0zu4nDEK6tI9veUFmaz0AAwIwYeI0tjq0eZ9dao+06Jmt1cprjhljU7W/bPH8iALgJAg+AAAtsLDLQAAWyH4AAC2QvABAGyF4AMA2ArBBwCwFYIPAGArBB8AwFYIPgCArRB8AABb+f9VQFjErCgQPQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "implicit_graph = make_implicit(graph)\n",
    "nx.draw(implicit_graph, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "187bd5af",
   "metadata": {},
   "source": [
    "## Problem 2: Contract from `implicit` to `user`\n",
    "\n",
    "The same basic idea applies, but we have a slightly different test criterion. This is something like $O(V\\langle E^2\\rangle)$, where $E$ is the number of edges a removed node is connected to. In practice, we expect $E$ will be very small relative to $V$, and so this will be effectively $O(V)$ in the real world."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "a1210789",
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "def make_user(graph):\n",
    "    graph = graph.copy()\n",
    "    for node in list(graph.nodes):\n",
    "        if not graph.nodes[node]['is_user']:\n",
    "            connected_nodes = set(node for _, node in graph.edges(node))\n",
    "            for n1, n2 in itertools.combinations(connected_nodes, 2):\n",
    "                graph.add_edge(n1, n2)\n",
    "            graph.remove_node(node)\n",
    "    return graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "9f1d4048",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAwk0lEQVR4nO3de1TU1eI28Ge4CIKChIgagvzkJkpRuBxQjyClhW9inshDKkd59aQ/zUu/8tUTeMODHo+WF8preElSUUQYSO2oeaXwqCnqIW5vAWFIgIKgDsww8/7RwVeDwQsz7Lk8n7VcS2Quz7RaPOzv3t+9JWq1Wg0iIiITYSY6ABERUUdi8RERkUlh8RERkUlh8RERkUlh8RERkUlh8RERkUlh8RERkUlh8RERkUlh8RERkUlh8RERkUmx0PUbVNU3IOVSGfJu3sEduRJ21hbw6WmHtwNc4NjFStdvT0RE9AiJrvbqzPm5Bp+dKsLpgkoAQINS9eB71hZmUAMI8XbCzGAPvNinmy4iEBERtaCT4kvKLkb84TzIlU1o69UlEsDawhwxo30wKbCvtmMQERG1oPVLnb+V3g+4r1A99rFqNXBf0YT4wz8AAMuPiIh0TquLW3J+rkH84bwnKr2H3VeoEH84D1fLarQZh4iIqAWtFt9np4ogVzY903PlyiZsPFWkzThEREQtaK34quobcLqgstU5vYabRSjf9T5KP3kbv6Ysh7KuCmUbo/Hw9KJaDZzMr0R1fYO2IhEREbWgteJLuVTW6r+rFA2oTIlDF//X0WfuHkDdhMrUFej8XwGQSCSPPFYCIOX71l+HiIhIG7RWfHk37zxyy0Kzxl/yoVap0OWFkZCYW8LW71U0lhfAxiuoxWPlShXyyuu0FYmIiKgFra3qvCNXtvrvTXdvw8LeCRLJbx3bqYc7JJ06w9rthVYffyU3H2lpxXBzc4ObmxscHBxajAyJiIieldaKz8669Zcyt3WASl7/4GtFddlvE3pmrT9ecbcW27dnoqSkBMXFxVCr1Q9K0M3NDX379n3ka2dnZxYjERE9Ma0Vn09PO1hZ3GxxubNTb2+oGu5BXpYLaxdf1F0+DECNxor/C6ueHo881trCDFFhr2D68Hcf/FtNTc2DEiwpKUFJSQnOnz//4Ov6+nq4urq2Wox9+/ZF7969YW5urq2PSUREBk5rO7dU1Tdg6KpvWp3nk5dew+1vEqFWNsLSyQ22Pn/A7VM74fi/5sHaxffB46wszPDtgtCn2sPz7t27Dwqx+c/DJVlVVYXevXu3Wopubm7o06cPOnXqpI3/BEREZAC0umXZu7sv4tgPFW1uU6YxiAR4zdcZmycN0lYcAEBDQwN+/vlnjcX4yy+/oHv37i0uoT78tY2NjVYzERGROFotvpyfaxC5LRv3FU9/E3tnS3MkvxuIF1y6aSvOE1Eqlfjll19aLcWSkhKUlpaiS5curY4Wm/9069axmYmI6NlpfZPqp9mrs1lnSzPEjO6vl3t1qlQq/Prrr62WYvPX5ubmbS7AcXJy4gIcIiI9IfR0BkCNzpYWBn06g1qtxu3bt1sU48N/l8vlDxbgtHZJtVevXjAz45nAREQdQWfn8V0tq8HGU0U4mV8JCX67Ob2ZtYUZmlQqNBZfxsHl0zHov5x0EUFv1NXVtbkA5/bt23j++ec1zjO6uLjA0tJS9McgIjIKOiu+ZtX1DUj5vgx55XW4I1fAztoSPr26IuJlF0yOfAuvvfYaZs+ercsIek8ul6O0tFTjPGN5eTmcnZ01FqOrqys6d+4s+mMQERkEnRdfW65cuYKwsDAUFRXB1tZWVAy9p1AocOPGDY3zjGVlZejWrVub84x2dnaiPwYRkV4QWnwAEBkZiRdffBF//etfRcYwaCqVCjdv3mxzAY6VlZXGUuzbty+ee+45LsAhIpMgvPgKCgowdOhQFBQUwMHBQWQUo6VWq1FdXa2xFEtKSqBQKDTuftO8NRwX4BCRMRBefAAwbdo0ODs7Iz4+XnQUk1VbW6uxFEtKSlBbW4s+ffponGd8/vnnYWGhtR3wiIh0Ri+Kr7S0FC+99BJyc3Ph7OwsOg614t69exoX4BQXF+PXX399sDVcayNHV1dXWFk9+VZ0RES6ohfFBwDz5s2DWq3G+vXrRUehZ9DY2IiysjKN84w3btyAo6OjxnlGNzc3dOnSRfTHICIToDfFV1FRAV9fX1y+fBmurq6i45CWNTU1oby8XOON/qWlpbCxsWlznrFbt25cgENE7aY3xQcAsbGxuHnzJj7//HPRUaiDqdVqVFZWalyAU1xcDAAaV6W6ubmhR48eLEYieiy9Kr6amhp4enri3Llz8Pb2Fh2H9IharX5wNqOmBTjNZzNq2lCcZzMSEaBnxQcAK1euRE5ODvbt2yc6ChmY+vr6BwtwWhs5VldX4/nnn9c4z8izGYlMg94V3927d+Hh4YEjR47A399fdBwyIg+fzdjaPGN5eTmcnJzaXIDDsxmJDJ/eFR8AJCQk4Ouvv0ZmZqboKGRCms9m1DTPWFpaCjs7uzbnGe3t7UV/DCJ6DL0svoaGBnh5eWHPnj0YOnSo6DhEAH7bGq6ioqLNecbmsxk1zTN2796dC3CIBNPL4gOAHTt2YOfOnTh16hR/UJBBUKvVuHXrlsZiLC4uRkNDQ4vLpw8XI89mJNI9vS0+pVKJgQMHYsOGDRg1apToOERa8fDZjK3NM9bU1MDFxUXjPCPPZiRqP70tPgA4cOAAVq1ahQsXLnDURybh/v37+PnnnzXOM1ZUVMDZ2Vnjjf6urq6wtrYW/TGI9JpeF59KpcKgQYMQGxuLP/7xj6LjEAnXfDZja6PFkpKSR85m1LQAp2vXrqI/BpFQel18AHDkyBF8+OGHuHr1Km8+JnoMlUr1YGs4TQtwrKysNJaim5sbz2Yko6f3xadWqzF8+HC8++67iIqKEh2HyKCp1WpUVVVpLMXi4mIolUqNq1J5NiMZA70vPgA4c+YMpkyZgry8PO6sQaRjzWczappnrKurQ58+fTTOM/bu3ZtnM5JeM4jiA4DXX38dY8eOxX//93+LjkJk0prPZtRUjJWVlejVq5fGecY+ffrwbEYSymCK79KlSwgPD0dhYSG3jSLSY42NjQ+2hmvtkmrz2YxtzTPa2tqK/hhkxAym+AAgIiICUqkU8+fPFx2FiJ5RU1MTfvnlF43zjCUlJbC1tW2zGHk2I7WHQRVfbm4uQkJCUFhYyD0RiYyUWq3Gr7/+2uaN/hKJRGMp9u3bF05OTixG0sigig8ApkyZAjc3Nyxbtkx0FCIS4OGzGTXNM967dw+urq4a5xl79erF26NMmMEV308//YRBgwYhLy8PTk5OouMQkR5qPptR043+D5/N2NqtGy4uLlxBbsQMrvgA4L333oOVlRU+/vhj0VGIyADJ5fI2F+D88ssv6NGjh8Z5RldXVy6yM2AGWXzl5eUYOHAgcnJy4OLiIjoOERkZpVKJGzduaFyA03w2Y1s3+nMdgv4yyOIDgIULF6KmpgabN28WHYWITMzDZzNqmme0tLTUWIp9+/aFo6MjF+AIYrDFd+vWLXh5eSE7OxseHh6i4xARPfDw2Yya5hkfPpuxtWLs2bOnSWwNV1XfgJRLZci7eQd35ErYWVvAp6cd3g5wgWMX3Wx0YLDFBwDLly9Hfn4+kpKSREchInoqd+7caXH/4sPF2Hw2o6Z5RhcXF4PeGi7n5xp8dqoIpwsqAQANStWD71lbmEENIMTbCTODPfBin25afW+DLr66ujp4eHjg+PHj8PPzEx2HiEhr7t+/j9LSUo3zjDdv3kTPnj01zjPq89mMSdnFiD+cB7myCW01kEQCWFuYI2a0DyYF9tXa+xt08QHA2rVrcfr0aaSlpYmOQkTUYRQKBcrKyjTOM5aVleG5557TeKO/qLMZfyu9H3BfoXr8g/+js6UZYkb311r5GXzxyeVyeHp6IiUlBVKpVHQcIiK90NTUhJs3b7Y5z9i5c+c25xkdHBy0ugAn5+caRG7Lxn1F01M/t7OlOZLfDcQLLt3ancPgiw8Atm3bhuTkZBw/flx0FCIig9B8NqOmVaklJSVoamrSuC1c89mMT1OM7+6+iGM/VLR5eVMTiQR4zdcZmycNevon//61jKH4FAoFfH19sXnzZrzyyiui4xARGYXmreE0zTM2n82oaQHOw2czVtU3YOiqbx5ZxFK+cx4s7Hqg+7i/PijQ2yd3QHW/Do6j57TIY2Vhhm8XhLZ7tadRFB8A7N27F+vXr8d3333He2OIiDrA3bt3NS7AKS4uRlVVFXr37g03NzdIfEeh1H4gmvD/90hVKeQo3z4HjmFzYO06EGpVE25sjEb38P8Da9eBLd7P2sIM74/0wvTh/dqV23DXwv7On/70J6xcuRIZGRkIDw8XHYeIyOjZ2tqif//+6N+/f6vff/hsxrXZt9BU9+jG4GaW1rAdOAL38rNg7ToQ8p8uA+aWsOozoNXXkytVyCuva3duo7k70szMDPHx8YiNjYVK9eSrhYiISDc6deqEfv36ITQ0FE7Pu7X6GBuvINwrzIZarUb9tRPoMmBEm1ft7sgV7c5lNMUHAG+88QZsbW2RnJwsOgoRET3Ezrr1C4ydnPpCYm4B+U/f437Redj6hT7mdSzbncWoik8ikSA+Ph6LFy+GQtH+3wqIiEg7fHrawcqi9cqx8QxC9dFP0cm5Hywdemt8DWsLM/j0av+9h0ZVfAAQGhoKNzc37Ny5U3QUIiL6j4gAzSfpdPYKQtOdStgObHu0pwYQ8XL7T+QxuuIDgPj4eMTFxUEul4uOQkREALp3scJQ926AuuUaDKvnvQEA1m4vaHy+RAKM8HbSysbVRll8UqkUAQEB2LRpk+goREQE4Mcff8S3iUthhpbFJ5GYNf9F4/OtLcwxM0Q7J/EYZfEBv53c8Pe//x11de1f+kpERM/uzJkzGDJkCN57Zwzi3nwRnS2frnp+26vTRyvblQFGdAN7ayZNmgRvb28sWrRIdBQiIpO0Y8cOLFiwAElJSRg1ahQAns6gU0VFRQgMDER+fj4cHR1FxyEiMhlNTU1YuHAh0tLSkJGRAR8fn0e+f7WsBhtPFeFkfiUk+O3m9GbN5/GN8HbCzBAPrY30mhl18QHAjBkzYG9vj1WrVomOQkRkEurq6jBhwgTU19cjJSWlzYFHdX0DUr4vQ155He7IFbCztoRPr66IeJknsD+zGzdu4IUXXsC1a9fQu7fm+0OIiKj9iouLMWbMGAQFBeHTTz9Fp06dREdqwWgXtzR7/vnnER0djfj4eNFRiIiMWlZWFoKCgjB16lRs2bJFL0sPMIERHwBUVVXB29sbFy9ehLu7u+g4RERGZ/fu3fjggw+wa9cuhIWFiY7TJpMoPgBYsmQJSkpKuKMLEZEWqVQqxMbGIjk5GTKZDAMGtH6ygj4xmeKrra2Fp6cnTp06BV9fX9FxiIgMXn19PaKiolBdXY3U1FR0795ddKQnYvRzfM3s7e0xf/58LF68WHQUIiKDV1paimHDhsHBwQHHjh0zmNIDTKj4AGDWrFn47rvvcPHiRdFRiIgMVnZ2NoKCgjBp0iQkJibCyko3tx3oislc6my2adMmpKen4+jRo6KjEBEZnL1792Lu3LlITEzEmDFjRMd5JiZXfI2NjfDx8cGOHTsQHBwsOg4RkUFQqVRYunQpdu/eDZlMBj8/P9GRnpnJFR/w27LbLVu24OzZs20ecU9ERMDdu3cxefJklJeX49ChQ+jRo4foSO1iUnN8zSZMmIDbt2/jyJEjoqMQEem1GzduYPjw4bCxscGJEycMvvQAEy0+c3Nz/O1vf0NMTAxUqpZnQxEREXDx4kVIpVK8/fbb2LVrF6ytrUVH0gqTLD4AePPNN2FhYYGDBw+KjkJEpHf279+PsLAwJCQkYOHChUY1LWSSc3zN/vnPf2LOnDm4fv06LCwsRMchIhJOrVZj+fLlSExMRHp6Ovz9/UVH0jqTHfEBwMiRI9GzZ0/s3r1bdBQiIuHu37+PCRMm4PDhwzh//rxRlh5g4sUnkUgQHx+PpUuXoqGhQXQcIiJhysvLERwcDIlEgpMnT6Jnz56iI+mMSRcfAAwdOhR+fn7YunWr6ChEREJcvnwZUqkU4eHh+PLLL9G5c2fRkXTKpOf4ml25cgVhYWEoKiqCra2t6DhERB0mNTUV06dPx6ZNmxARESE6Tocw+REfAPj7+yM4OBgbNmwQHYWIqEOo1WqsWLECc+fOxdGjR02m9ACO+B4oKCjA0KFDUVBQAAcHB9FxiIh0Ri6XY9q0acjPz0d6ejp69+4tOlKH4ojvP7y8vDB27FisWbNGdBQiIp2pqKjAiBEj0NjYiNOnT5tc6QEc8T2itLQUL730EnJzc+Hs7Cw6DhGRVuXk5CA8PBzR0dFYvHgxzMxMc+zD4vudefPmQa1WY/369aKjEBFpjUwmw9SpU5GQkIDIyEjRcYRi8f1ORUUFfH19cfnyZbi6uoqOQ0TULmq1GqtXr8b69etx6NAhDB48WHQk4Vh8rYiJiUFFRQU+//xz0VGIiJ5ZQ0MDpk+fjqtXr0Imk8HFxUV0JL3A4mvF7du34eXlhXPnzsHb21t0HCKip1ZZWYlx48bB2dkZX3zxBe9Rfohpzmw+hoODA/7nf/4HS5YsER2FiOipXb9+HYMHD0ZwcDAOHDjA0vsdjvg0uHv3Ljw8PHDkyBGj3aiViIzPV199hejoaHzyySeYNGmS6Dh6icXXhoSEBHz99dfIzMwUHYWIqE1qtRpr167FmjVrcPDgQQQFBYmOpLdYfG1oaGiAl5cX9uzZg6FDh4qOQ0TUqsbGRsycORMXLlyATCaDm5ub6Eh6jXN8bbCyssLSpUvx0Ucfgb8fEJE+qqqqwsiRI1FZWYmsrCyW3hNg8T1GVFQUKioqcOzYMdFRiIgekZubC6lUisDAQKSmpqJLly6iIxkEFt9jWFhYYPny5Rz1EZFeOXr0KEJCQrBo0SKsWrUK5ubmoiMZDBbfE3jrrbegUqlw6NAh0VGIyMSp1WokJCQgOjoaqampmDJliuhIBoeLW57Q4cOHMX/+fFy9epW/WRGREAqFArNnz8a5c+eQkZEBd3d30ZEMEkd8TygsLAwODg7Ys2eP6ChEZIJu3bqF119/HT///DO+/fZbll47sPiekEQiwYoVK7BkyRI0NjaKjkNEJiQ/Px+BgYHw9/eHTCaDnZ2d6EgGjcX3FIYPHw4vLy8kJiaKjkJEJuL48eMYPnw4FixYgI8//phTLVrAOb6ndOnSJYSHh6OwsBA2Njai4xCREdu0aROWLVuG5ORkBAcHi45jNFh8zyAiIgJSqRTz588XHYWIjJBSqcS8efNw4sQJZGZmol+/fqIjGRUW3zPIzc1FSEgICgsLYW9vLzoOERmRmpoajB8/HmZmZkhOTubPGB3gHN8z8PX1xejRo/HJJ5+IjkJERqSoqAiBgYHo378/MjMzWXo6whHfM/rpp58waNAg5OXlwcnJSXQcIjJwJ0+eRGRkJJYtW4YZM2aIjmPUWHzt8N5778HKygoff/yx6ChEZMC2bduG2NhY7N27F6GhoaLjGD0WXzuUl5djwIABuHr1KlxcXETHISIDo1QqMX/+fBw+fBgZGRnw8vISHckksPjaacGCBaitrcXmzZtFRyEiA1JbW4t33nkHjY2NOHDgABwcHERHMhksvnaqrq6Gt7c3srOz4eHhIToOERmAH3/8EWPGjEFwcDDWr18PS0tL0ZFMCld1tpOjoyPmzp2LpUuXio5CRAbgzJkzGDJkCGbOnImNGzey9ATgiE8L6urq4OHhgePHj8PPz090HCLSUzt27MCCBQuQlJSEUaNGiY5jslh8WrJ27VqcPn0aaWlpoqMQkZ5pamrCwoULkZaWhoyMDPj4+IiOZNJYfFoil8vh6emJlJQUSKVS0XGISE/U1dVhwoQJqK+vR0pKChwdHUVHMnmc49MSa2trLF68GDExMaKjEJGeKC4uxpAhQ9CrVy98/fXXLD09weLToilTpqCkpAQnTpwQHYWIBMvKykJQUBCmTp2KLVu2oFOnTqIj0X/wUqeW7d27F+vXr8d3330HiUQiOg4RCbB792588MEH2LVrF8LCwkTHod/hiE/L/vSnP+HevXvIyMgQHYWIOphKpcJf//pXLF26FCdPnmTp6SmO+HRAJpMhNjYWV65cgZkZf7cgMgX19fWIiopCdXU1UlNT0b17d9GRSAP+VNaBMWPGwMbGBsnJyaKjEFEHKC0txbBhw+Dg4IBjx46x9PQci08HJBIJVqxYgcWLF0OhUIiOQ0Q6lJ2djaCgIEyaNAmJiYmwsrISHYkeg8WnI6GhoXBzc8POnTtFRyEiHdm7dy/Cw8OxZcsWfPjhh1zQZiA4x6dD58+fR0REBAoLC2FtbS06DhFpiUqlwpIlS5CUlASZTMatCg0MR3w6JJVKERAQgE2bNomOQkRacvfuXYwfPx7ffPMNzp8/z9IzQBzx6di1a9fw6quvoqioCF27dhUdh4ja4caNGwgPD8eAAQOwdetWXskxUBzx6Zifnx9GjhyJdevWiY5CRO1w8eJFSKVSvP3229i1axdLz4BxxNcBioqKEBgYiPz8fO7VR2SA9u/fj1mzZmHbtm148803RcehdmLxdZAZM2bA3t4eq1atEh2FiJ6QWq1GXFwctm/fjvT0dPj7+4uORFrA4usgZWVleOGFF/Dvf/8bvXr1Eh2HiB7j/v37iI6ORnFxMdLS0tCzZ0/RkUhLOMfXQVxcXBAdHY34+HjRUYjoMcrLyxEcHAwzMzOcPHmSpWdkOOLrQJWVlfDx8cHFixfh7u4uOg4RteLy5csYO3Ys3n33XcTExPCmdCPE4utgS5YsQUlJCXd0IdJDqampmD59OjZt2oSIiAjRcUhHWHwdrLa2Fp6enjh16hR8fX1FxyEi/LaIZcWKFdi8eTPS0tIQEBAgOhLpEItPgNWrV+P8+fNISUkRHYXI5MnlckybNg35+flIT09H7969RUciHePiFgFmzZqF7777DhcvXhQdhcikVVRUYMSIEWhsbMTp06dZeiaCxSeAjY0NYmNjERsbKzoKkcnKycmBVCrFa6+9hn379sHGxkZ0JOogvNQpSGNjI3x8fLBjxw4EBweLjkNkUmQyGaZOnYqEhARERkaKjkMdjMUn0O7du7FlyxacPXuWS6aJOoBarcbq1auxfv16HDp0CIMHDxYdiQTgpU6BJkyYgNu3b+PIkSOioxAZvYaGBkRHR2Pfvn04f/48S8+EsfgEMjc3x/LlyxETEwOVSiU6DpHRqqysxCuvvIK6ujqcPXsWLi4uoiORQCw+wcaNGwdzc3McPHhQdBQio3T9+nUMHjwYISEhOHDgAGxtbUVHIsE4x6cH/vnPf2LOnDm4fv06LCwsRMchMhpfffUVoqOjsXbtWkycOFF0HNITHPHpgZEjR6Jnz57YvXu36ChERkGtVuOTTz7BX/7yF6Snp7P06BEc8emJrKwsTJgwAQUFBbCyshIdh8hgNTY2YubMmbhw4QJkMhnc3NxERyI9wxGfnhg6dCj8/PywdetW0VGIDFZVVRVGjhyJyspKZGVlsfSoVRzx6ZErV64gLCwMRUVFnIAnekq5ubkYM2YMIiIisGLFCpibm4uORHqKIz494u/vj+DgYGzYsEF0FCKDcvToUYSEhGDx4sVYtWoVS4/axBGfnikoKMDQoUNRUFAABwcH0XGI9JparUZCQgJWrlyJAwcOYNiwYaIjkQFg8emhadOmwdnZGfHx8aKjEOkthUKB2bNn49y5c8jIyIC7u7voSGQgWHx6qLS0FC+99BJyc3Ph7OwsOg6R3rl16xbefvttWFtbY+/evbCzsxMdiQwI5/j0kKurKyZNmoSVK1eKjkKkd/Lz8xEYGAh/f3/IZDKWHj01jvj0VEVFBXx9fXH58mW4urqKjkOkF44fP46JEydixYoVmDp1qug4ZKBYfHosJiYGFRUV+Pzzz0VHIRJu48aNiIuLQ3JyMs+wpHZh8emx27dvw8vLC+fOnYO3t7foOERCKJVKzJs3DydOnEBmZib69esnOhIZOBafnlu5ciVycnKwb98+0VGIOlxNTQ3Gjx8PMzMzJCcnw97eXnQkMgJc3KLn5syZg9OnT+PKlSuioxB1qKKiIgQGBqJ///7IzMxk6ZHWsPj0nK2tLT766CPExsaKjkLUYU6ePIlhw4bh/fffx/r163lcF2kVL3UagIaGBnh5eWHPnj0YOnSo6DhEOrV161YsWrQIe/fuRWhoqOg4ZIRYfAZix44d2LlzJ06dOgWJRCI6DpHWKZVKfPjhhzhy5AgyMjLg5eUlOhIZKV7qNBBRUVGoqKjAsWPHREch0rra2lqEh4fj+vXryM7OZumRTrH4DISFhQXi4uIQExMDDtLJmPz4448YMmQI3N3dceTIEW7OTjrH4jMgERERUCqVSEtLEx2FSCvOnDmDIUOGYObMmfjss89gaWkpOhKZAM7xGZjDhw9j/vz5uHr1Ks8cI4O2fft2LFy4EElJSRg1apToOGRCOOIzMGFhYXBwcMCePXtERyF6Jk1NTZg/fz5WrlyJM2fOsPSow3HEZ4DOnDmDKVOmIC8vD506dRIdh+iJ1dXVYcKECaivr0dKSgocHR1FRyITxBGfARo+fDi8vLyQmJgoOgrREysuLsaQIUPQq1cvfP311yw9EoYjPgN16dIlhIeHo7CwEDY2NqLjELUpKysLERERWLhwIebMmcN7UUkojvgMVEBAAIKCgvDZZ5+JjkLUpi+++ALjxo3D9u3bMXfuXJYeCccRnwHLzc1FSEgICgsLuYEv6R2VSoWYmBjs378fMpkMAwYMEB2JCACLz+BNmTIFbm5uWLZsmegoRA/U19cjKioK1dXVSE1NRffu3UVHInqAxWfgfvrpJwwaNAh5eXlwcnISHYcIpaWlCA8Px8svv4zNmzdz5THpHc7xGTh3d3dERkbi73//u+goRMjOzkZQUBCioqKQmJjI0iO9xBGfESgvL8fAgQORk5MDFxcX0XHIRO3Zswdz587Fjh078MYbb4iOQ6QRi89ILFiwALW1tdi8ebPoKGRiVCoVlixZgqSkJMhkMvj5+YmORNQmFp+RqK6uhre3N7Kzs+Hh4SE6DpmIu3fvYvLkySgvL8ehQ4fQo0cP0ZGIHotzfEbC0dERc+fOxdKlS0VHIRNx48YNDB8+HDY2Njhx4gRLjwwGi8+IzJs3D8eOHcO1a9dERyEjd/HiRUilUowfPx67du2CtbW16EhET4yXOo3M2rVrcfr0aZ7ZRzqzf/9+zJo1C9u2bcObb74pOg7RU2PxGRm5XA5PT0+kpKRAKpWKjkNGRK1WIy4uDomJiZDJZPD39xcdieiZsPiM0LZt25CcnIzjx4+LjkJG4v79+4iOjkZxcTHS0tLQs2dP0ZGInhnn+IzQlClTUFJSghMnToiOQkagvLwcwcHBMDMzw8mTJ1l6ZPBYfEbI0tISy5YtQ0xMDDigp/a4fPkypFIpxo4diy+//BKdO3cWHYmo3Vh8RioyMhL37t1DRkaG6ChkoFJTUzFq1Ch88skniImJ4XFCZDQ4x2fEZDIZYmNjceXKFZiZ8XccejJqtRorVqzA5s2bkZaWhoCAANGRiLSKPw2N2JgxY2BjY4Pk5GTRUchAyOVyREVFIS0tDefPn2fpkVFi8RkxiUSCFStWYPHixVAoFKLjkJ6rqKjAiBEjoFAocPr0afTu3Vt0JCKdYPEZudDQULi5uWHnzp2io5Aey8nJgVQqxWuvvYZ9+/bBxsZGdCQineEcnwk4f/48IiIiUFhYyK2lqIX09HRMmzYNCQkJiIyMFB2HSOc44jMBUqkUAQEB2LRpk+gopEfUajVWrVqFmTNn4quvvmLpkcngiM9EXLt2Da+++iqKiorQtWtX0XFIsIaGBkyfPh1Xr16FTCbjAcZkUjjiMxF+fn4YOXIk1q1bJzoKCVZZWYlXXnkFdXV1OHv2LEuPTA5HfCakqKgIgYGByM/Ph6Ojo+g4JMD169cxZswYTJw4EXFxcby/k0wSi8/ETJ8+Hd26dcOqVatER6EO9tVXXyE6Ohpr167FxIkTRcchEobFZ2LKysrw4osv4vr16+jVq5foONQB1Go11q5dizVr1uDgwYMICgoSHYlIKBafCfrggw/Q0NCATz/9VHQU0rHGxkbMnDkTFy5cgEwmg5ubm+hIRMKx+ExQZWUlfHx8cPHiRbi7u4uOQzpSVVWFt956C926dcOXX36JLl26iI5EpBc4s22CnJyc8N5772HZsmWio5CO5ObmQiqVIigoCIcOHWLpET2EIz4TVVtbC09PT5w6dQq+vr6i45AWHT16FH/+85+xevVqTJ48WXQcIr3D4jNhq1evxvnz55GSkiI6CmmBWq1GQkICVq5ciQMHDmDYsGGiIxHpJRafCbt37x48PT2Rnp6OQYMGiY5D7aBQKDB79mycO3cOGRkZnLslagPn+EyYjY0NYmNjERsbKzoKtcOtW7fw+uuvo6ysDN9++y1Lj+gxWHwmburUqSgoKMDp06dFR6FnkJ+fj8DAQLz00ktIT0+HnZ2d6EhEeo/FZ+I6deqEpUuXIiYmBrzqbViOHTuG4cOHY8GCBVizZg3Mzc1FRyIyCCw+wsSJE3Hr1i0cOXJEdBR6Qhs3bkRUVBT279+PqVOnio5DZFC4uIUAAKmpqfjb3/6GixcvcuNiPaZUKjFv3jycOHECmZmZ6Nevn+hIRAaHP+EIADBu3DiYmZnh4MGDoqOQBjU1NRg9ejSKioqQnZ3N0iN6Riw+AgBIJBKsWLECixYtglKpFB2Hfqf5SClfX19kZmbC3t5edCQig8XiowdGjhyJnj17Yvfu3aKj0ENOnjyJYcOG4f3338e6detgYWEhOhKRQeMcHz0iKysLEyZMQEFBAaysrETHMXlbt27FokWLsHfvXoSGhoqOQ2QUOOKjRwwdOhR+fn7YunWr6CgmrXkRy8cff4yzZ8+y9Ii0iCM+auHKlSsICwtDUVERbG1tRccxObW1tXjnnXegUCiwf/9+ODg4iI5EZFQ44qMW/P39ERwcjA0bNoiOYnJ+/PFHDBkyBO7u7jh8+DBLj0gHOOKjVuXn52PYsGEoKCjgD98OcubMGYwfPx6LFi3CrFmzRMchMloc8VGrvL29ER4ejjVr1oiOYhK2b9+OiIgIfPHFFyw9Ih3jiI80Kikpwcsvv4zc3Fw4OzuLjmOUmpqasHDhQqSlpSEjIwM+Pj6iIxEZPRYftWnu3LmQSCRYt26d6ChGp66uDhMmTEB9fT1SUlLg6OgoOhKRSWDxUZsqKirg6+uLy5cvw9XVVXQco1FcXIwxY8YgKCgIn332GSwtLUVHIjIZnOOjNjk7O2PGjBmIi4sTHcVoZGVlISgoCNOmTcOWLVtYekQdjCM+eqzbt2/Dy8sL586dg7e3t+g4Bu2LL77Ahx9+iF27diEsLEx0HCKTxOKjJ7Jy5Urk5ORg3759oqMYJJVKhZiYGOzfvx8ymQwDBgwQHYnIZLH46IncvXsXHh4eOHLkCPz9/UXHMSj19fWIiopCdXU1UlNT0b17d9GRiEwa5/joidja2uKjjz5CbGys6CgGpbS0FMOGDYODgwOOHz/O0iPSAyw+emLvvvsurl27hqysLNFRDEJ2djaCgoIQFRWFxMREdOrUSXQkIgIvddJT2r59O3bt2oVTp05BIpGIjqO39uzZg7lz52LHjh144403RMchooew+OipKJVKDBgwAAkJCRg1apToOHpHpVJhyZIlSEpKgkwmg5+fn+hIRPQ7LD56avv378fq1avxr3/9i6O+h9y9exeTJ09GeXk5Dh06hB49eoiORESt4BwfPbWIiAgolUqkpaWJjqI3bty4geHDh8PW1hbffPMNS49Ij7H46KmZmZkhPj4esbGxaGpqEh1HuAsXLkAqlWL8+PHYuXMnrKysREciojaw+OiZhIWFwcHBAXv27BEdRaj9+/dj9OjR+PTTT7FgwQJe+iUyAJzjo2d25swZTJkyBXl5eSa3VF+tViMuLg6JiYmQyWS8qZ/IgHDER89s+PDh8PLyQmJiougoHer+/ft45513cOTIEfzrX/9i6REZGI74qF0uXbqE8PBwFBYWwsbGRnQcnSsvL8fYsWPh6emJxMREWFtbi45ERE+JIz5ql4CAgAdnyhm777//HlKpFGPHjkVSUhJLj8hAccRH7Zabm4uQkBAUFhbC3t5edBydOHjwIGbMmIFNmzYhIiJCdBwiagcWH2nF5MmT0bdvXyxbtkx0FK1Sq9VYsWIFNm/ejLS0NAQEBIiORETtxOIjrfjpp58waNAg5OXlwcnJSXQcrZDL5Zg2bRry8/ORnp6O3r17i45ERFrAOT7SCnd3d0RGRmLVqlWio2hFRUUFRowYAYVCgdOnT7P0iIwIR3ykNeXl5Rg4cCBycnLg4uIiOs4zy8nJwdixYzFlyhQsWbKEN6UTGRkWH2nVggULUFtbi82bN4uO8kzS09Mxbdo0JCQkIDIyUnQcItIBFh9pVXV1Nby9vZGdnQ0PDw/RcZ6YWq3GP/7xD2zYsAGHDh3C4MGDRUciIh1h8ZHWLV++HPn5+UhKShId5Yk0NDRg+vTpuHr1KmQymUFfpiWix2PxkdbV1dXBw8MDx48f1/uDWCsrKzFu3Dg4Ozvjiy++gK2trehIRKRjXNVJWte1a1csXLgQixYtEh2lTdevX8fgwYMREhKCAwcOsPSITARHfKQTcrkcnp6eSElJgVQqFR2nhczMTERHR2PdunWYOHGi6DhE1IFYfKQzW7duxf79+3H8+HHRUR5Qq9VYu3Yt1qxZg4MHDyIoKEh0JCLqYCw+0hmFQoH+/ftjy5YteOWVV0THQWNjI2bOnIkLFy5AJpPBzc1NdCQiEoBzfKQzlpaWiIuLQ0xMDET/flVVVYWRI0eisrISWVlZLD0iE8biI52KjIzEvXv3kJmZKSxDbm4upFIpgoKCcOjQIXTp0kVYFiISj5c6SedkMhliY2Nx5coVmJl17O9aR48exZ///GesXr0akydP7tD3JiL9xBEf6dyYMWNgY2OD5OTkDntPtVqNDRs2IDo6GqmpqSw9InqAIz7qEN988w2mT5+O3NxcWFpa6vS9FAoFZs+ejaysLMhkMri7u+v0/YjIsHDERx0iNDQUbm5u2Llzp07f59atW3j99ddRVlaGrKwslh4RtcDiow4THx+PuLg4yOVynbx+fn4+AgMD8dJLLyE9PR12dnY6eR8iMmwsPuowUqkUAQEB2LRpk9Zf+9ixY/jDH/6ABQsWYM2aNTA3N9f6exCRceAcH3Woa9eu4dVXX0VRURG6du2qldfcuHEj4uLikJycjODgYK28JhEZLxYfdbiJEyfCx8en3ZtYK5VKzJs3D9988w0yMjLQr18/LSUkImPG4qMOV1RUhMDAQOTn58PR0fGZXqOmpgbjx4+HmZkZkpOTYW9vr+WURGSsOMdHHc7DwwNvvfUW/vGPfzzT8wsLCxEYGAhfX19kZmay9IjoqXDER0KUlZXhxRdfxPXr12HZ9TmkXCpD3s07uCNXws7aAj497fB2gAscu1g98ryTJ08iMjIScXFxmD59uqD0RGTIWHwkTPSHS/ED+uB2594AgAal6sH3rC3MoAYQ4u2EmcEeeLFPN2zduhWLFi3C3r17ERoaKig1ERk6Fh8JkZRdjL999QPuNyohaWP/TokEsLIwg9fdfyM/cxsyMzPh6enZgUmJyNiw+KjDJWUXI/7wD7iv+G2Ep6yrRnXmJ2i4WQiLLo5wGDkDnfu++MhzJE0KLHzdG9ND+4uITERGhItbqEPl/FyD+MN5D0oPAGrOJkHSqTP6zP4Sz4XNQfVXa1s8T21uiXWnSnC1rKYD0xKRMWLxUYf67FQR5MqmR/6tsbwQXQaGQmJhCWuX/lCrlGi6V9viuXJlEzaeKuqoqERkpFh81GGq6htwuqASv7+4rmq4B4mVDQBArVRAJa+HxKzllmNqNXAyvxLV9Q0dEZeIjBSLjzpMyqWyNr+varyP2ye3w9KxD8ysWz8lXQIg5fu2X4eIqC0WogOQ6ci7eeeRWxZ+ryxhEtSKBnQNGAO1WgWJpOXvZXKlCnnldbqMSURGjiM+6jB35Mo2v9/n/f3o9b8T0FCWi9pze9t4HYW2oxGRCWHxUYexs277AoPEzByderjDdmAoGm8WtvE6uj3BnYiMG4uPOoxPTztYWbT+v1z91WNoul8HVcM93C/6Fyx7tH5yurWFGXx6aec4IyIyTSw+6jARAS4av9d0pwq/bPkLbmyaCjMbO9hLI1p9nBpAxMuaX4eI6HG4uIU6TPcuVgj2csKxHypa3NJgP+wddO7r3+bzJRJghLdTi42riYieBkd81KFmhXjA2qLlPXpPwtrCHDNDPLSciIhMDYuPOtSLfbohZrQPOls+3f96nS3NEDPaBy+4dNNNMCIyGdykmoT4baPqPMiVTS0uez5MIvltpBcz2geTAvt2WD4iMl4sPhLmalkNNp4qwsn8Skjw283pzZrP4xvh7YSZIR4c6RGR1rD4SLjq+gakfF+GvPI63JErYGdtCZ9eXRHxcssT2ImI2ovFR0REJoWLW4iIyKSw+IiIyKSw+IiIyKSw+IiIyKSw+IiIyKSw+IiIyKSw+IiIyKSw+IiIyKSw+IiIyKT8P6CZ3F89h+lmAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "user_graph = make_user(implicit_graph)\n",
    "nx.draw(user_graph, with_labels=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "2bd72ce9",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAb4AAAEuCAYAAADx63eqAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAzIUlEQVR4nO3deViVZf4G8PtwQEARwQVBcWEHRUBQAxRZjmaao/NzKZ0sp8VmWmYqS7DLrunKyQowyx0zdVLKUjNp0TJZVFRcQHEBRQEVFUU2AVnPOe/vD/MtEhQVeM5yf/6aYTnv3eZ9nvN+n+dVSJIkgYiIyEiYiA5ARETUnlh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVEzb+gLFVXXYkn4Jp69WoKJWDWsLU3jaW2NqgCO6WZm39eWJiIgaUbTVWZ2ZBeVYnnIOu3OuAwDq1Fr5examJpAAhHn0wMuhrvDtY9MWEYiIiO7QJsUXn3YeC7afRq1ag7u9ukIBWJgqMW+cJ2YE9m/tGERERHdo9Y86b5VeNmoabq3w1JUlKPlxEequnoWpVTfYjv4nLPv7AgAkCahp0GDB9mwAYPkREVGba9XhlsyCcizYflouPQAo3xsPRQdL9PnXl+g69t8o+emTO36vpkGLBdtP4/il8taMQ0REdIdWLb7lKedQq9Y0+lp94VlYeUdAYWoGC0cvSFo1NNU37vjdWrUGK1LOtWYcIiKiO7Ra8RVX1WF3zvU77ulp66qhMO8IAJDUDdDWVkFhorzj9yUJSD5zHSVVda0ViYiI6A6tVnxb0i/d9fva+hqUJa+FWbc+MLGwavJnFAC2ZNz9dYiIiB5Gqw23nL5a0WjLwp9dWjoDUkMdOgf8BZKkhUJxZ+fWqrU4XVjZWpGIiIju0Gorvopa9V2/3+eNTXB4binqLmXhRurGu7xOQ2tFIiIiukOrFZ+1xd0XjwoTJTrYOaGTdwTqr55t9ufMcPcCJSIiehitVnye9tYwN2365aqO/wpNTSW0ddWoOXcIZnZOTf6cQqvGd+uWwdvbG6+99hp++OEHVFRUtFZEIiKi1ju5pbiqDsOjk+64z3dpxXMwte6BhuILABSwcPJDtzGvwsSi0x2vYW5qgj1vheLCmZNITEzErl27cPDgQQwaNAijRo2CSqVCUFAQzM15xicRET2YVj2y7MUNR/Br9rVGWxourXgO3cb9G5b9/e4eRAGMGdATcTOGNPp6TU0N9u/fLxdhdnY2goKC5CL08/ODUnnn9ggiIqKmtGrxZRaUY9rqNNQ0/L6JvaXFZ2mmxDcvBsLH0eauP1deXo6UlBTs2rULiYmJKCoqQnh4OFQqFVQqFdzc3KBQKFrhr4aIiAxRqx9S/eezOltSfJZmJpg3zuuBzuq8fPkykpKS5CJUKBTyalClUsHBweEB/0qIiMgQGdTTGSRJQk5OjlyCKSkpcHBwkEswLCwMXbp0eejrEBGR/mqz5/Edv1SOFSnnkHzmOhS4tTn9NnNTBQAFwj164OUw13t+vPmgNBoNjh49KhdhWloaBg4cKBdhcHAwLCws2uTaRESkm9qs+G4rqarDloxLOF1YiYraBuxL2YWJoUMQOWVkuz+Bvba2Vh6USUxMxKlTpxAYGAiVSoVRo0Zh8ODBHJQhIjJwbV58f/bqq6/CxcUFb7zxRntetknl5eXYvXu3XISFhYUICwuTi9Dd3Z2DMkREBqbdi2/t2rVISkpCfHx8e162Ra5cuYKkpCS5CLVarVyCKpUKvXr1Eh2RiIgeUrsXX2ZmJqZPn46srKz2vOx9kyQJZ8+elUswOTkZdnZ2chGGhYXBxsZGdEwiIrpP7V58DQ0NsLGxwbVr12Bl1fTjiXSRRqPBsWPH5CLcv38/vLy85NXg8OHDOShDRKQH2r34AGDYsGFYtGgRRowY0d6XbjV1dXU4cOCAfKLMiRMn8Mgjj8hFGBAQwEEZIiIdJKT4XnrpJXh5eeHf//53e1+6zVRUVMiDMrt27cLly5flQRmVSgVPT08OyhAR6QAhxbd69Wqkpqbiiy++aO9Lt5urV682OlFGrVbLJahSqeDo6Cg6IhGRURJSfBkZGZg5cyZOnDjR3pcWQpIk5ObmyiWYnJyM7t27yyUYHh4OW1tb0TGJiIyCkOKrq6uDra0tiouL0bFjx/a+vHBarbbRoMy+ffvg6ekpF+GIESNgaWkpOiYRkUESUnwAEBAQgOXLlyMwMFDE5XVKXV0d0tLS5CLMzMzEsGHD5CIcMmQITE3v/oR7IiJqGWHFN2vWLPj5+eGVV14RcXmdVlFRgT179shFePHiRYSGhsp7CL28vDgoQ0T0gIQVX1xcHA4fPow1a9aIuLxeuXbtmnyizK5du1BfX4+IiAh5Rdi3b1/REYmI9Iaw4jt8+DBmzZqFY8eOibi83pIkCXl5efJqMCkpCba2tvJqMDw8HF27dhUdk4hIZwkrvtraWnTt2hWlpaU88eQhaLVaHD9+XF4N7tu3D25ubnIRjhgxwigHiIiImiOs+ADAz88Pq1evxtChQ0VFMDj19fU4ePCgXITHjh3DkCFD5BNlhg4dykEZIjJqQovvueeew7Bhw/DPf/5TVASDV1lZib1798p7CC9cuICQkBC5CAcOHMhBGSIyKkKLb/ny5cjMzMRnn30mKoLRKSoqQnJyslyE1dXVjU6U6devn+iIRERtSmjxHThwAK+++irS09NFRTB6fx6Usba2lleD4eHh6N69u+iIREStSmjxVVdXo3v37igvL0eHDh1ExaDfaLVanDx5Ul4N7t27F66urvJqMCQkBJ06dRIdk4jooQgtPgAYNGgQvvjiC/j7+4uMQU2or6/HoUOH5BVhRkYGAgIC5InRoUOHwszMTHRMIqL7Irz4Zs6ciREjRmDWrFkiY1ALVFVVYe/evXIR5uXlISQkRC5Cb29vDsoQkc4TXnxLlixBdnY2Vq5cKTIGPYDr168jOTlZLsLKykpERETI9wj79+8vOiIR0R2EF19qaipmz56NQ4cOiYxBreD8+fNyCSYmJsLKyqrRiTI9evQQHZGISHzxVVVVwc7ODjdu3OD9IgMiSRJOnjwpl+CePXvg5OQkrwZDQkJgZWUlOiYRGSHhxQcAXl5e+Prrr+Hr6ys6CrWRhoYGHD58WD5RJj09HYMHD5aL8JFHHuEbHyJqFzpRfDNmzIBKpcKzzz4rOgq1k5s3byI1NVUuwnPnzsmDMiqVCoMGDYKJiYnomERkgHSi+D755BPk5uZi2bJloqOQICUlJY1OlLlx40ajRy85OzuLjkhEBkInim/37t2YO3cuDhw4IDoK6YiLFy/Kq8HExER07NhRLsGIiAjY2dmJjkhEekoniq+iogIODg64ceMGnxxAd5AkCVlZWXIJ7tmzB/369ZOLcOTIkejcubPomESkJ3Si+ADA3d0dW7duhbe3t+gopOPUajWOHDkiF+Hhw4fh5+cnF2FgYCCPwCOiZulM8U2fPh1jx47FM888IzoK6Znq6mp5UCYxMRE5OTkYPny4vIfQx8eHgzJEJNOZ4ouNjcWlS5ewePFi0VFIz5WWljY6Uaa0tBTh4eFyETo7O/NoNSIjpjPFl5SUhHfffRd79+4VHYUMTEFBgVyCu3btgrm5uVyCERER6Nmzp+iIRNSOdKb4ysvL0adPH5SXl0OpVIqOQwZKkiRkZ2fLRZiSkoI+ffrIRThy5EhYW1uLjklEbUhnig8AXFxc8OOPP8LLy0t0FDISarUa6enp8mrw0KFD8PHxkU+UCQwMhLm5ueiYRNSKdKr4nnjiCUycOBFPPfWU6ChkpGpqarBv3z65CE+fPo3g4GC5CP38/DgoQ6TndKr4PvroIxQVFWHRokWioxABAMrKypCSkiJvnbh+/XqjE2VcXV05KEOkZ3Sq+H799VcsWLAAKSkpoqMQNenSpUtISkqSi1CpVMqrQZVKBXt7e9ERiegedKr4SkpK4OzsjLKyMn6cRDpPkiScOXNGLsGUlBT07t1bLsHQ0FB06dJFdEwi+hOdKj4A6N+/P3799Ve4ubmJjkJ0XzQaDTIyMuQiTEtLw6BBg+QiDA4O5qAMkQ7QueKbPHkypk6dimnTpomOQvRQampqsH//fnnrRFZWFoKCguStE35+fty6QySAzhXfggULUF5ejtjYWNFRiFpVeXk5UlJS5CK8du0awsLC5HuEbm5uHJQhagc6V3w///wzYmNjkZiYKDoKUZu6fPkykpKS5CIEIK8GVSoVHBwcBCckMkw6V3xFRUXw8PBAaWkp3/2S0ZAkCTk5OXIJJicnw97eXi7BsLAwDsoQtRKdKz4A6NOnD3bv3s2nbpPR0mg0OHr0qFyEBw4cwIABA+QiDA4OhoWFheiYRHpJJ4tv4sSJmDFjBqZOnSo6CpFOqK2txYEDB+QTZU6dOoXAwEB5YtTf35+DMkQtpJPFN3/+fNTU1ODDDz8UHYVIJ924cQO7d++Wi7CwsBBhYWFyEXp4ePBWAVEzdLL4fvrpJyxevBg7d+4UHYVILxQWFjY6UUar1colqFKp0Lt3b9ERiXSGThZfYWEhvL29UVxczHetRPdJkiScO3dOXg0mJyfDzs5OLsGwsDDY2tqKjkkkjE4WHwD06tULBw4cQL9+/URHIdJrWq0Wx44dk1eD+/fvh5eXl1yEw4cPh6WlpeiYRO1GZ4tv/PjxeO655zBp0iTRUYgMSl1dHdLS0uQiPHHiBIYNGybvIQwICOCgDBk0nS2+d999FxqNBu+//77oKEQGraKiQh6USUxMxKVLlxAaGioXoaenJ285kEHR2eJLSEhAXFwcduzYIToKkVG5evWqfKLMrl270NDQ0OhEGUdHR9ERiR6KzhbfpUuX4O/vj2vXrvHdJpEgkiQhNzdXXg0mJSWhW7duchGGhYWha9euomMS3RedLT5JkmBvb4/09HS+wyTSEVqtFpmZmfJqcN++ffDw8JBXg8OHD0fHjh1FxyS6K50tPgAYO3Ys/vnPf2LixImioxBRE+rr65GWliYXYWZmJoYOHSoX4ZAhQ2Bqaio6JlEjOl1877zzDpRKJd577z3RUYioBSorK7Fnzx55YvTixYvyoIxKpcKAAQN464KE0+ni27p1K9auXYsff/xRdBQiegDXrl1DcnKyXIS1tbWNTpTp27ev6IhkhHS6+C5cuICgoCBcuXJFdBQiagV5eXlyCSYlJcHW1lYuwfDwcHTr1k10RDICOl18kiShe/fuOHnyJB/KSWRgtFotTpw4IRdhamoq3Nzc5CIMCQnhoAy1CZ0uPgB49NFH8dprr+Hxxx8XHYWI2lB9fT0OHjwob504evQohgwZIhfh0KFDYWZmJjomGQCdL763334blpaW+M9//iM6ChG1o6qqKuzZs0cuwvz8fIwcOVLeQzhw4EAOytAD0fni27x5M+Lj45GQkCA6ChEJVFRUhOTkZLkIb968iYiICHnrBA+0p5bS+eLLy8tDaGgoCgoKREchIh2Sn58vl2BiYiKsra3l1WB4eDi6d+8uOiLpKJ0vPkmS0LVrV5w5cwZ2dnai4xCRDtJqtTh58qRcgnv37oWzs7O8GgwJCUGnTp1ExyQdofPFBwAqlQpz5szBY489JjoKEemBhoYGHDp0SD5RJiMjA/7+/nIRDhs2jIMyRkwvim/OnDmwsbHBvHnzREchIj108+ZN7N27Vy7CvLw8hISEyBOj3t7eMDExER2T2oleFN/XX3+NzZs349tvvxUdhYgMQHFxcaMTZSoqKhqdKOPk5CQ6IrUhvSi+s2fPYvTo0Th//rzoKERkgC5cuCCvBhMTE2FlZSWXYEREBHr06CE6IrUivSg+rVYLW1tb5OXl8UgjImpTkiTh1KlTcgnu2bMHTk5OchGOHDkSVlZWomPSQ9CL4gOAsLAwzJs3D6NHjxYdhYiMSENDA44cOSIX4ZEjRzB48GC5CB955BF06NBBdEy6D3pTfLNnz4adnR3mzp0rOgoRGbGbN28iNTVV3jpx9uxZjBgxQt5DOGjQIA7K6Di9Kb4vv/wSCQkJ2LRpk+goRESykpKSRifKlJWVISIiQi5CZ2dn0RHpT/Sm+LKzszF+/Hjk5uaKjkJE1KyLFy/KJbhr1y5YWlrKJRgREcGDOHSA3hSfRqOBjY0NLl68CFtbW9FxiIjuSZIkZGVlySW4Z88e9O3bVy7CkSNHonPnzqJjGh29KT4ACAkJwXvvvYeIiAjRUYiI7ptarcaRI0fkIjx8+DB8fX3lE2UCAwM5KNMO9Kr4XnvtNfTp0wdvvfWW6ChERA+turoa+/btkydGc3JyEBwcLBehr68vB2XagF4V3/r167Fjxw5s3LhRdBQiolZXWlqKlJQUuQhLSkrkQRmVSgUXFxc+g7AV6FXxnTx5EpMmTUJOTo7oKEREba6goKDRo5fMzMzk1WBERATs7e1FR9RLelV8arUaXbp0QWFhIaytrUXHISJqN5Ik4fTp0/JqcPfu3XB0dJRXg6GhofxzsYX0qvgAICgoCB999BFCQ0NFRyEiEkatViM9PV1eDR48eBA+Pj5yEQYFBcHc3Fx0TJ2kd8X36quvwsXFBW+88YboKEREOqOmpgb79u2TizA7OxvBwcFyEfr5+UGpVIqOqRP0rvjWrVuHxMRExMfHi45CRKSzysrKkJKSIhdhUVERwsPD5T2Erq6uRjsoo3fFl5mZienTpyMrK0t0FCIivXH58uVGJ8oolcpGzyB0cHAQHbHd6F3xNTQ0wMbGBteuXeOjQYiIHoAkSThz5oxchMnJyejVq5e8GgwNDUWXLl3aJUtxVR22pF/C6asVqKhVw9rCFJ721pga4IhuVm1zj1Lvig8Ahg0bhkWLFmHEiBGioxAR6T2NRoOMjAx5NXjw4EEMHDhQ3joRFBQECwuLVr1mZkE5lqecw+6c6wCAOrVW/p6FqQkkAGEePfByqCt8+9i06rX1svheeukleHl54d///rfoKEREBqe2thb79++XizArKwtBQUHyx6KDBw9+qEGZ+LTzWLD9NGrVGtytgRQKwMJUiXnjPDEjsP8DX++O19XH4lu9ejVSU1PxxRdfiI5CRGTwysvLsXv3bnkP4dWrV+VBGZVKBXd39xYPytwqvWzUNGjv/cO/sTQzwbxxXq1WfnpZfBkZGZg5cyZOnDghOgoRkdG5cuUKkpKS5CIE0GhQplevXk3+XmZBOaatTkNNg+a+r2lppsQ3LwbCx9HmYaID0NPiq6+vh42NDYqLi9GxY0fRcYiIjJYkSTh79qxcgsnJybC3t5dLMCwsDDY2NgCAFzccwa/Z1+768WZzFApgzICeiJsx5KEz62XxAUBAQACWL1+OwMBA0VGIiOg3Go0Gx44dk4vwwIEDGDBgAIZHPIbvTYZB/adPOOuunkPpL8vRUHIJFn190HXMS7i6YQ56v7T2jo9PzU1NsD8q4qGnPfX2eRcBAQFIT08XHYOIiP5AqVQiICAAUVFR2LlzJ65fv46PPvoI+Qo7qBsaGv2stqEO17fMh5XfY+jz2leApMH1rR/A0jmgyXuGCgBbMi49dEa9LT5/f38WHxGRjrOwsEB4eDj6+QYDSrNG36u/cgaSVgsrn9FQKM3QadAo1BfmoKN7UJOvVavW4nRh5UNn0tviCwgIQEZGhugYRETUAhW16ju+prlZBtMuPaBQ3KqiDnZOUHSwhEU/n7u8TkOz32spvS2+QYMGIScnB7W1taKjEBHRPVhbmN7xNWUnW2hrq+T/31ByCZAkwOTOn/39dcya/V5L6W3xWVhYwN3dnVsaiIj0gKe9NTooG9+369DLA9q6atReunX2cuXR7QAk1F/LbfI1LExN4OnQ+aGz6G3xAbzPR0SkDw4cOIAflsxDXV1do6+bmJmjx1/nomzXZ7jy+cswMe+I7uPfRHFCjFyGfyQBmOLv+NB5ml9P6gHe5yMi0k2SJGH79u2Ijo5GQUEB3nrrLdh36oWknOJG+/gs+g6Cw98/bfS7HT2C73g9hQII9+jRKgdX633xrV27VnQMIiL6TUNDA77++mvExMRAqVQiKioKU6dOhampKTILyrE/r+yBTm6xMFXi5TDXVsmotxvYAaC6uhrdu3dHWVkZzM3b5vEVRER0bzdv3sTnn3+ORYsWwcXFBVFRUXj00Ufv2I+nC2d16vU9vo4dO8LFxQWnTp0SHYWIyCgVFxfj3XffhZOTE/bu3YstW7YgKSkJY8aMaXIT+ozA/pg3zguWZkrc61xrheLWGZ2tWXqAnhcfwAEXIiIRzp8/j3/9619wd3dHYWEhUlNTsWXLFgwdOvSevzsjsD++eTEQYwb0hLmpCSxMG1eRhakJzE1NMGZAT3zzYmCrlh6g5/f4AA64EBG1p+PHjyM6Oho///wzZs2ahVOnTsHBweG+X8fH0QZxM4agpKoOWzIu4XRhJSpqG2BtYQZPh86Y4t92T2DX++Lz9/dHfHy86BhERAZLkiTs2bMH0dHROHbsGF5//XWsWLECXbp0eejX7mZljn+MdGmFlC2n18MtAFBVVYWePXuivLwcZmYPv6OfiIhu0Wq1SEhIQHR0NEpLSxEZGYmnn35a74cJ9X7FZ2VlhX79+iErKwu+vr6i4xAR6b26ujrEx8cjNjYW1tbWiIqKwl//+lcolUrR0VqF3hcf8PuAC4uPiOjBVVRUYNWqVfj0008xaNAgrFy5EmFhYU1OZ+ozvZ/qBDjgQkT0MK5evYq3334bzs7OOHr0KH766Sf8/PPPCA8PN7jSAwyk+LilgYjo/p09exb/+Mc/MGDAAFRWVuLw4cP46quv4OfnJzpamzKI4hs8eDCOHz8OtfrO5z0REVFjR44cwdSpUxEcHIyePXvizJkzWLZsGZycnERHaxcGUXzW1tbo3bs3Tp8+LToKEZFOkiQJO3fuhEqlwqRJkzB8+HDk5+dj/vz56NGjh+h47coghluA3+/zeXt7i45CRKQz1Go1vv32W0RHR6Ourg5RUVGYPn26UW//MogVH3Cr+Hifj4jolpqaGqxYsQIeHh5YunQp3nvvPZw4cQLPPPOMUZceYEArPn9/f2zbtk10DCIiocrKyrBixQosXboUw4YNw/r16zF8+HDRsXSKwaz4/P39kZmZCY3m/p/zRESk7y5duoQ333wTLi4uOHv2LBITE/H999+z9JpgMMVnY2MDOzs75OTkiI5CRNRusrOz8eyzz8LHxweSJCEzMxP/+9//MHDgQNHRdJbBFB/AjexEZDz279+PiRMnIiwsDC4uLjh37hwWLVqEPn36iI6m8wyq+LiRnYgMmVarxY8//oiQkBDMmDEDY8aMQX5+Pt555x107dpVdDy9YTDDLcCtFd+CBQtExyAialUNDQ3YuHEjYmJiYGpqirlz52LKlCkwNTWoP8Lbjd4/luiPSkpK4OzsjLKyMpiYGNRiloiMUFVVFT7//HMsWrQIrq6uiIqKwqOPPmqQ52e2J4Nqh27dusHW1hbnzp0THYWI6IEVFxfj3XffhZOTE1JTU/Htt98iKSkJY8aMYem1AoMqPoADLkSkv86fP49//etfcHd3R2FhIfbt24ctW7Zg6NChoqMZFIMrPg64EJG+yczMxFNPPYWAgAB06tQJp06dwmeffQZ3d3fR0QySwRUfV3xEpA8kSUJKSgrGjh2LsWPHwtfXF3l5efjoo4/g4OAgOp5BM6jhFgAoKiqCh4cHSktL+Vk4EekcrVaLbdu2ITo6GuXl5ZgzZw6efvppmJubi45mNAxuFtbOzg5WVlbIz8+Hs7Oz6DhERACAuro6bNiwAbGxsbCxsUFUVBQmTpwIpVIpOprRMbjiA35/UgOLj4hEq6ioQFxcHBYvXgwfHx/ExcUhLCyMn0gJZHD3+IBbAy68z0dEIl29ehVvv/02nJyccOzYMfz000/YsWMHwsPDWXqCGWTx8dl8RCTK2bNn8Y9//AMDBgxAZWUljhw5gq+++gp+fn6io9FvDLL4bm9pMLC5HSLSYUeOHMHUqVMRHByMnj174syZM1i2bBmcnJxER6M/Mcjic3BwgLm5OS5evCg6ChEZMEmSsHPnTqhUKkyaNAnDhw9Hfn4+5s+fjx49eoiOR80wyOEW4PdVX79+/URHISIDo1arsWXLFsTExKC+vh6RkZGYPn06zMzMREejFjDY4ru9kX3SpEmioxCRgaipqcG6devw8ccfo1evXpg/fz7GjRvHQ/H1jMH+0+KACxG1lrKyMrz//vtwcnLCL7/8gg0bNmDv3r0YP348S08PGew/MQ64ENHDKigowOzZs+UnnCclJSEhIQHBwcGio9FDMNji6927NxQKBS5fviw6ChHpmaysLPz973+Hr68vgFuHSP/vf//DgAEDBCej1mCwxadQKPikBiK6L/v27cOECRMQHh4OV1dXnDt3DosWLUKfPn1ER6NWZLDFB/BJDUR0b1qtFj/++CNCQkLw9NNP47HHHsP58+fxzjvvoGvXrqLjURsw2KlO4NZ9vrVr14qOQUQ6qKGhARs3bkRMTAzMzMwQFRWFKVOmwNTUoP9YJBjgY4n+6MKFCwgKCsKVK1dERyEiHVFVVYXPP/8cixYtgpubG6KiojB69Gien2lEDPqjzr59+6K+vh6FhYWioxCRYNevX8d//vMfODk5Yd++ffj222+RmJiIRx99lKVnZAy6+G4PuPA+H5Hxys/Px6uvvgoPDw9cu3YN+/fvx+bNmzF06FDR0UgQgy4+gBvZiYxVZmYm/va3v2HIkCHo3LkzsrKysGrVKri5uYmORoIZfPFxSwOR8ZAkCcnJyXjssccwduxY+Pn5IS8vDx9++CHs7e1FxyMdYdDDLQCQl5eH0NBQFBQUiI5CRG1Eo9EgISEBH330EW7cuIE5c+bg6aefhrm5uehopIMMvvgkSULXrl1x5swZ2NnZiY5DRK2orq4OGzZsQGxsLGxsbBAVFYWJEydCqVSKjkY6zOA/6uSAC5HhuXHjBmJiYuDs7Ixvv/0Wq1atQlpaGiZNmsTSo3sy+OIDOOBCZCgKCwsxd+5cODs7IzMzE9u3b8eOHTsQFhbGLQnUYkZRfFzxEem3s2fP4sUXX8TAgQNx8+ZNHDlyBF9++aV8iDTR/TCK4uOKj0g/HT58GFOmTEFwcDAcHBxw5swZLF26FE5OTqKjkR4z+OEW4NYhtLa2tsjLy0O3bt1ExyGiu5AkCTt37kR0dDTOnTuHN998E88//zysrKxERyMDYRSnsZqYmGDw4MHIyMjA6NGjRcchoiao1Wps2bIF0dHRaGhoQFRUFKZNmwYzMzPR0cjAGEXxAb9vZGfxEemWmpoarFu3DgsXLkTv3r3x3//+F+PGjYOJiVHciSEBjKb4AgICkJCQIDoGEf2mtLQUK1aswLJly/DII48gPj4ewcHBomORETCat1QccCHSDQUFBZg9ezZcXV2Rm5uLpKQkJCQksPSo3RhN8bm5uaGoqAhlZWWioxAZpaysLPz973+Hr68vFAoFjh8/jnXr1mHAgAGio5GRMZriUyqV8PPzw9GjR0VHITIq+/btw4QJExAREQE3Nzfk5ubi448/hqOjo+hoZKSMpvgAPqmBqL1otVr88MMPGDFiBJ555hmMHTsW+fn5mDdvHmxtbUXHIyNnNMMtwK37fDt27BAdg8hg1dfXY+PGjYiNjYWZmRnmzp2LyZMnw9TUqP6oIR3HFR8RPbSqqip88skncHV1xfr167Fo0SJkZGTgySefZOmRzjGqfyM9PT1x5coVVFRUwNraWnQcIr13/fp1LFmyBHFxcQgLC8PWrVsxZMgQ0bGI7sqoVnympqbw8fHhgAvRQ8rPz8err74Kd3d3FBUVYf/+/di8eTNLj/SCURUfwCc1ED2MzMxM/O1vf8PQoUPRuXNnZGdnY9WqVXBzcxMdjajFjK74uJGd6P5IkoTk5GQ89thjGDduHAYPHoy8vDx8+OGHsLe3Fx2P6L4Z1T0+4NaKLyYmRnQMIp2n0Wiwbds2REdHo6KiAnPmzEFCQgLMzc1FRyN6KEbxWKI/amhoQJcuXVBUVMTHnBA1oa6uDuvXr8fChQthY2ODuXPnYuLEiTw0mgyG0f2bbGZmBm9vbxw7dkx0FCKdcuPGDURHR8PJyQlbt27FqlWrkJaWhv/7v/9j6ZFBMcp/mwMCAjjgQvSbwsJCREVFwdnZGcePH8eOHTuwY8cOhIWFQaFQiI5H1OqMtvg44ELGLicnB7NmzcKAAQNQXV2N9PR0fPnll/D19RUdjahNGWXxcUsDGbPDhw9jypQpGD58OHr16oWcnBwsXboU/fv3Fx2NqF0Y3XALcOs8QRsbGxQXF6Njx46i4xC1OUmSsHPnTkRHRyM3NxezZ8/G888/zwEvMkpGt50BADp06AAvLy9kZmYiKChIdByiNqNWq7F582bExMRArVYjMjIS06ZNg5mZmehoRMIYZfEBvw+4sPjIEFVXV2PdunXyc+/ef/99jBs3jsMqRDDi4vP398ehQ4dExyBqVaWlpVi+fDmWLVuGoKAgfPnll3xzR/QnRjncAnBLAxmWgoICvPHGG3B1dUV+fj5SUlKwbds2lh5RE4y2+AYNGoScnBzU1taKjkL0wE6dOoWZM2fC19cXSqUSx48fx9q1a+Hl5SU6GpHOMtris7CwgLu7O06cOCE6CtF9S01NxYQJE6BSqeDu7o7c3FwsXLgQjo6OoqMR6TyjLT6AG9lJv2i1Wvzwww8YMWIEZs6cibFjxyI/Px/z5s2Dra2t6HhEesNoh1uAWwMuLD7SdfX19di4cSNiYmJgbm6OqKgoTJ48GaamRv2fL9EDM+r/cgICArB27VrRMYiaVFVVhdWrV+OTTz6Bu7s7Pv30U4waNYpbEogeklGe3HJbdXU1unfvjrKyMj5jjHRGUVERli5diri4OISHhyMyMhJDhgwRHYvIYBj1Pb6OHTvCxcUFp06dEh2FCHl5eXjllVfg6emJ69ev48CBA9i0aRNLj6iVGXXxAbzPR+IdO3YM06dPx9ChQ9GlSxdkZWUhLi4Orq6uoqMRGSSjLz5uZCcRJElCUlISxowZg8cffxz+/v7Iz8/HBx98AHt7e9HxiAyaUQ+3ALeKLz4+XnQMMhIajQbfffcdYmJiUFFRgTlz5uD777/nPWaidmTUwy3Arcm5nj17ory8nCfWU5upra3Fhg0bEBsbi65duyIqKgoTJ06EiYnRf+hC1O6MfsVnZWWFfv36ISsri0+eplZ348YNxMXFYfHixfDz88Pq1asxcuRIbkkgEohvN8EBF2p9hYWFiIqKgrOzM06cOIGff/4Z27dvR2hoKEuPSDAWHzjgQq0nJycHs2bNwsCBA1FTU4P09HTEx8fDx8dHdDQi+g2LD1zx0cM7dOgQJk+ejOHDh6N3797IycnBkiVL0L9/f9HRiOhPjH64BQAqKirQq1cvlJeX8/xDajFJkvDLL78gOjoaeXl5mD17Nl544QV06tRJdDQiugv+KQ/A2toavXv3xunTp+Ht7S06Duk4tVqNTZs2ISYmBhqNBpGRkZg2bRqngon0BIvvN/7+/sjIyGDxUbOqq6uxdu1afPzxx+jTpw8WLFiAcePGcViFSM/wHt9v+Gw+ak5JSQn++9//wsnJCbt27cJXX32FPXv24PHHH2fpEekhFt9vOOBCf1ZQUIA33ngDbm5uyM/PR0pKCrZt24agoCDR0YjoIbD4fuPv74/MzExoNBrRUUiwU6dOYebMmfD19YVSqcTx48exdu1aeHl5iY5GRK2AxfcbGxsb2NnZIScnR3QUEiQ1NRV/+ctfoFKp4OHhgdzcXCxcuBCOjo6ioxFRK+Jwyx/c3sjOd/bGQ6vV4scff0R0dDSuXr2Kt956C5s2bYKlpaXoaETURlh8f3B7wOWpp54SHYXaWH19Pb766ivExsbC3Nwcc+fOxeTJk6FUKkVHI6I2xo86/+D2lgYyXJWVlVi0aBFcXFwQHx+PTz/9FOnp6XjiiSdYekRGgiu+P/D398fRo0eh1Wr5uBgDU1RUhCVLlmDVqlUIDw/Htm3bEBAQIDoWEQnAP93/oFu3brC1tcW5c+dER6FWkpeXh1deeQUeHh4oLi7GgQMHsGnTJpYekRFj8f0Jn9RgGI4ePYrp06dj2LBh6NKlC7KzsxEXFwdXV1fR0YhIMBbfn3Aju/6SJAlJSUkYM2YMxo8fj4CAAOTl5eGDDz6Avb296HhEpCN4j+9PAgICEBsbKzoG3QeNRoPvvvsO0dHRqKysRGRkJL7//nuYm5uLjkZEOoiPJfqToqIieHh4oLS0lOcw6rja2lqsX78eCxcuRNeuXTF37lxMmDCBg0lEdFdc8f2JnZ0drKyskJ+fD2dnZ9FxqAk3btzAypUrsWTJEvj5+WH16tUYOXIk36gQUYvwrXET+KQG3XTlyhVERkbC2dkZJ0+exM8//4zt27cjNDSUpUdELcbiawIHXHTLmTNn8MILL8Db2xu1tbVIT09HfHw8fHx8REcjIj3E4msCtzTohoMHD2LSpEkICQmBo6MjcnJysGTJEvTv3190NCLSYxxuaUJhYSG8vb1RXFzMj9DamSRJ+OWXXxAdHY28vDy8+eabeP7559GpUyfR0YjIQHC4pQkODg4wNzfHxYsX0a9fP9FxjIJarcamTZsQExMDjUaDqKgoPPnkkzAzMxMdjYgMDIuvGbcHXFh8bau6uhpr167Fxx9/jL59++KDDz7A2LFjudImojbDe3zN4JMa2lZJSQnmz58PJycnJCYmYuPGjdi9ezfGjRvH0iOiNsXiawa3NLSNixcv4vXXX4ebmxsuXLiAlJQUfPfddwgMDBQdjYiMBIuvGbe3NHD2p3WcPHkSzzzzDPz8/GBqaooTJ05gzZo1fNo9EbU7Fl8zevfuDYVCgcuXL4uOotdSU1Mxfvx4jBo1Cp6ensjNzcXChQvRu3dv0dGIyEhxuKUZCoVCXvU5OjqKjqNXtFotfvjhB8TExODatWt46623sHnzZlhaWoqORkTE4rub2xvZJ06cKDqKXqivr8dXX32FmJgYWFpaIioqCpMnT4ZSqRQdjYhIxuK7i4CAAKxZs0Z0DJ1XWVmJ1atX45NPPoGnpyeWLFkClUrF6Uwi0km8x3cX3NJwd0VFRXjnnXfg5OSEgwcPYtu2bfj1118xatQolh4R6SwW31307dsX9fX1KCwsFB1Fp+Tl5eHll1+Gp6cnSkpKkJaWhm+++QYBAQGioxER3ROL7y7+OOBCwNGjRzFt2jQMGzYMNjY2yM7OxsqVK+Hq6io6GhFRi7H47sHYn9QgSRISExPx6KOP4i9/+QuGDBmCvLw8fPDBB+jZs6foeERE943DLffg7++P+Ph40THanUajwdatWxETE4PKykpERkbiqaeegrm5uehoREQPhY8luoe8vDyEhoaioKBAdJR2UVtbi/Xr1yM2Nhbdu3dHVFQUJkyYABMTfjhARIaBK757cHJyQlVVFYqKimBnZyc6TpspLy9HXFwcFi9eDH9/f6xZswYhISGcziQig8O38fdwe8DFUO/zXblyBZGRkXBxccGpU6ewc+dO/PTTTxg5ciRLj4gMEouvBQzxSQ1nzpzBCy+8AG9vb9TV1SEjIwMbNmzAoEGDREcjImpTLL4WMKQtDQcPHsSkSZMQEhKCPn36ICcnB4sXL+YDd4nIaLD4WkDftzRIkoQdO3YgLCwMTzzxBMLCwpCfn493330X3bt3Fx2PiKhdcaqzBbRaLWxtbZGXl4du3bqJjtNiarUa33zzDWJiYiBJEiIjI/Hkk0/CzMxMdDQiImE41dkCJiYmGDx4MDIyMjB69GjRce6puroaa9euxcKFC9GvXz98+OGHGDt2LIdViIjAjzpbTB8GXEpKSjB//nw4OTkhMTERX3/9NXbv3o1x48ax9IiIfsPiayFd3tJw8eJFvP7663Bzc8OFCxewe/dufPfddwgMDBQdjYhI57D4WkgXV3wnT57EM888g8GDB8PMzAwnTpzAmjVr4OnpKToaEZHOYvG1kJubG4qKilBWViY0hyRJ2Lt3L8aPH49Ro0bBy8sLubm5iI2NRe/evYVmIyLSByy+FlIqlfDz88PRo0eFXF+r1SIhIQHDhw/Hs88+i/HjxyM/Px9vv/02bGxshGQiItJHnOq8D7c3skdERLTbNevr6/Hll18iNjYWlpaWiIqKwuTJk6FUKtstAxGRIWHx3YeAgADs2LGjXa5VWVmJzz77DJ988gm8vLywZMkSqFQqTmcSET0kftR5H9pjwOXatWuYN28enJyccOjQISQkJODXX3/FqFGjWHpERK2AxXcfPDw8cOXKFVRUVLT6a+fm5uKll16Cp6cnSktLkZaWhm+++QYBAQGtfi0iImPG4rsPpqam8PHxadUBl6NHj2LatGl45JFH0LVrV5w+fRorV66Eq6trq12DiIh+x3t892lgQCBW7cnDd1etUVGrhrWFKTztrTE1wBHdrMxb9BqSJCEpKQnR0dHIysrCG2+8gdWrV6Nz585tnJ6IiHhIdQtlFpRjeco5JGVfhUajgWTy+3sGC1MTSADCPHrg5VBX+PaxafI1NBoNtm7diujoaNy8eRORkZF46qmn0KFDh/b5iyAiIhZfS8SnnceC7adRq9bgbn+3FArAwlSJeeM8MSOwv/z12tpafPHFF1i4cCG6d++OqKgoTJgwASYm/KSZiKi98aPOe7hVetmoadDe82clCahp0GDB9mwAwHhPG6xcuRJLliyBv78/1qxZg5CQEE5nEhEJxBXfXWQWlGPa6jTUNGju+3eVkgYV383HY8O8EBkZiUGDBrVBQiIiul8svrt4ccMR/Jp97a4fbzZL0iLE2QYbXgxp9VxERPTgeJOpGcVVddidc71R6RX+73Vc3/oB/vheoSx5HUq2L7nzBRQmOFRQhZKqunZIS0RELcXia8aW9Et3fK3nUx+h/vp51BWcAgBIWg1unkpGJ++mz+5UANiScefrEBGROCy+Zpy+WoE6deOBFhMzC3TyDkf1mX0AgNr8o4DSDOZ9Bjb5GrVqLU4XVrZ5ViIiajkWXzMqatVNfr2jexCqz6ZBkiRUnUiE1cDwu05pVtQ2tFVEIiJ6ACy+ZlhbNL3To0OP/lAoTVGbn4GacwfRadDdH1FkbWHWFvGIiOgBsfia4WlvDXPTpv/2dHQLQsnPy9ChpwvMbHs1+xoWpibwdOAxZEREuoTF14wpAY7Nfs/SPQiaiuvNDrXcJgGY4t/86xARUftj8TWju5U5Qt17oKnbd+a9PQAAFv18mv19hQII9+jR4oOriYiofbD47uKVMFdYmCrv+LpCYXL7fzT7uxamSrwcxkcLERHpGhbfXfj2scG8cZ6wNLu/v02WZiaYN84TPo42bROMiIgeGI8sa4GHfToDERHpDhZfCx2/VI4VKeeQfOY6FLi1Of2228/jC/fogZfDXLnSIyLSYSy++1RSVYctGZdwurASFbUNsLYwg6dDZ0zxb/kT2ImISBwWHxERGRUOtxARkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVFh8RERkVH5f6X9fQjCwoKxAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# note that we get the same result if we start with the original graph, too\n",
    "user_graph = make_user(graph)\n",
    "nx.draw(user_graph, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "bb4f892a",
   "metadata": {},
   "source": [
    "## Extra: Generalize the code\n",
    "\n",
    "Both of these problems have a very similar structure, so we create a template function that handles them both."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "c0b63133",
   "metadata": {},
   "outputs": [],
   "source": [
    "def contract_graph(graph, remove_node):\n",
    "    graph = graph.copy()\n",
    "    for node in list(graph.nodes):\n",
    "        if remove_node(graph, node):\n",
    "            connected_nodes = set(node for _, node in graph.edges(node))\n",
    "            for n1, n2 in itertools.combinations(connected_nodes, 2):\n",
    "                graph.add_edge(n1, n2)\n",
    "            graph.remove_node(node)\n",
    "    return graph\n",
    "\n",
    "def filter_for_implicit(graph, node):\n",
    "    return graph.degree(node) == 2 and not graph.nodes[node]['is_user']\n",
    "\n",
    "def filter_for_user(graph, node):\n",
    "    return not graph.nodes[node]['is_user']"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "92f7bca0",
   "metadata": {},
   "source": [
    "## Extra 2: Structure to facilitate this\n",
    "\n",
    "Here's an easy data structure that, combined with `contract_graph` from the generalized code above, handles this nicely."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "76f42cc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "class ThreeLevelGraph:\n",
    "    def __init__(self, edges, user_nodes):\n",
    "        self._implicit_graph = None\n",
    "        self._user_graph = None\n",
    "        self._full_graph = nx.Graph(edges)\n",
    "        self.user_nodes = user_nodes\n",
    "        \n",
    "    def is_user_node(self, node):\n",
    "        return node in self.user_nodes\n",
    "    \n",
    "    def _implicit_remove(self, graph, node):\n",
    "        \"\"\"Conditions for node to be removed from full graph to make implicit\n",
    "        \"\"\"\n",
    "        return graph.degree(node) == 2 and self.is_user_node(node)\n",
    "    \n",
    "    def add_edge(self, n1, n2):\n",
    "        # ground truth is changing; invalidate other models\n",
    "        self._implicit_graph = None\n",
    "        self._user_graph = None\n",
    "        \n",
    "        self._full_graph.add_edge(n1, n2)\n",
    "        \n",
    "    def to_dict(self):\n",
    "        return {\n",
    "            'edges': list(self.full_graph.edges),\n",
    "            'user_nodes': self.user_nodes\n",
    "        }\n",
    "\n",
    "    @classmethod\n",
    "    def from_dict(cls, dct):\n",
    "        return cls(**dct)\n",
    "        \n",
    "    @property\n",
    "    def full_graph(self):\n",
    "        # possibly return as read-only view?\n",
    "        return self._full_graph\n",
    "        \n",
    "    @property\n",
    "    def implicit_graph(self):\n",
    "        if self._implicit_graph is None:\n",
    "            self._implicit_graph = contract_graph(self.full_graph, self._implicit_remove)\n",
    "        return self._implicit_graph\n",
    "        \n",
    "    @property\n",
    "    def user_graph(self):\n",
    "        if self._user_graph is None:\n",
    "            implicit = self.implicit_graph  # generate if doesn't exist\n",
    "            self._user_graph = contract_graph(\n",
    "                implicit,\n",
    "                lambda graph, node: self.is_user_node(node)\n",
    "            )\n",
    "        return self._user_graph"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "284faab8",
   "metadata": {},
   "source": [
    "## To-Do: Proper testing\n",
    "\n",
    "A few test cases to consider:\n",
    "\n",
    "* user-specified nodes of degree 2 should not be removed\n",
    "* check that behavior is as expected if there are multiple nodes removed in the implicit -> user stage (i.e., multiple implicit nodes connected to each other)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c32d1dbf",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}