cliques.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx # library to handle graphs\n",
    "import matplotlib.pyplot as plt # plotting library\n",
    "import numpy as np # library for maths\n",
    "from networkx.drawing.nx_agraph import graphviz_layout"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## CLIQUES algorithm:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Implementation of the algorithm CLIQUES from Fig. 2 of E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci., 363(1):28–42, October 2006.\n",
    "\n",
    "https://snap.stanford.edu/class/cs224w-readings/tomita06cliques.pdf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def intersection(sets):\n",
    "    \"\"\"\n",
    "    given a list of sets (each set is a list of nodes),\n",
    "    return a list of the nodes that are in all of the sets.\n",
    "    \"\"\"\n",
    "    return list(set.intersection(*map(set, sets)))\n",
    "\n",
    "def exclusion(A, B):\n",
    "    \"\"\"\n",
    "    returns the set of nodes A without any of the nodes in B.\n",
    "    \"\"\"\n",
    "    try:\n",
    "        excluded = [x for x in A if x not in B]\n",
    "    except:\n",
    "        excluded = [x for x in A if x != B]\n",
    "    return excluded\n",
    "\n",
    "def largestVertex(G, SUBG, CAND):\n",
    "    \"\"\"\n",
    "    returns the node v in SUBG that maximizes \n",
    "    |CAND (intersection symbol) neighborhood of v|.\n",
    "    \"\"\"\n",
    "    intersectionLengths = []\n",
    "    for node in SUBG:\n",
    "        intersectionLengths.append( len( intersection( [list(G.neighbors(node)), list(CAND.nodes())] ) ) )\n",
    "    index = np.where( intersectionLengths==np.max(intersectionLengths) )\n",
    "    return list(SUBG.nodes())[index[0][0]]\n",
    "\n",
    "def EXPAND(G,SUBG,CAND,L):\n",
    "    \"\"\"\n",
    "    the procedure EXPAND \n",
    "    given in Fig.2 of the paper.\n",
    "    \"\"\"\n",
    "    if len(list(SUBG.nodes())) == 0:\n",
    "        print( \"CLIQUE!\" )\n",
    "        L.append('clique')\n",
    "    else:\n",
    "        u = largestVertex(G, SUBG, CAND)\n",
    "        while len( exclusion(list(CAND.nodes()), list(G.neighbors(u)) )) != 0:\n",
    "            previous_node = [\"ROOT\"]\n",
    "            q = list(CAND.subgraph( exclusion(list(CAND.nodes()), list(G.neighbors(u)))).nodes())[0]\n",
    "            print( q, end=\",\" )\n",
    "            L.append(q)\n",
    "            SUBGq = SUBG.subgraph( intersection([list(SUBG.nodes()), list(G.neighbors(q))]) )\n",
    "            CANDq = CAND.subgraph( intersection([list(CAND.nodes()), list(G.neighbors(q))]) )\n",
    "            EXPAND(G,SUBGq,CANDq,L)\n",
    "            CAND = CAND.subgraph( exclusion(list(CAND.nodes()), q) )\n",
    "            print( \"back\", end=',' )\n",
    "            L.append('back')\n",
    "            \n",
    "def CLIQUES(G):\n",
    "    L = list()\n",
    "    \"\"\"\n",
    "    the CLIQUES algorithm.\n",
    "    \"\"\"\n",
    "    EXPAND(G,G,G,L)\n",
    "    print( 'finished.')\n",
    "    return L\n",
    "\n",
    "def preprocess(G):\n",
    "    \"\"\"\n",
    "    enumerate all wedges in G\n",
    "    \"\"\"\n",
    "    wedges = dict()\n",
    "    for i in list(G.nodes()):\n",
    "        wedges_i = []\n",
    "        for j in list(G.nodes()):\n",
    "            if i!=j:\n",
    "                wedges_from_j = [x for x in list( nx.all_simple_paths(G,j,i,2)) if (len(x)==3)]\n",
    "                for w in wedges_from_j:\n",
    "                    if w !=[]:\n",
    "                        wedges_i.append(w)\n",
    "        wedges[i] = wedges_i\n",
    "    return wedges\n",
    "\n",
    "def hierarchy_pos(G, root=None, width=1., vert_gap = 0.2, vert_loc = 0, xcenter = 0.5):\n",
    "    \n",
    "    \"\"\"\n",
    "    basic tree plot function\n",
    "    \"\"\"\n",
    "    \n",
    "    if not nx.is_tree(G):\n",
    "        raise TypeError('cannot use hierarchy_pos on a graph that is not a tree')\n",
    "    if root is None:\n",
    "        if isinstance(G, nx.DiGraph):\n",
    "            root = next(iter(nx.topological_sort(G)))  #allows back compatibility with nx version 1.11\n",
    "        else:\n",
    "            root = random.choice(list(G.nodes))\n",
    "    def _hierarchy_pos(G, root, width=.8, vert_gap = 0.2, vert_loc = 0, xcenter = 0.5, pos = None, parent = None):\n",
    "        if pos is None:\n",
    "            pos = {root:(xcenter,vert_loc)}\n",
    "        else:\n",
    "            pos[root] = (xcenter, vert_loc)\n",
    "        children = list(G.neighbors(root))\n",
    "        if not isinstance(G, nx.DiGraph) and parent is not None:\n",
    "            children.remove(parent)  \n",
    "        if len(children)!=0:\n",
    "            dx = width/len(children) \n",
    "            nextx = xcenter - width/2 - dx/2\n",
    "            for child in children:\n",
    "                nextx += dx\n",
    "                pos = _hierarchy_pos(G,child, width = dx, vert_gap = vert_gap, \n",
    "                                    vert_loc = vert_loc-vert_gap, xcenter=nextx,\n",
    "                                    pos=pos, parent = root)\n",
    "        return pos\n",
    "    return _hierarchy_pos(G, root, width, vert_gap, vert_loc, xcenter)\n",
    "\n",
    "def formatCliquesList(L):\n",
    "    \"\"\"\n",
    "    the CLIQUES algorithm outputs a string of code.\n",
    "    This function formats that into a nice list.\n",
    "    \"\"\"\n",
    "    newList = []\n",
    "    for i in range(len(L)):\n",
    "        if (L[i]!='clique'):\n",
    "            if L[i]!='back':\n",
    "                newList.append(L[i])\n",
    "            else:\n",
    "                xx = 0\n",
    "                rest = L[i:]\n",
    "                for x in range(len(rest)):\n",
    "                    if rest[x]=='back':\n",
    "                        xx += 1\n",
    "                    if rest[x]!='back':\n",
    "                        break\n",
    "                newList.append(str(xx))\n",
    "    fmtList = [newList[x] for x in range(len(newList)-1) if (not isinstance(newList[x],str)) or (not isinstance(newList[x-1],str))]\n",
    "    return fmtList\n",
    "\n",
    "def createTree(List):\n",
    "    \"\"\"\n",
    "    creates a networkx tree from the (formatted) list output by the CLIQUES algorithm.\n",
    "    \"\"\"\n",
    "    tree = nx.DiGraph()\n",
    "    tree.add_node(0, value=\"ROOT\")\n",
    "    previousNodes = [0]\n",
    "    lastNode = 0\n",
    "    labels = {0:\"ROOT\"}\n",
    "    for i in range(len(List)):\n",
    "        if not isinstance(List[i], str):\n",
    "            labels[i+1] = List[i]\n",
    "            tree.add_node(i+1, value=List[i])\n",
    "            tree.add_edge(lastNode, i+1)\n",
    "            try:\n",
    "                if isinstance(List[i+1], str):\n",
    "                    shift = -int(List[i+1])+1\n",
    "                    if shift<0:\n",
    "                        previousNodes = previousNodes[:shift]\n",
    "                    lastNode = previousNodes[-1]\n",
    "                else:\n",
    "                    lastNode = i+1\n",
    "                    previousNodes.append(i+1)\n",
    "            except:\n",
    "                lastNode = i+1\n",
    "                previousNodes.append(i+1)\n",
    "        else:\n",
    "            pass\n",
    "    pos = hierarchy_pos(tree,0)\n",
    "    return tree, pos, labels\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A toy example:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Create some graph with a few cliques:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAYYAAAD8CAYAAABzTgP2AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XecXHXVx/HPSSEJBAm9CAENIqB0AggECIiBBKWKUiTySBNFVECMCIjSRFEUC4LPY0K1YESQRJQSgQQwlFCkhCIgSBUiJYUke54/zh1mZndmd2f2ztw7s9/367UvTXbm3t8Cr/3O/ZVzzN0REREpGJD1AEREJF8UDCIiUkbBICIiZRQMIiJSRsEgIiJlFAwiIlJGwSAiImUUDCIiUkbBICIiZRQMIiJSRsEgIiJlFAwiIlJGwSAiImUUDCIiUkbBICIiZQZlPQARkYYzWw2YCGwKjADmAQ8Ak3F/Jcuh5ZGpUY+ItC2z0cAkYE/AgWEl310AGDAdOAf32c0fYD4pGESkPZkdA5wPDKX7afMOYCFwAu4XNWNoeadgEJH2UwyFZWt413wUDoCCQUTaTUwfzaBTKOwC3ElxYfW9wGNd3z0f2Bn3uxs4wtzTriQRaTeTiOmjLn4CvJV8VQgFkvdNatC4WoaCQUTaR+w+2pP6f7cNAMZjtmp6g2o9CgYRaScTid1HFU0CVgF2IOaaqvDkOv2WgkFE2smmlG9Jfdd3gaeA54GjgI8DT1a+xrDkOv2WgkFE2smIat/YFlgeGEI8DuwATKvjOv2BgkFE2sm83r7Q6GbOqYbrtCMFg4i0kweIE81l5gE3EKfYlgBXALcC4ypfY0FynX5L5xhEpH3ErqRn6LRd9RVgPPAoMBDYEPgOsHvlqywERvbnGkoKBhFpL2ZTgb2pb0akA7gG9/3THVRr0VSSiLSbc4hP/fVYmLy/X1MwiEh7iSqpJxDlLWpRqJXUr8thgIJBRNqR+0XPwBnzAY/poao6YnOSCuiVUDCISFtaD0YdCpcbXENMEXXerbRgKSz+C7z5FoxVKBRp8VlE2o6ZbUxUvfigu7+e1D7q0sHtbZgyHP4IXOTul2Y24JxRMIhI2zGzPwE3ufsPe/HaMcDlRIjUu2jdVjSVJCJtxcx2BTYGftab17v7bcD9wLGNHFcr0RODiLQNMxsA3A2c6+6/reF9HwJuATZw935dDgP0xCAi7eVg4B3gd7W8yd3/AVwHnNyIQbUaPTGISFsws2FE1YtD3P32Ot6/NjGltJm7P5f2+FqJnhhEpF18CbinnlAASMLgEuBbaQ6qFemJQURansV21EeA7d19bh+uMwKYC+zi7g+nNb5Wo2AQkZZnZhcC7u5fSuFaJwA7ufvefR9Za1IwiEhLM7MNgFnAhu7+agrXGwo8Rp1rFe1Aawwi0urOBb6XRigAJIfcTgXOMzNL45qtRsEgIi3LzHYEtgJ+nPKlrwCGE30d+h0Fg4i0pOTT/PeBU9y9SzvPvnD3pcSZhnPMbFCa124FCgYRaVWfBAYDVzbo+n8GXgQOb9D1c0uLzyLScsxsCLE99Qh3v7mB9xlNlO3ewN3fbtR98kZPDCLSio4FHm5kKAB4dIObCRzfyPvkjZ4YRKSlmNmKxHbSphxCM7MPAHeQ0nbYVqBgEJGWYmbfB5Z396ObeM+fAu+4+1eadc8sKRhEpGWY2fuIstofcvcXm3jf1YGHga3d/Z/Num9WtMYgIq3kbOBHzQwFAHd/CbgQ+E4z75sVPTGISEsws22AP5DRDiEzW54osDfe3e9r9v2bSU8MIpJ7JYfZTstq26i7vwmcSZTgaGsKBhFpBXsDKwKTMx7HJcAoM/toxuNoKAWDiOSamQ0GvguclJSqyIy7vwN8A/hu0l+6LbXtDyYibeMo4BnghqwHkrga6AAOzHogjaLFZxHJLTNbgTjMNs7d7896PAVmNhb4JbBR8hTRVvTEICJ5djIwPU+hAODutxA7lJp2yK6Z9MQgIrlkZusAc4DN3P25rMfTmZltRkxvbeAwFJgIbAqMAOYBDwCTcX8lu1HWR8EgIrlkZlOAf7n7N7MeSzUTzK4/E96/BawHODCs5NsLAAOmA+cQBflagoJBRHLHzLYAphGH2d7MejwVmR3TAT9wGDaw+1d2AAuBE3C/qBlD6ysFg4jkSnKY7Ubganf/edbjqcjsGOB8YNka3jWfFgkHLT6LSN7sCaxF7PrJn2jeUzEUfg1sBCwHjAJuK//2ssD5mG3d8DH2kYJBRHIj6a/8PeBkd1+c9XiqmEQsNpf5K7GF6lfAm8CtwPu7vndo8v5c01SSiOSGmR0JHAKM9Tz+cjJbjThs1yUYtgc+l3z1YCEwMs+7lfTEICK5YGbDgTOAE3MZCmEisfuozFKiScQrwPrA2sAXiW1JFXhyndxSMIhIXpwI3OLud2c9kG5sSvmWVABeAhYTtTJuIw5f3EeUYq1gWHKd3FIwiEjmzGxN4DjglKzH0oMRlf6ykBTHAWsCqwBfJfbb1nKdvFAwiEgefBv4X3d/OuuBVGNm73kMlq/0vRWJ6SPr/eXmpTOqxlAwiEimzOzDRL+Fs7MeSykzG2Bmo83sm2Z2K/D8H2GtxTFr1MXhRO/Pl4HXgQuAvSpfegFRLiO3tCtJRDJlZtOAG9z9RzkYy1rAOOBjwEeJ9eQbkq9bHYZTZVfSYuB44MrkmwcC51V6YQvsSlIwiEhmkk5oFwEbZ1G+2syGAWOIIBgHvJc4dX0D8Bd3/1eFN00lnnDqmXHpAK7Bff96x9wMCgYRyYSZDQTuAc5096ubdE8DNqYYBDsQ0zqFp4K7e+wSZzbaYYbVVg6jYD6wM/neecWgrAcgIv3WocQvyt838iZmtjKwG8UpoqVECFwCfNrda1oINrj7XLj3ePjIUOihfl6ZQq2kXIcC6IlBRBopTgp36VNwLfxmb5gJfMrdZ6V7SxsEbEsEwTiifNGtwF+IQJjblwN0ZnYqsO9rMGXFWDAfSjfTSh3gA2LBuSUK6IGCQUQaIQrNTSIK4nXpU7AYBt8BL+0E+6bRp8DM1qMYBGOBpykGwUx3X9TXeyT3+SxwOrC9u7+QFMSbBIynws+5FAbdDG+MhT0GtcCTQoGCQUTSVSxJ3e0naYcOq7NPQVI+YxeK00MjiDp2NwB/dfcX6xt8t/ccB0wBdnH3Rzt9c1UqPBk9C5etC38DvujuN6Y9pkZRMIhIehrUp8DMBgCbUQyC0UR5osKi8f3u3lHvsHtiZlsm99nH3WfW+N5DgGOAnXJcA6qMgkFE0hHTRzOoEgqPA5sABwCXd/12l906ZrY6EQKFr/9SDIIZ7v5WmsOvJpmmmgkc5+5T63j/QOBh4PPufnO6o2sMBYOIpKOH/f0fI1Zg16ViMHQsgWsHx+HhwlbS9wE3UzxT8M+GjLsbyY6mmcBP3f3CPlznM8CRwM6t8NSgYBCRvuumTwFEZ7OpxAGCJ6gYDCwERsG9/4briYXju7Js1pMcfruRWLz+Wh+vNQh4BDjK3W9JY3yNpFpJIpKGin0KAN4ATiMWHrqzDCx4Hq5y99Pc/faMQ2EgcAXwLPD1vl7P3ZcQVbhP7+u1mkHBICJpqNinAOBUoqvZOj1cYEBO+hQkp6N/SOwu+myKi9pXAGub2c4pXa9hdPJZRNJQsb/AHGIu5r4+XqfJTiTOQoxJ6/wDxFODmRWeGnZN67qNoGAQkTRULCsxgzhpNjL581tEPYqHgXsrvN5hXg09DVJnZgcR/XZ2qLVURi9dDpxqZmPc/bYGXD8VmkoSkTQ8QIUWx0cBTxJPDnOIzfwTiG1GnS0APw0mmNlPzWyCmdVTpK5uZjYW+BEwoWJV1RQkaw1nkfO1BgWDiKRhChUamC0LrFHyNZzYtrRqhQsMhUVPxHbXp4GTgBfNbJqZfcHM3teogQOY2SbAb4jaTQ828l7AZcD7zWzHBt+nbtquKiKpeMrsznVh21rKjZbo0qfAzEYAuxN1iMYD/yHaKF9PbCFNpX+Dma0NzAJOdver0rhmL+55BBFCuzfjfrVSMIhInyRTPj/cASb8DVYeWOUsQw+67VOQlMTYkpiJGg98kFjXngZMd/cX6hz7COA24FJ3/14916jzvssAc4GD064umwYFg4jUzcw2B64i6hZ9weFgGlArqcJ9VwP2IILiY8BTxJPENGB2j8124hpDgD8DDwLHN/tEspkdCRzg7uOaed/eUDCISM2Svf7HA6cAX3H3y0u+2avqqsT0UV3VVTuNZTDwEeJJYgKxnPFnkhPU7v5ahfcMIM4VDAE+2ZsgSVvJU8On3f3OZt+/OwoGEalJUtzuV8BKxFTIUxVeVLVPwSJYOhA6BsF1wDlpdzQzs5EU1yV2Ae6nuDbxoLu7mZ0HbA/s7u5ddlM1i5kdTVRs3TOrMVSiYBCRXjOzPYD/S77O6LFsRYU+BX+CgZ+HVf7VhCkUMxsK7Ew8SUwAliFqOq1HNNt5ttFj6E7y1PAE8dRyV5ZjKaVgEJEeJfPx5xBVsw9z9xl9uNYKwL+Addz9v+mMsFf3NeALRM2ih4j+DneQrE24++PNGkuncX0e+Li7j8/i/pXoHIOIdMvMNgLuIj5lb96XUABIwmAGsFdfx1aj7Yl6fru6+47AWsDPgQ8DM8xsrpldYGa7J0HYLP8HbGJm2zTxnt3SE4OIVJR8wj6CaHh/CnBJWjt3zOwwYF933zeN6/XifhsSLTYPc/cuB6+Tn3UzitthPwzcQqxNTHP35xo8vmOB8e7e7LCsSMEgIl2Y2UrAxcD6wEHu/kjK11+ROOG8tru/mea1K9xrDWLK6Ax3n9zL96xMNAuakPzv8xQXsO9MSlukOcYhxFrDvh6lvrv0jwYm4/5KmvetOh4Fg4iUSspCXwb8Hpjk7gsbdJ9pxMGyXzfi+sk9lieeFP7g7t+p8xoDgW0pbocdSTQSmgb82VP6Zf0/ZudNhEN3hhXptJOLqENlwHRiJ9fsNO5ZjYJBRIB3zwOcRrRP+Jy7T2/w/f6HmD45oEHXH0xsiX0WODrFabD3AnsSQbEb0ZmtcLjuvrr6N5gd43B+ByzbQ0mRVM5+9DgcBYOImNn7iQNf/wUmuvtLTbjnysSJ5bXc/e2Ur23Eou6qxDmBVKd+Su4zBNiR4trECsSn+uuBv7r7G724SOFAYENPi9dCwSDSz5nZwcAFxCLzj1PsWNabe99ALGpfnfJ1v02UzBibduj0cN9RFKecdgBmU1ybeLTLU4vZaGKH1ruhMLzTNRcAxwIXdr1dt/Wl+kLBINJPmdl7gJ8A2xALzDU0WkttDEcCu7n7p1O85lHA14gDbC+ndd06xrEc0amtEBRLKU453eLuCzCbSpQar3h04G1g9eQNO3X9dpeKtKmNXcEg0v8ke+avBG4CvtrMT9WdxrEq8DiwZhqlKcxsL+ASYKesDqxVkkxtfYjilNMW68BdT8Eug7rppDkFOINodlSls91CYGTau5V0wE2kHzGzgWY2iViUPdndj84qFACSHT33ENM+fWIxLfMrYk0hN6EA4OEhd/+uu+8MrHsxvNhR9fd9mAIcRrcvcmJra6rU81mkn0h201wGDAS2blT7yjpcTZTa+EO9FzCz9YFrid1Uuak5VI27v44ZxL+Lip4l9tn+b/eXGkacd0iVnhhE+gEz2we4l5g62jVHoQARCOOTgnc1S6ajphMH2K5NdWSNNaK7b15KbHfqRU/Tbq9TDwWDSBszs2XN7CLgB8QUy1lZ9B7ojru/SJTGrrnNZdI97k/Ab72B+/rTlPw72eEeWLO7111Kr+eI5qUwrDIKBpE2ZWabEZ3Vlge2cPc7Mh5SdwrTSb1mZoOAXwOPAt9sxKD6yswGmdnmZnakmV1iZnOAV4ELZsM7S6Bi2fJZRA2OT/Z8iwVEuYxUaVeSSJtJdsAcB5xK7Di6LOMh9cjM1iJKYa/h7u/04vVGVEYdBUzozXsaLRnTKGL77+jkfzcjSoz/nTjT8HfgfndfRLQnfYYKPbKPJg4p9OJfXEN2JWnxWaSNJL2QfwWsAmzn7k9mPKRecfd/m9nDRImJ3pTimETUL9o5q1AwszUpBsDo5OstigFwKnBP1Z4T7i9jNp0K5xh+0bshdADTGlFYT08MIm3CzMYRZSCmAKf32F0tZ8zsy++DbZ6C++imsmhSsvvbxAG2fzdpbCsAW1H+NLAc5U8Cs5P1klou3OXkcw108llEKkvq9ZwNHEjUObo54yHVzmz0G/DtZWCPIbDAqlQWPRVuPjM+iY9194cbMxQbSkwBlT4NrAPMoTwInkqlMJ9qJYlImszsg8BVxFz1Ee7+n4yHVLviL8ahdLMhxqFjAQy4E87f1f3EdG5tA4ENKX8S2Bh4jJInAeAfjSrElwykV/8MUHVVEakmWej8HHAusSPnF2mVlW6qJn5aTv6ZjSR++ReCYEvgJcqfBOa4+/xarp0Ks62JtZPxVO/HMI3ox5D69FHZUFrxvyWR/izpfnYx8EHg042aUmm4KvPrTxPVRO8AhhB7WC+gy06ZHufXzWwVyqeDtiEK2f2dYhDc7e6v9f2HSVEc2KvUwW2KOriJSBdmNga4HLiGqHXUkO5qTVGlsuh4YDXgIuI34u7AkcCXyt9dVlnUzIYTn/5Lg2Al4hxH6ZTQ8y35ZNVkCgaRFpAc5jqN+B15hLtfn/GQ+qabPfwbEXNL45M/nwS8QdctnEtgyQfgt0/HJ+v3Aw9SPiX0eDN7S7QTnWMQyTkzex/RXe1NYEt3fyHjIaVhIjGP3sXxxHHmXYDXiUMNlZo1d4B9H4YcAJ8FHszDIbd2oZIYIjlmZgcBdxElI/Zsk1CA+JQ/rNI3dgb+AbwHWBvYGtinwuuWgYH7w3x3v0ehkC4Fg0gOmdnyZjYZ+Bawh7v/oM2mRSpWBO0AxgH7Ed3LXiWeGk6u8TrSNwoGkZxJGs7cBywhpo7uzXhIqbCwgZl97qY4K9DFa0RhoS8SO5JWBg4n9mhWkXplUVEwiOSGmQ0ws5OJvsCT3P2ILLur9VVSWXQrM/uymf0eeBG4Edh1HszpgEWd37MK0X/g50QqziPqe2xW+RYNqSwq2pUkkgtJd7VLgcHAoe7+bMZDqlnSG2EbYEzytR3RiOx24Dbgtnd/rm52Jc0Bvkw0aBgIjAV+Smxh7aQhlUVFwSCSOTPbm9iN+VPg7Lw10qnGzFYimoztSATBpsQn+EIQzOy2REeVcwy9VHaOQdKlYBDJiJkNI7bs7wkc4u6zMh5St8xsJBEAhSAYCdxJMQjuqqmURE4ri4rOMYhkwsw2IbbrPwBsXrVmf0bMbABx1qw0CIaRTAkRPern9KmwnPtszE6g/lpJCoUG0RODSBMlhdy+AJwOnAhcmocSDWa2DFFSohAEOwD/pRgEtwNzGzLWnFUWFQWDSNNYFEf7FbA6cLC7P57hWIYDH6G4UDwaeIKSIGhWE5xkQLmpLCoKBpGmMLPdgclEG9/Tmn1SN2n5WZgSGkP0ILiX4vrArFxMZ+WgsqgoGEQaKpmiOQs4iOiudlMT7mlEUbnSIFgNmEUxCO5u6cqs0lBafBZpEDPbgOiu9hyxwPxqg+4zENiE8oVip7g2cCHwUKtsg5Xs6YlBJGXJJ/bDgfOIUtk/T3PRNulJPJpiEGxPnCouXSj+Zx4WtaU1KRhEuhNz85XmvCdXmvM2sxHEYbWNgYPc/aG+D8FGEL/8C0GwBfAIxSCY6e4v9/U+IgUKBpFK4vDVJOLwWbVdMtOJXTKz4y22I9Fd7Trga+6+oL5b21oU1wbGEOsFsykGwZ3u/lY91xbpDQWDSGc17qt/B04aEou7xxDd1f7U+1uZEb2bSxeKV6CkvhBwr7svrudHEamHgkGkVDEUen0SdwF0nAVzz4Jde2qkk7To3IJiEOxInOQtrA3cBjzaZr0XpMUoGEQKqtTuORS4iWgcswbwNeCITm91mG8VavckFUe3oxgC2xJVRd8NAnf/V+o/i0gfKBhECqpU+/wHsD7ROOZRohfx9cBW5e/uAK4xOIryp4FNiArShSCY6e6vNe6HEOk7BYMIdNsfoNRjRDD8CDiw0/cWgY+Et16GOyiuD8yuqeKoSA7ogJtImEjsPqroWKKexQJigWB8hdcMgkXPwZmD3c9ryAhFmkStPUXCppRvSS3zM+BN4hFgP2JaqbOBMHQwfLgxwxNpHgWDSBjR0wsGEosGzxE9ieu9jkjeKRikXzOzlcxs/xmwQW/fswR4svq35/V9VCLZUjBIv2Jmw8zso2Z2rpnNJhacj3gB5nbAos6vf5los/YWsBS4gaiKt2vlyy8gymWItDTtSpK2llQe3Qr4KLAbcY7gAeBG4njCne6+qNqupFeAA4j9ph3AusCXgCMr324hMFJ9A6TVKRikrZSUmNiNCINdgOcpBsHf3P2NSu9dZHbtYNhrQNRBqlUHcA3u+9c1cJEcUTBIy0uKzu1GMQw6iBC4Ebi5pzIVyTXWGwM3/hXWHVLfNu75VDj5LNKKFAzScsxsBeJJoBAEawC3UHwqeLyWXgRmtj1wNXDuUnhnQI21kohQUIN6aRs64Ca5Z2ZDiMb1hXWCTYjTxTcBhwH31dudzMwOAX5ItN2cnvwl1FBdFYWCtBk9MUjumNkAYHOKTwTbE41pbky+ZvW1X3Fyj28DBwMfd/d/dHrB1kQ/hvFU78cwjejHoOkjaSsKBslcsmA8imIQjAVepTg1NMPdX0/xfssCU4A1gX29u11EZqtSuYPbFO0+knalYJBMmNnqxHGAQhgsQ3HB+CZ3f65B910LuBZ4GDjS3bucXRDp7xQM0hRmNhzYieI6wbrA3yiGwSONbl5vZlsCfyRKH53b6PuJtCoFgzSEmQ0mDpMVgmALom9xIQjudvclTRzPfsAvgKPdfWqz7ivSihQMkopkMffDFKeGxgBPUFwnuN3d385gXAZ8naicvbe739vsMYi0GgWD1M3M1iVC4KPEesGbFJ8IbnH3VzMcXmGb68XAh4hQeD7L8Yi0CgWD9JqZrUz5gvF7KF8wfjq70ZWz2E30B+BF4DB1URPpPQVDq4gib5W2TU5u1LbJZFvnjhSfCtYnetUUwuAhd+9oxL37wsw+BFwHXAmclscxiuSZgiHvzEYTB632pPpBq+nEQavZfbuVDQK2prhgPBqYQ/Fg2d/d/Z2+3KPRzGwP4FLgq+5+edbjEWlFCoY8MzuGBpZmSBZmN6I4NbQz8CzFBeNb3f3N+gbfXMnPchyx0HyAu8/KeEgiLUvBkFfFUFgWooPMscRv7NeIOZ2ziceIEj0WczOztSmvRLqY4hPBze7+Uro/SOMlW2N/TOyE2itPax0irUjBkEcxfTSDkgqfbwPfAz4LjCSK9BwEPAisV/7usvLPZrYi5ZVIVwVupvhU8GQrH/RKfr7fEdl5ULVeCyLSewqGPDKbCuxND61XNwVOB0o7wzh0PA8z14HbiTDYGJhFccF4TrssxprZB4hF5unAifVWWBWRcgqGvKnSYrKzl4iaEnOADTt9bxH4JnDB41ET6I52rAdkZrsQ7ZhPc/eLMx6OSFtRP4b8mUjsPqpqMXBI8sLOoQAwBBbOhX/jPiP94WXPzI4AziKmjm7Oejwi7UbBkD+bUr4ltUwH8BmiFOlPql9jWHKdtmJmA4HvAp8Axrj73IyHJNKWFAz5M6LaNxz4HDGNNA0YXOd1WpGZLU8cWFsO2M7dX8t4SCJtq9vFTcnEvGrf+DzRxuw6unmk6MV1Wk1Sk+l24AVgnEJBpLEUDPnzAHGiucwzRM3oOUTn++HJ1xWVr7EguU7LM7PtiP7Ok4mS2YuzHZFI+9OupLzp5a6kHiwERrZ660kzOwj4EXC4u1+f9XhE+gs9MeSN+8vAdI915np0ANNaORTMbICZnUEc7t5NoSDSXAqGHHoOzl/Uw5bVajyeFs5JeUhNY2bDgKuA3YFt3f3BjIck0u8oGHLGzIasA984D+73KG/Rawug41yYY9CSXcrMbE2iD/RiYFePpycRaTIFQ44kHcemAgtOh+0MTiDCoadppQ5g/jvwlW/AEuCXSavNlmFmWwB3Eae1P+PuCzMekki/pcXnnEhC4ffEVNBB7+6+Mdua6Mcwnur9GKYR/RjuNrPlkj8/CRzRCnWRzGwf4BLgWHf/XdbjEenvFAw5kITC1cA7wKcrbsmMVpWVOrhN6bzQ3CrhkPRQOAn4ErCPJxVhRSRbCoaMlYTCYuBTae3Tz3s4mNkyxNGMzYBPuPtzGQ9JRBItNQ/dbpJQ+B0phwKAu79NTD+NImdrDma2ClECfAWi5pFCQSRHcvPLor9JPjH/DlhKtemjPspjOJjZxsQi8+1EC863Mx6SiHSiqaQMJKFwNREKn3L3dxp8v1xMK5nZOOAyoqnOpVmMQUR6pmBospInBQcObHQolNy3EA5PAEc2OxzM7IvAKcAn3f32Zt5bRGqjYGiiJBR+m/yxaaFQcv/hwPU0MRzMbBBR72gX4OPu/lSj7ykifaNgaJIkFH5DrOt8stmhUDKOpoWDmY0gfuYOYh3lv426l4ikJ/PFyP4gL6EA4O5vAROA9YFLGrUgbWajiHLZjxJPCgoFkRahYGgwMxtMNK0fSMahUNDocDCznYCZwI/d/Xh3X5Lm9UWksRQMDZSEwm+IFqq5CIWCRoWDmR1OLK5/xt1/nsY1RaS5tMbQICWhMJjYr78o4yFV1O2aQzQNqlSGY3KFMhwDiXLf+wF7ufujTfkBRCR1CoYGKJk+GgLsn9dQKOgSDrAVUbhvT6oX7ptOFO6bnbz/ciI89nf3/zRz/CKSLgVDypJQuIpozZn7UCgohMPZMOjrsLnF+LubXuoAFj4BZ34APgXcTVRHzc10mYjUR8GQoiQUrgSWBfZrlVAomGd2/BD4wbAa1p7mg18BU4+KNRT9xyTSBhQMKWn1UMBsNDCDGP+7HgG+ANwDrAp8D9i367vnAzujstkibUG7klKQhMIVwHK00PRRJ5OI6aN3LQH2BvYCXgMuBg4F5nZ979Dk/SLSBvTE0EdJyYcrgeHEk0LrtaSM3UfP0CkYHgK2A94kVpsBPgZsC3yn61UWAiM771YSkdajJ4Y+KAmF5WnVUAgv9dtFAAAEAklEQVQTid1HZSp9ZHAiMKp8a2KagxKRbCgY6pSEwhVEKOzbwqEAcU5hWOe/3BBYjVhXWAz8BfgbsaBQwbDkOiLS4hQMdUhC4XKiA1mrhwLE+YMuBgPXEAcc1gDOBw4E1q7xOiLSWgZlPYBWk4TCZcQvwX1aMRSSlqKbAaOB0b+HMftVee2mxFNCwfZ0O180L6UhikiGFAw1KAmFlYC9WyEUklIVG5OEQPK1EfA4MBuYNQpedzjaKkwnPQBsQJxm+xnwAvDZyrdakLxcRFqcdiX1UhIKlwKrEKGwIOMhdWFmRvR3Lg2BzYF/EyFQ+Jrj7vNL3lhxVxLAScAviTWGMcCFRNW9CrQrSaRNKBh6IQmFKcQZr9yEgpm9l/IQ2Bp4i/IQuMfde57iMZtKHFuoZ92pA7gG9/3reK+I5IyCoQd5CQUzW5n4xV8aBIMpD4HZ7v5SnTeoePK5l3TyWaSN9M9g6GU56WR+/lJi1+YnmhUKZrY8sCXlIbAKUZmiNAieSbU+kdkxxOajWsJhPnAC7helNg4RyVT/Cob4VNyrctIG9xJPCqsTTwpVtu/3dUjlO4SSr/WIoLqbYgg81sj+zCUDKoRDr6qrolAQaTv9Jxhq+IXnsPBsePCbMV//ibRCIZmW2ojyENiYKD9U+iTwkLsvTuOedTHbmgjQ8VQP0GlEPwZNH4m0mf4RDHVMkSyEjsXw5eXdL6zvlmbEBp7SdYGedwjlidmqVJ5ym6LdRyLtq/2Docqi6k+AycCDwEHJ/6+gV4uqSQhU2iH0JvXsEBIRyVB/CIaK2zCnJn9xAzE3Mrnyuytuw0x2CI3u9DWItHYIiYhkqL2DoZuDWwXfBJ6jajDgsGh3OPCmOADcvB1CIiIZafeSGBXLSddiAQwZCz++Ca4j6sl9i2btEBIRyUC7B0PFctK1WBY4BW49xf24dIYkIpJv7V52O60y0ConLSL9RrsHQ1o7gLSTSET6jXYPhgeITUddLCGO7S5NvhYmf1eBykmLSL/Sb3clfQs4o9PfnZ78fScqJy0i/Up7BwOonLSISI3afSoJ4BziU389FibvFxHpN9o/GNxnAycQ5S1qUSgnrSJxItKvtPs5huB+EWagctIiIj1q/zWGUionLSLSo/4VDAUqJy0iUlX/DAYREamq/RefRUSkJgoGEREpo2AQEZEyCgYRESmjYBARkTIKBhERKaNgEBGRMgoGEREpo2AQEZEyCgYRESmjYBARkTIKBhERKaNgEBGRMgoGEREpo2AQEZEyCgYRESmjYBARkTIKBhERKaNgEBGRMgoGEREpo2AQEZEyCgYRESmjYBARkTIKBhERKaNgEBGRMgoGEREpo2AQEZEyCgYRESnz/3Ysond7y3uDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "G = nx.Graph() # instantiate a graph object\n",
    "\n",
    "G.add_nodes_from([1,2,3,4,5,6,7,8,9]) # add some nodes\n",
    "\n",
    "G.add_edges_from([(1,9), (1,2), (9,2), (9,3), (2,3), (8,3), (3,4),\n",
    "                 (8,4), (8,6), (8,7), (7,6), (6,4), (6,5), (4,5), (4,7)])  # add edges between some nodes\n",
    "\n",
    "labels = nx.draw_networkx(G, pos=nx.spring_layout(G)) # draw the graph with labels\n",
    "plt.axis('off')\n",
    "plt.show() # show the plot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The cliques algorithm works its magic. The collection of nodes on any path from root node to leaf is a maximal clique."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,9,2,CLIQUE!\n",
      "back,back,back,9,3,2,CLIQUE!\n",
      "back,back,back,2,back,4,3,8,CLIQUE!\n",
      "back,back,6,8,7,CLIQUE!\n",
      "back,back,5,CLIQUE!\n",
      "back,back,back,finished.\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAeEAAAFCCAYAAADGwmVOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMi4yLCBodHRwOi8vbWF0cGxvdGxpYi5vcmcvhp/UCwAAIABJREFUeJzt3XucVXW9//HXnvuMKIJCmhdEPWJeME+i4i3pqNzMFBOOEDoeqwOmBj7IS8dKyw4/ccLSRK1+NRSaePt5KqGOVwIUBS9BYlpeoLyBCSgwMAOzfn8sBofN3nPbl7Vn7dfz8ZiHzuy11/4uPmvPe9Z3f/dnJ4IgCJAkSXlXEvUAJEkqVoawJEkRMYQlSYqIISxJUkQMYUmSImIIS5IUEUNYkqSIGMKSJEXEEJYkKSKGsCRJETGEJUmKiCEsSVJEDGFJkiJiCEuSFBFDWJKkiBjCkiRFxBCWJCkihrAkSRExhCVJioghLElSRAxhSZIiYghLkhQRQ1iSpIgYwpIkRcQQliQpImVRD0BSG1atgvp6WLoU1q2Dnj1h4EC46CLo0yfq0UnKUCIIgiDqQUhKsngxTJ0Kc+eG32/a9PFt1dUQBDB8OFxzDQwaFM0YJWXMEJYKze23w5Qp0NAQhm06iUQYyHV1MHFi/sYnKWucjpYKSUsAb9zY/rZBEG43ZUr4vUEsdTsuzJLy5IADDqC6upoePXqw1157UVtby/r167ff/tT//b987tJL2XXjRnoCnweWJ+1jLTAR2AuoAY4EftESxEuW0KNHj+1fJSUl2x+vR48e3HXXXXk6UkkdZQhLefTb3/6W9evX8+KLL/LCCy8wdepUAJ5++mnO+M//5AvNzbwNvAEcBZwIvL7tvo3AacAK4GlgHXATcDUwfeNGmDqV9evXb//af//9tz/e+vXrGTduXJ6PVlJ7DGEpAnvttRdDhw7lxRdfBODKyZO5APg6sCvQG7gBOB64btt9fgWsBO4D+gPlwDDgFuDbwIcPPwyrV+fxKCRlyhCWIvCPf/yDuXPncvDBB7Nx40aeevZZzivZ+ek4Gnhk2/8/AgwHdkna5lxgE/B0EIRvZ5LUbRjCUh6dffbZ7Lrrruy333707duX66+/ng8++IDmIGDvpqadtt8beH/b/7+/7ftkZcCewPuNjbBsWc7GLin7DGEpjx566CE++ugjnnzySf7yl7/w/vvv06tXL0qAd1Js/w5hwLLtv6m22UIY0HsCrFmTi2FLyhFDWIrAZz/7WWpra5kyZQq77LILg/v04b4U290L/Nu2/z8NmAtsSNrmAaCS8PVjevXK1ZAl5YAhLEVk0qRJPPLII9TV1XFydTUzCRdZfQSsAa4lXAX9nW3bjwf2Bc4D3gSagD8AlxMu3qopL2fjwQfn9RgkZcYQlvIsCAKee+45vvvd79Lc3My0adM4+hvf4Pfl5TxI+LpvP+AFYAHwL9vuVwk8CuwHHAfsBlwBfB/4BhBs3cqRdXWMGTOGuS3tLiUVNENYypNFixbxpz/9iYEDB3LeeefRp08fXn75ZVatWsXoSy/l5DPP5MlEgvXAh8DDwBFJ++gN3Am8BzQALwFfBkgkqDj7bJasWMGQIUO4/vrraWxs5JFHHmH58uSWH5IKhb2jpRzavHkzv/vd76ivr2fBggWcc8451NbWctJJJ1GS/JakxYvZesoplLb+sIaOqqmBefPgmGO2/+jll19m5syZ/PKXv2S//fajtraWf//3f6eXrxtLBcMQlrIsCAKef/556uvrueeeezjyyCOpra1l1KhR9OjRI+39VqxYwe1HHcUNDQ2UNTZ2+PG2VlZSevPNaXtHb9myhUcffZT6+np+//vfM3ToUGprazn99NMpK7N9vBQlQ1jKknfffZe77rqL+vp6NmzYQG1tLRdccAEHHHBAu/f94IMPOPHEE5k4cSKXl5d3+FOUtlZUcHV5OWP/+EeOPvrodh9nzZo1zJ49m/r6elauXMn48eO58MILOeywwzpxpJKyxRCWMtCp6eY0GhoaOP300xk8eDA33XRT+MMlS8LPE54zJ/zIwoaGj+/Q8nnCI0bANdfwwIoVXH755SxcuLBDgd/C6Wopeoaw1EldnW5OZevWrYwePZrKykpmzZq1c3CvXh22oly2LGzE0asXHHkk1NZCnz7bN7v11lu57bbbWLhwIXvssUenxuB0tRQdQ1jqoEymm1MJgoDLL7+cl156iblz51JZWZnR+K688koWLlzIo48+SnV1dZf24XS1lF+GsNSGbEw3pzNt2jRmzZrF/Pnz6dmzZ8ZjbW5uZvz48TQ0NHDfffdRWlqa0f6crpZyzxCWkmRzujmdWbNm8V//9V889dRT7LPPPlnZJ0BjYyPDhw/n0EMP5cc//jGJRCLjfTpdLeWOISxt8+677zJr1izq6+vZuHFjxtPN6Tz66KOMGzeOxx9/nMMPPzyr+wZYt24dp5xyCueffz5XX311VvftdLWUXYawitrmzZv57W9/S319PQsXLszqdHMqL774ImeccQYPPPAAJ598ctb33+Ltt9/mhBNO4Hvf+x7jx4/PyWM4XS1lzhBW0cnHdHMqK1as4MQTT+SHP/whX/ziF3P2OC2WL1/OkCFDmDVrFqeffnrOHsfpaqnrDGEVjXxNN6eyQzOOyy/P+eO1mD9/Pueeey5/+MMfOtTMI1NOV0udYwgr1vI93ZxKymYcefTAAw90qZlHppyultpnCCt2oppuTqXdZhx5kkkzj0w5XS2lZwgrNqKcbk4l2804MpWNZh6Zcrpa2pEhrG6tEKab08l2M45MZbuZR6acrpYMYXVDhTTdnE6umnFkKhfNPDLldLWKmSGsbqPQppvTyXUzjkzlsplHppyuVrExhFXQCnm6OZV8NePIVD6aeWTK6WoVA0NYBac7TDenku9mHJnKVzOPTDldrTgzhFUwust0cypRNePIVL6beWTK6WrFjSGsSHW36eZUom7GkamomnlkyulqxYEhrLzrrtPNqRRKM45MRdnMI1NOV6s7M4SVN8nTzRdeeCEXXnhht7r6ai0IAi677DKWL19eEM04MlUIzTwytWbNGu655x5mzpzpdLW6BUNYORWH6eZ0brzxRu66666CacaRqZZmHhs3buT++++PvJlHppyuVndgCCvr4jTdnE6hNuPIVGNjIyNGjGDAgAEF08wjU05Xq5AZwsqa7ry6uTNamnE88cQTsZzmLORmHplydbUKjSGsjMR5ujmV7tKMI1PdoZlHppyuViEwhNVpxTDdnEp3a8aRqe7SzCNTTlcrSoawOqxYpptT6a7NODLV3Zp5ZMrpauWbIaw2Fdt0cyrdvRlHprprM49MOV2tfDCEtZNinW5OZevWrZx33nlUVVV162YcmerOzTwy5XS1cskQ1nbFPN2cSkszjpdffpk5c+Z0+2YcmbrqqqtYsGBBt27mkSmnq5VthnCRc7o5vRtvvJG7776bP/7xj7FoxpGp5uZmLrjgAjZs2BCLZh6Zcrpa2WAIFyGnm9sX12YcmYpjM49MOV2tTBjCRcTp5o6JezOOTMW5mUemnK5WZxnCMed0c+cUSzOOTBVDM49MOV2tjjCEY8jp5q4ptmYcmSqWZh6ZcrpabTGEY8Tp5q4r1mYcmSq2Zh6ZcrpayQzhbs7p5sy1NOM44YQTmDZtWtTD6XYeeOABvv71r7NgwQL/4OsEp6sFhnC35HRz9tiMIzuKuZlHppyuLm6GcDfidHN22Ywju2zmkTmnq4uPf/YXuM2bN3P//fdz5pln8qlPfYrly5czY8YM/va3v/Htb3/bAO6k1atXM2zYMFauXMm0adOYP38+Dz74oAGcBVOnTqV///6MHTuW9evXM3bsWObPnx/1sLqVXr16MWHCBBYtWsRjjz1GIpHgtNNO47jjjuP2229nzZo1UQ9RWeaVcAFyujl3fvWrX3HxxRdTUVHBrrvuypIlS2zGkUWNjY2cdtppLF++nLVr1zJ+/Hh+8YtfRD2sbs3p6ngzhAuI0825d+655/Lggw8CUF1dzW9+8xtOO+20iEcVH2+88QYnnXQSb7/9NgCf+MQnePfddyMeVXw4XR0/hnBHrFoF9fWwdCmsWwc9e8LAgXDRRdCnT0a7dnVzFrVTpyAI2G233Vi/fj2JRIKKigqGDh3K//zP/0Q98tj4wQ9+wFVXXUVJSQlNTU2Ul5fzyiuv0L9//483yuHzqZjkdHW1NcqfQOk9+2wQnHNOEFRVhV/w8Vd1dfizc84Jt+uE5ubmYMmSJcGll14a7LnnnsGQIUOCmTNnBh999FGODiTmOlinF3/60wAIysvLg7FjxwbPPPNM0NzcHPXoY+f1118PpkyZEvTo0SMAgiuvvDK8IUfPp2LX1NQUzJ07NxgzZkzQs2fPYPTo0cGcOXOCpqamzu/MGuWdIZzOjBlBUFMTBInEjidi8lciEW43Y8ZOu5g6dWowceLE7d+/8847wU033RQcfvjhQf/+/YPrr78+eOONN/J4UDHUiTptra4O7v+3fwvWrl0b9aiLQmNjYzB9+vTgd7/7XVaeT2rfBx98ENx+++3BcccdF+y9997BlVdeGbz00kvbb581a1YwatSo1AFtjSJhCKfScjK2dSImfyWdlLfddltQXV0dVFVVBTNnzgxGjhwZ7L777sFFF10UzJs3L9i6dWuEBxgTWaiT8sA6RWL58uXBVVddFey9997BscceG8yYMSM45JBDgvLy8mDMmDE7/g6yRpExhJM9+2znT8bWJ+XixcHdd98dVFZWBkAABAMGDHC6OduyUCflgXWKXMt09bBhw7b/TqqsrAwmTJgQvhxjjSLlyp9kU6dCQ8MOP/oxcAxQCdS2dd+GBv5+ySWMHTuWzZs3b/9xZWUlF1xwgW8vyqYUdQJ4Gfgc0BM4GPh/qe7b0BDeX7mXok6bgYuBfsCuwNHA3FT3tU5ZUVZWxrBhwzj00EMpLS0FwgWhd9xxB1/96lfTPpda/BWoAr6U6kZrlDHfZNbaqlUwd274N14rnwSuBf4ApD9VgSBgn6VL+c4ll7B5t9147bXXWLFiBYlEgiAI/AD0bElTpy3AF4AJwCPAPODzwAvAIa03DAKYMwdWr3alZy61Uaf9COuzPzAHGA0sAw5ovaF1yqoNGzZwxBFHsP/++3PQQQdRXV3NaS0rnpNq1NrXgEHpbrRGGTOEW6uvT/njUdv+uwT4Rzu7KCkp4boDDoBvfCN749KO0tTpL8DbwGQgQXhFfCLwK+B7yRsnEuF+rFPupKnTLsB1rb4/E+gPPEdSCIN1yqKf/OQnO/+wnQ8suQfYHTgB+Fu6jaxRRpyObm3pUti0KbN9NDTAsmXZGY9SS1OnVH/LB8CfU+3DOuVeB59P7wGvAoenutE65VYbNfoQ+Dbwg/b2YY0yYgi3tm5ddvZjf9fcSlOnQ4G+wE1AE/C/hFOeG9PtxzrlVgeeT03AOOBCwvqlZJ1yp40afYvwtfv9OrIfa9RlTke31rNndvbj54HmVpo6lQMPAZcBNxIuphtNuKAuJeuUW+08n5qB8UAF4eLHtKxT7qSp0YvAo4TrKTrEGnWZV8KtDRwIVVWZ7aO6Go48MjvjUWpt1Gkg4dXvPwkX0r0OHJtqQ+uUe23UKSC8ynoPeIDwD6iUrFNupanRk8CbhAvn9gLqCOv0r6n2YY0yYu/o1latgn79dnqNZMu2r+sJF2b9lHAKIeU0QlUVrFzpSsFcSlMngKWEK6GbgRnAbYQLtna6GrZOuddGnSbw8dVWm2/cs065laZGGwlfE25RRxjKtwM7VcIaZcQr4db69oXhw8PVfq3cAFQD/weYte3/b0h1/0QCRozwZMy1NHWCcCX03oSvDT9G+FalnQLYOuVHmjqtAO4kDOG9CEO4B3BX8v2tU+6lqVENYW1avnoQvld4p0pYo4x5JZxs8WI49VTYmHY5T3o1NTBvHhxzTNaHpSTWqXuwToXPGkXKK+FkgwZBXV14cnVGTU14P0/G/LBO3YN1KnzWKFKl11133XVRD6LgDBoEvXvDE0/Ali1tb5tIfHwyTpyYn/EpZJ26B+tU+FrVqHnLFtrq7RckEiSsUdY4Hd2WJUvCvqhz5oS/HFr3V62uDlu2jRgB11zjX4NRsk7dg3UqeFsWLeJ/hwxhWHMzJaWlO9WosbGR1wYM4FMzZ1qjLDGEO2L1aqivZ/HPf07vkhIO+sxnwiX5tbUuSCgk2+o0Z9o0jh8wgN4HHmidCtG2OrFsWdjkoVcv61Qgfv3rX3PnnXfy5H33pazRy8cdx+fGjOHNN9+ksjLtO/DVCYZwJ0yaNIkDDjiASZMmRT0UtWHw4MFMnz6dwYMHRz0UqdsIgoBjjz2Wb33rW5x11llptxs6dCjnn38+tbW1+RtcjLkwS5LEwoULWbt2LWeeeWab211xxRXcfPPNeP2WHYawJInp06czefJkSkrajoUzzjiDLVu28Pjjj+dpZPFmCEtSkXvttdeYP38+F154YbvbJhIJrrjiCqZPn56HkcWfISxJRe5HP/oRX/7yl9lll106tP24ceNYsmQJL7/8co5HFn+GsCQVsbVr1zJr1iwuvfTSDt+nqqqKiRMn8sMf/jCHIysOhrAkFbGf/vSnjBw5kn322adT95s4cSL33nsv77//fo5GVhwMYUkqUk1NTdxyyy1Mnjy50/f9xCc+wbnnnssdd9yRg5EVD0NYkorU/fffz8EHH8y//mvKTwpu1+TJk7ntttvYvHlzlkdWPAxhSSpCQRBsf1tSVx1++OEMHDiQX//611kcWXExhCWpCC1YsKBDzTna0/J2JZt3dI0hLElF6Oabb+5Qc472nHHGGWzdutXmHV1kCEtSkelMc4722LwjM4awJBWZzjbnaI/NO7rOEJakItKV5hztsXlH1xnCklREutqcoz0tzTtWr16d1f3GnSEsSUUik+Yc7Wlp3nHnnXdmfd9xZghLUpHItDlHe2ze0XmGsCQVgWw052iPzTs6zxCWpCKQreYc7bF5R+cYwpJUBLLVnKM9Nu/oHENYkmIum8052mPzjs4xhCUp5n70ox/xla98JWvNOdozbtw4nnvuOZt3dIAhLEkxtmbNGmbNmsXXvva1vD1mVVUVEyZMsHlHBxjCkhRjuWrO0Z6W5h3vv/9+Xh+3uzGEJSmmmpqauPXWW3P6tqR0Wpp33HHHHXl/7O7EEJakmMp1c4722LyjfYawJMVQS3OOK664IrIxHH744Rx11FE272iDISxJMbRgwQLWrVvHyJEjIx3H5MmTbd7RBkNYkmJo+vTpTJo0KefNOdrT0rzjsccei3QchcoQlqSYee2111iwYEFemnO0p6V5x8033xz1UAqSISxJMZPv5hztsXlHeoawJMVIS3OOSy+9NOqhbFdVVcXEiRNt3pGCISxJMdLSnOOTn/xk1EPZQUvzjtWrV0c9lIJiCEtSTETZnKM9ffv2tXlHCmVRD6A7ePHFF3n44Yd59tln+etf/8qGDRsYO3Ys/fv3j3poamXOnDm88MILvPXWW9TX1zN//nwuueQSevToEfXQpJxqbGykoqIi8uYc7Zk8eTKnnXYaV155JaWlpZSUlES+ejtqicA3b7Vr5syZXHzxxWzduhUIV/s9+eSTnHLKKRGPTK39x3/8BzNnzqS5uZlEIkFZWRnvvvsuvXv3jnpoUk4deOCB7L777nz44YfU1dVx9tlnRz2ktIYMGUKPHj2YN28eU6dOzesHSxSi4v4TpIPGjh3Lnnvuuf37T3/605x88skRjkipfOc736GiogKAsrIyJkyYYACrKDQ2NvLCCy/w+uuvM2HCBO69996oh7STTZs2MX78eJ566ikefvhhNm3aFPWQCoIh3AHl5eV8//vfp6ysjIqKCurq6kgkElEPS0n69evH6NGjASgpKeHaa6+NeERSftTU1ABhq8o1a9bw1ltvRTyinQVBwPPPP08ikSAIAkpLS32pCEO4wy644AIqKiro06cPQ4YMiXo4SuO73/0uAGeddRZ9+/aNeDRSfpSVhct7ampqmD17dkEuzKqurmbJkiUMHz6ciooKGhsbC+Z9zFEyhDuovLycW2+9lZ/97GdeBRewfv368c1vfpO6urqohyLlzfr166mpqWHRokUF/XpwdXU1Dz74IFdffTXNzc2sX78+6iFFzoVZHbFqFdTXw9KlsG4d9OwJAwfCRRdBnz5Rj04trJPiLs05/uh++/EvJ5xAv379oh5hh82ePZuhQ4eye2NjUT9vDeG2LF4MU6fC3Lnh960XElRXQxDA8OFwzTUwaFA0Y5R1UvzF8RyP4zF1RaDUZswIgpqaIEgkgiA8HVJ/JRLhdjNmRD3i4mSdFHdxPMfjeExdVHrdddddF/UfAgXn9tthyhTYuLFj2zc1wRNPQO/e8f6LrdBYJ8VdHM/xOB5TBpyOTrZ4MZx66k4nyMvA14DngD7ATcA5yfetqYF58+CYY/Iw0CKXpk5fAh4DNgB7AVcCX06+r3VSdxDHczzNMQHcA1wPrCQ8rnpgh24MhXpMGXJ1dLKpU6GhYYcfbQG+AJwJfAD8hPCJ8GryfRsawvsr91LUCeAa4E3gQ+A3wLWEfzjtwDqpO4jjOZ7mmB4BrgJ+AXwE/BE4MHmjQj2mDHkl3NqqVdCv344LBIA/A8cTnhwtb046AzgO+F7yPqqqYOXKoljVF5k0dUr2CnAq8CNgdPKN1kmFLI7neBvHdAJw8bavNhXaMWWBV8Kt1den/HGqv1ICwnDeSSKRdj/Kknb+fS8BaoBDgb2BEak2sk4qZHE8x9OMZSuwBFgNHAzsC1wK7Hy9TOEdUxYYwq0tXZryr7RDgb6ErwM3Af8LzANSLitoaIBly3I4SKWrU4sZhLMW84FRQGWqjayTClkcz/E0x/Qe4e/V+wmP50XgBeCGVPsotGPKAkO4tXXrUv64HHgIeJhwwcAPCKd+9k23nzVrcjA4bZemTq2VAicB/wBuT7eRdVKhiuM5nuaYqrf99zLCq/o9gSuAOen2U0jHlAV+nnBrPXumvWkg4dVvixOAC9Nt3KtX9saknbVRp2RbgNfS3WidVKjieI6nOaZehBc0HW4GXEjHlAVeCbc2cGD4wn8KS4FNhFPQdcA7QG2qDaur4cgjczRAAWnrtIrwbQ7rCV9n+gPwa+BzqfZhnVTI4niOt/H79SLgVsLjWwP8kPDdKDsptGPKAldHt9bG6r1vAD8jfO3iZMIT5uBU+4jh6r2Ck6ZOq4EvAn8CmoF+wOXAV1LtwzqpkMXxHG/j92sT8HXgbqCK8OW+adv+fweFdkxZ4JVwa337hr1KU3xK0k2Ef6GtB+aSJoATCRgxIlYnSEFKU6c+hC8ZrCV8D+Uy0vxysk4qdHE8x9v4/VpOuNhsLfAucAspArgQjykLvBJO1kZHl3bFtKNLQbJOirs4nuNxPKYMeSWcbNAgqKsLC94ZNTXh/WJ2ghQs66S4i+M5HsdjypAf4JDKoEFhs/AnnoAtW9reNpH4+ASZODE/41PIOinu4niOx/GYMuB0dFuWLAl7lc6ZE54MrXuetnze5YgR4eddxvAvtG7DOinu4niObzumxoceoqSsjLLGxu03NVdWUtLyGnB3OqYuMIQ7YvVqqK9n8c9/Tu+SEg76zGfCZfK1tbFbJNCtbavTnGnTOH7AAHofeKB1UrxsO8f/OGMGB/bqxb5HHNGtz/Hm5mYG9O7Nc5ddxm4rVsCaNSxcvpySo45i8J13dstj6ixDuBMmTZrEAQccwKRJk6IeitowePBgpk+fzuDBg6MeipQT559/PmeddRbnn39+1EPJyF/+8heGDRvGm2++uf1nP/nJT1i4cCEzZ86MbmB55MIsSVIkFi1atNMfy4MHD+bpp5+OaET5ZwhLkiLx9NNP7xTChx12GO+99x7vv/9+RKPKL0NYkhSJVCFcWlrKoEGDWLRoUUSjyi9DWJKUdx9++CGvv/46Rx111E63FdOUtCEsScq7Z599lqOPPpqKioqdbhs8eLBXwpIk5UqqqegWxx9/PIsXL2br1q15HlX+GcKSpLx7+umnOf7441Pe1rt3bz75yU/y5z//Oc+jyj9DWJKUV0EQ8Mwzz7T5Xv5ieV3YEJYk5dWrr77Krrvuyt577512G0NYkqQcaOv14BaGsCRJOdCREC6Wph2GsCQprzoSwqWlpRx77LGxf6uSISxJypu2mnQkK4YpaUNYkpQ3bTXpSHb88ccbwpIkZUtb7w9Odvzxx7NkyZJYN+0whCVJeZPq4wvTKYamHYawJCkvgiDoVAhD/F8XNoQlSXnRkSYdyQxhSZKyoCNvTUpmCEuSlAVdCeG4N+0whCVJedGVEI570w5DWJKUc51p0pEszlPShrAkKec606Qj2eDBg70SliSpqzrTpCPZcccdx+LFi2PZtMMQliTlXFdeD24R56YdhrAkKaeCIOCZZ57pcghDfF8XNoQlSTnVlSYdyQxhSZK6IJOp6BaGsCRJXZCNEI5r0w5DWJKUU9kI4ZamHc8880yWRlUYDGFJUs5k0qQjWRynpA1hSVLOZNKkI5khLElSJ2RjKrpFHJt2GMKSpKxramoCMuuUlax1046mpiaCIMjKfqNkCHfArbfeSllZGbfccgtXXHEFZWVl/OY3v4l6WEoyZswYysrKWLRoESeddBJVVVX8/e9/j3pYUtZ885vfpKysjNmzZ/OlL32J8vLygu2pfOCBB7LHHnvwyCOPsGzZsoy7XW3YsIH77rsPgGHDhlFTU7P9++7MEO6AoUOHUl5eThAEBEFAZWUlJ510UtTDUpIvfOELVFVVAdDc3Ez//v3Zd999Ix6VlD0jR46koqKCIAhobm5mt9124+ijj456WCkddNBBfPDBB2zZsoUbbriBMWPGZLS/uXPnMnr0aF555RXeffddysvLOeyww7I02ugYwh1wyCGHMHLkSBKJBGVlZVx22WX07t076mEpyZgxY+jVqxcA1dXV1NXVkUgkIh6VlD0nnngin/70pwGorKzkuuuuo7KyMuJRpfb5z3+esrIyACoqKrj33nsz2t+5557LqFGjth9vaWlpLEI4EcRhUj0PXn31VQ477DBKS0tYiXZDAAAJAklEQVR55513DOECdffddzNu3Dj2339/3nzzTUNYsbNw4UJOOeUUqqur+ec//1mwIfz8889z7LHHUlJSwuzZsznnnHMy3mdDQwNHH300r7zyCkOGDOHxxx/Pwkij5ZVwBx1yyCEcccQRjBw50gAuYGPGjGG33Xbj2muvNYAVSyeeeCL77LMPF198ccEGMMBRRx1FEASMHz8+KwEM4QzXI488QllZGYcffnhW9hk1r4Q7YtUqqK8nWLqUxLp10LMnDBwIF10EffpEPTq1sE6Ku0I/x7eNj6VLYd06Vjc1scepp1Jy8cVZHd9LTzzBQfPnU/Xqq1CI/w6dESi9Z58NgnPOCYKqqvALPv6qrg5/ds454XaKjnVS3BX6OZ6v8RX6v0MXGMLpzJgRBDU1QZBI7Fjo5K9EItxuxoyoR1ycrJPirtDP8XyNr9D/HbrIEE6lpdhtFTr5qxsVPTask+Ku0M/xfI2v0P8dMuBrwskWL4ZTT4WNGzt/35oamDcPjjkm68NSEuukuCv0czxf4yv0f4cMuTo62dSp0NCww482AxcD/YBdgaOBuanu29AQ3l+5Z50UdynOcYA3gRFAL2Av4FJgS/JG+TjH8zW+NI9zKlAF9Nj2NSDVfbvBc90r4dZWrYJ+/WDTph1+vAG4CagF9gfmAOcDy4ADkvdRVQUrV3a/FXrdiXVS3KU5xyEMuL7AHcBa4HTgK8DlyRvm8hzP1/jaeJxTgS8BX25vrAX+XPdKuLX6+pQ/3gW4jvAXeQlwJtAfeC7VxolE2v0oS6yT4q6Nc/MNYDThVeBewDDgpVQb5vIcz9f4sjH+An+uG8KtLV2a8i+uZO8BrwIp3yre0ADLlmV5YNqBdVLctXGOfx24B9gIvEX4ksuwVBvm8hzP1/jaea5fA+wJnAg8mW6jAn+uG8KtrVvX7iZNwDjgQuDQdButWZO9MWln1klx18Y5/lnCK8vdgH2BY4Cz022cq3M8X+Nr43FuBF4nDPqvAp8HXuvq40TIEG6tZ882b24GxgMVwI/b2nDbhwgoR6yT4i7NOd4MDAVGEa6BeB9YA1yVbj+5OsfzNb42nuvHES7ArCT8Y/tEwnUgXXqcCBnCrQ0cGL6In0JAuPL2PeABoDzdPqqr4cgjczI8bWOdFHdpzvEPgL8TrjiuBPYALiJN+OTyHM/X+Np4ridLED7/u/Q4EXJ1dGttrMSbALwIPEq4HD6tAl+JFwvWSXHXxjl+IOH06xRgPWHI1QB3JW8Y0erorI4vzeOsBZ4hnPouA2Zve8znSfFWpQJ/rnsl3FrfvjB8eLiarpUVwJ2Ev9z34uP3pe10UiUSMGJEwRY7NqyT4i7NOQ7wIPB7oA9wMGEI3Zy8Ua7P8XyNL83jNAHXbnuMPYFbgYdIEcDd4LnulXCymHdniQ3rpLgr9HPcjllZ4ZVwskGDoK4uLF5n1NSE9yvgYseKdVLcFfo5nq/xFfq/Q6aia1td4GL6iR2xY50Ud4V+jvspShkxhNuyeHEQjBoVfkZldfWOhW757MpRo8LtFB3rpLgr9HM8X+Mr9H+HLvA14Y5YvTpse7ZsWfim7169wiXvtbUF/YJ/0bFOirtCP8e3je9XV17JuJEjKendOzfjK/R/h04whCVJWVVWVsamTZsoKyuLeigFz4VZkiRFxBCWJCkihrAkSRExhCVJioghLElSRAxhSZIiYghLkhQRQ1iSpIgYwpIkRcQQliQpIoawJEkRMYQlSYqIISxJUkQMYUmSImIIS5IUEUNYkqSIGMKSJEXEEJYkKSKGsCRJETGEJUmKiCEsSVJEDGFJkiJiCEuSFBFDWJKkiBjCkiRFxBCWJCkihrAkSRExhCVJioghLElSRAxhSZIiYghLkhQRQ1iSpIgYwpIkRcQQliQpImVRD0CSFA8///nPee+992hububGG2+kT58+fPWrX416WAUtEQRBEPUgJEnd36c+9SleeeUVgiAgkUjQr18/3njjjaiHVdCcjpYkZcWNN97ILrvsAkBNTQ1Tp06NeESFzythSVJWBEHAgAED+Otf/8r+++/P66+/TmlpadTDKmheCUuSsiKRSFBXVwfAf//3fxvAHeCVsCQpa4IgYMKECdx2222Ulbn2tz2GsCQpO1atgvp6WLoU1q2Dnj1h4EC46CLo0yfq0RUkQ1iSlJnFi2HqVJg7N/x+06aPb6uuhiCA4cPhmmtg0KBoxligDGFJUtfdfjtMmQINDWHYppNIhIFcVwcTJ+ZvfAXOCXtJUte0BPDGje1vGwThdlOmhN8bxIBXwpKkrli8GE49dYcA7pG0SQNwCXBr8n1ramDePDjmmJwOsTvwLUqSpM6bOjWcgm5lfauv94Bq4LxU921oCO8vr4QlSZ20ahX067fjAqwkM4HrgdeARKoNqqpg5cqiXzXtlbAkqXPq69vdZCZwAWkCGMKFWh3YT9wZwpKkzlm6tM2r4JXAPODCtvbR0ADLlmV5YN2PISxJ6px169q8+ZfASUD/9vazZk2WBtR9GcKSpM7p2bPNm39JO1fBLXr1ysZoujVDWJLUOQMHhgurUngKeIs0q6Jbq66GI4/M8sC6H1dHS5I6p43V0f8JbAR+1d4+XB0NeCUsSeqsvn3DXtCJndc+30kHAjiRgBEjij6AwSthSVJXpOiY1WF2zNrOK2FJUucNGhR+GENNTefuV1MT3s8ABvwAB0lSV7V8CIOfotRlTkdLkjKzZEnYC3rOnDBsW/eUbvk84REjws8T9gp4B4awJCk7Vq8OW1EuWxY24ujVK3wbUm2ti7DSMIQlSYqIC7MkSYqIISxJUkQMYUmSImIIS5IUEUNYkqSIGMKSJEXEEJYkKSKGsCRJETGEJUmKiCEsSVJEDGFJkiJiCEuSFBFDWJKkiBjCkiRFxBCWJCkihrAkSRExhCVJioghLElSRAxhSZIiYghLkhQRQ1iSpIgYwpIkRcQQliQpIoawJEkRMYQlSYqIISxJUkQMYUmSImIIS5IUEUNYkqSIGMKSJEXEEJYkKSKGsCRJETGEJUmKiCEsSVJEDGFJkiJiCEuSFBFDWJKkiBjCkiRF5P8DCjUCPQwJS9wAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "L = formatCliquesList(CLIQUES(G))\n",
    "tree, pos, labels = createTree(L)\n",
    "nx.draw(tree, pos=pos, labels=labels, with_labels=True)\n",
    "plt.show()"
   ]
  }
 ],
 "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.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}