Example_Identifiability_Experiments_with_Random_Polytope_Generation.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5765b029",
   "metadata": {},
   "outputs": [],
   "source": [
    "import sys\n",
    "from sage.all import *\n",
    "import numpy as np\n",
    "from tqdm import tqdm\n",
    "import pandas as pd\n",
    "from time import time \n",
    "from poly_iden import *"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3dadc2ad",
   "metadata": {},
   "source": [
    "# Experiment with Polytope in 4 Dimensional Space"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "54dab96d",
   "metadata": {},
   "source": [
    "### Generate A Random Polytope As Described in Numerical Experiments Section"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a5e40b21",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of relative Sparsity Constraints: 3\n",
      "Number of Anti-Sparse Constraints: 3\n",
      "Number of Nonnegative Constraints: 1\n",
      "The number of vertices : 11\n",
      "The vertex matrix is given as follows: \n",
      "\n"
     ]
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\begin{bmatrix} \n",
       " 0.000 & -0.500 & 1.000 & 0.500 & 1.000 & 0.500 & 0.000 & -0.500 & 0.000 & -1.000 & -1.000 & \\\\\n",
       " 0.000 & 0.500 & 0.000 & 0.500 & 0.000 & -0.500 & 1.000 & -0.500 & -1.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & -1.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & -1.000 & \\\\\n",
       " 1.000 & 0.500 & 0.000 & 0.500 & 0.000 & 0.500 & 0.000 & 0.500 & 0.000 & 0.000 & 0.000 & \\\\\n",
       "\\end{bmatrix}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dim = 4\n",
    "number_of_relative_sparsity_constraint = np.random.randint(2,dim)\n",
    "number_of_antisparse = np.random.randint(dim)\n",
    "number_of_nonnegative = dim - number_of_antisparse\n",
    "\n",
    "n_max_trial_for_random_poly_gen = 100\n",
    "for i in range(n_max_trial_for_random_poly_gen):\n",
    "    (A,b), V = generate_random_practical_polytope(dim, number_of_antisparse, number_of_nonnegative, number_of_relative_sparsity_constraint)\n",
    "    if V is not None:\n",
    "        break\n",
    "print(\"Number of relative Sparsity Constraints: {}\".format(number_of_relative_sparsity_constraint))\n",
    "print(\"Number of Anti-Sparse Constraints: {}\".format(number_of_antisparse))\n",
    "print(\"Number of Nonnegative Constraints: {}\".format(number_of_nonnegative))\n",
    "\n",
    "print(\"The number of vertices : {}\\nThe vertex matrix is given as follows: \\n\".format(V.shape[1]))\n",
    "display_matrix(V)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b222d2d",
   "metadata": {},
   "source": [
    "### Following Cell Decides the Identifiability of Polytope Using Graph Isomorphism"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c824ddde",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Polytope Identifiability with Graph Isomorphism Algorithm Run Time: 0.4294700622558594\n",
      "\n",
      "Given Polytope is Identifiable\n"
     ]
    }
   ],
   "source": [
    "t0 = time()\n",
    "p = PolytopeIdentifiability(V)\n",
    "n_aut_order, iden = p.check_identifiability(verbose = False, return_generator_order = True)\n",
    "t1 = time()\n",
    "print('The Polytope Identifiability with Graph Isomorphism Algorithm Run Time: {}\\n'.format(t1-t0))\n",
    "\n",
    "if iden:\n",
    "    print('Given Polytope is Identifiable')\n",
    "else:\n",
    "    print('Given Polytope is Not Identifiable')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57b23acb",
   "metadata": {},
   "source": [
    "### Following Cell Decides the Identifiability of Polytope with Brute Force \n",
    "(Runs over all the Possible Permutations)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "d36cfecc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Now, we will see the execution time of brute force algorithm for the same vertex matrix\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "39916800it [12:18, 54051.22it/s]"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Brute Force algorithm run time: 738.584480047226\n",
      "\n",
      "Given Polytope is Identifiable\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "print('Now, we will see the execution time of brute force algorithm for the same vertex matrix')\n",
    "t0 = time()\n",
    "iden2 = CheckPolytopeBruteForce(V)\n",
    "t1 = time()\n",
    "\n",
    "print('Brute Force algorithm run time: {}\\n'.format(t1-t0))\n",
    "\n",
    "if iden2:\n",
    "    print('Given Polytope is Identifiable')\n",
    "else:\n",
    "    print('Given Polytope is Not Identifiable')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2eda49b0",
   "metadata": {},
   "source": [
    "# Experiment with Polytope in 10 Dimensional Space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "eef1af20",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of relative Sparsity Constraints: 3\n",
      "Number of Anti-Sparse Constraints: 8\n",
      "Number of Nonnegative Constraints: 2\n",
      "The number of vertices : 32\n",
      "The vertex matrix is given as follows: \n",
      "\n"
     ]
    },
    {
     "data": {
      "text/latex": [
       "$\\displaystyle \\begin{bmatrix} \n",
       " 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & -1.000 & \\\\\n",
       " 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & -1.000 & -1.000 & -1.000 & -1.000 & -1.000 & -1.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & -1.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & -1.000 & -1.000 & -1.000 & -1.000 & -1.000 & -1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       " 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       " 0.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 1.000 & 0.000 & 0.000 & -1.000 & 0.000 & 0.000 & 0.000 & 0.000 & \\\\\n",
       "\\end{bmatrix}$"
      ],
      "text/plain": [
       "<IPython.core.display.Math object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "dim = 10\n",
    "number_of_relative_sparsity_constraint = np.random.randint(2,dim)\n",
    "number_of_antisparse = np.random.randint(dim)\n",
    "number_of_nonnegative = dim - number_of_antisparse\n",
    "\n",
    "n_max_trial_for_random_poly_gen = 100\n",
    "for i in range(n_max_trial_for_random_poly_gen):\n",
    "    (A,b), V = generate_random_practical_polytope(dim, number_of_antisparse, number_of_nonnegative, number_of_relative_sparsity_constraint)\n",
    "    if V is not None:\n",
    "        break\n",
    "print(\"Number of relative Sparsity Constraints: {}\".format(number_of_relative_sparsity_constraint))\n",
    "print(\"Number of Anti-Sparse Constraints: {}\".format(number_of_antisparse))\n",
    "print(\"Number of Nonnegative Constraints: {}\".format(number_of_nonnegative))\n",
    "\n",
    "print(\"The number of vertices : {}\\nThe vertex matrix is given as follows: \\n\".format(V.shape[1]))\n",
    "display_matrix(V)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4554d997",
   "metadata": {},
   "source": [
    "### Following Cell Decides the Identifiability of Polytope Using Graph Isomorphism"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "6128daf9",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "The Polytope Identifiability with Graph Isomorphism Algorithm Run Time: 0.30795860290527344\n",
      "\n",
      "Given Polytope is Identifiable\n"
     ]
    }
   ],
   "source": [
    "t0 = time()\n",
    "p = PolytopeIdentifiability(V)\n",
    "n_aut_order, iden = p.check_identifiability(verbose = False, return_generator_order = True)\n",
    "t1 = time()\n",
    "print('The Polytope Identifiability with Graph Isomorphism Algorithm Run Time: {}\\n'.format(t1-t0))\n",
    "\n",
    "if iden:\n",
    "    print('Given Polytope is Identifiable')\n",
    "else:\n",
    "    print('Given Polytope is Not Identifiable')"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0b389f3b",
   "metadata": {},
   "source": [
    "### Following Brute Force Identifiability Decision Might Take a Lifetime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "ac0fe0de",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Now, we will see the execution time of brute force algorithm for the same vertex matrix\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "10768740it [05:15, 34116.06it/s]\n"
     ]
    },
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[0;32m<ipython-input-7-1e24f1cb8a22>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m\u001b[0m\n\u001b[1;32m      1\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'Now, we will see the execution time of brute force algorithm for the same vertex matrix'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      2\u001b[0m \u001b[0mt0\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m----> 3\u001b[0;31m \u001b[0miden2\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mCheckPolytopeBruteForce\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mV\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m      4\u001b[0m \u001b[0mt1\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m      5\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32m/scratch/users/bbozkurt15/IdentifiablePolytope/v2.0/poly_iden.py\u001b[0m in \u001b[0;36mCheckPolytopeBruteForce\u001b[0;34m(V)\u001b[0m\n\u001b[1;32m    270\u001b[0m     \u001b[0mVp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlinalg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mpinv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mV\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    271\u001b[0m     \u001b[0;32mfor\u001b[0m \u001b[0mi\u001b[0m\u001b[0;34m,\u001b[0m\u001b[0mindxp\u001b[0m \u001b[0;32min\u001b[0m \u001b[0mtqdm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0menumerate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mmultiset_permutations\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mindxs\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 272\u001b[0;31m         \u001b[0mVindxp\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mV\u001b[0m\u001b[0;34m[\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mindxp\u001b[0m\u001b[0;34m]\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m    273\u001b[0m         \u001b[0mG\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mVindxp\u001b[0m\u001b[0;34m@\u001b[0m\u001b[0mVp\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m    274\u001b[0m         \u001b[0;32mif\u001b[0m \u001b[0;34m(\u001b[0m\u001b[0mnp\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mlinalg\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mnorm\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mG\u001b[0m\u001b[0;34m@\u001b[0m\u001b[0mV\u001b[0m\u001b[0;34m-\u001b[0m\u001b[0mVindxp\u001b[0m\u001b[0;34m)\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m1e-6\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
      "\u001b[0;32msrc/cysignals/signals.pyx\u001b[0m in \u001b[0;36mcysignals.signals.python_check_interrupt\u001b[0;34m()\u001b[0m\n",
      "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "print('Now, we will see the execution time of brute force algorithm for the same vertex matrix')\n",
    "t0 = time()\n",
    "iden2 = CheckPolytopeBruteForce(V)\n",
    "t1 = time()\n",
    "\n",
    "print('Brute Force algorithm run time: {}\\n'.format(t1-t0))\n",
    "\n",
    "if iden2:\n",
    "    print('Given Polytope is Identifiable')\n",
    "else:\n",
    "    print('Given Polytope is Not Identifiable')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "978a6f2f",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "SageMath 9.3",
   "language": "sage",
   "name": "sagemath"
  },
  "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.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}