\def\NomChapitre{Parcours de graphes}
\def\Type{TP}
\LeTitre{\Type}{\NomChapitre}

\shorthandoff{:} 
%%%%%%%%%%%%%%%%%%%%% Styles %%%%%%%%%%%%%%%%%%%%%
\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\tikzstyle{preno}=[semithick] % arêtes non orientées.
\tikzstyle{pre}=[->,>=stealth,semithick] % arêtes orientées.
\tikzstyle{select}=[-,cap=round,style=nearly transparent,line width=6pt] %
\tikzstyle{fl_actif}=[-,cap=round,style=nearly transparent,line width=6pt,color=black!50!red]
\tikzstyle{infini} =[circle,thick,inner sep=0pt,minimum size=6mm,node
distance=20mm,draw=black!50,fill=blue!2, text=red]

\section{Notions élémentaires} 

\begin{exo}
\begin{DeuxCol}{.7}{.2}
{
\begin{enumerate}
\item Donner la liste d'adjacence $L$ correspondant au graphe ci-contre. On
  rappelle que, dans le cas d'un graphe non orienté, s'il y a une arête
  $\{i,j\}$, alors la liste $L[i]$ contient $j$, et la liste $L[j]$ contient $i$.
\item Donner les degrés des sommets $2$ et $5$.
\item Donner un chemin de $3$ à $5$ (il y a
  plusieurs possibilités). 
On précisera sa longueur.
\item Trouver un cycle de longueur $4$ et un cycle de longueur $3$.
\item Déterminer les composantes connexes. 
\end{enumerate}
}
& 
\begin{tikzpicture}[scale=1,baseline=(current bounding box.north)]
  \node[infini]      (0)                            {$0$};
  \node[infini]      (1)        [above right of=0]  {$1$};
  \node[infini]      (3)        [above left of=0]   {$3$};
  \node[infini]      (2)        [above right of=3]  {$2$};
  \node[infini]      (4)        [below of=0]  {$4$};
  \node[infini]      (5)        [below of=4]  {$5$};
  \node[infini]      (6)        [right of=4]  {$6$};
  \node[infini]      (7)        [right of=5]  {$7$};
\draw[preno] (0) to  (1) ;
\draw[preno] (0) to  (3) ;
\draw[preno] (0) to  (4) ;
\draw[preno] (0) to  (2) ;
\draw[preno] (1) to  (2) ;
\draw[preno] (1) to  (3) ;
\draw[preno] (2) to  (3) ;
\draw[preno] (4) to  (5) ;
\draw[preno] (6) to  (7) ;
\end{tikzpicture}
\end{DeuxCol}
\end{exo}


\begin{exo}
\begin{DeuxCol}{.7}{.2}
{
\begin{enumerate}
\item Donner la liste d'adjacence correspondant au graphe ci-contre.
\item Donner les degrés entrants et sortants des sommets $2$ et $3$.
\item Donner un chemin de $0$ à $4$ (il y a
  plusieurs possibilités). 
On précisera sa longueur.
\item Trouver un cycle de longueur $2$ et un cycle de longueur $4$. 
\end{enumerate}
}
& 
\begin{tikzpicture}[>=stealth,scale=1,baseline=(current bounding box.north)]
  \node[infini]      (s)                            {$0$};
  \node[infini]      (t)        [above right of=s]  {$1$};
  \node[infini]      (y)        [below right of=s]  {$2$};
  \node[infini]      (x)        [right of=t]  {$3$};
  \node[infini]      (z)        [right of=y]  {$4$};
