Quandle-counting-poly.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The quandle counting polynomial invariant of knotted 4-valent graphs\n",
    "\n",
    "This notebook is intended to show the process of finding the quandle counting polynomial invariant $\\Psi_Q (G)$ for a choice of knotted 4-valent graph $G$, and a quandle $Q$. It uses Python code from the package Graphpoly to do this; here are the steps used, given a specific Dowker-Thistletwaite sequence for a knotted graph.\n",
    "\n",
    "1. Find the orientation of the graph nodes by running the DT algorithm on the sequence, giving the $f(i)$ function on node labels $i$. The convention is that $f(i) = +1$ if the other arc crosses from right to left, and $f(i) = -1$ if the other arc crosses from left to right.\n",
    "1. Find the planar diagram (PD) code for the graph, using the DT sequence and the orientation just found.\n",
    "1. From the PD code, find all possible Eulerian circuits through the graph. This gives the multiset of induced knot diagrams for the knot.\n",
    "1. For each induced knot diagram, find the number of quandle colorings of the knot, with the chosen quandle $Q$.\n",
    "1. Construct the polynomial invariant $\\Psi_Q (G)$ by writing the generating function for the multiset of quandle colorings.\n",
    "\n",
    "For this notebook, we will use the example of the graph given by the DT sequence $3^\\ell 5^u 7^- 1^+$. This is represented as a Python list by\n",
    "\n",
    "```python\n",
    "    seq = [[0, 3, -2], [2, 5, 2], [4, 7, -1], [6, 1, 1]]\n",
    "```\n",
    "\n",
    "For each node, there is a list of three numbers in this list. The first element is an even number, the second an odd; these are the two labels for that particular node. The node labels are in the set $\\{0, 1, \\cdots, 2N - 1\\}$, for a graph with $N$ nodes. The third element gives the crossing or vertex type: -2 for a vertex with the upper edge on the odd label (label superscript $\\ell$), -1 for a crossing with the upper edge on the odd label (label superscript $-$), and the positive numbers are the flipped cases (superscripts $u$ and $+$)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find the orientation of the graph nodes\n",
    "\n",
    "First, we import the function `isRealizable(seq, f_list = False)`. If the function is given a Python list `seq`, the function returns `True` if the sequence is a realizable DT sequence, and `False` if the sequence does not represent a planar graph. Note that the given sequence `seq` may or may not include the crossing or vertex type. If the parameter `f_list` is set to `True`, for a realizable sequence, the function will return a list of $f(i)$ values for each node label $i$. These indicate the crossing information at the node $i$ for the Eulerian circuit described by the DT sequence. See \"Classification of knot projections\", Topology Appl. 16, 19–31 (1983), for details."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Graphpoly.isRealizable import isRealizable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next command creates the orientation list `orientList` for the example DT sequence `seq`. Remember that DT sequences do not differentiate between a sequence and its mirror image. Thus, one can make a global change in sign of the $f(i)$ for all $i$, and still have a realizable sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 1, -1, -1, 1, 1, -1, -1]"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Example sequence 3^l 5^u 7^- 1^+\n",
    "\n",
    "seq = [[0, 3, -2], [2, 5, 2], [4, 7, -1], [6, 1, 1]]\n",
    "\n",
    "orientList = isRealizable(seq, f_list = True)\n",
    "orientList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Find the planar diagram code\n",
    "\n",
    "The function `planarDiagram(seq, f_list)` takes the DT sequence `seq` and the orientation list `f_list`, and produces a planar diagram list from them. Thus, the function returns a list of two lists. The first list gives the PD code for the graph. **Note:** the numbers in this list refer to *half-edges* (or *darts*), not *nodes*. There can be problems if an induced knot diagram has self-loops, so using half-edges allows for a unique number associated with each of the four half-edges incident to the node.\n",
    "\n",
    "A vertex is treated as the appropriate crossing, based on its vertex state. The second list gives the node type for each node. Again, we use 1 for a crossing, and 2 for a vertex. The sign of the numbers comes from $f(i)$, so they are positive if the upper crossing is right-to-left, and negative if left-to-right."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Graphpoly.planarDiagram import planarDiagram"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here, we show the planar diagram notation for $3^\\ell 5^u 7^- 1^+$, where the orientation is that found above in a previous cell. The node type, along with the value of $f(i)$, is recorded in `nodeTypeList`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[[0, 6, 1, 7], [2, 12, 3, 13], [8, 14, 9, 15], [10, 4, 11, 5]]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[PD_code, nodeTypeList] = planarDiagram(seq, orientList)\n",
    "PD_code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## List all induced knot diagrams\n",
    "\n",
    "We use a modified version of Hierholzer's algorithm to find all possible Eulerian circuits through the graph. Note that there is only one possible way to pass along the circuit when coming into a crossing, but three possible ways for a vertex. Thus, the algorithm must take this freedom into account, using the list `nodeTypeList` obtained from `planarDiagram()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Graphpoly.createCircuits import createCircuits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `createCircuits()` returns a list of `graph` objects, each of which represents a particular choice of Eulerian circuit through the original graph. The half-edges of the circuit can be returned using `graph.listEPath()`. The labels of the half-edges are the same as those used in `planarDiagram()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 15, 14, 13, 12, 11, 4, 3, 2, 1, 6, 5, 10, 9, 8, 7]\n",
      "[0, 7, 8, 9, 10, 5, 6, 1, 2, 3, 4, 11, 12, 13, 14, 15]\n",
      "[0, 6, 5, 10, 9, 8, 7, 1, 2, 3, 4, 11, 12, 13, 14, 15]\n",
      "[0, 15, 14, 13, 12, 11, 4, 3, 2, 1, 7, 8, 9, 10, 5, 6]\n",
      "[0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]\n",
      "[0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 1, 2, 3, 4, 5, 6]\n",
      "[0, 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12, 13, 14, 15]\n",
      "[0, 15, 14, 13, 12, 11, 5, 6, 1, 2, 3, 4, 10, 9, 8, 7]\n",
      "[0, 7, 8, 9, 10, 4, 3, 2, 1, 6, 5, 11, 12, 13, 14, 15]\n",
      "[0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5, 11, 12, 13, 14, 15]\n",
      "[0, 15, 14, 13, 12, 11, 5, 6, 7, 8, 9, 10, 4, 3, 2, 1]\n",
      "Number of circuits: 12\n"
     ]
    }
   ],
   "source": [
    "Ecircuits = createCircuits(PD_code, nodeTypeList)\n",
    "graphList = [graph for graph in Ecircuits]\n",
    "\n",
    "for graph in graphList:\n",
    "    print(graph.listEPath())\n",
    "    \n",
    "print('Number of circuits:', len(graphList))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## PD codes for induced knot diagrams\n",
    "\n",
    "Now that we have lists of half-edges that give all of the induced knot diagrams for a given graph, we write these in terms of planar diagram codes. This is done by the function `createInducedKnot()`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "from Graphpoly.createInducedKnot import createInducedKnot"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The function `createInducedKnot(circuit, PD_code)` takes a list `circuit` produced by `createCircuits()`, along with the PD code `PD_code` for the original knotted graph. It returns the PD code and the $f(i)$ for the induced knot diagram. For the PD code, the labels for the half-edges have been renumbered, to ensure that for an induced knot with $N$ crossings, all half-edge labels are in the set $\\{0, 1, ..., 4N\\}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 15, 14, 13, 12, 11, 4, 3, 2, 1, 6, 5, 10, 9, 8, 7] -> [[[1, 0, 0, 0], [0, 0, 1, 0]], [1, 1]]\n",
      "[0, 7, 8, 9, 10, 5, 6, 1, 2, 3, 4, 11, 12, 13, 14, 15] -> [[[0, 0, 1, 0], [1, 0, 0, 0]], [1, 1]]\n",
      "[0, 6, 5, 10, 9, 8, 7, 1, 2, 3, 4, 11, 12, 13, 14, 15] -> [[[0, 0, 1, 0], [1, 0, 0, 0]], [-1, 1]]\n",
      "[0, 15, 14, 13, 12, 11, 4, 3, 2, 1, 7, 8, 9, 10, 5, 6] -> [[[1, 0, 0, 0], [0, 0, 1, 0]], [-1, 1]]\n",
      "[0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] -> [[[3, 0, 2, 0], [2, 0, 1, 0], [0, 2, 3, 2], [1, 2, 0, 2]], [1, 1, 1, 1]]\n",
      "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] -> [[[0, 2, 1, 2], [1, 0, 2, 0], [3, 2, 0, 2], [2, 0, 3, 0]], [1, 1, 1, 1]]\n",
      "[0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 1, 2, 3, 4, 5, 6] -> [[[2, 0, 1, 0], [1, 0, 0, 0], [0, 0, 2, 0]], [1, -1, -1]]\n",
      "[0, 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12, 13, 14, 15] -> [[[2, 0, 0, 0], [0, 0, 1, 0], [1, 0, 2, 0]], [-1, -1, 1]]\n",
      "[0, 15, 14, 13, 12, 11, 5, 6, 1, 2, 3, 4, 10, 9, 8, 7] -> [[[1, 0, 0, 0], [0, 0, 1, 0]], [1, -1]]\n",
      "[0, 7, 8, 9, 10, 4, 3, 2, 1, 6, 5, 11, 12, 13, 14, 15] -> [[[0, 0, 1, 0], [1, 0, 0, 0]], [1, -1]]\n",
      "[0, 1, 2, 3, 4, 10, 9, 8, 7, 6, 5, 11, 12, 13, 14, 15] -> [[[0, 0, 1, 0], [1, 0, 2, 0], [2, 0, 0, 0]], [-1, 1, -1]]\n",
      "[0, 15, 14, 13, 12, 11, 5, 6, 7, 8, 9, 10, 4, 3, 2, 1] -> [[[0, 0, 2, 0], [2, 0, 1, 0], [1, 0, 0, 0]], [-1, 1, -1]]\n"
     ]
    }
   ],
   "source": [
    "for graph in graphList:\n",
    "    print(graph.listEPath(), '->', createInducedKnot(graph))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Alexander quandles\n",
    "\n",
    "Now that we have a list of induced knot diagrams for the original knotted graph, we need a way of finding the quandle counting polynomial for these diagrams. This can be done with linear algebra when we use a class of quandles known as *linear Alexander quandles*. For a number $n$, and a number $t$ relatively prime to $n$, the Alexander quandle $\\Lambda_{n, t}$ is defined on integers $x, y \\in \\mathbb{Z}_n$ by\n",
    "$$\n",
    "    x \\triangleleft y = t x + (1 - t) y\n",
    "$$\n",
    "The inverse $\\triangleleft^{-1}$ of this operation is given by\n",
    "$$\n",
    "    x \\triangleleft^{-1} y = t^{-1} x + (1 - t^{-1}) y\n",
    "$$\n",
    "where $t^{-1}$ is the inverse of $t$ mod $n$. Since $n$ and $t$ are relatively prime, there is a unique inverse.\n",
    "\n",
    "Suppose there is a crossing in the induced knot diagram, with the edges colored by $x_i, x_j, x_k \\in \\mathbb{Z}_n$. Then, testing whether these colors are a valid coloring of the knot with $x_i \\triangleleft x_j = x_k$ by quandle elements is equivalent to solving the equation\n",
    "$$\n",
    "    t x_i + (1 - t)x_j - x_k = 0\n",
    "$$\n",
    "Thus, finding all allowed quandle colorings of an $N$ crossing knot is the same as finding the nullspace of the $N \\times N$ matrix, whose entries are determined by the equation above.\n",
    "\n",
    "To help in this process, we first define a function `extEuclid(n, t)` which uses the extended Euclidean algorithm to find the greatest common divisor (GCD) of two integers $n, t$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"\n",
    "This program uses the Euclidean algorithm to find the inverse of t mod n. This\n",
    "is done by solving the equation\n",
    "\n",
    "    an + bt = 1\n",
    "    \n",
    "for the number b. The method uses recursive calls to the algorithm, as outlined\n",
    "on the page https://theprogrammingexpert.com/euclidean-algorithm-python/\n",
    "\"\"\"\n",
    "\n",
    "def extEuclid(n, t):\n",
    "    \n",
    "    if n == 0:\n",
    "        return t, 0, 1\n",
    "    \n",
    "    gcd, u, v = extEuclid(t % n, n)\n",
    "    x = v - (t // n) * u\n",
    "    y = u\n",
    "    \n",
    "    return gcd, x, y"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, if the GCD of $n, t$ is 1, we can define a linear Alexander quandle $\\Lambda_{n, t}$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "import sympy as sp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}0 & 2 & 1\\\\2 & 1 & 0\\\\1 & 0 & 2\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[0, 2, 1],\n",
       "[2, 1, 0],\n",
       "[1, 0, 2]])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Define numbers n, t\n",
    "\n",
    "N = 3      # Must be prime\n",
    "t = 2\n",
    "\n",
    "(gcd, a, b) = extEuclid(N, t)\n",
    "\n",
    "if gcd != 1:\n",
    "    print('N, t not relatively prime')\n",
    "else:\n",
    "    Q = sp.Matrix([[(t * iii + (1 - t) * jjj) % N for jjj in range(N)] for iii in range(N)])\n",
    "    display(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we use this operation matrix to find the appropriate matrix to solve for the number of quandle colorings for a given induced knot."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import Matrix, Poly, GF\n",
    "from sympy.matrices.normalforms import smith_normal_form\n",
    "from sympy.abc import u"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n, t, f = 3 2 Poly(2*u**9 + 10*u**3, u, domain='ZZ')\n"
     ]
    }
   ],
   "source": [
    "# Create dictionary to hold multiset information\n",
    "\n",
    "coeffDict = {}\n",
    "\n",
    "# Go through each induced knot diagram for the graph;\n",
    "# find number of quandle colorings for the induced knot diagram\n",
    "\n",
    "for kkk in range(len(graphList)):\n",
    "    \n",
    "    # Definitions\n",
    "    \n",
    "    [knot, f_list] = createInducedKnot(graphList[kkk])\n",
    "    num_nodes = len(knot)\n",
    "    \n",
    "    # Special cases\n",
    "    \n",
    "    if knot == [] or knot == [[0, 0, 0, 0]]:\n",
    "        coeffDict[(N, )] = coeffDict.get((N, ), 0) + 1\n",
    "        continue\n",
    "        \n",
    "    # General case with knot having more than one crossing\n",
    "    \n",
    "    M = Matrix([[0 for jjj in range(num_nodes)] for iii in range(num_nodes)])\n",
    "    \n",
    "    # Go through each node, and add appropriate linear equation coefficients to M\n",
    "    \n",
    "    for iii in range(num_nodes):\n",
    "        node, f = knot[iii], f_list[iii]\n",
    "\n",
    "        if node[0] == node[1]:          # Self-loop; entering edge is undercrossing\n",
    "            M[iii, node[0]] = 1\n",
    "            M[iii, node[2]] = N - 1\n",
    "            continue\n",
    "\n",
    "        if node[1] == node[2]:          # Self-loop; entering edge is overcrossing\n",
    "            M[iii, node[0]] = 1\n",
    "            M[iii, node[2]] = N - 1\n",
    "            continue\n",
    "\n",
    "        if f == 1:                      # Overcrossing is right-to-left\n",
    "            M[iii, node[0]] = N - 1\n",
    "            M[iii, node[1]] = (1 - t) % N\n",
    "            M[iii, node[2]] = t\n",
    "\n",
    "        if f == -1:                     # Overcrossing is left-to-right\n",
    "            M[iii, node[0]] = t\n",
    "            M[iii, node[1]] = (1 - t) % N\n",
    "            M[iii, node[2]] = N - 1\n",
    "            \n",
    "    # Find null space of matrix M\n",
    "            \n",
    "    A = smith_normal_form(M, domain = GF(N))\n",
    "    dim = len(A.nullspace())\n",
    "    \n",
    "    coeffDict[(N ** dim, )] = coeffDict.get((N ** dim, ), 0) + 1\n",
    "    \n",
    "# Create generating function for multiset\n",
    "\n",
    "f = Poly.from_dict(coeffDict, u)\n",
    "print('n, t, f =', N, t, f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Directing counting\n",
    "\n",
    "The matrix method above works only for a linear Alexander quandle. For an arbitrary quandle, we can directly count the number of quandle colorings of the graph. The quandle can be defined by a matrix $M_{ij}$, giving the results $x_i \\triangleleft x_j$ of the quandle operation. An example is shown below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\left[\\begin{matrix}0 & 0 & 0 & 0\\\\1 & 1 & 3 & 2\\\\2 & 3 & 2 & 1\\\\3 & 2 & 1 & 3\\end{matrix}\\right]$"
      ],
      "text/plain": [
       "Matrix([\n",
       "[0, 0, 0, 0],\n",
       "[1, 1, 3, 2],\n",
       "[2, 3, 2, 1],\n",
       "[3, 2, 1, 3]])"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "Q = sp.Matrix([[0, 0, 0, 0], [1, 1, 3, 2], [2, 3, 2, 1], [3, 2, 1, 3]])\n",
    "display(Q)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code below goes through a similar algorithm to that given above, going through each induced knot diagram for the original knotted graph. However, instead of constructing a matrix using a linear Alexander quandle, the number of quandle colorings is counted by trying each possible crossing."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "from itertools import product"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Poly(2*u**10 + 10*u**4, u, domain='ZZ')\n"
     ]
    }
   ],
   "source": [
    "# Create dictionary to hold multiset information\n",
    "\n",
    "coeffDict = {}\n",
    "\n",
    "# Number of elements in quandle\n",
    "\n",
    "N = sp.shape(Q)[0]\n",
    "\n",
    "# Go through each induced knot diagram for the graph;\n",
    "# find number of quandle colorings for the induced knot diagram\n",
    "\n",
    "for kkk in range(len(graphList)):\n",
    "    \n",
    "    # Definitions\n",
    "    \n",
    "    [knot, f_list] = createInducedKnot(graphList[kkk])\n",
    "\n",
    "    num_nodes = len(knot)\n",
    "    num_colorings = 0\n",
    "    \n",
    "    # Special cases\n",
    "    \n",
    "    if knot == [] or knot == [[0, 0, 0, 0]]:\n",
    "        coeffDict[(N, )] = coeffDict.get((N, ), 0) + 1\n",
    "        continue\n",
    "    \n",
    "    # General case with knot having more than one crossing; there are\n",
    "    # num_nodes total edges, since every edge on an oriented knot (not a \n",
    "    # link!) starts at a crossing.\n",
    "\n",
    "    for colorList in product(range(N), repeat = num_nodes):\n",
    "        colorList = list(colorList)\n",
    "\n",
    "        flag = False\n",
    "        iii = 0\n",
    "\n",
    "        while iii < (num_nodes - 1):\n",
    "\n",
    "            node, f = knot[iii], f_list[iii]\n",
    "\n",
    "            if node[0] == node[1] or node[1] == node[2]:    # Self-loop\n",
    "                if colorList[node[0]] != colorList[node[1]] != colorList[node[2]] != colorList[node[3]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "\n",
    "            if f == 1:                                      # Overcrossing is right-to-left\n",
    "                if Q[colorList[node[2]], colorList[node[1]]] != colorList[node[0]] \\\n",
    "                    or colorList[node[1]] != colorList[node[3]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "\n",
    "            if f == -1:                                     # Overcrossing is left-to-right\n",
    "                if Q[colorList[node[0]], colorList[node[1]]] != colorList[node[2]] \\\n",
    "                    or colorList[node[1]] != colorList[node[3]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "\n",
    "            iii += 1\n",
    "\n",
    "        if not flag:            # All nodes pass required tests\n",
    "            num_colorings += 1\n",
    "\n",
    "    coeffDict[(num_colorings, )] = coeffDict.get((num_colorings, ), 0) + 1\n",
    "\n",
    "# Print polynomial obtained\n",
    "\n",
    "f = Poly.from_dict(coeffDict, u) \n",
    "print(f)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}