{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Example script to use Nauty from Python"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nauty can be used to reduce any graph into a normal form. In this notebook, we show how to use the Nauty functionality from Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "import oapackage"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Define a function to invert a permutation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def inverse_permutation(perm):\n",
    "    inverse = [0] * len(perm)\n",
    "    for i, p in enumerate(perm):\n",
    "        inverse[p] = i\n",
    "    return inverse"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We define a graph with 5 nodes. The graph is defined by the incidence matrix of size $5\\times 5$ and a coloring with two colors."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph = np.zeros((5, 5), dtype=int)\n",
    "graph[0, 1] = graph[0, 2] = graph[0, 3] = graph[1, 3] = 1\n",
    "graph = np.maximum(graph, graph.T)  # make array symmetric\n",
    "colors = [0, 0, 0, 1, 1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Reduce the graph to normal form using Nauty."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Help on function reduceGraphNauty in module oalib:\n",
      "\n",
      "reduceGraphNauty(G, colors=None, verbose=1)\n",
      "    Return vertex transformation reducing array to normal form\n",
      "    \n",
      "    The reduction is calculated using `Nauty <http://users.cecs.anu.edu.au/~bdm/nauty/>`_\n",
      "    \n",
      "    Args:\n",
      "        G (numpy array or array_link) :   the graph in incidence matrix form\n",
      "        colors (list or None): an optional vertex coloring\n",
      "    Returns:\n",
      "        v: relabelling of the vertices\n",
      "\n"
     ]
    }
   ],
   "source": [
    "help(oapackage.reduceGraphNauty)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input graph: \n",
      "[[0 1 1 1 0]\n",
      " [1 0 0 1 0]\n",
      " [1 0 0 0 0]\n",
      " [1 1 0 0 0]\n",
      " [0 0 0 0 0]]\n",
      "normal form reduction: (1, 2, 0, 4, 3)\n",
      "reduced graph: \n",
      "[[0 0 1 0 1]\n",
      " [0 0 1 0 0]\n",
      " [1 1 0 0 1]\n",
      " [0 0 0 0 0]\n",
      " [1 0 1 0 0]]\n",
      "colors reduced: [0, 0, 0, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "def reduce(graph, colors):\n",
    "    tr = oapackage.reduceGraphNauty(graph, colors=colors, verbose=0)\n",
    "    tri = inverse_permutation(tr)\n",
    "\n",
    "    graph_reduced = oapackage.transformGraphMatrix(graph, tri)\n",
    "    colors_reduced = [colors[idx] for idx in tr]\n",
    "    return graph_reduced, colors_reduced, tr\n",
    "\n",
    "\n",
    "graph_reduced, colors_reduced, tr = reduce(graph, colors)\n",
    "\n",
    "print(\"input graph: \")\n",
    "print(graph)\n",
    "\n",
    "print(f\"normal form reduction: {tr}\")\n",
    "print(\"reduced graph: \")\n",
    "print(graph_reduced)\n",
    "print(f\"colors reduced: {colors_reduced}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apply a random permutation to the graph and reduce the graph again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "random permutation: [3 2 0 4 1]\n"
     ]
    }
   ],
   "source": [
    "perm = np.random.permutation(5)\n",
    "iperm = inverse_permutation(perm)\n",
    "print(f\"random permutation: {perm}\")\n",
    "graph2 = graph[perm, :][:, perm]\n",
    "colors2 = [colors[idx] for idx in perm]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Show the transformed matrix and color vector."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0 0 0 0 0]\n",
      " [0 0 0 1 1]\n",
      " [0 0 0 0 1]\n",
      " [0 1 0 0 1]\n",
      " [0 1 1 1 0]]\n",
      "[1, 1, 0, 0, 0]\n"
     ]
    }
   ],
   "source": [
    "print(graph2)\n",
    "print(colors2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "input graph: \n",
      "[[0 0 1 0 1]\n",
      " [0 0 1 0 0]\n",
      " [1 1 0 0 1]\n",
      " [0 0 0 0 0]\n",
      " [1 0 1 0 0]]\n",
      "tr2: (4, 1, 2, 3, 0)\n",
      "reduced graph: \n",
      "[[0 0 1 0 1]\n",
      " [0 0 1 0 0]\n",
      " [1 1 0 0 1]\n",
      " [0 0 0 0 0]\n",
      " [1 0 1 0 0]]\n",
      "colors2_reduced: [0, 0, 0, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "graph2_reduced, colors2_reduced, tr2 = reduce(graph2, colors2)\n",
    "\n",
    "print(\"input graph: \")\n",
    "print(graph2)\n",
    "\n",
    "print(f\"tr2: {tr2}\")\n",
    "print(\"reduced graph: \")\n",
    "print(graph2_reduced)\n",
    "\n",
    "print(f\"colors2_reduced: {colors2_reduced}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Check that the two reduced graphs are equal."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "reduced arrays are equal!\n",
      "reduced colors are equal!\n"
     ]
    }
   ],
   "source": [
    "if np.all(graph_reduced == graph2_reduced):\n",
    "    print(\"reduced arrays are equal!\")\n",
    "if np.all(colors_reduced == colors2_reduced):\n",
    "    print(\"reduced colors are equal!\")"
   ]
  }
 ],
 "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.8.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}