{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Détection de cycle eulérien"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les sommets des graphes sont des entiers indexés à partir de 0 et les relations d'djacence sont représentées par des listes d'adjacence."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithme de Fleury\n",
    "\n",
    "Source : [https://www.irif.fr/~habib/Documents/Eulerien.pdf](https://www.irif.fr/~habib/Documents/Eulerien.pdf)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cycle_eulerien(graphe, depart, debug = False):\n",
    "    \"\"\"\n",
    "    Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n\n",
    "    Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste)\n",
    "    Implémentation de l'algorithme de Fleury\n",
    "    \"\"\"\n",
    "    pile_aretes_vues = []\n",
    "    source = depart\n",
    "    dest = graphe[depart][0]\n",
    "    #depart_cycle : départ du cyle\n",
    "    #depart_cycle_inter : départ d'un cycle intermédaire inséré dans le cycle final qui remiera depart_cycle à depart_cycle\n",
    "    depart_cycle = depart_cycle_inter = depart\n",
    "    pile_aretes_vues.append((None, None))\n",
    "    cycle = []\n",
    "    #tant que la pile est vide\n",
    "    #il reste des sommets sur le chemin à partir desquels on n'a pas terminé l'exploration de cycles intermédiaires\n",
    "    # c'est à dire des sommets qu'on n'a pas encore inséré dans le cycle\n",
    "    while pile_aretes_vues: \n",
    "        #on enlève l'arête (source, dest) du graphe qui relie source à dest\n",
    "        if dest in graphe[source]:\n",
    "            graphe[source].remove(dest)  #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles\n",
    "        if source in graphe[dest]: #cas d'un graphe non orienté\n",
    "            graphe[dest].remove(source)\n",
    "        # s'il reste des aretes non explorées partant du sommet dest\n",
    "        if len(graphe[dest]) > 0:\n",
    "            #on empile l'arête qu'on vient de parcourir\n",
    "            pile_aretes_vues.append((source, dest))      \n",
    "            #on met à jour source, dest avec l'arête libre issue de dest\n",
    "            source, dest = dest, graphe[dest][0]\n",
    "        #sinon il n'y a plus d'arete libre partant de dest\n",
    "        else:\n",
    "            #si on n'est pas revenu au sommet depart_cycle_inter le graphe n'est pas eulérien\n",
    "            if dest != depart_cycle_inter: #pas de cycle eulérien, sommet de degré impair\n",
    "                return (False, dest)\n",
    "            #sinon on a terminé un cycle intermédiaire\n",
    "            else:\n",
    "                #on peut insérer le sommet dest dans le cycle eulérien car plus aucune arete libre n'en part\n",
    "                cycle.append(dest)\n",
    "                #on recherche un cycle après du sommet précédent (source) dans notre exploration \n",
    "                depart_cycle_inter = source\n",
    "                #on dépile l'arete qui nous avait amené en ce sommet source (dest après dépilement)\n",
    "                #en effet la pile permet de mémoriser tous les sommets (extémité d'arete dans la pile)\n",
    "                #qui n'ont pas encore été inséré dans le chemin\n",
    "                source, dest = pile_aretes_vues.pop()\n",
    "    #on referme le cycle avec le sommet de départ\n",
    "    cycle.append(depart_cycle)\n",
    "    return (True, cycle)   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, [0, 3, 2, 1, 0])"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Tests\n",
    "graphe1 = [[1], [2], [3], [0]] #graphe orienté eulérien\n",
    "cycle_eulerien(graphe1, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, [0, 1, 2, 3, 0])"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Tests\n",
    "graphe2 = [[3,1], [0,2], [1,3], [0,2]] #graphe non orienté eulérien\n",
    "cycle_eulerien(graphe2, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, [0, 4, 1, 3, 2, 1, 0])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Tests\n",
    "graphe3 = [[1], [2,4],[3],[1], [0] ] #graphe  orienté eulérien\n",
    "cycle_eulerien(graphe3, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(False, 5)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Tests\n",
    "graphe3 = [[1], [2,4],[3],[1, 5], [0], []] #graphe  orienté non eulérien\n",
    "cycle_eulerien(graphe3, 0, True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(True, [0, 2, 6, 7, 9, 11, 10, 5, 9, 8, 7, 5, 6, 4, 5, 3, 1, 4, 2, 1, 0])"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Tests graphe RT\n",
    "graphe4= [[1,2], [0,2,3,4],[0,1,4,6],[1,5],[1,2,5,6],\n",
    "          [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9],\n",
    "          [5,7,8,11],[5,11],[10,9]\n",
    "         ] #graphe  non orienté  eulérien\n",
    "cycle_eulerien(graphe4, 0, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![cycle eulérien](../euler.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Détection de parcours eulérien"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_sommet_impair(graphe):\n",
    "    \"\"\"Renvoie la liste des sommets de degré impair d'un graphe\n",
    "    représenté sous forme de liste d'adjacence avec les sommets \n",
    "    numérotés à partir de 0\n",
    "    \"\"\"\n",
    "    sommet_impair = []\n",
    "    for sommet in range(len(graphe)):\n",
    "        if len(graphe[sommet]) % 2 == 1:\n",
    "            sommet_impair.append(sommet)\n",
    "    return sommet_impair\n",
    "\n",
    "\n",
    "def chemin_source_destination(graphe, source, destination):\n",
    "    dejavu = [False] * len(graphe)\n",
    "    pile = [source]\n",
    "    chemin = []\n",
    "    while pile[-1] != destination:\n",
    "        sommet = pile.pop()\n",
    "        dejavu[sommet] = True\n",
    "        chemin.append(sommet)\n",
    "        for voisin in graphe[sommet]:\n",
    "            if not dejavu[voisin]:\n",
    "                pile.append(voisin)\n",
    "    chemin.append(destination)\n",
    "    for k in range(len(chemin) - 1):\n",
    "        source = chemin[k]\n",
    "        dest = chemin[k + 1]\n",
    "        if dest in graphe[source]:\n",
    "            graphe[source].remove(dest)  #on pourrait implémenter la liste d'adjacence comme une liste d'ensembles\n",
    "        if source in graphe[dest]: #cas d'un graphe non orienté\n",
    "            graphe[dest].remove(source)\n",
    "    return chemin\n",
    "\n",
    "def parcours_eulerien(graphe, debug = False):\n",
    "    \"\"\"\n",
    "    Paramètre : graphe sous forme de listes d'adjacences (listes de listes), sommets numérotés de 0 à n\n",
    "    Valeur renvoyée : tuple (booleen, cyle eulérien sous forme de liste)\n",
    "    Implémentation de l'algorithme de Fleury\n",
    "    \"\"\"\n",
    "    sommet_impair = liste_sommet_impair(graphe)\n",
    "    if len(sommet_impair) == 0: #tous sommets pairs, cycle eulérien\n",
    "        return cycle_eulerien(graphe, 0, debug)\n",
    "    elif len(sommet_impair) == 2: #2 sommets impairs, parcours eulérien\n",
    "        sommet1, sommet2 = sommet_impair\n",
    "        print(sommet1, sommet2)\n",
    "        chemin_entre_impair = chemin_source_destination(graphe, sommet1, sommet2)\n",
    "        print(chemin_entre_impair)\n",
    "        premier_cycle = []\n",
    "        eulerien = True\n",
    "        if len(graphe[sommet1]) > 0:\n",
    "            (eulerien, premier_cycle) = cycle_eulerien(graphe, sommet1, debug)\n",
    "        second_cycle = []\n",
    "        if eulerien:\n",
    "            if len(graphe[sommet2]) > 0:\n",
    "                (eulerien, second_cycle) = cycle_eulerien(graphe, sommet2, debug)  \n",
    "        if premier_cycle:\n",
    "            premier_cycle = premier_cycle[:-1]\n",
    "        if second_cycle:\n",
    "            second_cycle = second_cycle[1:]\n",
    "        return (eulerien, premier_cycle + chemin_entre_impair  + second_cycle)\n",
    "    else:   #nb de sommets impairs différents de 2 : pas de parcours eulérien\n",
    "        return (False, [])     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3 4\n",
      "[3, 5, 10, 11, 9, 8, 7, 6, 4]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(True, [3, 5, 10, 11, 9, 8, 7, 6, 4, 5, 9, 7, 5, 6, 2, 1, 0, 2, 4])"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Tests graphe RT\n",
    "graphe4= [[1,2], [0,2],[0,1,4,6],[5],[2,5,6],\n",
    "          [3,4,6,7,9,10],[2,4,5,7],[5,6,8,9],[7,9],\n",
    "          [5,7,8,11],[5,11],[10,9]\n",
    "         ] #graphe  non orienté  eulérien\n",
    "parcours_eulerien(graphe4, True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![parcours eulérien](../euler2.png)"
   ]
  }
 ],
 "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.8.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}