Tuto-GUDHI-simplex-Trees.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Topological Data Analysis with Python and the Gudhi Library \n",
    "\n",
    "# Introduction to simplex trees "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Authors** : F. Chazal and B. Michel"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "TDA typically aims at extracting topological signatures from a point cloud in $\\mathbb R^d$ or in a general metric space. By studying the topology of the point clouds, we actually mean studying the topology of unions of balls centered at the point cloud (offsets). However, non-discrete sets such as offsets, and also continuous mathematical shapes like curves, surfaces and more generally manifolds, cannot easily be encoded as finite discrete structures. [Simplicial complexes](https://en.wikipedia.org/wiki/Simplicial_complex) are therefore used in computational geometry to approximate such shapes.\n",
    "\n",
    "A simplicial complex is a set of [simplices](https://en.wikipedia.org/wiki/Simplex). It can be seen as a higher dimensional generalization of a graph. It is a mathematical object that is both topological and combinatorial, which makes it particularly useful for TDA. Here is an exemple of simplicial complex:\n",
    "\n",
    "![title](Images/Pers14.PNG)\n",
    " \n",
    "A filtration is a increasing sequence of sub-complexes of a simplicial complex $\\mathcal K$. It can be seen as ordering the simplices included in the complex. Indeed, simpicial complexes often come with a specific order, as for [Vietoris-Rips complexes](https://en.wikipedia.org/wiki/Vietoris%E2%80%93Rips_complex), [Cech complexes](https://en.wikipedia.org/wiki/%C4%8Cech_complex) and [alpha complexes](https://en.wikipedia.org/wiki/Alpha_shape#Alpha_complex). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from IPython.display import Image\n",
    "from os import chdir\n",
    "import numpy as np\n",
    "import gudhi as gd\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In Gudhi, filtered simplicial complexes are encoded through a data structure called simplex tree. \n",
    "![](https://gudhi.inria.fr/python/latest/_images/Simplex_tree_representation.png)\n",
    "\n",
    "This notebook illustrates the use of simplex tree to represent simplicial complexes from data points.\n",
    "\n",
    "See the [Python Gudhi documentation](https://gudhi.inria.fr/python/latest/simplex_tree_ref.html#) for more details on simplex trees."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### My first simplex tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's create our first simplicial complex, represented by a simplex tree :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "st = gd.SimplexTree()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `st` object has class `SimplexTree`. For now, `st` is an empty simplex tree.\n",
    "\n",
    "The `SimplexTree` class has several useful methods for the practice of TDA. For instance, there are methods to define new types of simplicial complexes from existing ones.\n",
    "\n",
    "The `insert()` method can be used to insert simplices in the simplex tree. In the simplex tree:\n",
    "\n",
    "- vertices (0-dimensional simplices) are represented with integers, \n",
    "- edges (1-dimensional simplices) are represented with a length-2 list of integers (corresponding to the two vertices involved in the edge),\n",
    "- triangles (2-dimensional simplices) by three integers are represented with a length-3 list of integers (corresponding to the three vertices involved in the triangle),\n",
    "- etc.\n",
    "\n",
    "For example, the following piece of code inserts three edges into the simplex tree:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.insert([0, 1])\n",
    "st.insert([1, 2])\n",
    "st.insert([3, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When the simplex is successfully inserted into the simplex tree, the `insert()` method outputs `True` as you can see from the execution of the above code. On the contrary, if the simplex is already in the filtration, the `insert()` method outputs `False`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.insert([3, 1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We obtain the list of all the simplices in the simplex tree with the `get_filtration()` method : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "st_gen = st.get_filtration() "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The output `st_gen` is a generator and we thus we can iterate on its elements. Each element in the list is a tuple that contains a simplex and its **filtration value**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([0], 0.0)\n",
      "([1], 0.0)\n",
      "([0, 1], 0.0)\n",
      "([2], 0.0)\n",
      "([1, 2], 0.0)\n",
      "([3], 0.0)\n",
      "([1, 3], 0.0)\n"
     ]
    }
   ],
   "source": [
    "for splx in st_gen :\n",
    "    print(splx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitively, the filtration value of a simplex in a filtered complex acts as a *time stamp* corresponding to \"when\" the simplex appears in the filtration. By default, the `insert()` method assigns a filtration value equal to 0.\n",
    "\n",
    "Notice that inserting an edge automatically inserts its vertices (if they were not already in the complex) in order to satisfy the **inclusion property** of a filtered complex: any simplex with filtration value $t$ must have all its faces in the filtered complex, with filtration values smaller than or equal to $t$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Simplex tree description"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dimension of a simplical complex is the largest dimension of the simplices in it. It can be retrieved by the simplex tree `dimension()` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.dimension()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is possible to compute  the number of vertices in a simplex tree via the `num_vertices()` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.num_vertices()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The number of simplices in the simplex tree is given by"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.num_simplices()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [$d$-skeleton](https://en.wikipedia.org/wiki/N-skeleton) -- which is the union of all simplices of dimensions smaller than or equal to $d$ -- can be also computed with the `get_skeleton()` method. This method takes as argument the dimension of the desired skeleton. To retrieve the topological graph from a simplex tree, we can therefore call:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[([0, 1], 0.0), ([0], 0.0), ([1, 2], 0.0), ([1, 3], 0.0), ([1], 0.0), ([2], 0.0), ([3], 0.0)]\n"
     ]
    }
   ],
   "source": [
    "print(st.get_skeleton(1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One can also check whether a simplex is already in the filtration. This is achieved with the `find()` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.find([2, 4])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Filtration values\n",
    "\n",
    "We can insert simplices at a given filtration value. For example, the following piece of code will insert three triangles in the simplex tree at three different filtration values:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([0], 0.0)\n",
      "([1], 0.0)\n",
      "([0, 1], 0.0)\n",
      "([2], 0.0)\n",
      "([1, 2], 0.0)\n",
      "([3], 0.0)\n",
      "([1, 3], 0.0)\n",
      "([0, 2], 0.1)\n",
      "([0, 1, 2], 0.1)\n",
      "([2, 3], 0.2)\n",
      "([1, 2, 3], 0.2)\n",
      "([0, 3], 0.4)\n",
      "([0, 1, 3], 0.4)\n"
     ]
    }
   ],
   "source": [
    "st.insert([0, 1, 2], filtration = 0.1)\n",
    "st.insert([1, 2, 3], filtration = 0.2)\n",
    "st.insert([0, 1, 3], filtration = 0.4)\n",
    "st_gen = st.get_filtration() \n",
    "\n",
    "for splx in st_gen :\n",
    "    print(splx)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As you can see, when we add a new simplex with a given filtration value, all its faces that were not already in the complex are added with the same filtration value: here the edge `[0, 3]` was not part of the tree before including the triangle `[0, 1, 3]` and is thus inserted with the filtration value of the inserted triangle. On the other hand, the filtration value of the faces of added simplices that were already part of the tree before is left alone. One can modify the filtration value of any simplex included in the tree with the `assign_filtration()` method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([0], 0.0)\n",
      "([1], 0.0)\n",
      "([0, 1], 0.0)\n",
      "([2], 0.0)\n",
      "([1, 2], 0.0)\n",
      "([1, 3], 0.0)\n",
      "([0, 2], 0.1)\n",
      "([0, 1, 2], 0.1)\n",
      "([2, 3], 0.2)\n",
      "([1, 2, 3], 0.2)\n",
      "([0, 3], 0.4)\n",
      "([0, 1, 3], 0.4)\n",
      "([3], 0.8)\n"
     ]
    }
   ],
   "source": [
    "st.assign_filtration([3], filtration = 0.8)\n",
    "st_gen = st.get_filtration()\n",
    "for splx in st_gen:\n",
    "    print(splx)   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Notice that, the vertex `[3]` has been moved to the end of the filtration because it now has the highest filtration value. However, this simplex tree is not a filtered simplicial complex anymore because the filtration value of the vertex `[3]` is higher than the filtration value of the edge `[2 3]`. We can use the `make_filtration_non_decreasing()` method to solve the problem:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "([0], 0.0)\n",
      "([1], 0.0)\n",
      "([0, 1], 0.0)\n",
      "([2], 0.0)\n",
      "([1, 2], 0.0)\n",
      "([0, 2], 0.1)\n",
      "([0, 1, 2], 0.1)\n",
      "([3], 0.8)\n",
      "([0, 3], 0.8)\n",
      "([1, 3], 0.8)\n",
      "([0, 1, 3], 0.8)\n",
      "([2, 3], 0.8)\n",
      "([1, 2, 3], 0.8)\n"
     ]
    }
   ],
   "source": [
    "st.make_filtration_non_decreasing()\n",
    "st_gen = st.get_filtration()\n",
    "for splx in st_gen:\n",
    "    print(splx)  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, it is worth mentioning the `filtration()` method, which returns the filtration value of a given simplex in the filtration :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.8"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "st.filtration([2, 3])"
   ]
  }
 ],
 "metadata": {
  "anaconda-cloud": {},
  "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.0"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}