\draw[pre] (s) to node[auto] {} (t) ;
\draw[pre] (s) to node[auto,swap] {} (y) ;
\draw[pre] (t) to node[auto] {} (x) ;
\draw[pre] (y) to node[auto,near end] {} (x) ;
%\draw[pre] (y) to node[auto,swap] {} (z) ;
\draw[pre,bend right=20] (y) to node[auto,swap] {} (t) ;
\draw[pre,bend right=20] (t) to node[auto,swap] {} (y) ;
\draw[pre] (x) to node[auto,swap] {} (z) ;
\draw[pre,bend left=80] (z) to node[auto] {} (s) ;
% \draw[pre] (s) to node[auto] {$10$} (t) ;
% \draw[pre] (s) to node[auto,swap] {$5$} (y) ;
% \draw[pre] (t) to node[auto] {$1$} (x) ;
% \draw[pre] (y) to node[auto,near end] {$9$} (x) ;
% \draw[pre] (y) to node[auto,swap] {$2$} (z) ;
% \draw[pre,bend right=20] (y) to node[auto,swap] {$3$} (t) ;
% \draw[pre,bend right=20] (t) to node[auto,swap] {$2$} (y) ;
% \draw[pre,bend right=20] (x) to node[auto,swap] {$4$} (z) ;
% \draw[pre,bend right=20] (z) to node[auto,swap] {$6$} (x) ;
% \draw[pre,bend left=80] (z) to node[auto] {$7$} (s) ;
\end{tikzpicture}
\end{DeuxCol}
\end{exo}



\begin{exo}
On donne la liste d'adjacence suivante :
\begin{center}
\lstinline{L=[[4, 5], [3, 5], [3, 4, 5], [], [0, 1], [0, 1, 2]]}
\end{center}
\begin{enumerate}
\item Le graphe est-il orienté ?
\item Tracer le graphe correspondant.
\item Donner la matrice d'adjacence correspondante.
\end{enumerate}
\end{exo}


\section{Parcours en largeur} 

