amazon_braket_examples/quantum_annealing/Dwave_MaximumCut.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Basic Demo for D-Wave in Braket: The Maximum-Cut Problem"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This tutorial solves a small instance of the famous __Maximum-Cut (MaxCut)__ Problem using a D-Wave device on Amazon Braket. The MaxCut problem is one of the most famous NP-hard problems in combinatorial optimization. Given an undirected graph $G(V, E)$ with a vertex set $V$ and an edge set $E$, the Max Cut problem seeks to partition $V$ into two sets such that the number of edges between the two sets (considered to be severed by the cut), is a large as possible. Applications can be found (for example) in clustering problems for marketing purposes or portfolio optimization problems in finance. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Disclaimer: The code shown in this example has been taken from D-Wave tutorial available online [here]( https://github.com/dwave-examples/maximum-cut), with copyright to D-Wave Systems, Inc., licensed under the Apache License. The purpose of this example is to show how existing code using D-Wave's Ocean tool suite can easily be run on Amazon Braket, with minimal code changes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "from braket.aws import AwsDevice\n",
    "from braket.ocean_plugin import BraketSampler, BraketDWaveSampler"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "# magic word for producing visualizations in notebook\n",
    "%matplotlib inline\n",
    "import networkx as nx\n",
    "import dwave_networkx as dnx\n",
    "from dimod.binary_quadratic_model import BinaryQuadraticModel\n",
    "from dwave.system.composites import EmbeddingComposite"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Device: Device('name': Advantage_system4.1, 'arn': arn:aws:braket:::device/qpu/d-wave/Advantage_system4)\n"
     ]
    }
   ],
   "source": [
    "# session and device\n",
    "device = AwsDevice(\"arn:aws:braket:::device/qpu/d-wave/Advantage_system4\")\n",
    "print('Device:', device)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SETTING UP THE MAXCUT PROBLEM "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# helper function to plot graph\n",
    "def get_graph(graph, pos):\n",
    "    \"\"\"\n",
    "    plot colored graph for given solution\n",
    "    \"\"\"\n",
    "    # positions for all nodes\n",
    "    # pos = nx.spring_layout(graph)\n",
    "\n",
    "    # nodes\n",
    "    nx.draw_networkx_nodes(graph, pos, node_size=700)\n",
    "\n",
    "    # edges\n",
    "    nx.draw_networkx_edges(graph, pos)\n",
    "\n",
    "    # labels\n",
    "    nx.draw_networkx_labels(graph, pos, font_size=20, font_family='sans-serif')\n",
    "\n",
    "    # plot the graph\n",
    "    plt.axis('off')\n",
    "    #plt.savefig(\"figures/random_graph.png\") # save as png\n",
    "    plt.show();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAn1UlEQVR4nO3deXzU1fX/8debECCEfXcBA9pqRXHfwa1Wa2Nd+vX7c621ahdsRevSNl2trcbaulStYFutu7ValWpcvtYNUFTcd6xCUFERgbAGsp3fH/eDJphlMpnMZ+Yz5/l45KGSmc89CBzu3HPvuTIznHPOZUePuANwzrlC4knXOeeyyJOuc85lkSdd55zLIk+6zjmXRT3jDsA557KprKJqBDALGA306cKj1gLvAROrK8s/TvVN8i1jzrlCUVZRNRCYA5QBxRl4ZD1QDexSXVm+PJU3+PKCc66QTAXGkJmES/Sc0dFzU+IzXedcQSirqDoYuAPo29r337/qJBpXtL5K0KN0EKNPu6m9x68BjqyuLL+/ozh8Tdc5l3hlFVUizEZbTbjrqXcpA3Y+9PM/3qukoyH6AlPLKqrGVleWtzuT9aTrnCsEewNDO3pRj96lDJp0XLpjDAUmATPaHSPdpzvnXB6ZApR28xil0Tjt8pmuc64QTATU4asa61n16qM0rliMinvTa8RYeo8ej3oUpTKGonHaf5EX0pxzSVZWUTUYWEQHOxbaKqT1HDiSoeVn0GfMtqkMVw+MqK4sr2nrBT7Tdc4l3VjC7oKB7b2o34QD6L3peHoNH4N6ldBQ8xErn7uXVS8+yMf/PJdR3/wDvUaO62isWmAc8HxbL/A1Xedc0vVO5UWDJh5LSdl2FJUOpkdxH3oNL2PoV3/IgF0PxxrWUTPrllQeYx2N50nXOZd067ry5n47HBwe8t5rqbxcHY3nSdc5l1iShn9w7ZQtramxf7rPKCoJqxJN9WtTeXkJMK+9F/iarnMuEST1BLYB9gT2iL6G1X8872lrqKtVr5K0toyt++BNAIoHjUrl5UvbK6KBz3Sdc3lK0lBJ5ZLOl/QIsBS4FdiZcEDhMGCImR3Uo1fJg4T11lbVf/IeTXWfn8k21Cxi6UPTACgdv19HIRmhe1m7fKbrnMt5koqArWk5i90IeAaYDfwBeNrMlrbxiMuBA4F+rX1z9RszWDHnbvqMHk/RgBH06FVCQ82H1L7zLNZQR8nmOzNgtyM6CnN1NE67POk653KOpMHAbnyWZHcl7LWdHX1dArxmZo0pPnIGsIQ2km6fzSZQv3QhdYvmsfb9N7D6tfToXUrvTbemdPx+lG6zP1KHZyuWADM7/Ln54QjnXJwk9QC2IiTX9Ul2NPAsIcE+CTxlZp90ZZyOuox1UcpdxjzpOueyStIAWs5idyOsx66fxT4JvGJmDZkeu6yi6hbgCLp2Y8SG1gJ3VVeWH5vKi315wTnXbRQ+k3+RlmuxYwkntmYT2i1+y8wWZSmkyYRCWxmZuznivei5KfGZrnMuYyT1J6y/rk+wuwMr+WwGOxt4yczq44rR70hzzuWlaBa7OS1nsV8AXqRZkjWzD+OKsS3RXWlTCdvK0lnjXQPcDZya6t1o63nSdc6lRFIp4aN58yS7lpaz2BfNrEvHbrNp45P/fHSPPqU3F/UfViupL+23fzTCtrAlwORUimat8aTrnPucaBY7ls+S6x6EHQav0HIW+35sQWaApF+CRm/203tuIjQgnwgMIXQLM0ISLiEU+mYR9uHO7OhKnnbH9KTrnJNUQpjFNk+yTbScxT5vZik1IMgHknoRrk8/yMxeWf/jZRVVgwjtGXsTmtfM6+hob6fG9aTrXGGJZrFjaJlgxwOv81mCnQ28awlOEJKOBU42sy9nddwE/z91zgGS+gA70jLJ9qTlLPY5M1sTW5AxkPQUUGlm07M6ridd55JF0qa0TLATgLm0nMXOT/IstiOSdiM0x/lCJ44SZ2bsAv7/7lzei9Yld6Blku1Ly1nsHDNbHVuQOUjSLcCzZnZJ1sf2pOtc/pC0ES0T7A7A27Scxb5dyLPYjkjaGHgNGGtmNVkf339tnMtNkoqB7WiZZAfyWXKdDTxjZitjCzIPSfotoc/uD2IZ35Ouc7lB0ghaJtidCFuams9i3zKzprhizHdRUXEBsLeZzY0jBm9441wMoqtltqVlkh0GPEVIrucTmnJ36oip69DRhP3GsSRc8Jmuc1khaRih+cv6BLsL8D4tZ7Fv+Cy2+0T7k58Dfm5maR3hzQSf6bpYlFVUDSYcM11/6md+dWX5snijyozoapnxfJZg9wRGAU+T2tUyrntMBEqBB+MMwme6LivKKqoE7M1n59sHEzo1rdcXWMZn59tndOV8ezZFV8s0n8XuCnxEy4JXZ66Wcd1A0u3A42Z2ZaxxeNJ13S26JmUqMJQw0+j2Tk7dJbpa5ku0XIsdDczhswTb5atlXGZJGgO8AJTFvdvDk67rNlHP0mnAoaTfs3Q6IfnGUlCSNJBwnUzzptyf0HIW2y1Xy7jMkXQh0NvMfhR7LJ50XXeIuzt/OqJZ7BdpuRZbRii+fJpkzaxb43CZFfXJXQDsbmbvxB6PJ12XadEMdw6ZvYeqGtglkzPeDa6W2ZMwi11Oy1lsrFfLuK6T9B3g62Z2aNyxgO9ecN1jKqF1YEoJd9Wrj7Lk3osBGHLwafTf7qANX1JMmDFPBVK6cXVD0XahLWg5i92CsM43G/gboc1fzl0t49IX/bqfHn3lBE+6LqOiotlhhK1gHWpYsZilD01DvUqwutr2XtoHOKysourgVIpr0dUyu9Cy4FXLZzPY64AXzKwulThd3to/+ucjsUbRTI+4A3DJEW0Lm0qKRTMzY0nVZRSV9Kf/9gen8pa+wNRonE8pGCfpOElXSnoe+BioBIYDNwI7mNkYMzvKzC4zs6c94RaEKcDludQAyGe6LpP2JmwLS8nKZ//N2gUvM/LYStYueCnVtw1tWLX0y5LW0XKpoIHPZrG3kLCrZVznSVp/U/ExccfSnCddl0lTCPtwO1T/yXvUPH49/Xc+lD5jtkk56VpTU791C998AHiekGBvA84g4VfLuLT8ALg2127E8KTrMmki7R98AMCaGvnk3ospGjCcQfuc0KkB1KMHfb+4xxIz2zXdIF3yRTtTvkXoN5xTfE3XZUTUS2FwKq9dPutW6hbNY1j5GfQoTqne1oKkwdGNrc615QTgUTN7N+5ANuRJ12XKWFr2UmjVug/msnz2Pxmw6+H03uRL6Y5VS7gi27nPiQ65TAH+FHcsrfGk6zKlwylrWFa4hOIhmzBo0je7MpalMp4rWAcSJgCz4g6kNb6m6zJlXUcvsLpaGpYuBODdPx7R6muW3n8FS++/gv47H8qQA77b1qOUyniuYJ0O/ClXC6uedF2mzKej/blFxfSbcGCr36pb9A51i96h96ZbUzxkU3pvslV7TyoB5qUbqEsuSVsCOwKt/62eA7z3gsuYsoqqRcCIdN5bM/Nmlj9xa1vHgDe0qLqyfFQ647hkk3QlsMzMfhl3LG3xNV2XSbMI663dycjRtToXr6gN57GEU5E5y5Ouy6TLzWx1dw4QbXS/vDvHcHnrJOABM/sg7kDa48sLLmPUo+jLm5x67QM9+w/rtlpBw/LFTQunnvQLsMvMrN0OOa5wRPfSvQUcZ2ZPxR1Pe3ym67pM0nBJN2BN166Z++T5pLBfN01r6pct/C7YLsCbko6JWvc5Vw58kusJFzzpui6IunudBLwGLAbGL33o6nMJV+xkutnMWmD6olt/fo2ZfYNw4uhs4ElJe2R4LJd/TidPlp086bq0SPoS8BgwGfiqmZ1lZquib08mXLGTqRsX6qPnTV7/A2b2OKFf7jTgdkn/kFSWofFcHpG0DeGy0NvjjiUVnnRdp0jqI+k8YCZwB+Heqeebvya6Umci4Yqdrs5410bPmbjhVT1m1mRm1wNbAm8Az0mqlDSgi2O6/DIFmJYv/ZE96bqUSToAeAUYD2xvZleYWWNrr40ukdwFuIv013jXAHcS7kZr8zJIM1ttZr8BJgAbAW9J+p4kP/yTcJKGAv8LXB13LKny3QuuQ5JGABcTmpT/0Mzu6cz7oyt8phIanJfSfvtHA1YDSwhXr3d4NU8r8e4EXAIMAc4ys//r7DNcfpD0E+BLZnZi3LGkypOua1PUrenbhGtvbgDObbZu2ynRFTuTCB8FJxISYi0hyYpwtHcp4eDD5cDM6srytH9zRrsaDgf+QNhKdLaZvZ7u81zuiT7JzAMO33CJK5d50nWtkrQ1oUjVB/iemb2QyedH/XDHEbqFrQPmVVeW12RyDABJvYAfAhXAPwl/cSzO9Dgu+yQdCZxuZpPijqUzPOm6FiSVAD8Hvg+cC0xta902n0gaBvyKcF/W74ErzMw7leUxSTMIv455sWthPS+kuU81K5RtCWxnZlcmIeECmNknZjaFsMSxN/CGpCP9cEV+krQDUEYo1OYVn+m69YWySwhrrT80s3tjDqnbRX/BXAysAM40szkxh+Q6QdLfgblmdmHcsXSWz3QLmKQekk4BXgU+BMYXQsIFMLP/EPquXgdMl3SjpNHxRuVSEU0SDgf+GnMoafGkW6CiQtnjwHeAA83snO7uEJZrzKzRzK4hLKcsAF6UdJ6kfjGH5tr3XeAOM1sSdyDp8KRbYCSVSPodMAP4B7Cnmb0Yb1TxMrOVZvYLwnXd44C5kk6KOle5HBLtRplMnvRZaI0n3QIi6St8ViibYGZ/TkqhLBPM7F0zOx74BnAy8Kyk/WMOy7V0JGEt95W4A0mXF9IKgKSRhELZXsAPzKwq5pByXrSr4UjgIuBl4BwzeyveqJykp4BKM5sedyzp8plugkWFsu8QZrcLCYUyT7gpsOB2QveqJwgtJC+TNCTm0AqWpN0Id/DldbHXk25CSRpPWLc9GfiKmf240AplmWBma83sImBrwum5uZLOiNYWXXZNAfJ+77gn3YSJCmUXEHrd3gLsZWYvxRtV/jOzj81sMrAvcBDwqqTD/HBFdkjaGDgYuDbuWLrKk26CSDqQsOd2c8KJsqvyfVaQa8zsNTM7mDDrugB4ODod5brX94Fbzawm7kC6ygtpCdCsULYnoVB2X8whFYSoy9UphB4V9wG/yPWbaPORpD6EfdT7mNmbccfTVT7TzWNRoey7hELZ+8A2nnCzx8wazGwaYQveYuAVSb+S1Dfm0JLmKOCFJCRc8Jlu3oruhboaKAK+a2YvxxxSwZM0FriQ8InjZ8DNZtYUb1T5LVozfw74uZl1uqF9LvKZbp6R1DcqlD0K3Eg4UeYJNweY2XwzOwo4mtDD92lJedXrNQftRbht5MG4A8kUT7p5RNJBhKWEcYQTZdN8JpV7zOwJYA/gUuBmSXdI2jzmsPLV6YSeuYn5fe7LC3lA0ijCH+DdgVOT8jGrEERN4c+Mvq4Fzk9CBT4bJI0BXgDKzGxl3PFkis90c1hUKPseYXa7gHCizBNuHjGzWjM7n3CD8iDC4YofSCqON7K8cCpwQ5ISLvhMN2dJ2pZQKBPhjjJft00ASdsRtvdtDJwN3Gf+h/Bzoh0gC4DdzeyduOPJJJ/p5pioUFYJPEK4gXcvT7jJEZ0OPAA4h3BzxYPRX7CupeOA2UlLuOBJN6dI+irhRNlYvFCWWFEznXuBbYF7CKfaro4OuRS8aJvY6eRxz9z2eNLNAZJGSboVuIpQKDvazD6MOy7Xvcys3syuIByuWAW8JqkiOoFVyPaL/vlwrFF0E0+6MYoKZd8nFMqqCSfKHog3KpdtZrbMzM4ibDPbBXhT0tEF3EzndODypK51eyEtJs0KZRAKZXnbCd9llqR9CMW2OsJNxbNjDilrJI0DngY2M7M1ccfTHXymm2VRoexCQqHsemCiJ1zXnJk9TpjxTgNul/QPSWXxRpU1PwSuTWrCBU+6WSXpYEKhbAywrZld7YUy1xozazKz6wnrvW8Az0mqlDQg5tC6TXQL87cItY3E8qSbBZI2knQbcCUw2cyONbOP4o7L5T4zW21mvwEmABsRDld8N2ormTTfAh41swVxB9KdPOl2o6hQNplwseE7hNltYhp3uOwxs4VmdiJwCGEP6wvR7c6JIKkHcBoJ3SbWXBL/tswJkiYQCmVNwH5m9mrMIbkEMLPnJO0LHA5MlTSXcFPx63HGlQEHArXAzLgD6W4+080wSaWSfk/YY/h3YJInXJdJ0eGKuwiXZT4MPC7pz5KGxxxaV0whwdvEmvOkm0HNCmWjCUsJf/FCmesuZlZnZpcQrolvBF6XdLak3jGH1imStgR2Am6NO5Zs8H26GSBpI+AyYGdCoez/4o3IFSJJWwEXETqa/QT4Vz7MHCVdCdSY2S/ijiUbPOl2QbT4/z3gPOAvwO/MrDbeqFyhk3QAoZnOCsLhijkxh9QmSQOB+YRPhgvjjicbvJCWpqhF39VAA7Cvmb0Wc0jOAWBm/5G0I3AiMF3Sw0CFmb0fb2StOgl4sFASLviabqdFhbKLgIeAa4C9PeG6XGNmjWZ2DeFwxQLgJUnnRQcQcoKkIsIJtD/FHUs2edLtBElfIxTKNiZ8HPqrF8pcLjOzldFa6Q6Eu/XmSjopSnhxKwc+MbOn4g4km3xNNwWSNiYUynYkFMoeijci59IjaTdCM52+hPXeR2OM5T/A383s5rhiiIPPdNshqUjSD4CXgLcIs1tPuC5vmdnTwETgAuBaSdMlfTHbcUjahrDP+PZsjx03n+m2QdL2hEJZHfB9X7d1SRM1S58C/Bi4CTjPzJZm6vllFVWDCbeg9AbWAfOrK8uXRWNfDSw0s/MyNV6+8KS7AUmlwLmE5hsVhI8/vm7rEkvSCOA3wP8A5wNTzayus88pq6gSsDchkU8EBgPNWzT2BZY1NdQ9vfj2c/db98HcLZrq1i7q8k8gz3jSbUZSOfBnYBZhvevjmENyLmskjQf+CGxOuDjz36keriirqDoYmAoMBUoJt1i3yszMGusbe/TstRCYXF1Zfn+Xg88jnnT5tFD2J0KF1wtlrqBFF6ReDCwCzjKzF9p6bVlF1UBCs/VDCTPZzloDTCck3+VpvD/vFHQhbYNC2Zt4ocw5onv6tgP+Cdwv6dpoYtJCWUXVCGAOoeNZOgmX6H1HAHOi5yVewSbdqFA2Gzga2MfMfulHeJ0LzKzBzKYRDlcsBl6R9EtJfeHTGe4soAzo6u3FfaLnzIqem2gFdww4OpFzLnACXihzrl1mthz4iaRpwIWEwxU/G/OTe74maQxQvOF7lj36d+o++i/1Sz+gqXYF6tmLogEj6PvF3em/0yEUlbR641AxoTvfVODYbvwpxa6g1nQlHUK4MmcmYa3KC2XOdYKkvfpuNfGaoeU/+kKP4t6tflJecNHh9Bq1OcVDR1NUOgirW8u6D+ZS99F/Keo3hFEnXEzPAW22/l0DHJnk4lpBJF1JmxAKZdsRCmX/iTkk5/JSWUWVzKw6muW2yhrqUM9en/vxZY/fwIrZ/6TfDl9j6EGntjfMAmBsdWV5IpNTotd0o0LZacCLwOuEQpknXOfSt7ekIe29oLWEC1C61UQAGpZ90NEYQ4FJacSWFxK7pitpB0KP21pCJ7A3Yg7JuSSYQtiH22lr3n4GgOLhZR29tDQaZ0Y64+S6xCXdqFD2G+B4QqHsOi+UOZcxE2nn4ENzy5++E6urpWndGuo++i/r3n+d4uFlDNzjfzt6q6JxEilRa7qSvk4olD0GnG1mi+ONyLnkiHopLKKVHQutee+K42laXfPpf/cZtxPDys+gqHRwKm+vB0ZUV5bXdPTCfJOImW5UKLsc2Bb4tpk9EnNIziXRWMLugpT20o4+7SYAGlcvY937b7Ds8ev58O+nM/zIX9F71BYdvb2W0P/3+S7Em5PyupC2QaHsVWCCJ1znuk1atwwXlQ6m75Z7MvKo39JYu4Il916Sytss3fFyXd7OdJsVytYAk8zszZhDci7p1nXlzT0HjqB46BjqP55H45rlFPVtd8Ksro6Xq/Jupiupn6RLgAeAqwiXQnrCda77zSf9HgsANK6K2vX26PC2oBJgXlfGylUZn+m217i4qyQdSiiUPQps44Uy57KnurJ8WVlF1TKgzcY09UsXUtR3ED36tNxVZtZEzYybaFpTQ+9NvkRRnw7vx1yaxCIaZCDpptK4OPqFmkUods3o7EkTSZtG790GONHXbZ2LzSxCV7BWt43VvvMsNY9fT+9Nt6bnwJH0KOlP4+oa1r33Kg01H1FUOpghB5/W0RgWjZNIXVpeiBoXzwfuJfxCjCBsJxnY7Ks4+vEjotfNj97XoahQNoVQKHsZL5Q5F7fLgdVtfbNP2Xb0m/AVGtcsZ81bs1nx9J2seetJevTpz8C9jmGjU66i17A2TxCvtzoaJ5HS2qebjcbFknYi3FG2inBHma/bOhez6JPtfGCzbhzGey80192NiyX1l3QpcB9h/XY/T7jO5YYFFx5StPThv81oql/XXQlxDWEylsiEC51Mut3duFjSYcBrwCBgvJldl+odTc657iWpDHhs5Zy7N6apcTqwNsNDrAWmJ7mtI3S+kDYVaLVxcZqKgdFN61ZfL8mArYFvmdmjGXq+cy4DJB0HXAr8Hri0R+++/QmfeMvITD6oB94DJmfgWTkt5TXdqPh1B20sKTTWrmDNW7OpfXsO9YsX0LhqCRT1pNfwMkq3PYB+Ew5Aan1i3VS/lpoZN920cs7dp5hZIjdEO5ePJA0i3JC9A3Csmb24/nvR0uAswo0PXfnku5aQcCdWV5Yn/mKBlJJuKovnK1+4j6UPXkVRvyH0HrMtPQcMp3F1DWvemo2tW03fLfdk2OEVSG02KEr04rlz+UbSJOBGoAo4x8zWbPiaaGlwKnAY6RfV7wZOLZTbgFNNuvsQtnu1uaO5tvolrH4tJVvs0mJG27hqGR/ecCaNKxYz7PAKSrfaq61HrALKqyvLE9lD07l8IakY+BVwCvAdM7u3o/dEn4SnEhqQl9J++0cjbAtbQiiaJXoNd0OpFtI6bFxcUrYdfb+w2+eWEIr6Dab/9mFb7rp3X2nvEesbFzvnYiJpC8KSwc7ADqkkXIAocY4FyoE7CS0g64EVwPLon/XRj98ZvW5soSVcSL2QlnLj4lYVRees2z9vnejGxc7lMoV1v28TCmXnAVd2dudQtDQ4I/qirKJqEKE94/qWAPOSerS3MzpcXuhs4+INWVMjH/59CvWLFzDi//2GknE7tffyxDYudi5XRXee/QX4IqFY9mrMISVaKssL6xsXp6XmseuoX7yAks137ijhwmeNi51zWSBpf+Al4F1gV0+43S+V5YW0GwmvePbfrHjmLnoO3ZShh5yVylsS27jYuVwiqRfwO+A44CQzezDmkApGKkk3rX2zK567h2X/+QvFw8Yw8ujzKSrpn8rbEtu42LlcIWkr4BbC3tjtvUVqdqWyvNDpxsUr5kxn2UNXUzx8M0YecwFF/VK6iA4S3LjYubgp+D5hd8LVwOGecLMv1X26i2incXFzy5+6g5rHrqN4xDhGHv3bjq7k2NCi6sryUZ15g3OuY5KGA9cAmwDHeROp+KS6T3cWYb21XTVP3ErNY9fRa9QWjDzm/M4m3EQ3LnYuLpK+SuhJ/TqwhyfceKW6T/dy4EDaOZG26pWHWT7zZlAPem86npXP/vvzgw0cSb8JB7T1iEQ3LnYu2yT1AS4EvgEc742kckOqSXcG4chem0m3oeaj8C/WxMpnp7f6mt6jt2kz6Vpj/QoVFc9MMR7nXDskbUsolr1JKJYtjTkkF8lYl7GusMaGusV3XVBb+/YztwC/MrNPMj2Gc4UgOll2GvBL4Bzgeu9JnVtSbmIenZHulsbFKur5r9q3nxkHNABvSDo9arrhnEuRpFGEG1eOJazd+iUAOaiz1/VMJuztq8/Q+J82LjazpWY2BdiX0Azj5agA4JzrgKRDCcWyOcAkM3s73ohcWzp9MWU2GhdHH5EOAS4B5gJnmdncLozlXCJJ6gtcDHwV+KaZ+Q6gHNfpiymjBLkLcBfp92RYQ2jvtktrneItuAcYDzwGPCHp4qiLvXMOkLQD8BzQn1As84SbB9K6gn29bDUuljSScE7864TmyteYWWO6cTuXzxSaVp8J/AQ4w8xujjkk1wldSrrw6VU+kwgNyCcCQwjdwoyQhEuApYQlicuBmeleyRP9zf4nYADhN9tjXQreuTwjaRPgBkJjqOPNrDreiFxndTnpbqi7GxdH673/C1xEKBqc47/xXCGQ9D/AVcAVwIVm1hBzSC4NGU+62SKpBDgbOIOwxHGhma2KNSjnuoGkfoRPePsQ+iY8HXNIrgs6XUjLFWZWa2a/BbYj3FL8pqRvqq173p3LQ5J2BV6I/nMHT7j5L29nuhuStAdhNtBEWO99KuaQnEubpCLgp4RayQ/M7I6YQ3IZkpikC59WdY8HKoFHgJ+a2cJ4o3KucyRtBtxIOKF5gpm9H3NILoMS9VHczJrM7AZgS8KdTy9L+kW0/utczpN0DKFAfA9wgCfc5EnUTHdDksYBfwB2JDT/+JefRXe5SNJA4ErCwaNjzez5mENy3SRRM90Nmdk8M/sf4CRC16XHJG0fb1TOtSRpL0LfhFXAjp5wky3RSXe9qHnzjoT+og9IulpSStcPOdddJPWU9BvgX8DpZjbZzNI9Wu/yREEkXQAzazSzq4GtCMeRX5N0VnQVtXNZJWlzYCawO2Er2OevWnGJVDBJdz0zqzGzMwlHl/cHXpV0SHTSzbluFd3IeyLwFPAP4GAz+zDeqFw2JbqQlgpJXyO0kKwGfmRmb8QbkUsqSYMJV59/iXCy7OWYQ3IxKLiZ7obM7D5gW+ABYIakP0V/OJzLGEn7Ai8BHwK7esItXAWfdAHMrN7MLgO2BnoRjhSfKinVizuda5WkXpIuJBRxv2dmp5tZbdxxufgU/PJCayRNAC4DhhOOFD8cb0QuH0nakpBsPwBONrPPNex3hcdnuq2IPvp9Gfg18FdJd0XVZuc6FBXLvkPoIf034FBPuG49T7ptiK4MupOw5PAM8LSkCyX1jzk0l8MkDSNcZXUqsLeZTfVTkK45T7odMLO1ZlYJTABGAXMlfdtbSLoNSTqQUCx7C9jdd8K41viabidF/U0vIxTcTjezJ+KNyMVNUh/gAsKNJid6DcC1x2drnWRmzwB7Efb2/kPSLZJGxxyWi4mk8cDThEb623vCdR3xpJuGaL33FsKR4v8CL0r6taS+MYfmsiQqlv0QeIzQPP9IM1sSb1QuH/jyQgZETacvIpyj/wlwmxdPkkvSSOBawpbC48zsvzGH5PKIz3QzwMwWmNlRhFsrfgzMlLRTzGG5biCpnNCG8QVgL0+4rrN8ppth0d1WJwK/A+4HfmZmH8UalOuy6PaRPwCHEK7QmRFzSC5P+Uw3w6IWktcQ1nuXELqY/VhS75hDc2mKGt8/BwwlFMs84bq0edLtJma23MzOAfYg7HZ4TdJh3kIyf0jqIelM4CHClrBjzawm3qhcvvPlhSyR9BXC/t4PCf0cXo03ItceSRsD1wN9gePNbH7MIbmE8JlulpjZQ8B2wN3AI5KulDQ03qhcayQdATxPuNlhH0+4LpM86WaRmTWY2ZWEJtYGvCFpiqTimENzgKR+kv4K/BE43MzOM7OGuONyyeJJNwZmtsTMTgP2I1TDX5J0UMxhFTRJuxBmt8WEYtlTMYfkEsrXdGMWFda+DlwMvAmcZWZvxRtV4Yi2+P0Y+BFwmpndFnNILuF8phuz6Ejxv4FtgBnAk5L+KGlgzKElnqQxwCPAQcDOnnBdNnjSzRFmts7M/gCMBwYRrgw6JZqJuQyTdBTwLOEAy5fN7N2YQ3IFwpcXcpSkHQmNVPoRWkj6hvwMkDQAuILQJ+NYM3su5pBcgfGZbo4ys+eBvYELgRsl/TNqrOPSJGkPQt+EtcCOnnBdHDzp5rBovfc2whazV4HnJP1WUmnMoeUVST0l/Zpwjc6ZZvY9M1sdd1yuMHnSzQNmtsbMzgN2AMYR1nuP9yuDOiZpHKFAuRdhdnt3vBG5Qud/aPOImb1nZscBRwGnA09E1we5DURNxk8g3OpwO/BVM/sg5rCc80Javopmud8kNGL5D1DhSSWQNBiYCmxLKJa9FHNIzn3KZ7p5ysyazOx6QgvJD4CXJf0suiSxYEnah1AsW0zYe+sJ1+UUn+kmRLR2+Udge+Ac4M5CujIo6l9xLnAScLKZ3RdvRM61zpNuwkjan9BCcgmhhWTiZ3qSvgDcAnwMnGRmi2IOybk2+fJCwpjZI8COwG3A/0maJml4zGF1i6hYdjLwJHAdcIgnXJfrPOkmUNRCchphvbcWeF3SjyT1ijm0jIl6Ef8LmALsa2Z/LqTlFJe/POkmmJktM7MfAZOAA4FXJH0t5rC6TNIBwEvAPGBXM3st5pCcS5mv6RaQKOFeCrxDOJn1ZswhdUp0uef5wNHAt6PbOJzLKz7TLSBRRX9bwkWLMyVdGu1pzXmStiYcdNic0GTcE67LSz7TLVBRce23wBHAr4G/mlljpp5fVlE1GBgL9AbWAfOrK8uXpRGngMnAeUAF8Ddfu3X5zJNugZO0HWGL2VDCFrNH0nlOWUWVCF3RpgATgcHAmmYv6QssA2YBlwMzqivL2/3NJ2kEcC0winCyzG/UcHnPk65bP5v8BuFwxQvA2WY2L9X3l1VUHUw4djsUKAXUzssNWE3YRzy5urL8/jZiOhi4hrAV7Fwzq0s1HudymSdd96noCPGZ0ddfgEozW9nW68sqqgYC04BDCTPZzloDTCck3+VRDCXA74HDgBPM7PE0nutczvJCmvuUma01swuACcAmhBaS32qthWRZRdUIYA5wOOklXKL3HQHMKauoGiFpQvTMkYRimSdclzg+03VtkrQbYb23iHBl0Gz4dIY7BygjXFneJWZW37R2Vc3Caaf0sHWrzwRu9GKZSypPuq5d0Sz3GMK1QY8DP93sp/deRFgD7t38tavfnMW6d1+l7uN51H08H6urpXT8vgz7+tkdjtPUUG9Wv/be9y47+tBu+Gk4lzN8ecG1K2oheTPhyqD5JVvs+po1NhzJBgkXYPmTt7Hy+Xup+3g+Rf2HdmqcHj2LVVTS/8tRUc65xPKZrktZWUWVrLHhPRX13KS1769d8DJF/YfSc/DGrHv3FRbd+rOUZ7rNLADGdrSdzLl85TNd1xl7q6jnwLa+2WezCRQP2YSwAy1tQwm9IpxLJE+6rjOmEPbhdqfSaBznEsmTruuMibR/8CETFI3jXCJ50nUpiXopZKs5zpCyiqpBWRrLuazypOtSNZaWvRS6Uy0wLktjOZdVnnRdqj63RawbWZbHcy5rPOm6VK3L4ljK8njOZY0nXZeq+aTfY6GzSghX8TiXOJ50XUqiBuSdbkKepqXVleU1WRrLuazqGXcALq/MInQFa3Xb2Jq3ZrPmracAaFwd8vO6hW/yyb2XAlDUdwCD9z+5ozEsGse5RPKk6zrjcsKtwv1a+2bdonmsfvXhFj/WUPMRDTUfAVA0YEQqSXd1NI5zieRJ13XGDMKND60m3UGTjmPQpOO6OsYSYGZXH+JcrvI1XZeyqAnNZLpvv+4awi0S3uzGJZYnXdcp0Z1m04G1GX70WmB6W3emOZcUnnRdOiYD7wH1GXpeffS8yRl6nnM5y5Ou67ToEsmJQDVdn/GujZ4zcf3llM4lmTcxd865LPKZrnPOZZEnXeecyyJPus45l0WedJ1zLos86TrnXBb9f/eP3uSa2FfZAAAAAElFTkSuQmCC\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Copyright 2019 D-Wave Systems, Inc.\n",
    "#\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "# ------ Import necessary packages ----\n",
    "from collections import defaultdict\n",
    "\n",
    "# from dwave.system.samplers import DWaveSampler\n",
    "# from dwave.system.composites import EmbeddingComposite\n",
    "\n",
    "# ------- Set up the graph -------\n",
    "\n",
    "# Create empty graph\n",
    "G = nx.Graph()\n",
    "\n",
    "# Add edges to the graph (also adds nodes)\n",
    "G.add_edges_from([(1,2),(1,3),(2,4),(3,4),(3,5),(4,5)])\n",
    "\n",
    "# plot graph\n",
    "pos = nx.spring_layout(G)\n",
    "# plot graph with labels\n",
    "get_graph(G, pos)\n",
    "\n",
    "# ------- Set up the QUBO dictionary -------\n",
    "\n",
    "# Initialize our Q matrix\n",
    "Q = defaultdict(int)\n",
    "\n",
    "# Update Q matrix for every edge in the graph\n",
    "for u, v in G.edges:\n",
    "    Q[(u,u)]+= -1\n",
    "    Q[(v,v)]+= -1\n",
    "    Q[(u,v)]+= 2\n",
    "\n",
    "# print Q matrix\n",
    "# print('Show Q matrix:', Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## SOLVING THE MAXCUT PROBLEM ON DWAVE"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "------------------------------------------------------------\n",
      "          Set 0          Set 1    Energy        Cut Size    \n",
      "------------------------------------------------------------\n",
      "      [1, 4, 5]         [2, 3]     -5.0             5       \n",
      "         [1, 4]      [2, 3, 5]     -5.0             5       \n",
      "         [2, 3]      [1, 4, 5]     -5.0             5       \n",
      "      [2, 3, 5]         [1, 4]     -5.0             5       \n",
      "\n",
      "Your plot is saved to maxcut_plot.png\n"
     ]
    },
    {
     "data": {
      "text/plain": "<Figure size 432x288 with 1 Axes>",
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAV0AAADnCAYAAAC9roUQAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjQuMiwgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy8rg+JYAAAACXBIWXMAAAsTAAALEwEAmpwYAAAzOUlEQVR4nO3deVxU57348c8M+yYCgvuCoCAKooIgi8qWxqRpmra5Lo2JadqmNq9sbZJf7ZbkpqldvKa5SePN0sQkptH0Jte0jVnYFBXZBAV3JFFURBAQQXbm/P4YPXFgVMCBMzN836+Xr+Q5z5k535jhy5nnPM/30SmKghBCiKGh1zoAIYQYTiTpCiHEEJKkK4QQQ0iSrhBCDCFJukIIMYQcr9c5atQoZcqUKUMUihBC2Ie9e/eeVxTF31zfdZPulClTKCoqGpyohBiAmo4ONlZXU9rcTGNXF96OjkR4enL/mDH4OztrHZ6wdTU1sHEjlJZCYyN4e0NEBNx/P/ibzaFm6XS6k9fsu9483aioKEWSrrAGhRcvsraykk/r6gBou+pz66bXowBLfH1ZM2kS0SNGaBSlsFmFhbB2LXz6qbHd1vZ1n5sbKAosWQJr1kB09A3fTqfT7VUUJcpcn4zpCqu34cwZFu/bx9bz52lTFJOEC9BqMNBmMLD1/HkW79vHhjNnNIpU2KQNG2DxYti61Zhsr064AK2txmNbtxrP27Dhpi533eEFIbS24cwZnqiooMVguOG5CtBiMPBERQUAq8ePH+TohM3bsAGeeAJaWm58rqIYz3viCWN79eoBXVLudIXVKrx4sc8J92pXEm/RxYuDFJmwC4WFfU+4V7uSeAc49CpJV1ittZWVtJpLuM8/D9/9Ltx+O6xcCZ980uuUVoOBtZWVQxClsFlr1xqHDnpYDLgCnpf/hJh7bWur8fUDIMMLwirVdHTwaV0dZh/zrlgBTz4Jzs5QWQmPPQbBwRDy9Y+HAmyrr6e2o0NmNYjeamqMD82uMZHgZeCH13u9osC2bVBb269ZDSBJV1ipjdXV1+4MDDRt63RQVWWSdAFQFNYfPsxPRo7s9RY6nc6k7e/vj5ubm8mxqqoqDJfvtMeOHYuDg4Pa19XVxblz5675fuaOXe8cf39/9Pqvv3h2d3dTd3mmhoODA35+fiava29vp6mp6YbX7MsxvV6Pt7e3SX9nZyctl792Ozk54e7ubtLf1tZGR0fHgK959TEHBwdcXFx6Xb+rq0u9vqOjaarq6OjA3Myrvv6d6958Ez3Qu7cfdDrj9LInn+zXyyTpCqtU2tzca5aCiRdegM8/h/Z2mDYNYmN7ndKmKGw7fBiXI0dueL177rmH4OBgk2ObNm1SE89TTz1lkniam5t5/fXX+/hfc2M937+pqYlXXnkFgJEjR/LYY4+ZnF9RUcEHH3xgkWube//y8nL1/WfMmMHSpUtN+nfv3s3OnTstcn1z75+Tk6O+f0pKComJiSb9W7ZsoeLyA9OBuOujj5jdc5bCVdYAv8A4tPA8xiGHXlpboays39eWpCusUuPlu5xrevxxeOQROHQI9u0DJyezp7U5DvwjLrWm7ZfrdRLuH4EwwBnYDNwB7AOCzJ3c0NDva0vSFVbJuy/J0sEBwsMhPR0+/tj4cK0HPxcXJk+eDPROole3XV1de7123LhxtLe3A5h89Tde2oFx48Zd8/36e6zn++v1evwvjxV6eXn1Ot/Z2ZlRo0aZfb/+xjHCzGISJycndcih59ACgIuLS6+4+nJdc+f0HFoAcHR0VP+fXD2sc3V8Li4uA/477+gxlHS1mKv+/T7gfWAb8LC5k318rvk+1yIr0oRV+kVJCf9VX0+XmR+4Xv78Z3B1hYdNfyzc9HqenTKFJydNGqQohc3605/g6ad7L4QwY8nlP4/07HBzg2efNTumKyvShM350aRJxgcVPTU0QFaWcTytuxsKCoztuXN7naoAq8aMGfxghe1Ztcrs4QvA50Ab0AW8B+QAt5o7WVGu+T7XI8MLQnOnT59mxIgRJl9zg/z8mNfVRYGTE8rVyVenMw4lrF9v/NCPHg0PPQTx8SbvqQNu8/WV6WLCvIAAYy2FrVtNpo11Ar8GjgAOQCiwFZje8/U6Hdx2W7+ni4EMLwgNVVZWkpGRQWVlJbGxsdx6q+n9xM7aWm49fLjfK9IA3PV6dkRGEiXFb8S1FBaiLF6Mrr8r0gDc3WHHDogyO4IgwwvCOnV0dFB5edVYcXExrT1WByX6+7MuKAh3ff8+pu56PeuCgiThiuuLjmZbcjKX+vs6d3dYt+6aCfdGJOmKIdHS0kJ3d7fJsaCgIAICAnBwcCAsLEydDH+11ePHq4n3hhPZFQVng4F1QUFS7Ebc0M6dO/nWtm38HLgE3PD7lE73dcIdYLEbkDFdMcgaGhrYs2cPJSUl3HHHHURERKh9Op2Ob3/723h6epqdtnTF6vHjifbyYm1lJdvq69GBSU0GV52Oru5uguvqSKysJKnHVC4heqqrq2PFihUYDAZeBQxz5vA/kyfDZ58Zk+vV37qu1NO97TZjPd0B3uFeIUlXDIqqqip2797NoUOH1DmSubm5hIeHmyzN7DnX9VqiRozgw1mzqL28c0TZpUs0dHbi4+REuIcHEw8d4sjBgwCkp6czbdo0s/M7hVAUhQceeIDTp08D4Ovry2//+U/0EyYYayls3GhcadbQYJyHGx5unKUwgIdm5kjSFRajKArl5eXk5uZy4sQJs+e0tLTg4eEx4Gv4OzubnXfbMmoUX5WU0N7eTl1dHcXFxUT3ocK/GH7++te/8vHHH6vtt956iwkTJhgb/v79rqXQX5J0xU3r6uqirKyM3Nxcamtre/UHBQURFxfH1KlTzRYgsQR3d3cSExPJyMgAYPv27URERJhd7SSGr3379vHzn/9cbT/88MN861vfGtIYJOmKAWttbWXv3r3k5+f3qnil1+uZNWsWcXFxjBmiBQoxMTEUFBRw8eJFLl26RG5uLklJSUNybWH9mpubWbZsmVodLTIykj/96U9DHockXdFvFy5cIC8vj+LiYvUDfIWzszPz5s0jNja2V7nAwebk5ERycjJbt24FjGPIUVFRZmsXiOHn4Ycf5ujRowB4eHiwefNmszU3BpskXdFnZ8+eJTc3l4MHD6p1Zq/w8vIiNjaWefPmafJBviIiIoI9e/Zw7tw5Ojs72b59O3fccYdm8Qjr8N5777Fx40a1/de//pWQnvWXh4gkXXFDNTU1fPbZZ3z55Ze9+gICAoiLiyM8PNwqZgvo9XpuueUW3n33XcC46CI2Nlat2CWGn+PHj/OTn/xEbd9zzz3ce++9msUjSVfckLOzc6/ZCIGBgcTFxREcHDxoD8cGKigoiKCgICoqKnBzc6OhoUGS7jDV0dHBsmXLaG5uBiA4OJhXXnlF08+sJF1hoq2tDUVRTLauGTlyJDNnzuTgwYOEhYURFxfX5/m1WklLS2PcuHHEx8drOtwhtLVmzRr27t0LGMf8N2/erPkYvxS8EQBcvHiRvLw89u7dS1RUFGlpaSb9DQ0N6HQ6RprZb0wIa7Rt2zZuv/12tb1+/Xoef/zxIbm2FLwRN1RVVUVubi7t7e0UFRWpOyZc4ePjIwlX2Iyqqiruu+8+tX377bf32gdOK5J0hyFFUXptXxISEqJu/+Ll5cWFCxc0iGxwVVVVmS2qI+xLd3c399xzD+fPnweMS83feustq3n2IGO6w0h3dzcHDx4kNzeXxMREZs6cqfbpdDpuueUWFEVh+vTpVvMBtYSGhgYyMzM5cOAAt956K7Fmdg4W9uMPf/gD2dnZgPFzvWnTJqt6kCpJdxhob2+nuLiYvLw8GhsbAePCgbCwMJPkOn16r/r4duHo0aMcOHAAgB07dhAZGSkP1+zU7t27efrpp9X2r3/9a6tblShJ1441NTWRn59PUVERbT024KupqaGhoQFfX1+Nohs6UVFR5Ofn09DQQGBgIJ2dnZJ07VB9fT0rVqxQ6zYnJCTw29/+VuOoepOka4dqamrIzc2lrKysV+FwDw8P5s+fT3R0tNmtte2Ro6Mjd9xxB05OTkycOFHrcMQgUBSFH/7wh+pOJD4+Prz33ns4OlpfirO+iMSAKIrCiRMnyM3Npby8vFe/n58fcXFxRERE4OTkpEGE2po6darWIYhB9D//8z/83//9n9p+8803mWSmBKg1kKRr4wwGA4cOHSI3N5eqqqpe/RMnTiQ+Pp6QkBC7ejgmxBWlpaUm828feughvv3tb2sX0A1I0rVRHR0dlJSUsGfPnl7Tu3Q6HaGhocTFxcnX6Wvo6Ojg0KFDREZGah2KuAmXLl1i6dKl6rzyiIgI1q1bp3FU1ydJ18a0tLSQl5dHYWFhr91zHR0diYyMZMGCBfj5+WkUofUrLi4mKyuL5uZmvLy8CAoK0jokMUCPPvooR44cAYyF7Lds2WL1D0kl6dqYtrY2du7cabK4wd3dnejoaObPn39TW+EMF2fOnFELoKSnpxMYGIi+n9u8C+1t3ryZv/3tb2r75ZdfJjQ0VMOI+kaSrhVTFAWDwWBSMtHX15cZM2Zw6NAhfH19WbBgAZGRkcPy4dhALV68mNLSUjo7O6murqasrIzZs2drHZbohy+//JIf//jHanvFihWsWrVKu4D6QZKuFTIYDBw5coTc3FymTp1KcnKySf+iRYuYNWsWoaGhcoc2AF5eXsTFxbFjxw4AsrKyCAsLk19cNuJKucYrW0QFBQWxYcMGm3lQLD+xVqi8vJwPPviA06dPU1hY2GtLnNGjRxMWFiYJ9ybExcWpQzGNjY3k5+drHJHoq1/96lcUFhYCX5drHDFihMZR9Z381FqhadOm4ePjAxh/q58+fVrjiOyPi4uLyfLQnTt30tLSomFEoi8+++wzk9kJa9euJSrKbAVFqyVJV0N1dXX8+9//5tixYybH9Xo9ixYtYuHChTz++OMysX+QzJkzR62s1t7eTk5OjsYRies5e/asyTY7S5YsGbL6uJYkY7oaOHXqFLm5uRw5cgRFUaipqelVbEbmjw4+BwcHUlNT2bx5MwCFhYXMnz9/WNSjsDUGg4GVK1dSW1sLwNixY9m4caNNDrFJ0h0iiqJw9OhRdu/ezalTp0z6KisrOXv2LGPHjtUouuErJCSESZMmUVlZSXd3N1lZWXzve9/TOizRwx//+EcyMzOBr8s1BgQEaBzVwEjSHWSdnZ3s37+fPXv2UFdX16t/2rRpxMfHM2bMGA2iE1fqCL/xxhsAHDhwgAULFjB+/HiNIxNX7Nmzh9/85jdq+5e//GWvGT22RJLuIGlpaaGwsJCCggIuXbpk0ufg4EB4eDhxcXE2+9vankyYMIGwsDAOHToEGBdM3HfffTYzBcmeNTQ0sHz5crVaXlxcHM8884y2Qd0kSboWVl9fT15eHiUlJXR2dpr0ubq6EhUVRUxMjOY7kgpTKSkpHDlyBIPBwIkTJzh27BghISFahzWsKYrCj370I06ePAkYd6X++9//bpXlGvvDtqO3IqdPnyY3N5fDhw/32n/M29ub2NhY5s6di4uLi0YRiuvx8/MjOjpana+bkZHBtGnTbPJBjb147bXX+PDDD9X23/72NyZPnqxhRJYhSfcmKIrCsWPHyM3NVX8bX23MmDHEx8cTFhZmspRXWKeFCxeyb98+2tvbqa2tpaSkhHnz5mkd1rB04MABk917V69ezXe+8x3tArIgSbo3oaGhgc2bN/e6sw0KCiI+Pp7AwEAZF7QhHh4eJCQkqE/Js7OzCQ8Px9nZWePIhpeWlhaWLl2qbjEVHh7Of/3Xf2kcleXId6eb4Ovrq4776fV6Zs+ezerVq1m5ciVTp06VhGuDYmNj1SWlzc3N7NmzR+OIhp/HHntMfajp5ubGli1bcHNz0zgqy5E73T64cOECeXl5jBgxgri4OJO+hIQEfH19iYmJwdvbW6MIhaU4OTmRlJTExx9/jIuLi9XXZrU3W7Zs4fXXX1fbL730EjNmzNAwIsuTpHsDlZWVvPXWWyiKgoeHB9HR0SbVqCZMmMCECRM0jFBY2uzZs2lubmbevHnDZvNOa/DVV1+ZlGtcunQpP/jBDzSMaHDI8MINjB8/Xv26eenSJQ4fPqxxRGKw6fV6EhMTJeEOoc7OTpYvX87FixcBCAwM5NVXX7XLITq5072su7ubsrIyfHx8TKalODg4sGDBAo4dO0ZcXJxs7SLEIPjNb36jTtdzdHRk8+bNdjtcN+yTbltbG0VFReTn59PU1ERgYCD33XefyTkxMTHExsZqFKGwBjU1NRgMBlmuPQi++OIL/vjHP6rt3//+98yfP1/DiAbXsE26jY2N5OXlUVxcrO4kCsZxpaqqKsaNG6ces8evOKJvmpubycrKoqSkhPHjx/PAAw/I58GCqqurWblypdr+xje+wc9//nMNIxp8wy7pVldXk5uby4EDBzAYDCZ9np6exMbGSmk/oerq6mL//v0oisLp06c5fPgwYWFhWodlFwwGA/feey81NTWAcUeUt99+2+5XAQ6LpKsoCl9++SW7d+/myy+/7NXv7+9PXFwc4eHhNr+uW1jWyJEjiYmJITc3l+DgYLXoubh5f/7zn0lPTwe+Ltc4evRojaMafHadYbq7uzl48CC5ublUV1f36p8yZQpxcXFMmzZNvjKKa0pMTCQ4OFh28LCgvLw8fv3rX6vtX/ziF6SmpmoY0dCxy6Tb3t7O3r17ycvLU6egXKHT6QgLCyMuLk5qpoo+cXNzk4RrQRcuXGD58uV0dXUBxlWAzz77rMZRDR27SroXL14kPz+foqIik4djYFxpNHfuXGJjY9VNH4UQQ0tRFH784x9z4sQJwFiB7/333zdZcGTv7CbpNjU18eKLL6rFjq/w8PAgJiaGqKgomewuLKKrq4uCggJmzZplU1t/W4M33niDf/zjHybtKVOmaBeQBuwm6Xp5eREYGMjx48cBY33UuLg4Zs+eLQ/HhMWUl5fz73//m8bGRmpra7nzzju1DslmHDx4kEcffVRtP/jgg8NyPzqby0YGg4GDBw9iMBiYPXu2SV98fDwdHR3ExcUREhIiD8eExTk6OtLY2AjAvn37iI2NHRZP3G9Wa2srS5cupbW1FYCZM2fywgsvaByVNmwq6dbW1rJp0yYaGxvx9PRk5syZJnexU6ZMscsCGcJ6BAYGMm3aNMrLy1EUhYyMDL7//e9rHZbVe/zxxzl48CBgn+Ua+8OmZiH7+vqqCxqam5spLS016Zc7WzEU0tLS1M9aeXm52bnf4mv/+7//y6uvvqq2X3zxRWbOnKlhRNqy2qRbW1vLuXPnTI45ODgQGxuLu7s7ixcvlo0DhSYCAgKIjIxU2+np6b12DxFGJ06c4Ic//KHavvvuu03aw5FlhxdqamDjRigthcZG8PaGiAi4/37w97/hyxVF4eTJk+Tm5nLs2DGCgoJM1mUDzJ8/n/nz5w+rKSbC+iQlJXHgwAE6Ozs5e/YsZWVlREREaB2WVens7GTFihXqGPiUKVN47bXXhv03Ussk3cJCWLsWPv3U2L68txEAH30ETz8NS5bAmjUQHd3r5QaDgcOHD5Obm8uZM2fU4xUVFVRXV5tUdpJkK6zBiBEjWLBgATk5OQBkZmYSFhYmM2Wu8vTTT6vbHTk4OPD+++8zcuRIbYOyAjc/vLBhAyxeDFu3GpPt1QkXoLXVeGzrVuN5GzaoXR0dHRQUFPDSSy/xj3/8wyTh6nQ6QkNDZRddYbXi4+PVud+NjY0UFBRoHJH1yMjI4A9/+IPafv7556U86mU392t5wwZ44gloabnxuYpiPO+JJ2hrbyc3IoLCwkJ1CokakKMjs2fPZsGCBVJcRFg1FxcXFi9ezLZt2wDIyclhzpw5w/ap/BXnzp1j5cqV6jh3WloaTz75pMZRWY+B3+kWFppNuC8DUYALsMrc61pa0D/1FMc3bzZJuG5ubixcuJDHHnuMO+64QxKusAnz5s3Dz88PMBbEvzLcMFwZDAbuu+8+tcBUQEAA77zzjt2Xa+yPgf9NrF1rHDroYRzwa+B6s2UdOztJ2LkTAB8fH2677TYef/xxkpOT8fT0HHBIQgw1BwcHUlJS1HZBQQENDQ0aRqSt9evX8/nnn6vtd999V3bb6GFgwws1NcaHZmamyXzn8j+LgNPXeLkemH78OMtSUpgeHy+/BYVNmzFjBhMmTOD06dN0d3eTlZXFd7/7Xa3DGnIFBQWsWbNGbT/11FPccsstGkZknQaW7TZuvOkLOzg5EZqXJwlX2DydTmeSXMrKyqiqqtIwoqHX2NhoUq4xJiaG3/3udxpHZZ0GlvFKS3vPUugnXWsrlJXd1HsIYS0mTZrEjBkz1PYXX3wxbBZMKIrCgw8+qK7MGzFixLAr19gfA0u6lyc737RhPPYl7E9KSor6ze3EiROUl5drHNHQePPNN9myZYvafv311wkMDNQwIus2sKRrqf3opZi4sCOjRo1i3rx5ajs9Pb3X5qf25vDhwzz88MNq+0c/+hH/8R//oWFE1m9gSTciAlxdzXZ1AW1A9+U/bZeP9eLmBuHhA7q8ENZq0aJFODs74+TkRFhYmF0n3Z7lGsPCwvjLX/6ibVA2QHe9caeoqCilqKiod0dNDUyebHZc9xmg525HT18+bsLVFSor+1STQQhbcuzYMcaOHYuXl5fWoQyqhx56iFdeeQUAV1dXCgoKCJcbKQB0Ot1eRVGizPUN7E43IMBYS8FM4YpnAKXHn2d6RwS33SYJV9il6dOn233C/eijj9SEC/DCCy9Iwu2jgc/XWrPGOEQwEG5uxtcLIWzOyZMneeCBB9T2d7/7XR588EENI7ItA0+60dGwbh30c7NHxd3d+Loos3feQtid+vp6SkpKtA7DIrq6ulixYgUXLlwAYPLkybz++uvDvlxjf9xcwZvVq43/fOIJ45Lg64wPG4AuJyfO/+xnjLvyOiHsWHd3N1988QVFRUUoisKkSZPUOg226plnniE3Nxf4ulyjj8xC6pebXw62ejXs2AF33WV8ONZzyMHNjW4nJ46EhrJx1Sr+19+/1zbpQtgjvV7PuXPn6O7uxmAwkJGRoXVINyUrK4vf//73avu5555jwYIFGkZkmyxTcTkqCj78EGprjUuEy8qMCx98fCA8nI6lS/nX++8bp5bU11NUVERMTIxFLi2EtdLpdKSlpfH6668zadIk4uPjtQ5pwGpra7nnnnvUVXYpKSn8v//3/zSOyjYNbMrYAOzZs0etPuTu7s4jjzyC6zXm+gphT86cOcO4ceNsdtzTYDDwzW9+k08v7wzj7+/P/v37GTt2rMaRWS/LTxkbgOjoaHWrjpaWFnbt2jVUlxZCU+PHj7fZhAvwl7/8RU24AO+8844k3JswZEnX0dHRpO5oXl6eumGdEMI6FRUV8Ytf/EJtP/HEE9x6660aRmT7hrSu4qxZsxg3bhxgnHqSnZ09lJcXQnPd3d0UFhayf/9+rUO5oYsXL7Js2TI6OzsB47fV559/XuOobN+QJt0rDxau2L9/P+fOnRvKEITQzPnz53nllVf45JNP+OKLL2hvb9c6pGtSFIXVq1dTUVEBgJeXF5s3b8bZ2VnjyGzfkFcQDwwMZNq0aYDxf2x6evpQhyCEJry9vdUi35cuXWL37t0aR3Rtb7/9Nn//+9/V9muvvcbUqVM1jMh+aLJtQ1paGjqdjsDAQJKTk7UIQYgh5+TkZPJ537NnD01NTRpGZN6RI0d46KGH1PYDDzzAsmXLNIzIvmiSdAMCAvjJT37Cvffeq47xCjEcREREqBs1dnZ2Wt1zjba2NpYtW0bL5V2+Q0NDefHFFzWOyr5otkHZ6NGjbXoajRAD0fO5RklJCTU1NRpGZOrJJ59UH/K5uLiwZcsWPDw8NI7KvsiukEIMsaCgIIKCggDjcw1rWR68detWXn75ZbW9fv16IiIiNIzIPllF0u3u7iY/Px9LrX4Twtpdea4BxqLnX331labxnDp1ih/84Adq+6677mK1FKYaFJon3fr6el5++WU+/fRTMjIy1K0/hLBnY8aMYfbs2Wo7PT1ds92Dr5RrbLi8UezEiRN54403ZPhvkGiedL29vdUdVNva2sjPz9c4IiGGRlJSEo6OxppTVVVVHDhwQJM4nnvuOXVZ/pVyjb6+vprEMhxonnQdHBxITU3Fzc2Nb3zjGyQkJGgdkhBDwtvbm9jYWLWdmZmpzuMdKtnZ2Tz33HNq+9lnn7Xpami2wDKlHW9SaGgogYGBUnVMDDsJCQkUFxfT0tLChQsXKCwsHLIatefPnzcp15iUlGRSZ0EMDs3vdME4jUYSrhiOXF1dWbhwodrOyckZkucaiqKwatUqqqqqABg1ahSbNm3CwcFh0K893FlF0r0WrR4sCDGUoqOj1S1vWltbh6Ts6Ysvvsgnn3yitt9++21ZqDRErDLpVldX8+6771JeXq51KEIMOgcHB5Oyp/n5+erGj4Nh7969PPXUU2r7Zz/7GbfddtugXU+Ysrqku3//fl599VUqKipIT0/HYDBoHZIQg27mzJmMHz8eGNyyp01NTSblGufNm8fatWsH5VrCPKtLusHBwTg5OQHGfZn27dunbUBCDIGey4NLS0s5e/asxa/z0EMPcfz4cQA8PT2lXKMGrC7penh4mEwby87OpqOjQ8OIhBgaU6ZMISQkBAcHB2JjY9XtrSzlnXfe4d1331Xbr776KsHBwRa9hrgxq5gy1lNsbCyFhYU0NTXR1NREXl6eyRNeIezVla1wrjxYs5Rjx47x05/+VG2vWrWKFStWWPQaom+s7k4XwNnZmaSkJLW9a9cuLl26pGFEQgwNHx8fiyfc9vZ2li5dqv4MhYSE8NJLL1n0GqLvrDLpAkRGRhIQEABAR0cHO3bs0DgiIWzTU089pT4bcXFxYfPmzXh6emob1DBmtUlXr9eTmpqqtouKiqirq9MwIiGGXmNjI5999pk626C//vnPf/Lf//3fanvdunVERkZaKDoxEFabdAGmTZtGYGAgAAaDwWrqjgoxFHbv3s1LL71EXl7egApBnT59mvvvv19t33nnnSbb8AhtWHXS7TmN5vDhw5w6dUrDiIQYOi4uLmoBnJ07d9LW1tbn13Z3d/P973+f+vp6ACZMmMCbb74p5RqtgFUnXYBx48YRHh6utr/44gtZHiyGhblz5zJq1CjGjh3LsmXL+lWf5He/+x05OTmAcaju73//u5RrtBJWOWWsp+TkZA4dOkR3dzenTp3iyJEjzJgxQ+uwhBhUer2ee++9Fy8vr37doe7YsYP//M//VNvPPPMMiYmJgxGiGACrv9MF4zSa+fPnq+2MjAy6u7s1jEiIoTFixIh+Jdy6ujq+//3vq8vnFy9ezC9/+cvBCk8MgE3c6QIsXLiQkpIS2traqKuro7i4mOjoaK3DEmLo1dTAxo1QWgqNjeDtDRERKKtWcf8Pf8iZM2cA8PPzk3KNVshmkq6bmxuJiYmkp6cDsH37diIiInBxcdE4MiGGhiE/n4tr1uC1axd6Bwd0Vz9Y++gjun/1K1Z1dXEWKAI2btyoFtER1sMmhheuiImJwdvbG4BLly6xe/dujSMSYmgYXnmF7oULGZGdjUNnp2nCBWhtxbGrizuB7cAHycl885vf1CBScSM2lXQdHR1N6o7u2bNHdg8W9m/DBvRPPolTR8cNf2AdAA/ge3l5sGHDEAQn+sumki5AeHg4Y8aMYfz48dxzzz24ublpHZIQg6ewEJ54AlpazHaXA67APT2O61pajK8rKhrsCEU/2cyY7hU6nY6VK1fi7u4uE72F/Vu7Fq7zbe4h4JqPk1tbja//8MPBiEwMkM3d6YKx5q4kXGH3amrg00/hGouBNgMjgRSzvRhft20b1NYOTnxiQGwy6QoxLGzceM2ui8BvgfU3eg+d7rrvI4aezSddg8FAcXEx77//viwPFvaltBSuUW/hN8ADwIQbvUdrK5SVWTgwcTNsbkz3agaDgTfeeIOqqioADhw4YFKnQQib1tho9vA+IAMo6ev7NDRYJh5hETZ9p6vX65k6daraLigo0DAaISzs8pz0nrYDJ4BJwBhgHfAhMPda72PhnSjEzbHppAuQkJCAj48PycnJrFy5UutwhLCciAi6Lu+MfbUfAxUY73j3AT8Bbgc+N/cebm4g3/6siu5646BRUVFKkQ3M8zMYDOj1Nv/7QwhTNTUYJk5Ef4PdsJ8BjgObzHW6ukJlJfj7Wz4+cU06nW6voihR5vrsIlNJwhX2oKmpyfRAQAAsWYLhBtMjn+EaCVeng9tuk4RrZew2W0npR2ErLl68yL/+9S9eeOEFTp8+bdKn/9Wv0A101aWbG6xZY4EIhSXZXdI9f/48mzdv5uOPP9Y6FCH6JCMjg71796r7AJoM+UVHo1u3Dtzd+/em7u6wbh1Emf2GKzRkV0m3oaGBV155hSNHjlBaWsrZs2e1DkmIG1q0aJE6RKbX6+noOYa7erUxgbq7G4cMrken+zrhrl49SBGLm2FXSdfHx4fp06er7fT0dFkwIayGwWCgpKSE9vZ2k+N+fn6kpaVx7733cu+995qvEb16NezYAXfdZXw41nPIwc3NePyuu4znScK1Wja9OMKc1NRUjh07hsFg4Msvv6SiooLg4GCtwxLDmKIoHD16lMzMTGpra7lw4QJJSUkm5yxYsODGbxQVZSxeU1trXNpbVmZc+ODjY5wWtmqVPDSzAXaXdEeNGsXcuXO5MtUtPT2dqVOnygwHoYmTJ0+SkZHBqVOn1GN79uwhOjoaT0/Pgb2pvz88+aSFIhRDze6SLhg34ystLaWjo4Nz585RWlpKZGSk1mGJYeTcuXNkZGRQXl5uctzFxYX4+HicnZ01ikxozS6TrqenJ3FxcWzfvh2ArKwsZs6ciZOZ1T1CWNKFCxfIzs6mtLTU5HmCg4MD0dHRLFy4EPf+zkQQdsUuky5AXFwcRUVFNDc3c/HiRfLy8khMTNQ6LGGnWlpayMnJobCw0GSOuE6nIyIigqSkJEaOHKldgMJq2G3SdXZ2ZvHixfz73/8GYNeuXcydOxcPDw+NIxP2pKOjg7y8PHbv3t1rVsL06dNJSUlh9OjRGkUnrJHdJl2AuXPnkpeXx/nz52lvbycnJ4clS5ZoHZawA93d3RQXF7Njxw6am5tN+iZOnEhqaiqTJ0/WKDphzew66er1etLS0nj//fcBKCwsJCYmBl9fX40jE7ZKURQOHjxIVlYW9fX1Jn3+/v6kpKQQEhIi20mJa7LrpAvGr3iTJ0/m5MmTGAwGMjMzufvuu7UOS9ggRVHYtGkTFRUVJsdHjBhBUlISs2fPlqmJ4obs/hOi0+lIS0tT2wcPHuxVVESIvtDpdCZF893c3EhLS+Phhx9mzpw5knBFnwyLT8mECROYOXOm2pblwaIvLl261OvY/Pnz8fPzIyEhgUceeYT4+HiZiij6ZVgkXYCUlBQcHBwA4yqhY8eOaRyRsFbNzc188sknrF+/nurqapM+JycnHnroIVJTU3EbaMlFMawNm6Tr6+tL1FVl7tLT0zEYDBpGJKzVtm3b1Pm2mZmZvfplGEHcjGH16Vm0aJFawen8+fNytyvMWrx4sTr7oLOzs3epRSFugt3PXriau7s7iYmJlJWVkZaWRlBQkNYhCQ0ZDAYOHjxIaGioybhsQEAASUlJjB07luDgYJn+JSzKLjam7I/u7m50Op18RRzGFEWhvLycjIwMampqSE1NJSEhQeuwhB253saUw+pOF1Afponh6dSpU6Snp1NZWake27VrF/PmzZMHY2JIDLuka46iKPIV0s7V1taSmZnJkSNHTI47OzsTExMjv4zFkBnWSVdRFA4cOEB2djbLly/HX6ru253Gxka2b9/Ovn37epVanDdvHgsXLhx4MXEhBmBYJ93PPvuM/Px8wLgj6/LlyzWOSFhKa2sru3btIj8/n66uLpO+8PBwkpKSpAaH0MSwTrqRkZFq0j116hTNzc1y12PjOjs7yc/PZ9euXbS1tZn0BQcHk5KSwtixYzWKTohhnnTHjh2rPkBJSEjA1dVV65DEAF3ZaXf79u00NTWZ9I0bN460tDQCAwM1ik6Irw3rpAtwxx13aB2CuAmKonDkyBEyMzM5f/68SZ+fnx/JycmEhYXJg1JhNYZ90hW261qlFr28vFi0aBFz5syRWQnC6kjSNaO1tVXmbNoAnU7HxIkT1aTr4uJCQkICMTExstuusFqSdK/S0NBAVlYWFRUVPPLIIzLGa2XM/TJcsGABJSUlzJw5k4SEBNlpV1g9SbqXKYrCe++9p44L7tq1i9TUVI2jEmCsa5uTk0NxcTEPPvggo0aNUvtcXFx4+OGHcXSUj7KwDVKA4DKdTsfixYvVdl5eHo2NjdoFJFT//Oc/yc/Pp7Ozk6ysrF79knCFLZGke5WZM2cybtw4ALq6usjOztY4IgGwcOFC9d+bm5t7LXYQwpZI0r2KTqfjlltuUdv79+/vtXOAGDyKonDo0CG6u7tNjo8fP56EhASWL1/O/fffL3e2wqZJ0u1hypQpTJ8+HTAmgYyMDI0jsn+KonD8+HFeffVVPvjgA8yVE01NTZWtzYVdkKRrRmpqqvrDffz48V7zQIXlnDlzhnfeeYdNmzap3ypycnJob2/XODIhBod8TzMjICCAOXPmUFxcDBj3U5s6darcZVlQXV0dmZmZHDp0yOS4k5MTc+fO1SgqIQafJN1rSEpKoqysjM7OTqqrqyktLWX27Nlah2Xzmpqa2L59OyUlJSYbg+r1eubOncuiRYvw8vLSMEIhBpck3Wvw8vIiLi6OHTt2AJCVlUVYWJjJXlqi79ra2ti9ezd5eXl0dnaa9M2cOZPk5GT8/Pw0ik6IoSNJ9zri4uIoKiri0qVLNDY2UlBQQHx8vNZh2ZSuri4KCgrYuXMnra2tJn2BgYGkpqYyfvx4jaITYuhJ0r0OFxcXFi9ezCeffALAzp07mTNnjiw17QODwcD+/fvZvn17r0UmY8aMITU1laCgIBknF8OOJN0bmDt3Lnl5edTV1dHW1kZOTg633nqr1mFZLUVROHbsGJmZmdTU1Jj0+fj4kJyczKxZsyTZimFLku4NODg4kJqaypYtWwAoLCwkJiYGHx8fjSOzPtcqtejh4cGiRYuYN2+elFoUw57M0+2D0NBQJk6cCEB3dzeZmZkaR2SddDodY8aMUdvOzs4kJSXxyCOPMH/+fEm4QiBJt096Lg8+cOAAZ86c0TAi62BuAUNCQgKenp7ExMTw6KOPsmjRIlxcXDSITgjrJEm3jyZOnMiMGTPUdmlpqYbRaKulpYXPP/+c9evXc+HCBZM+Nzc3Hn30UZYsWYKHh4c2AQphxWRMtx9SU1M5f/48ycnJhIaGah2OZj766COOHz8OQHZ2NnfddZdJv8xlFuLaJOn2g5+fHz/96U+H/ZP3xMRENenW19fT3d0t47VC9JEk3X4aTgn3yvSvadOmodd/PRI1efJkYmJimDJlCqGhocPq70SImyVJ9yYZDAYMBoPd1Xj96quvSE9Pp6qqim9961u9itAsWbJEo8iEsG32lSmGkKIoHD16lIyMDMLDw1m0aJHWIVnE2bNnycjIMJlru337dsLDw2WsVggLkKQ7QEePHmXz5s0A7N69m3nz5uHp6alxVANXX19PdnY2ZWVlJscdHR0JDw83qQgmhBg4SboDNH36dAICAqipqUGn01FdXU1wcLDWYfVbc3MzOTk5FBUVmSRWnU5HZGQkixcvxtvbW8MIhbAvknQHSK/Xc8stt1BeXs7ChQttbk5qe3s7ubm57Nmzh46ODpO+0NBQUlJS8Pf31yg6IeyXJN2bEBwcbHN3t11dXezdu5cdO3bQ0tJi0jd58mRSU1PVJc9CCMuTpDtMKIpCWVkZWVlZvVaRBQQEkJqayrRp02T6lxCDTJKuhdXV1eHr62s1yevKTrsZGRmcO3fOpM/b25vk5GTCw8NN5uEKIQaPJF0LaWpqIjs7m5KSEu6++27CwsK0DumapRbd3d1JTEwkOjra7uYXC2Ht5CfOQvLy8tTdgzMyMggJCdF8aaxOp8PPz09Nuk5OTixYsIC4uDhcXV01jU2I4Uq+U1pIQkKCmsjq6+vZu3fvkMfQc8NHgIULF+Lq6kp0dDSPPPIIycnJknCF0JAkXQtxc3MjMTFRbW/fvt1svdnB0NraSkZGBi+88AJNTU0mfZ6enjz++OPcfvvtsrW5EFZAkq4FxcTEqAsJWlpa2L1795Bc94MPPmDXrl20tLSoW8ZfTYqIC2E9JOlakKOjIykpKWp7z549XLx4cdCve/W28NXV1bJkVwgrJknXwsLDwxk7dixgHGPNzs622HsrikJFRQWKopgcDwoKYs6cOXzve9/jgQcekOlfQlgx+em0MJ1OR1pamtret29fr/mxA3Hy5EnefPNN3n33XQ4ePNjrmnfeeadsbS6EDZApY4Ng6tSpBAcHc/z4cRRFISMjg7S772ZjdTWlzc00dnXh7ehIhKcn948Zg7+z8zXf69y5c2RmZnLs2DH1WGZmJjNmzNB8SpoQov8k6Q6StLQ0KioqOO3pyRZnZx7IzUWn09F21dDAR+fP8/SJEyzx9WXNpElEjxih9l24cIHs7GxKS0tNhhMcHBwICQmRLXKEsFGSdAfJ6NGjORsdzdsuLnReGWPtMRbbevmB19bz5/m8vp51QUHc5+NDTk4OhYWFdHd3q+fqdDoiIiJISkpi5MiRQ/WfIYSwMEm6g2TDmTO84+FBZ49Ea44CtBgMPF5ezmcVFcw5dcqkf/r06aSkpDB69OhBilYIMVQk6Q6CwosXeaKigtarE25HB/zlL1BcDBcvwrhx8KMfQUyMeko78OmUKYy+cIFxTU1MmDCBtLQ0Jk+ePOT/DUKIwSFJdxCsraxUhw5U3d0QEGBMvAEBkJ8Pzz4Lb74JY8aop3Xq9RQEB7M5JISQkBCZjSCEnZGka2E1HR18WldHr0EFNzdYterr9oIFMHYsHD1qknTR6Tg6ciR+U6dKwhXCDsk8XQvbWF3dtxPr6+HUKQgM7NWl0+n6/j5CCJsiSdfCSpubTaaFmdXVBc8/D9/4Bkya1Ku71WCg7NKlQYpQCKElSboW1tjVdf0TDAb4/e/ByQkeffSapzWYKdMohLB9MqZrYd7X24lBUeDPf4aGBvjDH+A65/o4OQ1CdEIIrcmdroVFeHrieq0HYC+8ACdPGu90r1Nu0U2vJ9zGtnQXQvSNJF0LW3X1TISrVVfDv/4Fx4/Dd74DS5YY/6Sn9zpVud77CCFsmgwvWFiAszNL/PzYev686bSxMWOgD2UedcBtvr7XLYIjhLBdcqc7CNZMmoTbAGvauun1rDEzo0EIYR8k6Q6C6BEjWBcUhHs/E6+7Xs+6oCCirqo2JoSwLzK8MEhWjx8PYKzBYDD0XqF2FR3GO9x1QUHq64QQ9knudAfR6vHj2REZyV2jRuGq1/cacnDT63HV67lr1Ch2REZKwhViGJA73UEWNWIEH86aRW1HBxurqym7dImGzk58nJwI9/Bg1Q12jhBC2Bddz00OTTp1ulrg5NCFI4QQdmGyoij+5jqum3SFEEJYlozpCiHEEJKkK4QQQ0iSrhBCDCFJukIIMYQk6QohxBD6/+Q6fHyRrScSAAAAAElFTkSuQmCC\n"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# ------- Run the QUBO problem on the QPU -------\n",
    "# Set up QPU parameters\n",
    "chainstrength = 8\n",
    "numruns = 10\n",
    "\n",
    "# Run the QUBO on the Braket solver from your config file\n",
    "# set sampler\n",
    "sampler = BraketDWaveSampler(device_arn='arn:aws:braket:::device/qpu/d-wave/Advantage_system4')\n",
    "sampler = EmbeddingComposite(sampler)\n",
    "response = sampler.sample_qubo(Q, chain_strength=chainstrength, num_reads=numruns)\n",
    "energies = iter(response.data())\n",
    "\n",
    "# ------- Print results to user -------\n",
    "print('-' * 60)\n",
    "print('{:>15s}{:>15s}{:^15s}{:^15s}'.format('Set 0','Set 1','Energy','Cut Size'))\n",
    "print('-' * 60)\n",
    "for line in response:\n",
    "    S0 = [k for k,v in line.items() if v == 0]\n",
    "    S1 = [k for k,v in line.items() if v == 1]\n",
    "    E = next(energies).energy\n",
    "    print('{:>15s}{:>15s}{:^15s}{:^15s}'.format(str(S0),str(S1),str(E),str(int(-1*E))))\n",
    "\n",
    "# ------- Display results to user -------\n",
    "# Grab best result\n",
    "# Note: \"best\" result is the result with the lowest energy\n",
    "# Note2: the look up table (lut) is a dictionary, where the key is the node index\n",
    "#   and the value is the set label. For example, lut[5] = 1, indicates that\n",
    "#   node 5 is in set 1 (S1).\n",
    "lut = response.lowest().first.sample\n",
    "\n",
    "# Interpret best result in terms of nodes and edges\n",
    "S0 = [node for node in G.nodes if not lut[node]]\n",
    "S1 = [node for node in G.nodes if lut[node]]\n",
    "cut_edges = [(u, v) for u, v in G.edges if lut[u]!=lut[v]]\n",
    "uncut_edges = [(u, v) for u, v in G.edges if lut[u]==lut[v]]\n",
    "\n",
    "# Display best result\n",
    "pos = nx.spring_layout(G)\n",
    "nx.draw_networkx_nodes(G, pos, nodelist=S0, node_color='r')\n",
    "nx.draw_networkx_nodes(G, pos, nodelist=S1, node_color='c')\n",
    "nx.draw_networkx_edges(G, pos, edgelist=cut_edges, style='dashdot', alpha=0.5, width=3)\n",
    "nx.draw_networkx_edges(G, pos, edgelist=uncut_edges, style='solid', width=3)\n",
    "nx.draw_networkx_labels(G, pos)\n",
    "\n",
    "filename = \"maxcut_plot.png\"\n",
    "plt.savefig(filename, bbox_inches='tight')\n",
    "print(\"\\nYour plot is saved to {}\".format(filename))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__DISCUSSION__: The optimal cut size for this toy problem is 5. For every edge connecting nodes of different color we score a point (i.e., cut this edge), as displayed above by dashed lines. Here at maximum we can cut five edges. In this toy example we find multiple optimal degenerate solutions, apart from the obvious $\\mathbb{Z}_2$ symmetry (that is, the color choice for the two subsets is arbitrary), because there is no preferred coloring for node 5. This problem is equivalent to finding the antiferromagnetic ground state, in the presence of frustration (as present here in the subgraph with nodes 3-4-5). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## APPENDIX"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Original MaxCut example from here: https://github.com/dwave-examples/maximum-cut"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# # Copyright 2019 D-Wave Systems, Inc.\n",
    "# #\n",
    "# # Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# # you may not use this file except in compliance with the License.\n",
    "# # You may obtain a copy of the License at\n",
    "# #\n",
    "# #     http://www.apache.org/licenses/LICENSE-2.0\n",
    "# #\n",
    "# # Unless required by applicable law or agreed to in writing, software\n",
    "# # distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# # See the License for the specific language governing permissions and\n",
    "# # limitations under the License.\n",
    "\n",
    "# # ------ Import necessary packages ----\n",
    "# from collections import defaultdict\n",
    "\n",
    "# from dwave.system.samplers import DWaveSampler\n",
    "# from dwave.system.composites import EmbeddingComposite\n",
    "# import networkx as nx\n",
    "\n",
    "# import matplotlib\n",
    "# matplotlib.use(\"agg\")\n",
    "# from matplotlib import pyplot as plt\n",
    "\n",
    "# # ------- Set up our graph -------\n",
    "\n",
    "# # Create empty graph\n",
    "# G = nx.Graph()\n",
    "\n",
    "# # Add edges to the graph (also adds nodes)\n",
    "# G.add_edges_from([(1,2),(1,3),(2,4),(3,4),(3,5),(4,5)])\n",
    "\n",
    "# # ------- Set up our QUBO dictionary -------\n",
    "\n",
    "# # Initialize our Q matrix\n",
    "# Q = defaultdict(int)\n",
    "\n",
    "# # Update Q matrix for every edge in the graph\n",
    "# for u, v in G.edges:\n",
    "#     Q[(u,u)]+= -1\n",
    "#     Q[(v,v)]+= -1\n",
    "#     Q[(u,v)]+= 2\n",
    "\n",
    "# # ------- Run our QUBO on the QPU -------\n",
    "# # Set up QPU parameters\n",
    "# chainstrength = 8\n",
    "# numruns = 10\n",
    "\n",
    "# # Run the QUBO on the solver from your config file\n",
    "# sampler = EmbeddingComposite(DWaveSampler(solver={'qpu': True}))\n",
    "# response = sampler.sample_qubo(Q, chain_strength=chainstrength, num_reads=numruns)\n",
    "# energies = iter(response.data())\n",
    "\n",
    "# # ------- Print results to user -------\n",
    "# print('-' * 60)\n",
    "# print('{:>15s}{:>15s}{:^15s}{:^15s}'.format('Set 0','Set 1','Energy','Cut Size'))\n",
    "# print('-' * 60)\n",
    "# for line in response:\n",
    "#     S0 = [k for k,v in line.items() if v == 0]\n",
    "#     S1 = [k for k,v in line.items() if v == 1]\n",
    "#     E = next(energies).energy\n",
    "#     print('{:>15s}{:>15s}{:^15s}{:^15s}'.format(str(S0),str(S1),str(E),str(int(-1*E))))\n",
    "\n",
    "# # ------- Display results to user -------\n",
    "# # Grab best result\n",
    "# # Note: \"best\" result is the result with the lowest energy\n",
    "# # Note2: the look up table (lut) is a dictionary, where the key is the node index\n",
    "# #   and the value is the set label. For example, lut[5] = 1, indicates that\n",
    "# #   node 5 is in set 1 (S1).\n",
    "# lut = response.lowest().first.sample\n",
    "\n",
    "# # Interpret best result in terms of nodes and edges\n",
    "# S0 = [node for node in G.nodes if not lut[node]]\n",
    "# S1 = [node for node in G.nodes if lut[node]]\n",
    "# cut_edges = [(u, v) for u, v in G.edges if lut[u]!=lut[v]]\n",
    "# uncut_edges = [(u, v) for u, v in G.edges if lut[u]==lut[v]]\n",
    "\n",
    "# # Display best result\n",
    "# pos = nx.spring_layout(G)\n",
    "# nx.draw_networkx_nodes(G, pos, nodelist=S0, node_color='r')\n",
    "# nx.draw_networkx_nodes(G, pos, nodelist=S1, node_color='c')\n",
    "# nx.draw_networkx_edges(G, pos, edgelist=cut_edges, style='dashdot', alpha=0.5, width=3)\n",
    "# nx.draw_networkx_edges(G, pos, edgelist=uncut_edges, style='solid', width=3)\n",
    "# nx.draw_networkx_labels(G, pos)\n",
    "\n",
    "# filename = \"maxcut_plot.png\"\n",
    "# plt.savefig(filename, bbox_inches='tight')\n",
    "# print(\"\\nYour plot is saved to {}\".format(filename))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "name": "python3",
   "language": "python",
   "display_name": "Python 3"
  },
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}