fast_sweeping.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random\n",
    "import numpy as np\n",
    "import networkx as nx\n",
    "import pandas as pd\n",
    "from scipy import sparse as sp\n",
    "from scipy.sparse.linalg import eigs\n",
    "\n",
    "from graph_generator.community_graph import make\n",
    "from helpers import (\n",
    "    draw_nodes, draw_edges, get_borderless_fig, signed_normalized_laplacian, flatten, pos_adj, neg_adj,\n",
    "    num_pos_edges, num_neg_edges, get_v1\n",
    ")\n",
    "from core import sweep_on_x, sweep_on_x_fast\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "random.seed(12345)\n",
    "np.random.seed(12345)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "g, groundtruth = make(4, 2, 1, 0, 0.3, 1)\n",
    "g.add_edge(8, 0, sign=1)\n",
    "g.add_edge(9, 0, sign=-1)\n",
    "g.add_edge(10, 4, sign=-1)\n",
    "g.add_edge(11, 5, sign=1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADtCAYAAAAcNaZ2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAG/xJREFUeJzt3X9wHOWd5/F3x/wYTaRIMlhnckm8GKKE7ErLuiwqZOPE\n2R/nkmxspNrKXpDBNj8cnOSAuvLFpSTYMrVZFUTY8eVOOjjCySYGUgfht1lYksIhtwGNgVi6hER2\nnMTZBCydpRX+MTJYfu6PnrHHo54fQjNPd898XlVdlmZa40ff7vnomaef7naMMYiIiB3v87sBIiLl\nRKErImKRQldExCKFroiIRQpdERGLFLoiIhadk+N5zScTEZk+J9MT6umKiFik0BURsUihKyJikUJX\nRMQiha6IiEUKXRERixS6IiIWKXRFRCxS6IqIWKTQFRGxSKErImKRQldExCKFroiIRQpdERGLFLoi\nIhYpdEVELFLoiohYpNAVEbFIoSsiYpFCV0TEIoWuiIhFCl0REYsUuiIiFil0RUQsUuiKiFik0BUR\nsUihKyJi0Tl+N0BEXMPDw+zo62NoYICj4+NUVldT39jIqjVrmDNnjt/NkwJxjDHZns/6pIjMXCwW\nY1tXF888+yxtQNPEBFXAEaC/ooLHjGFpczO3dnTQ1NTkc2slT07GJxS6Iv65t7eXTevXsyEeZ5Ux\n1HqsMwb0OQ53VVSwububtevW2W6mTJ9CVyRo7u3t5c7163nu+HEuzWP9/cCSaJQNCt4wUOiKBEks\nFmP54sV88fhxngEGgWuA+xPPv5v4fg/wO+BF4DO4wbsoGuWp3btZuHCh/YZLvjKGrmYviPhgW1cX\nG+JxLgduB27wWGcRsBO4KOWxS4GvxuNs6+qy0EopBvV0RSwbHh7mY/PmcWBi4vQY7u3AHzjT0031\nYdzw/Uzi+1HgkkiEoYMHNashuNTTFQmKHX19tILnQbN8zAZaHYcdfX2Fa5RYo9AVsWxoYIArJiZm\n9BpN8ThDg4MFapHYpNAVsezo+DhVM3yNKuDI2FghmiOWKXRFLKusrubIDF/jCFBV+14HKMRPCl0R\ny+obG+mPRACYBCYS/54ETiS+Bngn8RyJx0+kvEasooL6hgYr7ZXC0uwFEctSZy/8V2AzZx/q3gRs\nBC4GDqb97G+ASjR7IQQ0e0EkKOrq6lja3Mx2x2ETcAq3d5tcNibW+03a45PAR4DtjsOylhYFbkip\npyvig+QZaS/leQpwks5ICw31dEWCpKmpic3d3SyJRtmf588kr72wubtbgRtiCl0Rn6xdt44N3d0s\nikbZ6jhkmgA2CmxxHBbpYjclQcMLIj7bs2cP27q6eHrXLlodh6Z4/PT1dGOJ6+kua2nh1o4O9XDD\nQ1cZEwm6kZER984Rg4M8+MAY11xbS31DA9etXq2DZuGj0BUJE8eB7G9NCTgdSBMRCQKFroiIRQpd\nERGLFLoiIhYpdEVELFLoiohYpNAVEbFIoSsiYpFCV0TEIoWuiIhFCl0REYsUuiIiFil0RUQsUuiK\niFik0BURsUihKyJikUJXRMSic/xuQJgNDw+7t1cZGODo+DiV1dXUNzayas0a3V4lheqUn9Q6VTLO\n2pWqUyah3qeMMdkW8dDf32/aW1tNTSRiro9ETC+Y74HpBbOmosLURCKmvbXV9Pf3+91UX6lO+VGd\n8heiWmXMVYXuNN3T02PmRqNmq+OYUfc2VlOWUTBbHMfMjUbNPT09fjfZF6pTflSn/IWsVgrdQrin\np8fMj0bNvgwbPH3ZB2a+/xvfOtUpP6pT/kJYK4XuTPX395u5aRv9v4FZCOZ8MGuybPy50aiJxWJ+\n/wpWeNXJgFkJ5iIwHwDzMTD3qU6edTJgPgsmAqYKTCWYj5dxnYzxrlVloj7JGs0Cc0uw9imF7ky1\nt7aarY5z1kZ9DMwTYL6UJXRN4uPOyrY2v38FK7zqZMD8Asw7ia9/BWYumNdUJ8/9ZTGY+7U/nZat\nVgbMsUT4/iRYtVLozsShQ4dMTSSScRzpGzlC9zCYmkjEDA8P+/2rFFWuOiWXXyZ6vf9bdcoYut/V\n/mSMyW+f6gNzSfBqlTFXNU83Dzv6+mgFat/jz88GWh2HHX19hWtUAOWq05eB9wOXAR8EWtKeV53O\n6ADqgEXA7rTnyqVOkF+tdgDXZXguiLVS6OZhaGCAKyYmZvQaTfE4Q4ODBWpRMOWq038HjgI/AdqA\n8z3WUZ3gLuAA8AfgJuAq4Ddp65RDnSB3rQ4CPwZWZXmNoNVKoZuHo+PjVM3wNaqABx8Yw3HAcaDT\n6eT0NylLp9Pp9XAo1j+6c2fOOjnAp4DfA70Z6nRkbAw6vdtDZ6f3C4do/Vz7UxPuJ4JzcXtwfwns\nSlsnfX8q1eWhndlrtQP4NDAvyzqn96mgyDb2YHsQJKhuam83vVnGlHKN6RowPWDWXnut379KUeWq\nU+pyI5jbVKe8lmYw3ynDOpnf/97ctGBB1lrVJ8Z0A/je05juTNQ3NtIfiUx5fBKYSPx7EjiR+NpL\nrKKC+oaGorUxCOobG3nFo04jwPeBY8Ap4DngYeCvPV6jXOrktT8BjAPPc2Zf2gm8BCxJW68c6sSb\nb1J/7rm8cu65nk//C/BH4O9yvEzgapUtkW3/aQiqTEdQO8E4YN6XsmzOcAS1+vzSPtp86pQxfX2H\nTNSZWqcR3LmntWCqwTRmODpfLkflsx2RHwHThDufuRbMlWB+6FGnylkR86tfhbhOJ08a89prxmzZ\nYsxXvuK5ysSEMXfeechU4F2rL4JZlaOXq9kLIVVXV8fS5ma2O85Zj2/C7blNpiwbPX7+f+HAqRY6\nOubwm/QjIiFnDDzxBCxYANu21fHJK5rpS6vThcCLwCjwb8Be4HqP19ruOCxraQn+BUtmKNP+BG6t\n+nF7vKO4vbm/Slunz3H4yIda+NSn5rBxI4yOFr3JhTE5CVu3wooVcOGFcM01MDQEixadtdqJE9Db\nCx/9KOzeXcfnPutdq/8B9OX4LwO5T2VLZNt/GoIs2xlE2ZbkWTEvvBAzt99uzAUXGHPDDcYcOOD3\nbzQzp04Z8/jjxlx+uTF/8RfGPPGE+9hM61QuZ1oVok6//rW7L11wgTG3327M4cN+/1Z56Ogw5uGH\njXnzzSlPTUwY09NjzIc/bExLizGvvOI+HtJ9KmOuKnSnoRDnfx8+bEIdvpnCNlUIz5P3RaHqFIjw\nTR0uWL7cmNdfz/tHM4VtqhDuUwrdQkle6WhLlisdHQZzd44rHYUtfPMJ21SFqlOpK2SdfAnfRx91\nQ7amxpiPf9yYm292e7JjYzl/NJ+wTRWyfUqhW0ixWMysbGszNZGIWVNRYXrAPIA7NSV5Tc+VbW15\nfawJevhON2xTFbJOpazQdbIavrt2ZRwuyGS6YZsqRPtUxlx1jDFZh3xtjS2H0cjIiHv1+sFBHnxg\njGuuraW+oYHrVq+e9sD96Ch8+9vQ0wNXXw1f/zpcfHGRGp4HY+DJJ8/M8e/shKuucr+erkLWqZQV\nuk4HDsA//iM8/jh86Utw220we3aePzw5CQMD8OKL7vKJT0BX17TbkOrECbj/fvdlGhpg0ya44or3\n9loh2Kcyv1OyJbIffx7CigJVy++e70x6tvkoVJ1KXSHrNK2e7xtvGHPVVVOHC9566z3//zPp2eYj\noPuUhheKrdAb3nb4FjtskwL6BgmcYtTprPD9xinv8B0envZwQSbFDtukgO5TGl4oNsdxP5IXWrGH\nHQo5jJCPYtWp1BS8TpOTsHcvvPgix3a9yMTLe7ns/APc/OVZ0xt2yEMhhxHyEdB9KuM7SCdHBNzs\n2XDHHe4c8g9+EJqa4MYbmfFJFiblpIbNm93l1Vdh+fLiBa745Jpr3JMRVq6E/ft5/9qVXLD/FV6O\nzeKPf4T6egpykkXqSQ1PPw2PPALPPFPcwA2lbN1gP/rkYWXrI85Mhx1sDSNkEtCPgoEz7TqdPGnM\nO+94P/ejH2UdLpjpbAdbwwiZBHSf0phusdne8NMNX7/DNimgb5DAyVmn9JMRamvdjToD0w1fv8M2\nKaD7lEK32Pza8LnCNyhhmxTQN0jgZK1TT48bspddZsy6dcZ8//sFOfCVlCt8gxK2SQHdp3Qgrdj8\nHsxPP+D2ta/B4KC9A2T58rtOYTHLmWRyeBS85pwePAjnnQdz5xa1DenzfNetc7+2dYAsXwHdpzK+\n0xS6BRKUDX/4sPsGefRRqKlx3yA33uh/2CYFpU6Bk3YywuiTLzH7+lb47nf9bhlvvOHuQy+/DPPn\nu3/Y//Zv/W7VGQHdpzR7odQlZyP8zd/Avn2wfbvbM+nogJtumvlsBymiffvcHm17u/t1ezuf4Be+\nB25yNsKSJe4f8Ecegc9+Fr7whcLMdihb2cYefBgHCS2/xpVSx2wvv9z9OnXM1u8z3NIFdPyt+E6e\nNGZgwPu5d9+dMibrZ51yjdkG4qpmKQK6T+lAWrHZ3vC5wjZdUMI3oG+QwkufXVBT4x74evvtvH7c\njzpN9wBZUMI3oPuUQrfYbG346YZtOr/DN6BvkMK78soZzS6wWaeZzkbwO3wDuk8pdIut2Bt+pmGb\nzq/wDegbZPqSPdmDB72fP3ZsRi9vo06FnvrlV/gGdJ/KmKs6kBZwyQNkCxa40746O+G119zbTM1k\nRkKxTi8uWZOT8PrrU+/xNTjovX40ard901Cs03Xnz4f77oP+fgp6enHJyZbIvvx9CKlC/7UtdM82\nF1s934D2SnLbuvXsSx0W8GQEL8Wok+2TGmz1fAO6T2l4odgKteFth226YodvQN8gZ4YL/umfvJ+f\nnLTanELWye8zyIodvgHdpzS8EHTFGkaYrrIZdsg0XPDyy97rvy98b5WgXPVLww5nC8UZacPDw+6t\nOQYGODo+TmV1NfWNjaxas8bXW3OktuuhneN8oX367TIp17MF998gXV6xENfzLUSdCu7wYVi0yJ3t\nv3ix+2+RT6vNpVB1sn092+ma0W2EEgK5T50tnLfr6e/vN+2traYmEjHXRyKmF8z3wPSm3ISuvbXV\n9Pf3h65dfg8jTNd7GXbwdfulzpONxwv/+gVUqDr5PYwwXe9l2CGomeAhfGO6ydstb81yu+VRMFss\n3255pu0KW9imyzd8fdl+AwNnn4yQPPA1MjLz1y6SQtQpbGGbLt/wDWomZBCu0L2np8fMj0bNvgyF\nTV/2gZlvocgzaVfYwzZdtvD1bfvdcou12QWFMNM6hT1s02UL36BmQhbhCd3+/n4z16O4vwXTAqYW\nzEVgvgJmMq3Ic6PRot3vPlO7RsFcDeb9YP4EzIMeG3/O+VFTXx8ribBNlx6+jz02tU4nwNwAZh6Y\nD4BZAOZZjzpl3X4nTxrz6qvG3H23MS+8YPeXLIJM+1NyGQITAXNthjpt2BArmbBNlx6+//zPmWv1\nEJjLEu+/S8H8xGIm5BCe0G1vbTVbHWdKcVvArAHzDphDYBrAfCdtnS2OY1a2tVlt139MLMcTG7wa\nzC/S1vkWjvmrT7aVVNimS4Zvzbmt5m7OrtMxMJvBHEx8/zSYKjC/y7X9fvtbd7gg/ZbgP/2pf79o\ngWTan5LLfwDzGY/QTe5PF/+7tpIL23TJ8PXapwyY5xMdnf7E939MLLYyIYdwhO6hQ4dMTSTiOV5z\nWVrv6L+AuTltncNgaiIRMzw8bKVdx8CcB2Z/ymPXgumw1K6gOXTokKk533v7pS+NYH6Qq04/+lFR\n7ozgt2z7ebL39veJP1ReoVsu+5Mxbq2qM+xTnwJzf479zMdaZczVQE0+3NHXRytQ6/HcbcBDQBz4\nA/As0Jy2zmyg1XHY0ddnpV1DwDnAJSmP/Tnwc0vtCpodfX20Ot7bL9UhYB/wp2mPT6nT5z7nzlX7\n/Od9n85VSNn287eBTcDdkHG+ZrnsT+DWqs1jnzoF7AGGgY8CHwH+E3Aibb0g1ipQoTs0MMAVExOe\nz30GN8w+gFvgJmC5x3pN8ThDmc6HL3C7jgLVaY9VA0cstStosm2/pJPASmA1UO/xfLnXaSNwE/Dv\nc7xGOdQJMtfqEPAu8Cjwf4CfAa8D/+DxGkGrVaBC9+j4OFUejxtgCfB3wHHg/wGjwAaPdauABx8Y\nw3Eo2PLQTu92VeL2TFK9nWiDjXYFbclUp9TtuBI4H/hOhnWqgCNjY2ceSN7kLX1Jnk2SLgTrH925\n07NOPwNewP1Ul0s57E/Z9qmKxL+3AHW4Pdr/DOzKUKuz9imfBSp0K6urPXuJo8C/Al8GzsX9qLEG\nd4gh3RHgmmtrcw8qTmP5Qrt3u+pxe26/TnlsL1M/NherXUFbMtUp6QbcP5g/AGZlWOcIUFWb8mGy\ns9P7P8sWcgFfv7K93bNOu4Hf4X6SuwjoBh4BFnqsWw77U7Z9qgb4kHfFPWt11j7ls0CFbn1jI/2R\nyJTHLwAuBnqBSeDfgO3A5R6vEauooL6hwUq7okAb7kfC47gfc54ErrXUrqDJVCeAm4Ff4tbnvCyv\nUc51+iLuH/Cf4f7xvhlYBjzv8RrlUCfIvk+twf3ENAKMAd8GrvJYL3C1ynaUzfbhvmxHdfeCWYw7\nT3cOmM+DGUlbx/bsBcPZ83TngXnYY51yOdqcqU6/A+OAqQBTmViqmDqnudzrlL50otkL2Wr1Lpgv\nganBnbt/G+6c8IDUKmOuBip0jck9fzHb4sc8Xb/bFTSqU35Up/yFtFbhCd1cZ+pkWvw6I83vdgWN\n6pQf1Sl/Ia1VeELXmOCeZx3UdgWN6pQf1Sl/IaxVuELXmDNXFNqS5YpCh8Hc7dNVxoLWrqBRnfKj\nOuUvZLUKX+gaY0wsFjMr29pMTSRi1lRUmB4wD4Dp4cy1M1e2tVn/+BDUdgWN6pQf1Sl/IapVxlwN\nxZ0jRkZG3KvEDw5yZGyMqtpa6hsauG71al+vEh/UdgWN6pQf1Sl/IaiVk/GJMIRuKJ06BW+95d5o\nTETKTcbQDdTJESXl+edh6VJ3pElEJEGhWyxLlrj/Pvmkv+2QcMp0WrGEnoYXiumJJ87cS93J+GlD\nZCrH0aekcNPwgi+WJy4+qd6uiCQodIspecm/5JWmRKTsneN3A0re8uVw8qQ7m2FWpgsaiki50Jiu\nSBBpTDfsNKYrEiqbNvndAikS9XRFRApPPV0RkSBQ6Np08iR873saqxMpYwpdm2bNgrvv1rxdkTKm\n0LVJ83ZFyp5C1zadpSb50LUXSpZmL/hB12SQXDRPN+w0eyFQkr3dH/7Q33aIiHXq6fplZAQuvFA9\nXfGmnm7YZXxj69oLfgnGLUUkQIaHh91b0AwMcBSoXLmS+sZGVq1ZE5Rb0EgBqKcr4rNYLMa2ri6e\nefZZ2oCmiQmqgCNAf0UFjxnD0uZmbu3ooKmpyefWSp50jzSRILq3t5dN69ezIR5nlTHUeqwzBvQ5\nDndVVLC5u5u169bZbqZMn0JXJGju7e3lzvXree74cS7NY/39wJJolA0K3jBQ6Abaffe5dw1uafG7\nJWJJLBZj+eLFvJRn4CbtBxZFozy1ezcLFy4sVvNk5jRlLNDmzIGvf11Hq8vItq4uNsTjPAc0ARHg\n+rR1fghcBlQCfw0cBC4FvhqPs62ry2ZzpYDU0w0CY2DBAveEiRUr/G6NFNnw8DAfmzePAxMT7Mbt\n+TwHxIH7E+scBi5JfL8M+AbwEvBTYBS4JBJh6OBBzWoILvV0A03XZCgrO/r6aAVqgauB5cDstHV+\nAPwZ0AacB3QCe4GhxLqtjsOOvj5LLZZCUugGha7JUDaGBga4YmIi6zo/B/485fsobs/354nvm+Jx\nhgYHi9NAKSqFblAke7s//rHfLZEiOzo+TlWudYDqtMeqcefuAu483rGxQjdNLNAZaUGyYoXGdMtA\nZXX16fDMuA7wdtpjb8PpsD4CVNV6zeqVoFNPV8Sy+sZG+iORrOv8KfCzlO+PAb9OPA4Qq6igvqGh\nOA2UotLsBRHLUmcvfAB4F7gD+Ffgf+J+/BwDPoo7e6EF2Ig7e+Ff0OyFkNDsBZGgqKurY2lzM9sd\nh3/APUh2J7Az8fU3gQuBR4Gv4c5WiAEPJ35+u+OwrKVFgRtS6ukG2eSke181KTk6I63kqacbOnv3\nwqc/rXm7JaqpqYnN3d0siUbZn+fPJK+9sLm7W4EbYgrdoGpshIkJeOopv1siRbJ23To2dHezKBpl\nq+OQaQLYKLDFcViki92UBA0vBNnjj8Mdd8Crr+oOEyVsz549bOvq4uldu2h1HJri8dPX040lrqe7\nrKWFWzs61MMND11lLJSS12TYvPnMGWtSskZGRtw7RwwOcmRsjKraWuobGrhu9WodNAsfhW5oqbcr\nEka6R1porVjhBu6xY1BZ6XdrRGSG1NMVESk8TRkTEQkCha6IiEUKXRERixS6YfPGGzpLTSTEFLph\nYgy0t+vuEiIhptANE8eBjRt1LzWREFPohk3yzhLq7YqEkkI3bBwHNm1Sb1ckpBS6YaTerkho6Yy0\nsBoYgLlzoa7O75aIyFS64I2IiEU6DVhEJAgUuiIiFil0RUQsUuiWgldegZde8rsVIpIHhW4pePNN\nuOUWzdsVCQHNXigFyXupdXYyfOWV7n22BgY4Oj5OZXU19Y2NrFqzRvfZErFHU8ZKXexb32LbN7/J\nMydO0AY0TUycvqNsf+KOskubm7m1o4OmpiafWytS8hS6peze3l42rV/PhuPHWQXUeqwzBvQ5DndV\nVLC5u5u169ZZbqVIWVHolqp7e3u5c/16njt+nEvzWH8/sCQaZYOCV6SYFLqlKBaLsXzxYl5KC9xf\nAl8GXgXqgLuAq1Oe3w8sikZ5avduFi5caK/BIuVDZ6SVom1dXWyIx88K3ElgBbAcd0jhHmAlbtAm\nXQp8NR5nW1eXtbaKiEs93ZAaHh7mY/PmcWBi4qwx3J8DVwJvpzy2BPgksDnlsVHgkkiEoYMHNatB\npPDU0y01O/r6aGXqQTOvv5IG+L9pj80GWh2HHX19RWidiGSi0A2poYEBrpiYmPL4x3HHcbuBk8Dz\nwG7guMdrNMXjDA0OFrOZIpJGoRtSR8fHqfJ4/BzgceBp4CJgK/D3wIc81q0CjoyNFa2NIjLVOX43\nQN6byupqjmR47s+AF1O+/0tgtcd6R4CqWq9ZvSJSLOrphlR9YyP9kYjnc4PACdwhhW7gLbxDN1ZR\nQX1DQ7GaKCIeNHshpDLNXgD4KnAf7pjuIuA7wPy0dTR7QaSoNHuh1NTV1bG0uZntztRtexduqL4N\nPMPUwAXY7jgsa2lR4IpYpp5uiGU6Iy0XnZEmUnTq6ZaipqYmNnd3syQaPeuMs2yS117Y3N2twBXx\ngUI35NauW8eG7m4WRaNsdRwyTQAbBbY4Dot0sRsRX2l4oUTs2bOHbV1dPL1rF62OQ1M8fvp6urHE\n9XSXtbRwa0eHergixaerjJWLkZER984Rg4McGRujqraW+oYGrlu9WgfNROxR6IqIWKQDaSIiQaDQ\nFRGxSKErImKRQldExCKFroiIRQpdERGLFLoiIhYpdEVELFLoiohYpNAVEbFIoSsiYpFCV0TEIoWu\niIhFCl0REYsUuiIiFil0RUQsUuiKiFik0BURsUihKyJikUJXRMQiha6IiEUKXRERixS6IiIWKXRF\nRCxS6IqIWKTQFRGx6JwczztWWiEiUibU0xURsUihKyJikUJXRMQiha6IiEUKXRERixS6IiIW/X9p\nsErljhIT4gAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x7f10b9f968d0>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "pos = {\n",
    "    0: [0, 0], 1: [0, 1], 2: [1, 0], 3: [1, 1],\n",
    "    4: [2, 0], 5: [2, 1], 6: [3, 0], 7: [3, 1],\n",
    "    8: [-0.5, 0], 9: [0.5, -2], 10: [2, -1], 11: [2, 2]\n",
    "}\n",
    "def show_graph():\n",
    "    fig, ax = get_borderless_fig()\n",
    "    draw_nodes(g, pos=pos, ax=ax)\n",
    "    draw_edges(g, pos=pos, ax=ax)\n",
    "\n",
    "show_graph()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.8666666666666667, 1.0, 1.0]\n",
      "[0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.8666666666666667, 1.0, 1.0]\n"
     ]
    }
   ],
   "source": [
    "print(exp_sbr_list)\n",
    "print(list(act_sbr_list[::-1]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0.0, 0.0, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.7333333333333333, 0.8, 1.0]\n",
      "[0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.7333333333333333, 0.8, 1.0]\n"
     ]
    }
   ],
   "source": [
    "print([0.0, 0.0, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.7333333333333333, 0.8, 1.0])\n",
    "print([0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.7333333333333333, 0.8, 1.0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 12/12 [00:00<00:00, 144.38it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "best_t: 0.16222142113076207\n",
      "comm1: [ 0  1  2  3  8 10]\n",
      "comm2: [ 4  5  6  7  9 11]\n",
      "\n",
      "pos_order [ 5  4  7  6  9 11 10  8  3  2  1  0]\n",
      "neg_order [ 0  2  1  3  8 10 11  9  7  6  5  4]\n",
      "abs_order [ 0  2  5  4  1  7  3  6  9  8 10 11]\n",
      "pos_vol_by_abs [ 4.  7. 11. 14. 17. 20. 23. 26. 26. 27. 27. 28.]\n",
      "neg_vol_by_abs [ 1.  3.  4.  6.  7.  8.  8.  8.  9.  9. 10. 10.]\n",
      "vol_by_abs [ 5. 10. 15. 20. 24. 28. 31. 34. 35. 36. 37. 38.]\n",
      "pos_cut_by_abs [ 4.  5.  9. 10.  9.  8.  5.  2.  2.  1.  1.  0.]\n",
      "neg_cut_by_abs [1. 3. 4. 4. 3. 2. 2. 2. 1. 1. 0. 0.]\n",
      "neg_inside_1 [ 0.  0.  0.  0.  0.  0.  2.  2.  2.  6.  8. 10.]\n",
      "neg_inside_2 [ 0.  0.  0.  0.  0.  0.  0.  2.  4.  4.  6. 10.]\n",
      "pos_inside_1 [ 0.  2.  6. 12. 12. 14. 14. 14. 14. 16. 20. 28.]\n",
      "pos_inside_2 [ 0.  2.  6. 12. 14. 14. 14. 14. 14. 16. 22. 28.]\n",
      "pos_cut_1 [4. 5. 4. 1. 1. 0. 0. 1. 4. 5. 4. 0.]\n",
      "pos_cut_2 [4. 5. 4. 1. 0. 0. 1. 1. 4. 5. 3. 0.]\n",
      "pos_between_1_2 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      "neg_inside_1_2 [0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0. 0.]\n",
      "x [-0.36273813 -0.32444284 -0.36273813 -0.28097574  0.36273813  0.36273813\n",
      "  0.28097574  0.32444284 -0.16222142  0.16222142 -0.16222142  0.16222142]\n",
      "[0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.8666666666666667, 0.8, 1.0]\n",
      "[0.0, 0.02702702702702703, 0.05555555555555555, 0.08571428571428572, 0.11764705882352941, 0.22580645161290322, 0.35714285714285715, 0.5, 0.7, 0.8666666666666667, 0.8, 1.0]\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "x = get_v1(g)\n",
    "exp_c1, exp_c2, exp_C, exp_best_t, exp_best_sbr, exp_ts, exp_sbr_list = sweep_on_x(g, x, verbose=1)\n",
    "print()\n",
    "act_c1, act_c2, act_C, act_best_t, act_best_sbr, act_ts, act_sbr_list = sweep_on_x_fast(g, x, verbose=1)\n",
    "\n",
    "exp_c1, exp_c2, exp_C = set(exp_c1), set(exp_c2), set(exp_C)\n",
    "act_c1, act_c2, act_C = set(act_c1), set(act_c2), set(act_C)\n",
    "\n",
    "print('x', x)\n",
    "print(exp_sbr_list)\n",
    "print(list(act_sbr_list[::-1]))\n",
    "\n",
    "assert exp_c1 == act_c2\n",
    "assert exp_c2 == act_c1\n",
    "assert exp_C == act_C\n",
    "assert exp_best_t == act_best_t\n",
    "assert exp_best_sbr == act_best_sbr\n",
    "assert (exp_ts == act_ts[::-1]).all()\n",
    "assert (exp_sbr_list == act_sbr_list[::-1]).all()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# more test cases"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [],
   "source": [
    "g1 = nx.Graph()\n",
    "nodes = range(5)\n",
    "g1.add_nodes_from(nodes)\n",
    "edges = [(0, 1, 1), (1, 2, 1), (0, 2, -1), (0, 3, 1), (2, 3, -1), (3, 4, 1)]\n",
    "for u, v, s in edges:\n",
    "    g1.add_edge(u, v, sign=s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "x1 = get_v1(g1)\n",
    "exp_c1, exp_c2, exp_C, exp_best_t, exp_best_sbr, exp_ts, exp_sbr_list = sweep_on_x(g1, x1)\n",
    "act_c1, act_c2, act_C, act_best_t, act_best_sbr, act_ts, act_sbr_list = sweep_on_x_fast(g1, x1)\n",
    "\n",
    "exp_c1, exp_c2, exp_C = set(exp_c1), set(exp_c2), set(exp_C)\n",
    "act_c1, act_c2, act_C = set(act_c1), set(act_c2), set(act_C)\n",
    "\n",
    "assert exp_c1 == act_c2\n",
    "assert exp_c2 == act_c1\n",
    "assert exp_C == act_C\n",
    "assert exp_best_t == act_best_t\n",
    "assert exp_best_sbr == act_best_sbr\n",
    "assert (exp_ts == act_ts[::-1]).all()\n",
    "assert (exp_sbr_list == act_sbr_list[::-1]).all()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# speed benchmark"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "from tqdm import tqdm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "from data_helpers import make_polarized_graphs_fewer_parameters\n",
    "g_list = [make_polarized_graphs_fewer_parameters(20, 0, 10, 0.05)[0] for i in tqdm(range(10))]\n",
    "x_list = [get_v1(g) for g in g_list]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "400"
      ]
     },
     "execution_count": 74,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "g_list[0].number_of_nodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "300 ms ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    }
   ],
   "source": [
    "%timeit -n1 -r1 [sweep_on_x_fast(g, x) for g, x in zip(g_list, x_list)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "10it [01:17,  7.71s/it]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1min 17s ± 0 ns per loop (mean ± std. dev. of 1 run, 1 loop each)\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "%timeit -n1 -r1 [sweep_on_x(g, x) for g, x in tqdm(zip(g_list, x_list))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "speed up raito: 256.6666666666667\n"
     ]
    }
   ],
   "source": [
    "print('speed up raito:', 77 * 1000 / 300)"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}