Vous trouverez ici :
\begin{center}
\url{http://mpechaud.fr/scripts/parcours/index.html}
\end{center}
une très belle animation de plusieurs algorithmes de parcours de graphe.

\begin{exo}\label{plarg}
Pour parcourir en largeur un graphe $G$ à $n$ sommets, 
on utilisera les structures de données suivantes :
\begin{itemize}
\item \lstinline{G} : une liste de liste de longueur $n$, qui contient la
  liste d'adjacence du 
  graphe à parcourir. 
\item \lstinline{c} : une liste de caractères \lstinline{'b'}, \lstinline{'g'} ou
  \lstinline{'n'}, de longueur $n$, où \lstinline{c[i]} contient la couleur --
  blanche, grise ou 
  noire -- du sommet \lstinline{i}.
\item \lstinline{f} : une collection (voir question 1) qui contiendra la liste
  des sommets gris.
\item \lstinline{p} : la liste des pères.
\item \lstinline{d} : la liste des distances.
\end{itemize}
\begin{enumerate}
\item Le module \lstinline{collections} propose une structure de « double
  ended queue » : des listes qui ont deux bouts, \cad{}
\begin{itemize}
\item On peut ajouter et enlever des éléments à droite avec \lstinline{append}
  et \lstinline{pop}, comme pour une liste habituelle.
\item On peut ajouter et enlever des éléments à gauche 
avec \lstinline{appendleft}
  et \lstinline{popleft}, à coût constant ($O(1)$).
\item La commande \lstinline{len} fonctionne comme pour une liste.
\end{itemize}
\medskip
Importer le module  sous le nom \lstinline{co},
  et poser \lstinline{f = co.deque()}. 
Ajouter (à droite), successivement,
  $0$, $3$ et $1$, et donner le contenu de \lstinline{f}. 
Retirer un élément à droite, et donner le contenu de \lstinline{f}. 
Retirer un éléments à gauche, et donner le contenu de \lstinline{f}. 
\item Écrire la liste d'adjacence \lstinline{G} des sommets du graphe orienté
  du cours.
\item Initialiser les variables \lstinline{c}, \lstinline{f}, \lstinline{p},
  \lstinline{d} comme indiqué dans le cours (première vignette).
\item Comment obtient-on la liste des sommets $a$  voisins de $u = 0$ ? 
\Cad{}, tel qu'il y ait un arc $(0,a)$.
\item Écrire les instructions (les plus génériques possibles) pour que les
  différentes variables passent à l'état de la seconde vignette. On affichera
  le contenu des variables à l'aide d'un \lstinline{print}.
\item À l'aide d'une boucle \lstinline{while}, écrire l'algorithme de parcours
  en largeur. On affichera l'état des variables à chaque étape.
\item Écrire une fonction \lstinline{parcours_en_largeur(G, s)} qui effectue
  un parcours en largeur du graphe \lstinline{G} depuis le sommet
  \lstinline{s}. Elle renvoie \lstinline{p} et \lstinline{d}.
\item Donner la complexité de cet algorithme. On note $|S| = n$ le nombre de
  sommets, et $|A|$ le nombre d'arêtes, et on comptera les accès aux données
  dans les listes, en
  notant qu'un sommet ne passe qu'une fois de blanc à gris.
\end{enumerate}
\end{exo}




\section{Parcours en profondeur} 


\begin{exo}
Pour parcourir en profondeur un graphe $G$ à $n$ sommets, 
on utilisera une partie des structures de données 
  de l'exercice \ref{plarg}):
\begin{itemize}
\item \lstinline{G} : une liste de liste de longueur $n$, qui contient la
  liste d'adjacence du graphe à parcourir.
\item \lstinline{c} : une liste de caractères 
  \lstinline{'b'}, 
  \lstinline{'g'} ou
  \lstinline{'n'}, de longueur $n$, où \lstinline{c[i]} contient la couleur --
  blanche, grise ou 
  noire -- du sommet \lstinline{i}.
\item \lstinline{p} : la liste des pères.
\end{itemize}

On utilise à nouveau le graphe orienté \lstinline{G} du cours.
{\em Toute fonction doit être testée ! Une fonction non testée est bugguée.}
\begin{enumerate}
\item Initialiser les variables \lstinline{c} et \lstinline{p} 
comme indiqué dans le cours (première vignette).
\item Écrire une fonction \lstinline{visiter_sommet(u)} qui prend en argument
  un sommet \lstinline{u} blanc et ne retourne rien :
elle modifie les variables \lstinline{c} et \lstinline{p} par effet de bord :
%Cette fonction:
\begin{itemize}
\item Elle colorie en gris le sommet \lstinline{u}, 
\item Elle parcourt les sommets \lstinline{a}, blancs et voisins de \lstinline{u}, 
note que le père de \lstinline{a} est \lstinline{u}, puis appelle
\lstinline{visiter_sommet(a)}.
\item Elle colorie en noir le sommet \lstinline{u}
\end{itemize}
\item Écrire une fonction \lstinline{parcours_en_profondeur(G, s)} qui effectue
  un parcours en profondeur du graphe \lstinline{G} depuis le sommet
  \lstinline{s}. Elle renvoie \lstinline{p}.
\item Donner la complexité de cet algorithme. On note $|S|=n$ le nombre de
  sommets, et $|A|$ le nombre d'arêtes, et on comptera les accès aux données
  dans les listes, en
  notant qu'un sommet ne passe qu'une fois de blanc à gris.
\end{enumerate}
\end{exo}


\begin{exo}
Dans cet exercice, on cherche à reconstituer un chemin depuis le sommet
\lstinline{s} de
départ vers un sommet \lstinline{u} à l'aide de la liste \lstinline{p} des
pères construite par l'algorithme de parcours.

\begin{enumerate}
\item Sur un exemple, reconstituer le chemin de \lstinline{s = 0}  vers
  \lstinline{u = 4} à l'aide de \lstinline{p}. 
\item Écrire une fonction \lstinline{chemin(s, u, p)} qui prend en arguments 
 deux sommets \lstinline{s} et \lstinline{u} du graphe, et
 la liste \lstinline{p} des pères construite par l'algorithme précédent, 
et retourne une liste de sommets représentant le chemin de \lstinline{s} vers
\lstinline{u}.  
\item Tester pour \lstinline$p$ donnée par l'algorithme de parcourt en largeur
  et en profondeur. Quel est le plus court chemin, en terme de nombre d'arêtes
  ?
\end{enumerate}
\end{exo}

\section{Plus court chemin} 

Dans cette partie, on s'intéresse aux graphes pondérés : on cherche un plus
court chemin, \cad{} un chemin de poids minimal, depuis un sommet \lstinline{s}. 

Un graphe pondéré sera codé par une liste d'adjacence \lstinline$G$. 
Désormais, \lstinline$G[i]$ contient une liste de couples \lstinline$(j, p)$,
où l'arête $(i,j)$ est de poids $p$.

Le premier exercice porte sur l'algorithme de {\bfseries Dijkstra}, qui
calcule les plus 
courts chemins depuis un sommet \lstinline{s} vers tous les autres sommets,
dans un graphe pondéré par des poids positifs. \rmqbla{On peut interrompre
  l'algorithme si on cherche le chemin vers un sommet \lstinline{sc} cible
  fixé : lorsque \lstinline{sc} devient {\em noir}, le plus court chemin est
  trouvé.} 


\begin{exo}[Dijkstra]

Pour coder l'algorithme de Dijkstra, on utilisera les structures de données
suivantes :
\begin{itemize}
\item \lstinline{G} : une liste de liste de longueur $n$, qui contient la
  liste d'adjacence du graphe à parcourir. 
\item \lstinline{c} : une liste de caractères \lstinline{'b'}, \lstinline{'g'} ou
  \lstinline{'n'}, de longueur $n$, où \lstinline{c[i]} contient la couleur --
  blanche, grise ou 
  noire -- du sommet \lstinline{i}.
\item \lstinline{d} : la liste des distances.
\item \lstinline{p} : la liste des pères.
\item \lstinline{E} : la liste des sommets gris.
\end{itemize}


\begin{enumerate}
\item Écrire la liste d'adjacence du graphe du premier exemple de la
  présentation de l'algorithme de 
  Dijkstra. On notera les sommets $0$, $1$, etc.

% \begin{center}
% \begin{tikzpicture}[>=stealth,scale=1]
%   \node[infini]      (0)                            {$0$};
%   \node[infini]      (1)        [above right of=0]  {$1$};
%   \node[infini]      (4)        [below right of=0]  {$4$};
%   \node[infini]      (2)        [right of=1]  {$2$};
%   \node[infini]      (3)        [right of=4]  {$3$};
% % flèches 
% \draw[pre] (0) to  (1) ;
% \draw[pre] (0) to  (4) ;
% \draw[pre] (1) to  (2) ;
% \draw[pre] (1) to  (4) ;
% \draw[pre] (2) to  (3) ;
% \draw[pre] (3) to  (2) ;
% \draw[pre] (3) to  (0) ;
% \draw[pre] (4) to  (1) ;
% \draw[pre] (4) to  (2) ;
% \draw[pre] (4) to  (3) ;
% \end{tikzpicture}
% \end{center}

\item Initialisation : 
\begin{itemize}
\item \lstinline$c$ : tous les sommets sont blancs,
\item \lstinline$d$ : tous les sommets sont à l'infini, codé \lstinline$'inf'$, 
\item \lstinline$p$ : tous les pères sont à \lstinline$-1$,
\item \lstinline$E$ : vide
\end{itemize}
Puis mettre à jour $s=0$ : il est gris et à distance
nulle de lui-même.
\item On suppose désormais les listes en cours de remplissage. Le c\oe ur de
  l'algorithme consiste à comparer 
\begin{itemize}
\item la distance entre \lstinline$s$ et 
\lstinline$a$ stockée dans \lstinline$d[a]$, %à
\item la distance entre \lstinline$s$ et 
\lstinline$a$ en passant par le sommet actif \lstinline$u$ : 
 \lstinline$d[u] + poids$, où  \lstinline$poids$ est le poids de l'arête $(u,a)$.
\end{itemize}
Si la seconde distance est strictement meilleure, on met à jour la distance 
 \lstinline$d[a]$ et le père  \lstinline$p[a]$.


Écrire une fonction \lstinline$relacher(u, a, poids, d, p)$ qui relâche
l'arête $(u,a)$. On prendra soin de traiter le cas où  \lstinline$d[a] = 'inf'$.
Cette fonction ne renvoie rien, mais modifie les listes \lstinline$d$ et 
\lstinline$p$, éventuellement.
\item À chaque étape, le sommet actif choisi est celui, gris, de
  valeur de \lstinline$d$ minimale.

Écrire une fonction \lstinline$choix_sommet(d, E)$ qui retourne le sommet
\lstinline$s0$ gris tel que \lstinline$d[s0]$ soit minimale. Elle met aussi à
jour 
\lstinline$E$.

\item Écrire une fonction \lstinline$dijkstra(G, s)$ qui retourne les plus
  courts chemins depuis \lstinline$s$. On peut s'inspirer et adapter la
  fonction écrite pour le parcours en largeur.
\item Modifier votre fonction pour ne plus utiliser la liste \lstinline$c$. La
  liste \lstinline$E$ doit suffire.
\item Donner la complexité de votre algorithme. On admet que l'on peut, avec
  des structures de données bien choisie, avoir une fonction de choix du
  sommet actif en $O(\log |S|)$. Donner la complexité de l'algorithme dans ce
  cas.
\end{enumerate}
\end{exo}

Le second exercice porte sur l'algorithme {\bfseries A$^\star$}, qui calcule le
plus court chemin entre deux sommets \lstinline{s} et \lstinline{sc}, dans un
graphe pondéré muni d'une heuristique. Ici, on suppose que la position des
sommets dans le dessin du graphe est une information pertinente, et
l'heuristique choisie sera la distance euclidienne au sommet cible. C'est une
heuristique plausible si on cherche le plus court chemin sur une carte
routière : la distance « à vol d'oiseau » n'est pas forcément le chemin le
plus rapide, ni même le plus court (montagnes, fleuves), mais elle indique la
direction à tester en priorité.

\begin{exo}
Les sommets du graphe sont désormais des points de $\R^2$, donc codés par des
couples de flottants. 
Au lieu d'une liste, \lstinline$G$ est désormais un
dictionnaire \lstinline${(x, y) : L}$. 
La liste \lstinline$L$ contient des arêtes
partant du sommet \lstinline$(x, y)$, codées sous la
forme \lstinline$(xc, yc)$. Le poids entre \lstinline$(x, y)$ et
\lstinline$(xc, yc)$ est la distance euclidienne entre ces deux sommets.
\begin{enumerate}
\item Donner un exemple de graphe et son dictionnaire associé.
\item Adaptation de l'algorithme de Dijkstra vu à l'exercice précédent.
  \begin{enumerate}
    \item Coder une fonction \lstinline$dist(a, b)$ donnant la distance euclidienne entre deux points
      \lstinline$a$ et \lstinline$b$ de $\R^2$: \lstinline$a$ et
      \lstinline$b$ sont des couples de flottants.
    \item Adapter la fonction \lstinline$dijkstra$ au nouveau type de graphe
      pondéré.
    \item Modifier la fonction \lstinline$dijkstra(G, s)$ en une fonction
        \lstinline$dijkstra_cible(G, s, sc)$ 
  \end{enumerate}
% \item On utilise les structures de données suivantes :
% \begin{itemize}
% \item \lstinline{G} : dictionnaire qui contient le graphe.
% \item \lstinline{d} : le dictionnaire des distances au sommet d'origine.
% \item \lstinline{p} : le dictionnaire des pères.
% \item \lstinline{E} : le dictionnaire des sommets non noirs, codé sous forme de
%   booléens. 
% \item \lstinline$prio$ : le dictionnaire des priorités. \lstinline$prio[s]$
%   est la somme de \lstinline$d[s]$ et de la distance euclidienne entre 
% \lstinline$s$ et le sommet cible \lstinline$sc$.
% \end{itemize}
% Initialiser ces données. Comme pour \lstinline$d$, le dictionnaire \lstinline$prio$ pour un
% sommet non visité est initialisé à \lstinline$"inf"$.
\item Modifier la fonction \lstinline$dijkstra_cible(G, s, sc)$
pour la transformer en \lstinline$Aetoile(G, s, sc)$ : le sommet suivant ne
sera pas simplement celui de plus petit poids, mais celui qui minimise 
  \lstinline$prio$ pour choisir le sommet actif.
\item Donner un exemple de graphe où l'algorithme A$^\star$ est inefficace.
\end{enumerate}
\end{exo}


%%% Local Variables:
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: FeuilleGraphesParcours_2022
%%% End:
